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


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

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2006/02/03 17:42:42
  • 終了:--

回答(4件)

id:xatm092dora No.1

xatm092dora回答回数1ベストアンサー獲得回数02006/02/03 18:53:18

ポイント20pt

URLはダミーです。

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

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

90^256>16^32

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

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

id:higepon

ありがとうございます。

2006/02/03 18:54:01
id:hiratch No.2

hiratch回答回数4ベストアンサー獲得回数02006/02/03 20:17:38

ポイント20pt

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

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

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

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

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

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

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

id:higepon

ありがとうございます。

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

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

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

2006/02/03 21:41:23
id:nurse No.3

成瀬回答回数13ベストアンサー獲得回数22006/02/04 04:11:39

ポイント100pt

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

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

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

MD5 - Wikipedia, the free encyclopedia

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

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

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

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

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

ハッシュ関数については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とか。

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

id:higepon

ありがとうございます。

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

2006/02/05 18:32:27
id:hiratch No.4

hiratch回答回数4ベストアンサー獲得回数02006/02/04 09:21:55

ポイント10pt

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

コメントはまだありません

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません