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, 興味深い)
ここで、我々のような利用者にとって重要な提言はこれでしょうね。
Re:関連記事 (スコア:2, おもしろおかしい)
新しい暗号化モジュール付きソフトでファイルを保存しなおさない限り古いアルゴリズムのままという事ですかね？
あと下位互換性とか肥大化とか・・・
・・・つまり保存するたびに
-------------------------
ワープロ2006
-------------------------
この文書は既に安全でない暗号化方式で暗号化されています。
最新の暗号化方式を使用しますか？
(ただし、ワープロ2006+暗号化PACK20051119以前のバージョンでは開くことが出来なくなります)
-------------------------
|はい(Y)| |いいえ(N)|
-------------------------
となる・・・わけないか
random関数 (スコア:3, 興味深い)
Cのrandom関数はあまり精度がよくないと聞きますが、
標準のrandom関数を使うのではなく
例えば mersenne twister を使うと実行速度が変わったりするのでしょうか？
mersenne twister の乱数生成速度が影響して
逆に遅くなったりするかもしれませんが、
単純に乱数生成速度が無視できたらどうなんでしょうね。
Re:random関数 (スコア:3, 参考になる)
このような実験ではそれほど重要ではないと思うです。
Re:random関数 (スコア:1, すばらしい洞察)
じゃぁ単純にハードウェアから取ってくれば
いいんじゃないかと・・・
少なくとも「生成」速度は無視できるような気がします
Re:random関数 (スコア:1, 参考になる)
> Cのrandom関数はあまり精度がよくないと聞きますが、
戻り値のどの辺りのビットを使っているかにもよりますね。
中間のビットを使用しているのであれば、それ程問題はないと思います。
参考：良い乱数・悪い乱数 [so-net.ne.jp]
Re:random関数 (スコア:1, 参考になる)
Re:random関数 (スコア:1, 興味深い)
それはなぜですか？
乗算を使わず高速化を図っているMTが
乗算を含んでしまう線形合同法よりさも当り前のように
遅くなってしまうと言い切る理由が全く分かりません。
＃ためしに簡単なベンチマークコードを作ってgccでコンパイルして
＃P4上で走らせてみたところglibcのrandやrandomよりMTの方が速かった。約5倍速。
＃これでmd5coll.cの高速化の手が見えた？
Re:random関数 (スコア:3, 興味深い)
問題の glibc の rand() は、初期化済みかどうかのチェックやら lock/unlock やらいろいろと複雑なことをやっているので遅くなっているようです。
Re:random関数 (スコア:1, 興味深い)
単純な線形合同法ではなくrandomの代用となれるだけの
周期を延長させた線形合同法にて比較しないと前提が崩れますよ。
今回の衝突目的として使い物にならない短周期疑似乱数を
代用品として提示しても規格外ですから。
もし要求仕様を満たさないものも比較対象にできるなら
「int rand(){static int a=1;return a+=1;}の方が速い」と言えます。
しかしそれでは衝突を見つけ出す目的として使えないので使えません。
同様に、単純な線形合同法による特定の実装が短周期であり
衝突を見つけ出すことができないならば、それもa+=1と同じようなものです。
Re:random関数 (スコア:2, 興味深い)
当然、線形合同法なんて使ってません。
組み合わせてはいけないの？ (スコア:3, すばらしい洞察)
たとえば，MD5で同じハッシュ値の出る二つのデータ列は何とか得られるでしょうが，これらのデータ列のSHA-1のハッシュ値も一致するものを探すのは，さすがに無理だと思うのですが。
ハッシュ値の長さが倍になるのは，各種の暗号化仕様にとってそんなに致命的なんでしょうか？
Re:組み合わせてはいけないの？ (スコア:3, すばらしい洞察)
ハッシュ値を入れる領域として16バイトのchar配列を
使うようにソースじか書きだったりするので変更が
難しいということはあると思います。ハードウェアでも
おそらく状況は同じで、ハッシュ値を入れるための
メモリーが16バイトとして配線してあったりして
それを拡張するのはかなり難しいのではないで
しょうか。
Re:組み合わせてはいけないの？ (スコア:2, 興味深い)
ただ、暗号方式が廃れていくことを前提に考えるなら、異なるアルゴリズムで算出されたハッシュ値を示しておくことは保険になると思う。
Re:組み合わせてはいけないの？ (スコア:1, 参考になる)
http://japan.linux.com/security/05/11/08/0213251.shtml
上記URLより引用
＞いま何かを開発中なら、迷わずSHA256を選択しよう。
ということのようです。
Re:組み合わせてはいけないの？ (スコア:2, 興味深い)
AからMD5でハッシュ値を計算して、それが既知のハッシュ値Xと等しければ本物のAだ、と言えたのが、BからもXが計算されるのでは、ハッシュ値は計算前データの証明にならなくなってしまう、と。
しかし、AからMD5で計算し、かつAからSHA-1で計算し、それぞれ既知のX、Yと等しいもの、とすればどうでしょう？
MD5(B)=X , SHA-1(B)=Y を同時に満たすBが存在する確率は、片方の時の比ではないと思います。
…という素人考えですがいかがでしょうか。
Re:組み合わせてはいけないの？ (スコア:2, 興味深い)
単独のハッシュ関数では安全なのに、複数組み合わせると安全性が低下してしまう
簡単な例を示してみます。
a,bの2数からなるデータのハッシュ値を作る関数として、以下の2つがあるとします。
hash1(a,b)= a+b
hash2(a,b)= a-b
この場合、どちらか片方のハッシュ関数の値からは元の値を求めることは不可能ですが、
両方のハッシュ値があると、
(hash1(a,b)+hash2(a,b))/2=a
(hash1(a,b)-hash2(a,b))/2=b
となり、元の値を求めることが出来てしまいます。
実用されているハッシュ関数では上記の例のように簡単にはいきませんが、
複数のハッシュ関数で求めた値を提供する場合安全性が低下する可能性があります。
なので、複数のハッシュ値を提供するには、慎重な検討が必要です。
＃素人考えでレスしてるのでAC
Re:組み合わせてはいけないの？ (スコア:2, すばらしい洞察)
でも今は「2つ使うと強衝突耐性の低さをカバーできるんじゃないか」、という話題ですよね？
脱線 (スコア:2, 参考になる)
先のコメントを書きつつ、「MD5は死んだ」と言われる意味がようやく飲み込めました。
つまり”関数単独で弱・強両方が高度である事が出来ない”点でもう使えないと言われてるわけですね。
当然ひとつの関数で両方達成できたほうが良いに決まってるし、最近までMD5はそういう関数だと期待されていたわけですから。
ハッシュ関数はこうして”死んで”いくのだなあ、と初歩的な事をしみじみ考えてしまいました。
Re:組み合わせてはいけないの？ (スコア:1, すばらしい洞察)
Re:組み合わせてはいけないの？ (スコア:1, すばらしい洞察)
素人考えをそのまま考慮なしに採用してしまうのであれば、
それが問題なのだと思います。
Re:組み合わせてはいけないの？ (スコア:2, すばらしい洞察)
の例証かと。
Re:組み合わせてはいけないの？ (スコア:1)
Re:そんな中途半端な (スコア:1)
それは、改竄チェック用ではなく、転送中に破損していないかを確認するためではないでしょうか。
そういう目的なら公開鍵暗号等の方法でデジタル署名をするかと思います。
Re:そんな中途半端な (スコア:1)
実際の運用側の対応は (スコア:2, 興味深い)
今回のニュースは、意図的な文書偽造を可能にするものではありませんが、コンピュータ環境の日進月歩な進歩と、遅々として進まない実際の運用サイドの意識を考えると、心配になってしまいます。
ソースアーカイブのハッシュとか (スコア:1, 興味深い)
# make build-install
とかすると、途中で自動的に検査を行うものもあったように思いますが、異なるハッシュを使うとなると、影響はどのぐらいあるんでしょうね。
Re:ソースアーカイブのハッシュとか (スコア:4, 参考になる)
FreeBSDのportsでは最近, 従来のMD5に加えてSHA-256によるチェックが行えるようになったみたいです. 今後はMD5はobsoleteになるんじゃないですかね.
Re:ソースアーカイブのハッシュとか (スコア:4, 興味深い)
報道がなされたときにSIZEが入り、今回のソフトウェア
の公開と同時にSHA256が入ってますね。
しかしながら、cnetの報道(*1)によるとSHA256はSHA-1
とアルゴリズムが異なりますが、安全性が確認
されているわけではなく、5年も持たないのではないか
と言われているようですね。
＃そういえば、160bitsのハッシュでもripemd160は
＃どうなんでしょうね。ほとんど使われていない
＃ようですが。
(*1)
http://japan.cnet.com/news/sec/story/0,2000050480,20090227,00.htm
Re:ソースアーカイブのハッシュとか (スコア:2, 参考になる)
NetBSDなどのpkgsrcでは、SHA-1とRIPEMD-160が使われてます。MD5は使われてません。
Re:ソースアーカイブのハッシュとか (スコア:4, 参考になる)
Re:ソースアーカイブのハッシュとか (スコア:3, 参考になる)
CRYPTO 2004に参加されたすずきひろのぶ氏曰く「安全性に関してですが、MD5に関してはかなり厳しいです。たとえばNSAあたりがダウンロード配布ファイルの中身に彼らが作ったトロイの木馬を潜ませるなんてことが可能になります。」「MD5はもうダメです。その点はあきらめてください。」と、弱衝突耐性を突破されたような事を匂わせてるし。
でもそれが本当ならもっと大ニュースになってるはずですよね。
Re:ソースアーカイブのハッシュとか (スコア:1, すばらしい洞察)
Re:ソースアーカイブのハッシュとか (スコア:1, 参考になる)
こちらは、データがユニークである事（改ざんされてないこと）をある程度保証します。
>任意のハッシュ値を持つデータ列の生成が困難であること(弱衝突耐性)
こちらは、データがユニークである事（改ざんされてないこと）はあまり保証できませんが、改ざん者が意図通りのデータをデータ列に入れ込む事が困難な事は保証しています。
ですから、アレですね、その記事は（詳細略
Re:ソースアーカイブのハッシュとか (スコア:1, 参考になる)
>こちらは、データがユニークである事（改ざんされてないこと）はあまり保証できませんが、改ざん者が意図通りのデータをデータ列に入れ込む事が困難な事は保証しています。
ちょっと違います。
データがユニークである事（改ざんされてないこと）はあまり保証できませんが、だからと言って、改ざん者が（データ,ハッシュ値）の組み合わせに対して、ハッシュ値を同一にしたままでデータを別の物に改ざんする事が容易になったわけではありません（そのような実装はまだ出ていない。理論が出されたかは不明）。
もしそのような弱衝突耐性をも突破されたとしたら、もはや検証符号としては誤り検出符号程度の意味しか持たなくなります。
Re:ソースアーカイブのハッシュとか (スコア:2, 興味深い)
たとえばWinnyなどのファイル交換・共有ソフトとか。
下手なコーディングがされていたら、同じMD5を持っている2種類のファイルを登録したら予期しない例外でとまってしまうとか、悪くすればバッファオーバーフローなどの脆弱性が発生したりとか。。。
前提とされていたものが崩れたときには、本当にいろいろなチェック項目が発生すると思います。たとえそれが、本来前提として必要ないものであっても、そう誤解されるようなものであれば。
Re:ソースアーカイブのハッシュとか (スコア:1)
ただ，多くのディストロでは電子署名も併用していると思うので多少の信頼性は確保できているのじゃないかと。
もっとも電子署名自体も基本的にSHA-1を使っているので，問題がないわけではないです。
結局「完璧」というのはあり得ないのでどこかのレベルで妥協せざるを得ないのでしょう。
Re:ソースアーカイブのハッシュとか (スコア:1)
Re:ソースアーカイブのハッシュとか (スコア:0)
何を今更... (スコア:0)
コリジョンが起こりにくくて実用に十分耐えうるから、今まで使用されてきたんじゃないのか。
ハッシュが嫌なら、圧縮値を使用するしかないでしょ。実用的だと思う？他に代替手段ある？
Re:何を今更... (スコア:1)
Re:何を今更... (スコア:1)
Re:何を今更... (スコア:1)
論点がズレてますね。
「MD5 は死んだ(も同然)」に脊髄反射したけど、それにしても、「いずれ『任意のハッシュ値を持つデータ列を生成』できる」ことに言及してるんですよね。
Re:何を今更... (スコア:1)
上のほうのコメントにもありますが、強衝突耐性ってやつかな？
Re:何を今更... (スコア:1, 興味深い)
というのでなければ、脅威としては弱いでしょう。
ハッシュ値を同じくする二つのデータ列が得られたとして、
そのデータ列はランダムな無意味なデータですよ、
というのであれば、アタックする視点から考えれば
利用価値はほとんどないように思えます。
衝突の有るハッシュ値を沢山生成できたとして、
あるダウンロード後の同値性チェック用のMD5値と
同じ値の元データの組が沢山生成した衝突ハッシュ値の
組の中にあるのではないか、と探すということは
単にハッシュ値が同じになる元データを盲目的に
探すこととセキュリティ的な耐性は変わらないのではないでしょうか？
Re:何を今更... (スコア:3, 興味深い)
仮に任意のデータ列 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 を探せばよい。
Re:何を今更... (スコア:2, 参考になる)
この辺にぶら下げればいいんですかね.
2005/06辺りに話題になったもので, 同じハッシュを持つ別のpsファイルの実例があります. CITS - MD5 Collisions - Attacking Hash Functions by Poisoned Messages "The Story of Alice and her Boss" [cits.rub.de]に悪用例があるので見ると良いかと.
奥村晴彦のWiki 2005/06/11 MD5の衝突 [mie-u.ac.jp]経由.
Re:何を今更... (スコア:1)
Re:何を今更... (スコア:1)
インストールしようとしたファイルが、ただのジャンクデータだったりしたらそれはそれで嫌だなー……っと思った。
--- どちらなりとご自由に --- --
Re:何を今更... (スコア:1)
条件次第で同じハッシュが出るところまで導き出せているのなら、比較元のデータを捏造する対象にして、もう一方に元データに似たサイズのランダムなデータを出力できるようにすればいい。
ファイルの中身をどの程度変更するかのさじ加減が難しくなるかもしれないけど、実証コードを改造すれば作れるんではないかと。
処理時間などを考えると、実用的な時間におさまらないかもしれないけど、圧縮したソースやjpg程度のサイズならいい線いくんじゃないだろうか？
今までの話の流れで出ているセキュリティ上の話だと、ハッシュが同じかつ意味のある（実際に動く）捏造データを求めるから困難なのであって、ただのジャンクデータでいいなら作れると思うんだけど……って話。
問題があるとすれば、総当り的にやるのはいいが実際にデータが作れるかどうかを運に頼っているところかな？ 全てのデータに対応できないので「容易じゃない」と言われればそれまでですが。
＃つーか、半分はジョークのつもりで書いたのに突っ込まれたですよ orz
--- どちらなりとご自由に --- --