パスワードを忘れた? アカウント作成
8755 story

SHA-0、MD5、 MD4にコリジョン発見、reduced SHA-1も 72

ストーリー by Oliver
電子署名のピンチ 部門より

電子署名などにつかわれる主要なハッシュ関数のコリジョン発見がカルフォルニアで開催中のCRYPTO 2004カンファレンスで次々と発表されている。
まずは80 ラウンドの完全版SHA-0のコリジョンをフランスの暗号学者Antoine Jouxが発見した。brute-forceの2^80に比べ、アタックの複雑性は約2^51で、256ノードのItanium2マシンで約8万CPU hours (約2週間?)必要だったという。次に中国の研究チームがMD5とMD4での複数のコリジョン発見[PDF]を報告した。驚くことに、コリジョン発見に要する時間はMD5でわずか数分で、MD4にいたっては手で計算する事が可能なぐらい簡単だという。また、MD5と共にもっとも使われているハッシュ関数であるSHA-1に関しても攻撃が発表され、36ラウンドの縮小版SHA-1のコリジョンがデモンストレーションされ、54ラウンドあたりまでは現時点でも現実的な攻撃が可能なことが示唆された。普段つかわれる80ラウンドの完全版SHA-1がすぐ脅かされる、ということではないが、他のハッシュ関数もラウンド数を減らした版の数年後には完全版への攻撃がみつかっている。

