バイナリ アセットごとに、MD5 ハッシュを生成します。これは、特定のバイナリ アセットがアプリケーションに既に存在するかどうかを確認するために使用されます。しかし、2 つの異なるバイナリ アセットが同じ MD5 ハッシュを生成する可能性はありますか? では、2 つの異なる文字列が同じ MD5 ハッシュを生成する可能性はありますか?
85035 次
12 に答える
99
何十億もの資産のセットであっても、ランダムな衝突の可能性は無視できるほど小さく、心配する必要はありません。誕生日のパラドックスを考慮すると、2^64 (または 18,446,744,073,709,551,616) のアセットのセットが与えられた場合、このセット内で MD5 衝突が1 回発生する確率は 50% です。この規模では、おそらくストレージ容量の点で Google に勝るでしょう。
ただし、MD5 ハッシュ関数が壊れているため (衝突攻撃に対して脆弱です)、決心した攻撃者は、数秒で CPU パワーに相当する 2 つの衝突アセットを生成できます。したがって、MD5 を使用する場合は、そのような攻撃者がアプリケーションのセキュリティを侵害しないようにしてください!
また、攻撃者がデータベース内の既存の資産との衝突を偽造できる場合の影響も考慮してください。MD5 に対するそのような既知の攻撃 (プリイメージ攻撃)はありませんが ( 2011 年現在)、衝突攻撃に関する現在の研究を拡張することで可能になる可能性があります。
これらが問題になる場合は、SHA-2 シリーズのハッシュ関数 (SHA-256、SHA-384、および SHA-512) を調べることをお勧めします。欠点は、少し遅く、ハッシュ出力が長くなることです。
于 2009-11-18T13:51:33.470 に答える
45
MD5はハッシュ関数です。そのため、2つの異なる文字列が衝突するMD5コードを絶対に生成する可能性があります。
特に、MD5コードの長さは固定されているため、MD5コードの可能な数は制限されていることに注意してください。ただし、（任意の長さの）文字列の数は確実に無制限であるため、論理的には衝突が発生する必要があります。
于 2009-11-18T13:38:51.770 に答える
13
はい、もちろん: MD5 ハッシュの長さは有限ですが、MD5 ハッシュ化できる文字列の数は無限にあります。
于 2009-11-18T13:41:43.317 に答える
13
はい、2 つの異なる文字列が同じ MD5 ハッシュ コードを生成する可能性があります。
以下は、非常によく似た 16 進文字列のバイナリ メッセージを使用した簡単なテストです。
$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c6b384c4968b28812b676b49d40c09f8af4ed4cc -
008ee33a9d58b51cfeb425b0959121c9
$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c728d8d93091e9c7b87b43d9e33829379231d7ca -
008ee33a9d58b51cfeb425b0959121c9
それらは異なる SHA-1 サムを生成しますが、同じ MD5 ハッシュ値を生成します。第二に、文字列は非常に似ているため、それらの違いを見つけるのは困難です。
違いは、次のコマンドで確認できます。
$ diff -u <(echo 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2 | fold -w2) <(echo 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2 | fold -w2)
--- /dev/fd/63 2016-02-05 12:55:04.000000000 +0000
+++ /dev/fd/62 2016-02-05 12:55:04.000000000 +0000
@@ -33,7 +33,7 @@
af
bf
a2
-00
+02
a8
28
4b
@@ -53,7 +53,7 @@
6d
a0
d1
-55
+d5
5d
83
60
上記の衝突の例は、Marc Stevens から取得したものです: MD5 のシングルブロック衝突、2012; 彼は自分の方法をソースコードで説明しています (論文への代替リンク)。
別のテスト:
$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
756f3044edf52611a51a8fa7ec8f95e273f21f82 -
cee9a457e790cf20d4bdaa6d69f01e41
$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
6d5294e385f50c12745a4d901285ddbffd3842cb -
cee9a457e790cf20d4bdaa6d69f01e41
異なる SHA-1 サム、同じ MD5 ハッシュ。
違いは 1 バイトです。
$ diff -u <(echo 0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef | fold -w2) <(echo 0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef | fold -w2)
--- /dev/fd/63 2016-02-05 12:56:43.000000000 +0000
+++ /dev/fd/62 2016-02-05 12:56:43.000000000 +0000
@@ -19,7 +19,7 @@
03
65
9e
-70
+74
4f
85
34
@@ -41,7 +41,7 @@
a3
f4
15
-5c
+dc
bb
86
07
上記の例は、Tao Xie and Dengguo Feng: Construct MD5 Collisions Using Just A Single Block Of Message、2010 から改作されています。
関連している：
- 同じ MD5 ハッシュ値を持つ 2 つの既知の文字列はありますか? Crypto.SEで
于 2016-02-05T12:50:44.970 に答える
4
より有益になるために。数学の観点からは、ハッシュ関数は単射ではありません。
これは、開始セットと結果セットの間に 1 対 1 (ただし一方向) の関係がないことを意味します。
編集:完全な単射ハッシュ関数が存在する:それは完全ハッシュと呼ばれます。
于 2009-11-18T13:45:40.813 に答える
3
はい、そうです！衝突の可能性があります（ただし、リスクは非常に小さいです）。そうでなければ、かなり効果的な圧縮方法があります！
編集：Konrad Rudolphが言うように：有限の出力セット（32 hex chars）に変換された潜在的に無制限の入力セットは、無限の数の衝突を引き起こします。
于 2009-11-18T13:38:51.037 に答える
3
他の人が言ったように、はい、2 つの異なる入力間で衝突が発生する可能性があります。ただし、あなたのユースケースでは、それが問題になるとは思いません。あなたが衝突に遭遇することはまずありません - 私は以前の仕事で多数の画像 (JPG、ビットマップ、PNG、raw) 形式の何十万もの画像ファイルのフィンガープリンティングに MD5 を使用しましたが、衝突はありませんでした。 .
ただし、何らかのデータのフィンガープリントを作成しようとしている場合は、おそらく 2 つのハッシュ アルゴリズムを使用できます。1 つの入力が 2 つの異なるアルゴリズムで同じ出力になる確率はほぼ不可能です。
于 2009-11-18T13:44:47.920 に答える
3
ハッシュの衝突は予想したほどまれではないため、要件に応じてハッシュ アルゴリズムを慎重に選択する必要があると思います。私は最近、私のプロジェクトで非常に単純なハッシュ衝突のケースを見つけました。ハッシュに xxhash の Python ラッパーを使用しています。リンク: https://github.com/ewencp/pyhashxx
s1 = 'mdsAnalysisResult105588'
s2 = 'mdsAlertCompleteResult360224'
pyhashxx.hashxx(s1) # Out: 2535747266
pyhashxx.hashxx(s2) # Out: 2535747266
システムで非常にトリッキーなキャッシングの問題が発生し、最終的にハッシュの衝突であることがわかりました。
于 2016-02-02T06:12:29.923 に答える
0
実際の理論について話すとき、理論の理解は役に立たないようで、1と0の2つの数字だけが何を意味するのかを知る必要があるようです.1111111111を意味するので、100はその10倍を意味します.
1 つのファイルシステムまたは 1 つの誕生日システムで必要なすべてのハッシュを使用するには、世界中のすべての人が 18446744073709551616/8000000000=2305843009.21 ファイルを持つ必要があります。 Google は、1 人あたり 15 GB を無料でドライブします。
ファイルを大きくすると、使用されるスペースが増え、ファイル数が減るということは、ハッシュが減ることを意味します。したがって、小さいサイズのファイルはまだありませんが、大きいだけです。
MD5 のすべてのハッシュを埋めるために必要なファイルの大きさを誰かに計算してもらいます。
平均ファイル サイズが 2002 年に 3.22 MB、2005 年に 8.92 MB である場合、同じ品質のファイル サイズを使用していると想定できます。したがって、Google ファイルシステムでさえ、1 つのシステムにそれほど多くのファイルが存在することはありません。15 GB の無料の Google ドライブが満杯で、世界の 80 億人ごとに平均して小さな 3 MB のファイルがたくさんある場合、すべての MD5 ハッシュからの 40000000000000 になるため、すべてのハッシュ可能なハッシュの 0.0000021684% の可能性があります。ファイルサイズ。
2 人の 100 歳の誕生年の誕生日のような関係のないことについて話すと、2 日または 0.02 を比較することになり、2 人の 365 人で 0.00547% の MD5 ファイルを比較することになります。全て。
それは、アダムとイブの世界で、世界に 365 人、ファイル システムのファイルに、または非常に多くのパスワードがまったくないときに、ハッシュの誕生日が同じかどうかを尋ねるようなものです。
したがって、ハッキングしようとする衝突は非常に多く、実際の安全なサーバーでは不可能です.
MD5 の最大制限が 18,446,744,073,709,551,616 の場合、全世界でそれほど多くのファイルが存在することはありません。
MD5 は、すべての世界の文字列をハッシュにカウントする例であり、これほど長く存在することはないため、MD5 が短いという問題にすぎませんが、本当に同じハッシュを持つ巨大な長さの文字列が何兆個もあるでしょうか?
実際には、365 日の異なる赤ちゃんと 366 人の赤ちゃんを比較して、どの誕生日が同じかを調べるようなものです。
ご覧のとおり、すべての答えは理論的にはイエスと答えていますが、実際の例を証明することはできません。そのパスワードの場合、非常に長い文字列のみが短い文字列と同じになる可能性があります。
そのファイル識別ハッシュの場合、別のハッシュまたはそれらの組み合わせを使用します。
誕生日の問題は、ある人は「abcd」という 4 文字の単語ですが、他の人の DNA は「abcdfijdfj」の場合にのみ同じである可能性があるためです。
誕生日の問題についてウィキペディアを読むと、誕生日の日付だけでなく、誕生日の生年月日、時、秒、ミリ秒など、DNA の問題にも似ています。
ハッシュを使えば、双子と同じDNAと誕生日を持つことができますか? いいえ。時には誰かと。
誕生日のパラドックスは確かに 365 のオプションまたは日の確率の信頼度の計算結果の可能性ですが、ハッシュはいくらからですか? はるかに。したがって、2 つの異なる一致する文字列がある場合は、MD5 ハッシュがあまりにも多くのファイルに対して短すぎるため、MD5 よりも長いものを使用してください。
365 日間で 50 人の赤ちゃんを比較するのではなく、複数の長さの文字列から同じである場合、2 つのハッシュを比較します。
したがって、そのパスワードの場合、誕生日の兄弟は、25文字のパスワードを作成する人がいないため、存在すらしないほど長くなります。
ファイルサイズの比較については、確率がどれくらい大きいかはわかりませんが、97% ではなく、0.0000001% でさえありません。
わかりました、より具体的にしましょう。
ファイルが異なるため、そのファイルが巨大なシステムで発生する可能性がありますが、UUID と MD5 の場合、5 千兆または 5 000 000 000 000 000 ファイルが同じシステムにある必要があるため、実際には問題にはなりません。
パスワードの場合、毎秒試行するのに 10 年かかりますが、ミリ秒ごとに試行することもできますが、3 回の間違った推測で 1 分間 IP をブロックすると、数百万年を推測することになります。
私が何か間違ったことを見ると、それが間違っていることがわかります。理論の約束と現実。
于 2021-12-18T10:51:24.133 に答える