Crea le tue collisioni MD5

Question

Sto facendo una presentazione sulle collisioni MD5 e vorrei dare alle persone alcuna idea di quanto sia probabile una collisione.

Sarebbe bello avere due blocchi di testo che hanno hash sulla stessa cosa e spiegare quante combinazioni di [a-zA-Z] erano necessarie prima di colpire una collisione.

La risposta ovvia è l'hash di tutte le combinazioni possibili fino a quando non si toccano due hash uguali. Quindi, come faresti a codificarlo. Come esperimento veloce ho provato a tagliare tutte le combinazioni di 5 colonne di [A-Z], memorizzandole in un hash net e catturando l'eccezione di collisione. Due problemi con questo - alla fine l'hashtable scade, e sono abbastanza sicuro che avrò bisogno di MOLTI caratteri in più.

Ovviamente questa struttura dati è troppo grande per essere gestita in memoria, quindi ora dovrò coinvolgere un database. Sembra anche un buon progetto per testare l'azzurro - un po 'come these guys.

Qualcuno può indicarmi un modo efficace per fare questo ?

Answer 1

Queste seguenti due differenti sequenze 128 byte hash alla stessa:

MD5 Hash: 79054025255fb1a26e4bc422aef54eb4

Le differenze di seguito sono evidenziati (grassetto). Mi dispiace, è un po 'difficile da vedere.

 
d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89 
55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b 
d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70 

e

 
d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89 
55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b 
d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70 

La visualizzazione della collisione/blocco1 (Fonte: Links.Org)

La visualizzazione della collisione/blocco2 (Fonte: Links.Org)

Answer 2

Vorrei dare un'occhiata a Hashcash. Con un algoritmo hash efficace, come md5, il tempo di calcolare una collisione in modo esponenziale con il numero di bit. Che cosa fa Hashcash calcola le collisioni parziali. Cioè, una corrispondenza dice i 16 bit più bassi dell'hash. Per ottenere la corrispondenza dei 16 bit più bassi, si dovrebbe provare in media l'hashing di 2^15 combinazioni diverse. Se si conosce il tempo necessario per ottenere una collisione a 16, 24 o 32 bit, è possibile calcolare facilmente il tempo per un numero maggiore di bit.

Answer 3

Se stai parlando di quanto sia probabile che si verifichi una collisione semplice, una in cui non esiste un tentativo intenzionale di causarne uno, allora rimarrai deluso: prima dovresti generare in media 2^64 testi in chiaro ci si può aspettare di vedere una collisione, e questo è sostanzialmente più di quanto si sarà in grado di fare in un tempo ragionevole (o addirittura, persino un _risultato).

Se stai cercando di dimostrare la difficoltà di creare deliberatamente una collisione, altre risposte lo hanno già dimostrato. Il vincolo in più di richiedere che le stringhe siano interamente testuali rende però anche questi approcci largamente poco pratici.

Answer 4

L'intero punto di tali hash è che le collisioni sono estremamente improbabili.Non ne genererai uno per caso: la tua macchina quasi sicuramente morirà di vecchiaia prima di riuscire. L'intero punto dell'utilizzo di un hash andrebbe via se si potesse ragionevolmente generare collisioni!

Answer 5

E 'difficile farlo con i file di testo solo, per quanto ne so. È possibile ottenere alcune collisioni, ma averle anche dal [a-zA-Z] non è facile (ancora).

D'altra parte, se si desidera solo due file "significativi" con lo stesso hash, è possibile farlo con qualcosa come, ad esempio, PostScript: avere blob binari diversi che causano la collisione e utilizzare un'espressione condizionale per visualizzare output diversi di conseguenza.

Vedere ad es. this problem (la parte H2) e solution. Ad esempio, this PS file e this one hanno lo stesso MD5sum ma sono entrambi file PostScript ben formati che contengono testo completamente diverso quando vengono aperti.