[PHP-users 28626] Re: MD5の仕組みについて

[canada-php@kaede.to]

金田です。

SATOH Fumiyasuさんの<871wxh7z4v.wl%fumiya ＠ samba.gr.jp>から
> > 確立的にはユニークであるという前提で普通は問題ないです。
> 個人的には、競合する可能性があるのにそれを放置するのは、
> 問題 (バグ)だと思う。

一般的に、可能性が充分低ければバグとはしません。MD5
が完全なメッセージダイジェストを吐くという前提であれ
ば、無視して良い可能性だと思います。RFC 1321によれば、

> the difficulty of coming up with any message 
> having a given message digest is on the order of 
> 2^128 operations.

だそうですので、

2 ^ 128 ≒ 3.4 * 10 ^ 38 (10進数39桁の数)

これは地球上の全人類の体に含まれる分子の総数に近く、
1秒間に100億回計算するとして、偶然コリジョンするまで
に100億年の100億倍くらい掛かる計算になると思います。

この程度の小さい可能性を考慮するなら、CPUの演算エラー
を考慮して全ての演算に検算を導入しないとバグ、という
ことになってしまいます(検算も間違える可能性も考えな
いといけません)。

似たような例で、RSA暗号の鍵に使う巨大な素数の生成に
は素数判定のアルゴリズムが使われますが、これには判定
失敗の可能性があったりします。しかし可能性が極端に低
いため、失敗する可能性は「ない」ものとしてそのまま使
われています。

> echo md5('メールアドレス'+'何か');

このような手法は、ハッシュが漏洩した場合の危険性の方
がずっと高いです。'何か'を変えない限りずっと同じ文字
列がキーとなりますので。

また'何か'が充分に長くない場合、ハッシュから'何か'を
推測される危険性があります。

意図的なコリジョンについては、

http://slashdot.jp/security/04/08/18/0257220.shtml

のようなニュースがありましたが、これは同じハッシュを
吐く文書の対を生成できた、というもので、(元文書の分
からない)任意のハッシュと同じハッシュを吐く方法が見
つかった訳ではないようです(コメントが詳しいです)。

> バグだと思うんだけどなぁ。マニュアルなどに重複する可能性が
> 記載されているなら、仕様 (制限事項) かな。

重複する可能性については記載がないようです。
-- 
かなだまさかつ
http://kaede.to/~canada/doc/