hash - substr md5 衝突

Question

4 文字のハッシュが必要です。現時点では、md5()ハッシュの最初の 4 文字を取得しています。80 文字以下の文字列をハッシュしています。これは衝突につながりますか？^{または、65,536 (16 4} )未満の異なる要素をハッシュすると仮定すると、衝突の可能性はどのくらいですか?

score 6 · Accepted Answer

の各文字md5は 16 進ビットです。つまり、16 の可能な値のいずれかを持つことができます。したがって、最初の 4 つの「16 進ビット」のみを使用している場合は、または 65536 または可能性があることを意味16 * 16 * 16 * 16し16^4ます2^16。

つまり、結果に使用できる合計「スペース」は 16 ビット幅しかないということです。さて、誕生日の攻撃/問題によると、次の衝突の可能性があります。

そのため、衝突の可能性が非常に高くなります。

ここで、4 文字のハッシュが必要だと言います。正確な要件に応じて、次のことができます。

16^4(65,536) の可能な値の 4 つの 16 進数ビット
26^4(456,976) の可能な値の 4 つのアルファビット
36^4(1,679,616) の可能な値の 4 つの英数字ビット
約93^4(74,805,201) の可能な値の 4 つの ASCII 印刷可能ビット (ASCII 33 -> 126 と仮定)
256^4(4,294,967,296) の可能な値の 4 つの完全なバイト。

どちらを選択するかは、実際のユースケースによって異なります。ハッシュをブラウザに送信する必要がありますか? 保管方法など。

それぞれの例を示します (PHP では、翻訳が簡単で、何が起こっているかを確認できます)。

4 つの Hex ビット:

$hash = substr(md5($data), 0, 4);

4 アルファビット:

$hash = substr(base_convert(md5($data), 16, 26)0, 4);
$hash = str_replace(range(0, 9), range('S', 'Z'), $hash);

4 つの英数字ビット:

$hash = substr(base_convert(md5($data), 16, 36), 0, 4);

4 印刷可能な Assci ビット:

$hash = hash('md5', $data, true); // We want the raw bytes
$out = '';
for ($i = 0; $i < 4; $i++) {
    $out .= chr((ord($hash[$i]) % 93) + 33);
}

4 バイト:

$hash = substr(hash('md5', $data, true), 0, 4); // We want the raw bytes

score 1 · Accepted Answer

確かに意外と高い。このおおよその衝突確率のグラフ(ウィキペディアのページの式) からわかるように、要素が数百個しかない場合、衝突する確率は 50% を超えます。

もちろん、攻撃者が文字列を提供する可能性に直面している場合は、おそらく 100% であると想定できます。16 ビットの検索空間で衝突を見つけるためのスキャンは、最新の PC でほぼ瞬時に実行できます。または、最新の携帯電話でさえもです。

score 0 · Accepted Answer

最初の 4 文字には 4*4 = 16 ビットのデータが含まれるため、衝突は 65536 要素で確実に発生し、誕生日攻撃により、はるかに高速に検出されます。より多くのハッシュを使用する必要があります。

3 に答える 3