2004年08月25日

MD5コリジョンの意味(1)

こちらに書いたヤツの続報が来てましたが、やっぱり危険な問題のようです。

詳しくは

が良くまとまってますが、個人的によく使っているMD5についての事なので、無い頭なりにどういう事なのか考えてみました。

なお、私自身よくわかって無いので下記を鵜呑みにすると痛い目に遭う確率大です(笑)

まず、今回の発見の何がすごいのかというと、あるファイルと同じMD5ハッシュ値を持つファイルが簡単に作れちゃったと言うことのようです。
(ソースファイルがある状態でそれと同じMD5値を持つファイルが出来ちゃったということですな)

このため、今回の発見の内容ではソースがない状態(つまりハッシュしか知らない)ようなケースではあんまり役に立たないんじゃないかと思います。
(総当たり計算(brute-force)での回数は減らせられるかもしれませんが)

なので、MD5hashの状態でファイルに書かれているパスワードが流出してもそれから平文パスワードや同一ハッシュになるコリジョンが見つけ出されるような事はまだ無いんじゃ無いかと思います。

※ここら辺は↓が参考になるかと

  • ハッシュ値のコリジョンには弱衝突と強衝突という概念がありまして。
    ハッシュ関数を f()として元の文章をAとします。
    Aのハッシュ値は f(A)= X とします。
    このときに、f(B) = X となるようなBを発見するのが難しい性質がある事を
    弱衝突耐性がある と言います。
    「既にある何かにぶつける事が難しい」事ですね。

    一方で強衝突耐性とは
    f(C)=f(D) となる、任意のC,Dのペアを見つける事が難しい性質がある事です。これは
    「ぶつかってしまう2つの物を発見することが難しい」事になります。

    今回は、強衝突に対する脆弱性発見のお話ですね。

で、実際同一ハッシュを持つファイルが作れるといってもそれもあんまり自由度が無いような気がするんですが・・・

発表[PDF]で例としてあげられているものをバイナリ値として起こしたファイルが

にありますが、同じMD5ハッシュ値となる二つのファイルの差異は
d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c
2f ca b5 07 12 46 7e ab 40 04 58 3e b8 fb 7f 89
55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 f1 41 5a
08 51 25 e8 f7 cd c9 9f d9 1d bd 72 80 37 3c 5b
d8 82 3e 31 56 34 8f 5b ae 6d ac d4 36 c9 19 c6
dd 53 e2 34 87 da 03 fd 02 39 63 06 d2 48 cd a0
e9 9f 33 42 0f 57 7e e8 ce 54 b6 70 80 28 0d 1e
c6 98 21 bc b6 a8 83 93 96 f9 65 ab 6f f7 2a 70
赤字の部分だけ。
2進数に置き換えた場合ならのべ6bitだけとなります。
(必ず6bitになるのか判りませんが)
それに見る限り、前半512bitと後半512bitでは同一の変更が必要な感じです。

で、このような規則性に沿った変更でしか求められないコリジョンで騒がれているような有害な捏造ファイルを作り出すのは相当大変だと思うんですが、私の認識って全然間違ってるんでしょうかね?

詳しい方からのツッコミお待ちしてます(笑)

ちなみに、署名(ファイルの正当性の保証)としての有効性という話なら端から存在してないと思っているので個人的には全然問題にしていません。

そもそもハッキングなどで掲載されているMD5ハッシュ自体が書き換えられる心配がある以上、ファイルの破損検査程度にしか使えないという認識でしたし。

ファイルの正当性の保証は本来、MD5程度のハッシュ関数になんぞ頼らず公開鍵暗号などを使ってちゃんとやるべきものだったので、今回の騒ぎでその動きが加速するのはむしろ良い傾向なんじゃないんでしょうか?

こっちへ続く

Posted by Takuchan at 2004年08月25日 00:27 | トラックバック(0)