In primo luogo, hai interpretato erroneamente la pagina: non si tratta di collisioni . La pagina di Wikipedia dice:
the cost of finding a set of CGA Parameters that yield the desired 59 bits is approximately O(259)
La parola importante qui è "desiderata". L'utente malintenzionato vuole trovare un input che esegua un hash specifico per un determinato output. Questo è chiamato un attacco preimage . Al contrario, un attacco di collisione consiste nel trovare due input distinti che eseguono lo hash sullo stesso valore, senza alcun vincolo su quel valore di output comune; non è affatto la stessa cosa (e le collisioni sono in effetti molto più facili, fino a circa 2 30 valutazioni per un output a 59 bit).
Detto questo, il costo medio di attacco è in effetti 2 59 , non 2 58 , perché questa è una funzione hash, non a codice a blocchi. Parli di "cercare metà dello spazio dei nomi", ma in questo caso non esiste un "namespace".
Quando provi a forzare brute una chiave a 59 bit, c'è uno spazio definito di possibili chiavi (tutte le sequenze a 59 bit) di dimensione 2 59 , e sai che una di esse è la soluzione, e puoi provarli tutti in ordine, senza mai provare due volte lo stesso . In queste condizioni, puoi aspettarti di trovare quella giusta dopo aver, in media, provato metà delle possibili chiavi.
Non è così qui. Nel caso di CGA, il problema è trovare un input (che è molto più grande di 59 bit) in modo tale che l' output sia una sequenza specifica di 59 bit di destinazione. Mentre provi vari input possibili, ottieni le uscite corrispondenti, ma (questo è il punto critico) queste uscite sono (dal tuo punto di vista) casuali (come in " random oracle "), e, in particolare, puoi ottenere lo stesso più volte. In effetti, è previsto che otterrai il tuo primo duplicato dopo aver provato circa 2 30 input o così (questo è il cosiddetto compleanno paradosso ), e, mentre accumuli tali output casuali, otterrai sempre più collisioni. Se provi 2 59 input distinti e li cancelli tutti, allora non otterrai tutti i possibili output 59 , ma sostanzialmente meno (circa il 63% di essi).
In altre parole, quando esegui l'attacco di forza bruta sulla funzione di hash, alcuni dei tuoi sforzi sono sprecati, perché producono output a 59 bit che avevi già con un altro input possibile. Questo riduce il tasso di successo, e quindi aumenta il costo di attacco complessivo.
Supponendo che la funzione di hash si comporti come un oracolo casuale (cioè senza debolezza strutturale nota), allora la probabilità di trovare l'output a 59 bit corretto ogni volta che provi qualche nuovo input è esattamente 2 -59 e, per definizione, questo significa che devi provare in media 2 59 volte prima di trovare una corrispondenza. Questa è una media : potresti essere fortunato e trovare una corrispondenza prima; potresti anche essere sfortunato e trovare una partita più tardi, senza limiti superiori. Questo (di nuovo) contrasta con la situazione "cerca la chiave per un codice a blocchi", dove sai che l'attacco funzionerà dopo aver provato, al massimo, tutte le possibili chiavi; nell'attacco preimage per una funzione hash, non si ottiene nemmeno una tale garanzia, solo una media.