独自のMD5コリジョンを作成する

Question

私はMD5コリジョンに関するプレゼンテーションを行っています。どのようにコリジョンが起こる可能性があるのか​​を人々に伝えたいと思います。

同じことをハッシュする2つのテキストブロックを持ち、衝突する前に[a-zA-Z]の組み合わせがどれくらい必要かを説明するとよいでしょう。

明らかな答えは、2つのハッシュ値が同じになるまで可能なすべての組み合わせです。ですから、これをコーディングするにはどうしたらいいですか？簡単な実験として、私は[A-Z]の5列のすべての組み合わせをハッシュして、これを.netハッシュテーブルに格納し、衝突例外をキャッチしました。この2つの問題は、ハッシュテーブルが最終的にタイムアウトし、私はさらに多くの文字が必要になると確信しています。

明らかに、このデータ構造は大きすぎてメモリで処理できないため、データベースを作成する必要があります。また、紺色をテストするには良いプロジェクトのように聞こえます。少しビットthese guysのようです。

効率的に私を指し示すことができますこのやり方？

Answer 1

これら次の二つの異なった128のバイトの配列が同じにハッシュ：

MD5ハッシュ：以下79054025255fb1a26e4bc422aef54eb4

差が強調されている（太字）。申し訳ありませんがそれは一見難しいです。

 
d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89 
55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b 
d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70 

と

 
d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89 
55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b 
d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70 

衝突/ BLOCK1の可視化（出典：Links.Org）

衝突/ BLOCK2の可視化（出典：Links.Org）

Answer 2

Hashcashをご覧ください。 md5のような有効なハッシュアルゴリズムでは、ビット数で指数関数的に衝突を計算する時間です。ハッシュキャッシュは部分衝突を計算します。つまり、ハッシュの下位16ビットをマッチさせます。下位16ビットを一致させるには、平均して2^15の異なる組み合わせをハッシュしなければならないでしょう。 16,24、または32ビットの衝突がどれくらい時間がかかっているか分かっている場合は、より高いビット数の時間を簡単に計算できます。

Answer 3

単純な衝突がどれほど起こりそうか - あなたが意図的に衝突しようとしていない場合、あなたは失望するでしょう：あなたは平均して2^64のプレーンテキストを生成する必要がありますあなたは衝突を見ることを期待することができ、それはあなたが合理的な（または実際には、_un_reasonable）時間内に行うことができるよりも大幅に多くなります。

意図的に衝突を作成することの難しさを実証しようとしている場合は、他の回答が既にそのことを実証しています。文字列を完全にテキストにするという余分な制約は、それらのアプローチでさえもほとんど実用的ではありません。

Answer 4

このようなハッシュのポイントは、衝突が非常に起こりにくいことです。あなたが成功する前に、あなたのマシンは老朽化することは間違いありません。あなたが合理的に衝突を起こすことができるなら、ハッシュを使用することの全ポイントは消えてしまうでしょう！

Answer 5

テキストファイルAFAIKだけでは難しいです。 をの衝突にすることもできますが、[a-zA-Z]からのものでも簡単ではありません（まだ）。

一方、同じハッシュを持つ2つの「意味のある」ファイルが必要な場合は、PostScriptのように、衝突の原因となる異なるバイナリブロブを作成し、条件式を使用しますそれに応じて異なる出力を表示する。

this problem（H2部分）およびsolutionである。たとえば、this PS fileとthis oneは同じMD5sumを持っていますが、それらは開いたときに完全に異なるテキストを持つうまく形成されたPostScriptファイルです。