ランプセッションで行われたHash Function Collisionセッションの3つのTalkはCRYPTOの歴史に残るんじゃないかな。
ランプセッションは、まだ論文にならないようなオンゴーイングな研究の状況や、他のカンファレンスなどの告知、あるいはエンターテイメント、ツッコミが3～5分で行われる場所なのですが、今回、ハッシュファンクションに関しては特別に15分つづ時間が割り当てられ特別発表みたいな形になっていました。ハッシュの3つ以外は、いつもと同じです。
こちらでは日曜の夜から発表したXiaoyun Wangと、共同研究者のXuejia Lai (IDEAの開発者）は、この論文に関してみんなからコメントを貰ったり、あるいはディスカッションが繰り返されていて、この発表の時点では論文にあったマイナーな違い部分はクリアーになっていていました。
あんまり妄想を書いていても仕方がないですし、それよりも、おなかがすいてきたので朝ごはんにいってきます。ちなみに昨日のランプセッションで、ハッシュの話以外ではマイクロソフトのDavid JaoのAlmost-Ramanujan graphs and random reducibilty of DLOG amang isogenous elliptic curvesが個人的には興味を引きました。
結果的には任意のビット列に適切なビット列を加えることで自由にMD5を設定できるのでしょう。そうでなければ今回の'発見'の意味はない。適切なビット列は結構長いかもしれないし、check sum 自体と同じ長さかもしれない。用途&検証方法次第ですが、あまり重要じゃないと思います。
で、どう使われてしまうかというと、どうでも良い部分にごみを付ければよいのです。
tar みたいなものでまとめてあるだけなら、本体の他にゴミファイルをつけてその部分で調整するのです。
gzip で圧縮するなら、XLEN bytes of "extra field" の中で調整するのです。適切な圧縮結果になる余分なファイルをつけてもいいのですが、それだと作業が大変そうです。
もちろん木馬本体に変なメッセージをつけてその部分で表現してもいいし、方法は山ほどあります。
NSA のダウンロードファイルがどんな形式なのか知らないのですが、'将来の拡張のため'と称して勝手なコンテンツをつけることができるformat は多いです。check sum のほかに長さも見ていると偽装は難しくなるので、メールの電子署名でメールのメッセージを偽造/偽装するのは大変でしょう。SPRM みたいなもんなら偽装を防ぐのは無理でしょう。
さっき、その会場から戻ってきました (スコア:5, 参考になる)
ランプセッションで行われたHash Function Collisionセッションの3つのTalkはCRYPTOの歴史に残るんじゃないかな。 ランプセッションは、まだ論文にならないようなオンゴーイングな研究の状況や、他のカンファレンスなどの告知、あるいはエンターテイメント、ツッコミが3～5分で行われる場所なのですが、今回、ハッシュファンクションに関しては特別に15分つづ時間が割り当てられ特別発表みたいな形になっていました。ハッシュの3つ以外は、いつもと同じです。
こちらでは日曜の夜から発表したXiaoyun Wangと、共同研究者のXuejia Lai (IDEAの開発者）は、この論文に関してみんなからコメントを貰ったり、あるいはディスカッションが繰り返されていて、この発表の時点では論文にあったマイナーな違い部分はクリアーになっていていました。
まず露払いのEli BihamがSHA-0に関して、Antoine Jouxがさらに計算してコリジョンを実際にみつけた、と発表。
さてXiaoyun Wangの登場。年齢は40歳を越えたぐらいに見える女性で、まったくの無名。論文にXuejia Laiが名前を連ねていなかったら誰も信じなかったかも。発表の終わってからの拍手がすごかったです。拍手が鳴り止まない。スタンディングしている人もちらほら。彼女が終わったあとに、Laiが補足で論文の間違い部分についての説明をしたけど、所でどこがでシュナイヤーがなんか突っ込みを入れていたんでしょうか？
今回が初めて来てから１０年、一回さぼって９回目のCRYPTOなんだけど、本番の発表でもこれだけ拍手が鳴り止まなかったのを見たのは僕は初めて。衝撃度でも何年か前に同じくランプセッションで発表されたShamirのSkipJackの解読法の講演よりも完全に上。 いやー、いい所に立ち会えたなぁ、という感じです。
たぶん既にこの3人同士が次のステップを議論しているだろうから、 SHA-1に関してのコリジョンを見つけるのは時間の問題だと思います。
１１：１０になって、やっと１０：１６分に予定していたEli Bihamの Ipossible fault analysis of RC4が始まりました。 でも眠たいのでもう寝ます。それではまた 。
パスワードなんか既に忘れている
すずきひろのぶ
Re:さっき、その会場から戻ってきました (スコア:5, 興味深い)
MD5に関してはゴミをつければいいということを投稿されていた方がいましたが、その通りです。つけくわえれば実行ファイルのデータ領域に参照しないデータを余計につけても、感の鋭い人以外はわからないでしょう、ということを付け加えるぐらいでしょうか。
メーカーの研究者の所には次から次へと会社から「ハッシュのことはどうだったんだ！」という問い合わせが殺到しているそうです。ちょっと誤解している人もいるので、はっきりさせておきましょう。
現在暗号システムに使われて主流となっているSHA-1はまだ安全です。
しばらくするとSHA-1のコリジョンは発見されるかも知れませんが、現実的に悪意を持って操作させれるほど簡単にSHA-1に関しては操作できません。まだまだ先の話です。またeJapanのために策定されたガイドラインCRYPTORECでは、既にSHA-1の寿命は折込でいてSHA-256にスライドできるようになっているので、これから先にSHA-1が寿命が尽きたとしても大丈夫なロードマップは仕様上きちんとできているはずです。あまり驚かないように。
ただしMD5はもうダメです。その点はあきらめてください。
今回このハッシュコリジョンを話したXiaoyun Wangを次の12月5日から韓国の済州島で行われるAsiaCryptoにはInvited Talkとして呼ぼう、ここで全容を詳細に語ってもらおう、という流れになっているというのが、今から6時間ほど前の状況です。
このハッシュコリジョンの研究成果がなんでIACRのeprint、そしてランプセッションに来たかという背景を色々な人から聴くと、非常に興味深いものがあります。それは、まるでNHKのプロジェクトX風のストーリーのようでもあります。それで...
この辺から、「風の～なかの～す～ばる～」のBGMがかかりつつ、なぜビザが必要なアメリカへすぐに出発することできたのか、最後の拍手の鳴り止まない感動のフィナーレまで、色々な謎と物語が展開しつつ話は続くわけですが、それはまたどこかで。
夜中の１時４５分。もう寝ます。
すずきひろのぶ
Re:さっき、その会場から戻ってきました (スコア:0)
Re:さっき、その会場から戻ってきました (スコア:3, 興味深い)
朝一番のセッションでEli BihamとAntoine Jouxが各々本来の発表するのですが、既に昨夜話しているので、何をやるのか別の意味で楽しみです。
さて安全性に関してですが、MD5に関してはかなり厳しいです。たとえばNSAあたりがダウンロード配布ファイルの中身に彼らが作ったトロイの木馬を潜ませるなんてことが可能になります。普通、ダウンロードにSSLなんか使わないのでMAN-IN-THE-MIDDLE攻撃です。ですから配布オリジナルを改ざんすることなく、狙った相手がダウンロードするときにすりかえればって感じです。
これを2、3週間程度でこなすためには計算量的には、そこそこのシステムが必要です。しかしながら最近はむかしと違って億単位のスーパーコンピュータじゃなくても可能で、ざっくりコストパフォーマンスを勘案するとOpteron 2xxシリーズ 2wayサーバを100台ぐらい用意するといけそうな気がします。総額5000万円ぐらい。ディスカウントしてもらって4000万円ぐらいかなぁ。
あんまり妄想を書いていても仕方がないですし、それよりも、おなかがすいてきたので朝ごはんにいってきます。ちなみに昨日のランプセッションで、ハッシュの話以外ではマイクロソフトのDavid JaoのAlmost-Ramanujan graphs and random reducibilty of DLOG amang isogenous elliptic curvesが個人的には興味を引きました。
あ、もうこんな時間だ
すずきひろのぶ
Re:さっき、その会場から戻ってきました (スコア:1)
> 彼らが作ったトロイの木馬を潜ませるなんてことが可能になります。
> 普通、ダウンロードにSSLなんか使わないのでMAN-IN-THE-MIDDLE攻撃です。
> ですから配布オリジナルを改ざんすることなく、
> 狙った相手がダウンロードするときにすりかえればって感じです。
それ以前の問題として、
検証に使うMD5サムが公開されている場合でも非SSLで公開されていたりして、
せいぜいダウンロード時の破損チェックくらいにしか使えてなかった
という現状もあったり(; ;)
そこまでストイックに配布物のセキュリティを管理している例は
数少ないような気もするんですが、
素朴な疑問として、実際にそういう事例があったとして、
それがMD5サムのみに頼ってるという事はあるもんなのでしょうか？
バックドアに関しては、NSAを出すまでもなく
クローズドソースなOSメーカーにしてみれば
それ以上の仕掛も容易いように思いますし。
もちろんMD5のクラック事態は由々しき問題だと思いますが、
セキュリティ上の大穴がもっと別な所に散在しているように感じられるのですが？
uxi
Re:さっき、その会場から戻ってきました (スコア:0)
そんなことまでは無理なのでは?
本物の MD5 に一致するような、偽のデータを作ることができるとしても、それがトロイ
Re:さっき、その会場から戻ってきました (スコア:1)
踏み台を設置する事はできるような気がします。
source code 中の条件式(+-=!<>)を違う条件式に変更できれば、
文字列の長さを check するコードを改竄できる可能性があります。
そしてバッファオーバーフローを容易に発生させる事が可能になれば
その後、トロイの木馬を仕込む事も可能でしょう。
Re:さっき、その会場から戻ってきました (スコア:0)
一文字変えると、ほかのところもたくさん変更しないと同じ MD5値にはできないのでは？
Re:さっき、その会場から戻ってきました (スコア:1)
/*
* buffer overflow check!!
*/
if( length > BUFSIZE ){
...
}
こんな風に。
/*
* auffer overflow check!!
*/
if( length >=BUFSIZE ){
...
}
Re:さっき、その会場から戻ってきました (スコア:1)
で、どう使われてしまうかというと、どうでも良い部分にごみを付ければよいのです。
tar みたいなものでまとめてあるだけなら、本体の他にゴミファイルをつけてその部分で調整するのです。
gzip で圧縮するなら、XLEN bytes of "extra field" の中で調整するのです。適切な圧縮結果になる余分なファイルをつけてもいいのですが、それだと作業が大変そうです。
もちろん木馬本体に変なメッセージをつけてその部分で表現してもいいし、方法は山ほどあります。
NSA のダウンロードファイルがどんな形式なのか知らないのですが、'将来の拡張のため'と称して勝手なコンテンツをつけることができるformat は多いです。check sum のほかに長さも見ていると偽装は難しくなるので、メールの電子署名でメールのメッセージを偽造/偽装するのは大変でしょう。SPRM みたいなもんなら偽装を防ぐのは無理でしょう。
Re:さっき、その会場から戻ってきました (スコア:0)
特定のファイルと同じ MD5 値になるデータを探すのは、弱-衝突耐性の方なのでは？