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

URLはダミーです。

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

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

90^256>16^32

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

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

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

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

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

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

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

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

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

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

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

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に‘圧縮’するわけですが、

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

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

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

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

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

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個のパラレルワールドのうち、たった一つのみで衝突が起きる、と。

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

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

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

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

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