Tasso di collisione per diversi algoritmi di hash

19

Esiste una misura della velocità di collisione per i più comuni algoritmi di hashing (md5, crc32, sha - *)?

Se questo dipende solo dalle dimensioni dell'output, è piuttosto semplice da misurare, ma suppongo che dipenda anche dalla distribuzione e dagli interni dell'algoritmo (e richiede una qualche prova formale, credo).

    
posta ts01 18.04.2011 - 11:26
fonte

1 risposta

23

Se provo a creare collisioni per MD5, posso crearne uno ogni 14 secondi (in media) sul mio PC, usando un single core (Core2, 2.4 GHz). Questo sfrutta le debolezze della struttura interna di MD5. Se provo solo dati casuali e attendo l'arrivo di collisioni, beh, aspetterò per un po 'di tempo: la prima collisione è prevista dopo circa 2 64 messaggi hash (datemi un migliaio di PC, e io dovrebbe raggiungere una collisione in circa 20 anni di computazione a tempo pieno).

Per le funzioni hash crittografiche attualmente ininterrotte, non vi è alcuna debolezza interna nota (questo è ciò che significa "ininterrotto"), quindi provare i messaggi casuali è il metodo più noto per creare collisioni. Le probabilità di ottenere una collisione in questo modo sono estremamente piccole fino a quando non si hanno almeno 2 messaggi n / 2 , per una funzione hash con un output n bit. Ciò significa che con qualsiasi funzione di hash corretta con un'uscita di 256 bit o più, il tasso di collisione è, in condizioni pratiche, zero (non ne otterrai nessuno e questa è la fine della storia).

Wikipedia ha alcuni suggerimenti sull'argomento. Vedi anche il capitolo 9 del Manuale di crittografia applicata (pagina 369).

    
risposta data 18.04.2011 - 14:19
fonte

Leggi altre domande sui tag