人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

255byte以内のURLに対してMD5でハッシュを得たときに、それがコリジョンを起こす場合はありますでしょうか。

255byte程度の短い文字列に対してであればコリジョンが発生しないと聞いたのですが根拠となる情報があれば教えてください。

●質問者: ひげぽん
●カテゴリ:コンピュータ
✍キーワード:md5 URL コリジョン ハッシュ 文字列
○ 状態 :終了
└ 回答数 : 4/4件

▽最新の回答へ

1 ● xatm092dora
●20ポイント

http://www.hatena.ne.jp/

はてな

URLはダミーです。

MD5のハッシュは16進の32桁の数と見なせるので16^32個の組み合わせしかありません。

一方文字列は、アルファベットと記号合わせて0x20-0x80あたりまでとしても最低90進くらいあることになります。これが256桁あるのですから、

90^256>16^32

より、鳩の巣原理からコリジョンの可能性はあると言えます。

ただ、URLの規格を満たす範囲で、となるとちょっと分かりません。

◎質問者からの返答

ありがとうございます。


2 ● hiratch
●20ポイント

http://eprint.iacr.org/2004/199.pdf

まず、鳩の巣箱の原理からコリジョンの無いハッシュアルゴリズムは存在しません。コリジョンを見つけるのが難しいアルゴリズムがあるだけです。

現在、上記URLのアルゴリズムが有名なようですが、これは二つの1024bitsのメッセージの組に対してコリジョンを見つけるようです。

これは256bytesになりますので、この論文が話の元のような気がします。

しかしながら、これは256bytes未満のデータに対して効率的なアルゴリズムが無いことを保証するものではないので、MD5は使わないほうが良いでしょう。

また、SHA-1についてもいつ破られるかわからない状態だそうです。

理想的には、ハッシュアルゴリズムを後から変更できるようにしておくのが良いでしょう。

ところで、URLに対してハッシュ値を求める目的はなんでしょう。改変を防ぎたいだけなら、素のURLを送るだけで十分な気がしますが。

◎質問者からの返答

ありがとうございます。

PDF見てみましたがさっぱり分かりませんでした。

ですがやはり保証はないのですね。

用途ですが、存在有無チェックのためにPermalinkをDBに保持しているのですが、これが膨大な件数になってきたので、ハッシュで保持したいなぁという感じです。


3 ● 成瀬
●100ポイント

http://www.srs.ne.jp/~north/text/misc/e40.html

TextPage/Misc/Tower of Hanoi

まず、MD5にしろSHA1にしろ、コリジョンの可能性は0ではありません。

コリジョンの無いハッシュ関数があったとしたら・・・それはハノイの塔アーカイバですよ。

http://en.wikipedia.org/wiki/MD5

MD5 - Wikipedia, the free encyclopedia

255byte以下なら?も嘘です。

そのような偏りがあったとしたら、入力と出力が独立で無いことを意味し、

‘よい’ハッシュ関数と呼ぶことはできません。

また、MD5のソースを読んでも長さが関係ないことは直感的にわかるかと。

大雑把に言えば、128bitで割った余りを求めているようなものなので。

http://www.google.com/search?hl=ja&lr=&q=site:www.radium...

Google

ハッシュ関数についてはRadium Software Developmentさんで連載されていたので、

そちらも参考になさるとよろしいかと。

完全ハッシュ関数なんかは使われる機会もあるのではないでしょうか。

Hashing(1-5)

http://www.radiumsoftware.com/0406.html#040630

http://www.radiumsoftware.com/0407.html


さて、URLの空間が、計算しやすくするために0xFF^256として、2048bitですか、

これをMD5なら128bit、SHA1なら160bitに‘圧縮’するわけですが、

よくできたハッシュ関数ならば入力の空間の大きさは関係ありません。

たとえ与える平文空間がハッシュ関数の平文空間に対してに偏りがあったとしても、

出力である暗号文空間では均等に分布するはずですから。


結局のところ、用いているハッシュ関数がよくできている、という仮定をおく限り、

その衝突可能性は与えられた入力の数のみに依存します。

http://www.ysearchblog.com/archives/000172.html

Yahoo! Search blog: Our Blog is Growing Up ? And So Has Our Index

Yahooが前にインデックス数が192億とか発表していましたので、1兆(=40bit)としましょう。


先述のRadium Software DevelopmentさんでBob Jenkins 氏の言葉が引用されていましたが、曰く、

「2^n 個のキーに関して,衝突の可能性を 1/(2^m) 程度に抑えたいならば,

2(n+m) ビットのハッシュ値を用いる必要があります。」

だそうです。

#このへんの詳細は「バースデイパラドックス」とかで。


つまり、80bitのハッシュ関数を用いれば衝突確率は1/2になります。

MD5ですと128bitですから、1/(2^88)程度ということになりますね。

2^88個のパラレルワールドのうち、たった一つのみで衝突が起きる、と。


この世界で衝突が起きると思いますか?

http://en.wikipedia.org/wiki/CRC32

Cyclic redundancy check - Wikipedia, the free encyclopedia

これでも衝突が怖いのでしたら、ハッシュ関数のグレードを落として他の方法と併用した方がいいでしょう。

CRC32やchecksumのような速いがおよそハッシュ関数とは呼べないものを使った上で、B-Treeとか。

これならば衝突可能性はゼロになりますからね。

◎質問者からの返答

ありがとうございます。

根拠となるデータソースや数字を混ぜての回答がとても参考になりました。


4 ● hiratch
●10ポイント

http://www.postgresql.jp/document/pg721doc/reference/sql-createi...

RDBMSを使うのなら、インデックスを使うのが良いでしょう。将来の拡張に対してもインターフェイスが煩雑にならずに済むでしょうし。

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