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

MD4/MD5 コリジョンの実証コードが公開 83

ストーリー by yoosee
実際に目にするとインパクトがあります 部門より

MACKS曰く、"セキュリティホールmemo経由で知ったのですが、MD4/MD5 コリジョンの実証コードが公開されています(SecurityFocus への投稿)。ためしに MD5 コリジョンの実証コードをコンパイルして引数なしで実行してみたところ、数十分程度でデータ列が 2 つ出力されました(Pen4 3.0GHz で 20~80分程度。たまに終了しないこともあります)。また、2 つのデータ列のハッシュ値は見事に一致していました。

論文や実際のコードを見ても私にはチンプンカンプンですが、こうして実行結果を見ると驚きです。今はまだ、任意のハッシュ値を持つデータ列を生成できたりはしないようですが、これからの研究や計算機能力の向上を考えると「MD5 は死んだ(も同然)」というのは誇張ではないかもしれない、というのが実感できました。関連記事: SHA-0、MD5、 MD4にコリジョン発見、reduced SHA-1も"

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • 関連記事 (スコア:5, 興味深い)

    by jmk (11245) on 2005年11月18日 13時28分 (#834076)
    セキュリティの大御所が集まり、代替暗号法を話し合う [linux.com]

    ここで、我々のような利用者にとって重要な提言はこれでしょうね。

    「アルゴリズム的に機敏」なアプリケーションにできればもっとよい。つまり、暗号化アルゴリズムの寿命が比較的短いことを踏まえ、アプリケーションの寿命よりアルゴリズムの寿命が先に尽きることを前提にしたアプリケーション作りをせよ、ということである。
  • random関数 (スコア:3, 興味深い)

    by towest (17977) on 2005年11月18日 11時11分 (#834001)
    ソースを覗いて見ましたが、random関数を使っていますね。
    Cのrandom関数はあまり精度がよくないと聞きますが、
    標準のrandom関数を使うのではなく
    例えば mersenne twister を使うと実行速度が変わったりするのでしょうか?

    mersenne twister の乱数生成速度が影響して
    逆に遅くなったりするかもしれませんが、
    単純に乱数生成速度が無視できたらどうなんでしょうね。
    • Re:random関数 (スコア:3, 参考になる)

      by Anonymous Coward on 2005年11月18日 12時05分 (#834037)
      randomの精度が問題になるのは、本当に自然乱数に近い値が欲しいときであって、
      このような実験ではそれほど重要ではないと思うです。
      親コメント
    • Re:random関数 (スコア:1, すばらしい洞察)

      by Anonymous Coward on 2005年11月18日 12時00分 (#834033)
      >単純に乱数生成速度が無視できたらどうなんでしょうね。

      じゃぁ単純にハードウェアから取ってくれば
      いいんじゃないかと・・・
      少なくとも「生成」速度は無視できるような気がします
      親コメント
    • Re:random関数 (スコア:1, 参考になる)

      by tekete (19724) on 2005年11月18日 16時26分 (#834155) 日記
      > ソースを覗いて見ましたが、random関数を使っていますね。
      > Cのrandom関数はあまり精度がよくないと聞きますが、

      戻り値のどの辺りのビットを使っているかにもよりますね。
      中間のビットを使用しているのであれば、それ程問題はないと思います。
      参考:良い乱数・悪い乱数 [so-net.ne.jp]
      親コメント
      • Re:random関数 (スコア:1, 参考になる)

        by Anonymous Coward on 2005年11月18日 18時16分 (#834211)
        そのサイトで解説されているrandomのアルゴリズムと 実際に実装されているrandomのアルゴリズムは 比べてみると別物でした。 つまり参考になりませんでした。 「中間のビットを使用しているのであればそれほど問題ない」 という結論になる理由を分かりやすく教えてくださいませ。
        親コメント
  • by tnk (13707) on 2005年11月18日 13時19分 (#834071)
    この手のハッシュのコリジョンの話題が出るたびにいつも思うのですが,組み合わせて使うわけにはいかないのでしょうか?

    たとえば,MD5で同じハッシュ値の出る二つのデータ列は何とか得られるでしょうが,これらのデータ列のSHA-1のハッシュ値も一致するものを探すのは,さすがに無理だと思うのですが。

    ハッシュ値の長さが倍になるのは,各種の暗号化仕様にとってそんなに致命的なんでしょうか?
    • by shojin (28072) on 2005年11月18日 13時39分 (#834083) 日記
      128bitのハッシュを使うように設計されているソフトは
      ハッシュ値を入れる領域として16バイトのchar配列を
      使うようにソースじか書きだったりするので変更が
      難しいということはあると思います。ハードウェアでも
      おそらく状況は同じで、ハッシュ値を入れるための
      メモリーが16バイトとして配線してあったりして
      それを拡張するのはかなり難しいのではないで
      しょうか。
      親コメント
    • by Eyu (13282) on 2005年11月18日 18時47分 (#834225)
      方式A(16bit)と方式B(16bit)を組み合わせて32bitを稼ぐことは、方式C(32bit)をつかうことにくらべると、32bit分のハッシュ値のばらつき方がより偏りやすくなる可能性があると思う。

      ただ、暗号方式が廃れていくことを前提に考えるなら、異なるアルゴリズムで算出されたハッシュ値を示しておくことは保険になると思う。
      親コメント
    • by Anonymous Coward on 2005年11月18日 13時30分 (#834079)
      japan.linux.com | セキュリティの大御所が集まり、代替暗号法を話し合う
      http://japan.linux.com/security/05/11/08/0213251.shtml

      上記URLより引用
      >いま何かを開発中なら、迷わずSHA256を選択しよう。
      ということのようです。
      親コメント
  • by SilentH (24329) on 2005年11月19日 8時28分 (#834550)
    前にSHA-1のニュースのときにセキュリティの先生が、「SHA-1がこんなになっちゃってるのに、世間じゃようやくMD-5採用なんだよね」とかぼやいていました。

    今回のニュースは、意図的な文書偽造を可能にするものではありませんが、コンピュータ環境の日進月歩な進歩と、遅々として進まない実際の運用サイドの意識を考えると、心配になってしまいます。
  • by njt (4968) on 2005年11月18日 11時30分 (#834011) 日記
    Linuxや*BSDなどのソースアーカイブは改ざん防止にMD5を同時に置いてあるところも多いように思います。
    # make build-install
    とかすると、途中で自動的に検査を行うものもあったように思いますが、異なるハッシュを使うとなると、影響はどのぐらいあるんでしょうね。
    • by SteppingWind (2654) on 2005年11月18日 11時43分 (#834020)

      FreeBSDのportsでは最近, 従来のMD5に加えてSHA-256によるチェックが行えるようになったみたいです. 今後はMD5はobsoleteになるんじゃないですかね.

      親コメント
      • by shojin (28072) on 2005年11月18日 13時14分 (#834068) 日記
        FreeBSDのportsではMD5の強衝突耐性が突破されたとの
        報道がなされたときにSIZEが入り、今回のソフトウェア
        の公開と同時にSHA256が入ってますね。

        しかしながら、cnetの報道(*1)によるとSHA256はSHA-1
        とアルゴリズムが異なりますが、安全性が確認
        されているわけではなく、5年も持たないのではないか
        と言われているようですね。

        #そういえば、160bitsのハッシュでもripemd160は
        #どうなんでしょうね。ほとんど使われていない
        #ようですが。

        (*1)
        http://japan.cnet.com/news/sec/story/0,2000050480,20090227,00.htm
        親コメント
    • by twovs (13797) on 2005年11月18日 11時59分 (#834032)
      任意のハッシュ値を持つデータ列の生成が困難であること(弱衝突耐性)と、同じハッシュ値を持つ 2つのデータ列の生成が困難であること(強衝突耐性)は違います。今回の話題は、後者の方ですね。
      親コメント
      • by seoth (17664) on 2005年11月18日 12時14分 (#834040)
        私もそうだと思うんですが、前のストーリのコメント [srad.jp]を見ても意見が割れてるんですよねえ…

        CRYPTO 2004に参加されたすずきひろのぶ氏曰く「安全性に関してですが、MD5に関してはかなり厳しいです。たとえばNSAあたりがダウンロード配布ファイルの中身に彼らが作ったトロイの木馬を潜ませるなんてことが可能になります。」「MD5はもうダメです。その点はあきらめてください。」と、弱衝突耐性を突破されたような事を匂わせてるし。
        でもそれが本当ならもっと大ニュースになってるはずですよね。
        親コメント
        • by Anonymous Coward on 2005年11月18日 12時52分 (#834057)
          まあ、すずきひろのぶ氏が言うことだからねえ・・・。
          親コメント
          • by Anonymous Coward on 2005年11月18日 15時59分 (#834145)
            >同じハッシュ値を持つ 2つのデータ列の生成が困難であること(強衝突耐性)
            こちらは、データがユニークである事(改ざんされてないこと)をある程度保証します。

            >任意のハッシュ値を持つデータ列の生成が困難であること(弱衝突耐性)
            こちらは、データがユニークである事(改ざんされてないこと)はあまり保証できませんが、改ざん者が意図通りのデータをデータ列に入れ込む事が困難な事は保証しています。

            ですから、アレですね、その記事は(詳細略
            親コメント
            • by Anonymous Coward on 2005年11月18日 17時20分 (#834180)
              >>任意のハッシュ値を持つデータ列の生成が困難であること(弱衝突耐性)
              >こちらは、データがユニークである事(改ざんされてないこと)はあまり保証できませんが、改ざん者が意図通りのデータをデータ列に入れ込む事が困難な事は保証しています。

              ちょっと違います。

              データがユニークである事(改ざんされてないこと)はあまり保証できませんが、だからと言って、改ざん者が(データ,ハッシュ値)の組み合わせに対して、ハッシュ値を同一にしたままでデータを別の物に改ざんする事が容易になったわけではありません(そのような実装はまだ出ていない。理論が出されたかは不明)。

              もしそのような弱衝突耐性をも突破されたとしたら、もはや検証符号としては誤り検出符号程度の意味しか持たなくなります。
              親コメント
      • by miri (12057) on 2005年11月19日 20時15分 (#834830) 日記
        強衝突耐性を前提としてデータ管理にMD5を使っているアプリケーションとかないんでしょうか?

        たとえばWinnyなどのファイル交換・共有ソフトとか。

        下手なコーディングがされていたら、同じMD5を持っている2種類のファイルを登録したら予期しない例外でとまってしまうとか、悪くすればバッファオーバーフローなどの脆弱性が発生したりとか。。。

        前提とされていたものが崩れたときには、本当にいろいろなチェック項目が発生すると思います。たとえそれが、本来前提として必要ないものであっても、そう誤解されるようなものであれば。
        親コメント
    • RPM も MD5 を使ってますね。
      ただ,多くのディストロでは電子署名も併用していると思うので多少の信頼性は確保できているのじゃないかと。
      もっとも電子署名自体も基本的にSHA-1を使っているので,問題がないわけではないです。
      結局「完璧」というのはあり得ないのでどこかのレベルで妥協せざるを得ないのでしょう。
      親コメント
    • Fedoraは、SHA1を使っていますね。大丈夫かどうか、知らないけど。
  • by Anonymous Bold (12187) on 2005年11月18日 11時53分 (#834026)
    ハッシュなんて、元々コリジョンが発生するのが当たり前でしょ。だって、巨大な可変長データ列から、固定長の十分短い値を計算するのだから。
    コリジョンが起こりにくくて実用に十分耐えうるから、今まで使用されてきたんじゃないのか。
    ハッシュが嫌なら、圧縮値を使用するしかないでしょ。実用的だと思う?他に代替手段ある?
    • by quickcopper (17781) on 2005年11月18日 11時56分 (#834028)
      圧縮値ってなんですか?
      親コメント
    • by Anonymous Bold (12187) on 2005年11月18日 11時58分 (#834031)
      投稿後に気づきました。
      論点がズレてますね。
      「MD5 は死んだ(も同然)」に脊髄反射したけど、それにしても、「いずれ『任意のハッシュ値を持つデータ列を生成』できる」ことに言及してるんですよね。
      親コメント
    • by attu (959) on 2005年11月18日 12時25分 (#834044)
      コリジョンが発生する2つのもとデータが「簡単に」得られる方法が見つかったことが問題なんですよ。
      上のほうのコメントにもありますが、強衝突耐性ってやつかな?
      親コメント
      • by Anonymous Coward on 2005年11月18日 12時59分 (#834062)
        任意のハッシュ値と衝突する元データを生成できる
        というのでなければ、脅威としては弱いでしょう。

        ハッシュ値を同じくする二つのデータ列が得られたとして、
        そのデータ列はランダムな無意味なデータですよ、
        というのであれば、アタックする視点から考えれば
        利用価値はほとんどないように思えます。

        衝突の有るハッシュ値を沢山生成できたとして、
        あるダウンロード後の同値性チェック用のMD5値と
        同じ値の元データの組が沢山生成した衝突ハッシュ値の
        組の中にあるのではないか、と探すということは
        単にハッシュ値が同じになる元データを盲目的に
        探すこととセキュリティ的な耐性は変わらないのではないでしょうか?
        親コメント
        • by oltio (3848) on 2005年11月18日 18時04分 (#834207) 日記
          考えられる悪用シナリオ。

          仮に任意のデータ列 A に対し、f(x) がハッシュ関数として

          f(A+B) = f(A+C) :ここで"+"は単なる連接か、部分的改変とする

          となる B,C のペアを見付けられる、という状態になったとして、A+B は無害、A+C が有害となるようなファイルが生成できるとする。A として人気コンテンツを用意し、まず無害な A+B を放流。頃合を見計らって A+C を同じIDで投入する。先に無害な方を放流しているので、そのIDとハッシュは安全という認識が広まっており、A+C も無害扱いされる。

          問題はいくつかの前提がどこまで現実味があるか。
          f(A+B) = f(A+C) になるB,Cの発見については、現在の手法の延長線上にあるので、一応現実味があるとしよう。A+B が無害で A+C が有害となる"+"および B,C の生成については、たとえばそもそも A に有害コードを埋め込んでおき、B,C の内容如何でそれが発現するかしないかを選択できる、という手法はあるかもしれない。B,C内のデータを参照して、ある条件が成立したら発現、というようにしておき、あとは B で成立せず C で成立するような B,C を探せばよい。
          親コメント
        •  セキュリティの脅威としては弱いけど、ただの捏造データなら容易に作れそうですね。
           インストールしようとしたファイルが、ただのジャンクデータだったりしたらそれはそれで嫌だなー……っと思った。
          --
          --- どちらなりとご自由に --- --
          親コメント
typodupeerror

あつくて寝られない時はhackしろ! 386BSD(98)はそうやってつくられましたよ? -- あるハッカー

読み込み中...