ほんの数分前に発表のウェブキャストが終ったばかりで、実際のアプリケーションへの影響はこれから専門家によるさらなる検証で明らかになっていくだろうが、これらのハッシュ関数の価値が激減したことは確実と見てよさそうだ。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by Anonymous Coward on 2004年08月18日 15時13分 (#607130)
    まだランプセッションは続いていますが、もう眠たいので10時になって部屋に帰って来て、新聞サイトやついでにslashdot.jpをみたら、 びっくり。早いね。

    ランプセッションで行われた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が補足で論文の間違い部分についての説明をしたけど、所でどこがでシュナイヤーがなんか突っ込みを入れていたんでしょうか?

    今回が初めて来てから10年、一回さぼって9回目のCRYPTOなんだけど、本番の発表でもこれだけ拍手が鳴り止まなかったのを見たのは僕は初めて。衝撃度でも何年か前に同じくランプセッションで発表されたShamirのSkipJackの解読法の講演よりも完全に上。 いやー、いい所に立ち会えたなぁ、という感じです。

    たぶん既にこの3人同士が次のステップを議論しているだろうから、 SHA-1に関してのコリジョンを見つけるのは時間の問題だと思います。

    11:10になって、やっと10:16分に予定していたEli Bihamの Ipossible fault analysis of RC4が始まりました。 でも眠たいのでもう寝ます。それではまた 。

    パスワードなんか既に忘れている
    すずきひろのぶ

    • by Anonymous Coward on 2004年08月19日 17時46分 (#607581)
      CRYPTO2004恒例ビーチバーベキューで飲み食いした後に、日本人若手研究者グループが提供してくれたワインを飲んだので、かなりよっぱらっています。すいません。

      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風のストーリーのようでもあります。それで...

      彼女が研究を始めてから15年ほど経っていた。既にこの内容は中国国内では発表済みだが世界には知られていない。スイスから上海に戻ったIDEA設計者のXuejia Laiが中国国内でしか知られていない、この研究を知った。Laiは思った。「これは偉業だ。世界は、このことを一刻も早く知るべきだ」。急遽英文の論文にしたてあげ、投稿。しかし論文としては質が低いので落選。それでハッシュのコリジョンを示すという内容でePrintにサブミット。つたない英語。big endianとlittle endianを間違えて論文に載せるという初歩的なミス。しかし、たとえ方法論が無視されていても、ハッシュがコリジョンを見つけたという事実は無視できない。

      この辺から、「風の~なかの~す~ばる~」のBGMがかかりつつ、なぜビザが必要なアメリカへすぐに出発することできたのか、最後の拍手の鳴り止まない感動のフィナーレまで、色々な謎と物語が展開しつつ話は続くわけですが、それはまたどこかで。

      夜中の1時45分。もう寝ます。
      すずきひろのぶ

      親コメント
    • by Anonymous Coward on 2004年08月19日 0時25分 (#607333)
      おはようございます。朝メールを一通り返事して、slashdot.jpをみてみたらスコア5でした。ありがとうございます。

      朝一番のセッションで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が個人的には興味を引きました。

      あ、もうこんな時間だ
      すずきひろのぶ

      親コメント
      • > たとえばNSAあたりがダウンロード配布ファイルの中身に
        > 彼らが作ったトロイの木馬を潜ませるなんてことが可能になります。
        > 普通、ダウンロードにSSLなんか使わないのでMAN-IN-THE-MIDDLE攻撃です。
        > ですから配布オリジナルを改ざんすることなく、
        > 狙った相手がダウンロードするときにすりかえればって感じです。

        それ以前の問題として、
        検証に使うMD5サムが公開されている場合でも非SSLで公開されていたりして、
        せいぜいダウンロード時の破損チェックくらいにしか使えてなかった
        という現状もあったり(; ;)

        そこまでストイックに配布物のセキュリティを管理している例は
        数少ないような気もするんですが、
        素朴な疑問として、実際にそういう事例があったとして、
        それがMD5サムのみに頼ってるという事はあるもんなのでしょうか?

        バックドアに関しては、NSAを出すまでもなく
        クローズドソースなOSメーカーにしてみれば
        それ以上の仕掛も容易いように思いますし。

        もちろんMD5のクラック事態は由々しき問題だと思いますが、
        セキュリティ上の大穴がもっと別な所に散在しているように感じられるのですが?
        --
        uxi
        親コメント
  • by Anonymous Coward on 2004年08月18日 13時14分 (#607058)
    論文を読む限りでは、コリジョンを発生させるための計算式があって、
    この計算式を満たすメッセージMの発見が数秒から数分で行われた、と読める。
    任意のメッセージに対するコリジョン発生式というわけではないのかしら?

    まあ、それはそれで重要な報告ではあるんだけど。
    • by Anonymous Coward on 2004年08月18日 14時03分 (#607096)
      # 親コメントの方は分かってそうですがフォロー

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

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

      今回は、強衝突に対する脆弱性発見のお話ですね。
      親コメント
      • 親コメントの投稿者です。丁寧にまとめたくださりありがとうございます。(_ _)
        # 出先なのでAC

        >今回は、強衝突に対する脆弱性発見のお話ですね。
        この報告が限られたC,Dの組み合わせなのか、(少なくとも片方は)任意のC,Dなのか、
        そこがインパクトの分かれ
      • 素人の者ですが、言葉の感覚からすると、

        強と弱というのは、耐性が強なのか弱なのかですよね。
        だから、「強衝突耐性に対する脆弱性」ならわかるのですが、
        「強衝突」と略してしまうと強弱が逆になってしまうような。
        • すみません、抜け落ちていますが「強衝突耐性に対する脆弱性」が正しいです。
          強衝突-耐性 ではなくて 強-衝突耐性 です。
    • by aurora (5149) on 2004年08月19日 0時17分 (#607323) 日記
      1024ビットのメッセージについて,
        MD5(M, N) = MD5(M', N')
        M: 前半512ビット,N: 後半512ビット
        M', N' はそれぞれ決まった位置の3ビットだけを変更したもの
      となるような M と複数の N の組み合わせを見つけることができる.

      ということなので,任意のメッセージではないと思います.p690(Regatta) [ibm.com]を使ってM を 1時間,N は 15秒から 5分で発見したみたいですね.
      親コメント
    • んー
      コリジョン発生数が多いのが問題?

      コリジョン数が多ければ任意文章+パディングで
      ハッシュ同値になるようパディングをつめるとき、
      そのパディングを探し出すのが早くなってしまう。

      --
      いなんず[いつでも前向きでイタい]
      親コメント
      • でも、逆に言えば、そのようなパティングを避けることができるともいえる...
        • うーん・・・こいつの場合は
          あらゆるハッシュ値に対して
          コリジョンを見つけるものだから
          それはちょっときついかな。

          解決策は二つ関数を使う、かなあ。

          たとえばMD5とMD4でコリジョンの出方が違うから
          2つ併用すればコリジョン確率はそうとう減るね・・・

          --
          いなんず[いつでも前向きでイタい]
          親コメント
          • > 2つ併用すればコリジョン確率はそうとう減るね・・・


            併用って
            /usr/bin/openssl dgst -md4 .bashrc | md5 ってこと?
            結局 md5 に依存してません?
            # 意味が違う?

            ## $ md4 .bashrc
            ## -bash: md4: command not found
            ## と怒られて man md4 を叩いたのは秘密だ。
            親コメント
            • > 併用って
              > /usr/bin/openssl dgst -md4 .bashrc | md5 ってこと?
              > 結局 md5 に依存してません?
              > # 意味が違う?

              そうじゃなくて、二つのハッシュ値を併記するってことじゃないですか。
              その書き方に合わせるなら
              /usr/bin/openssl dgst -md4 .bashrc ; md5 .bashrc
              ってことで。
              親コメント
              • ヒント2倍で答えを見つけるのも容易になりますね。

                # 一々突っ込む気がしないけど、#607064 以下のツリーは読む価値無いと思うよ。
              • > # 一々突っ込む気がしないけど、#607064 以下のツリーは読む価値無いと思うよ。

                同意な気がしなくもないですが、ハッシュ値の話で「ヒント2倍で正解が
                わかりやすくなる」てのも突っ込みたいポイントですよ。
              • ダイジェスト認証は2回あればヒント2個で楽かもしれないけど
                この議論は署名の安全性について。

                鍵を破る分にはコリジョンはさほどの脆弱性になんないけど
                たとえばzipにくっついてるMD5ハッシュについては
                攻撃しやすくなる、かなあと思う。

                --
                いなんず[いつでも前向きでイタい]
                親コメント
              • >ヒント2倍で答えを見つけるのも容易になりますね。
                使いかたにもよるだろうけど、ファイルが本物であることを証明するためにハッシュを使うなら、
                偽装のときに2つともコリジョンを発生させないといけないから有効な手段だと思います。

                # あれ?まちがってるかなぁ
                --
                1を聞いて0を知れ!
                親コメント
          • ちょっと違うけどトリプルDESみたいな感じかな?
  • by t-wata (10969) on 2004年08月18日 16時06分 (#607155) 日記
    > 驚くことに、コリジョン発見に要する時間はMD5でわずか数分で

    論文には、
    On IBM P690, it takes about one hour to find such M and M', after that, it takes only 15 seconds to 5 minutes to find N_i and N_i' , so that (M, N_i) and (M', N_i') will produce the same hash same value.
    とありますので、最初に1時間くらいかかるけど、それが終われば15秒から数分で計算できる、と読めます。
    それ以前に、この論文は不明瞭な点(our attack works for any given initial valueといっているのに、initial valueと計算式との関連がよく分からん、など)と明らかな誤植(Table-1の値で4バイトじゃないものがちらほら)があっていまいち理解できないのですが。
    • by aurora (5149) on 2004年08月19日 0時28分 (#607335) 日記
      initial value は MD5 のアルゴリズム内で使われている4つの定数のことです.RFC1321 [ipa.go.jp] ではセクション 3.3 に書いてある A, B, C, D です.

      4バイトになってないものは先頭の 0 が抜けているような感じです.

      肝心の M, N を発見する方法がどこにも書いてない気がしますが...

      -- 暑いからスーツはやめよう
      親コメント
  • これだけ一斉に出てくると言うことは、問題の根っこは一緒なのでしょうか?それにしてもMD5のコリジョン発見に数分というのは衝撃的ですね。

    とこれだけではなんなんで、CNET [cnet.com]の記事を紹介しておきます。
  • by Anonymous Coward on 2004年08月18日 12時56分 (#607042)
    コリジョンを発生する二つのメッセージを作る事は可能だったはず。 SHA-1についてはブルートフォース攻撃のように見えるし、慌てる必要なし。
  • by Anonymous Coward on 2004年08月18日 14時04分 (#607097)
    Winnyネットワークに同ハッシュ同サイズの捏造ファイルを撒く。
    • by unagi (2663) on 2004年08月19日 0時59分 (#607346) 日記
      一度、Winny本体をWinnyで配布したら、同じハッシュの捏造ファイルが出回ったのでWinnyで配布するのをやめたとかいう噂を聞いた事が。
      親コメント
    • by Anonymous Coward
      slashdot の cookie は MD5 なので
      偽の cookie を作って乗っ取る。

      --
      嘘ですよもちろん。念のため。
  • by Anonymous Coward on 2004年08月18日 16時33分 (#607172)
    で、実際のところ、電子署名にピンチが訪れるのでしょうか。

    何に署名するかによるでしょうが、
    少なくとも、自然言語文書に対する署名として用いる場合には、全く問題にならない

    ・・・・という理解で正しいですよね?
typodupeerror

私は悩みをリストアップし始めたが、そのあまりの長さにいやけがさし、何も考えないことにした。-- Robert C. Pike

読み込み中...