substr md5 Kollision

Question

Ich brauche einen 4-stelligen Hash. Im Moment nehme ich die ersten 4 Zeichen eines md5() Hashes. Ich hasse eine Zeichenkette, die maximal 80 Zeichen lang ist. Wird dies zu einer Kollision führen? oder, was ist die Wahrscheinlichkeit einer Kollision, vorausgesetzt, ich werde weniger als 65.536 (16) verschiedene Elemente hashen?

Answer 1

4 erste Zeichen enthält 4 * 4 = 16 Datenbits, also wird die Kollision definitiv bei 65536 Elementen sein, und aufgrund des Geburtstagsangriffs wird es viel schneller gefunden werden. Sie sollten mehr Hash-Bits verwenden.

Answer 2

Surprisingly high indeed. Wie Sie von this graph of an approximate collision probability (Formel aus der wikipedia page) sehen können, ist mit nur ein paar hundert Elementen Ihre Wahrscheinlichkeit einer Kollision über 50%.

Wenn Sie die Möglichkeit eines Angreifers sehen, der die Zeichenfolge bereitstellt, können Sie wahrscheinlich davon ausgehen, dass es 100% ist - das Scannen nach einer Kollision in einem 16-Bit Suchbereich kann fast augenblicklich ausgeführt werden jeder moderne PC. Oder sogar jedes moderne Handy.

Answer 3

Nun, jedes Zeichen von md5 ist ein Hex-Bit. Das bedeutet, dass es einen von 16 möglichen Werten haben kann. Wenn Sie also nur die ersten 4 "Hex-Bits" verwenden, können Sie 16 * 16 * 16 * 16 oder 16^4 oder 65536 oder 2^16 Möglichkeiten haben.

Also, das bedeutet, dass der gesamte verfügbare "Platz" für Ergebnisse nur 16 Bit breit ist. Nun, nach dem Birthday Attack/Problem, gibt es folgende Möglichkeiten zur Kollisions:

• 50% Chance ->300 Einträge
• 1% Chance ->36 Einträge
• 0.0000001% Chance ->2 Einträge.

So gibt es eine ziemlich hohe Chance für Kollisionen.

Jetzt sagen Sie, Sie brauchen einen 4-stelligen Hash. Je nach den genauen Anforderungen, können Sie tun:

• 4 Hex-Bits für 16^4 (65.536) mögliche Werte
• 4 Alpha-Bits für 26^4 (456.976) mögliche Werte
• 4 alphanumerische Bits für 36^4 (1.679.616) mögliche Werte
• 4 ascii druckbare Bits für etwa 93^4 (74.805.201) mögliche Werte (unter der Annahme, ASCII 33 -> 126)
• 4 volles Bytes für 256^4 (4294967296) mögliche Werte.

Nun, was Sie wählen, hängt vom tatsächlichen Anwendungsfall ab. Muss der Hash zu einem Browser übertragen werden? Wie speichern Sie es usw.

Ich werde ein Beispiel für jeden geben (In PHP, sondern sollte einfach zu übersetzen/sehen, was los ist):

4 Hex-Bits:

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

4 Alpha Bits:

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

4 Alpha Numeric Bits:

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

4 Druck Assci Bits:

$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 volle Bytes:

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