La "complessità computazionale" è una misura dello sforzo CPU / RAM coinvolto nell'esecuzione di un algoritmo. Nel caso di un attacco su un algoritmo crittografico (ad esempio MD5), la complessità viene misurata relativamente all'algoritmo attaccato. MD5 elabora i dati per blocchi da 512 bit, quindi ha un "costo elementare" che è la quantità di CPU che impiega per hash un piccolo messaggio (da 0 a 447 bit, per essere precisi). Poiché MD5 offre un output a 128 bit, quindi, per un attacco preimage (trovando m tale che MD5 ( m ) = x , dove < em> x è dato), l'attacco generico "get lucky" ha un costo medio 2 128 volte il costo di hashing di un piccolo messaggio. In effetti, l'attacco "get lucky" riguarda la scelta di m casuali finché non viene trovata una corrispondenza, che, per una funzione di hash "perfetta" (a oracle casuale ) funziona con probabilità 2 -128 per ogni tentativo.
Pertanto, esprimiamo lo "sforzo della CPU" come il numero di volte in cui la funzione attaccata potrebbe essere valutata con quel numero di cicli di clock investiti. Questa unità di misura ha la bella proprietà di mostrare facilmente se una funzione è "accademicamente rotta" o meno. L'attacco "get lucky" è generico: funziona per ogni funzione di hash, indipendentemente dalla sua perfezione. Il costo medio di quell'attacco è 2 n per una funzione di hash con un output n -bit. Quindi ogni attacco che fa meglio, anche leggermente, conta come una "pausa". Nel caso di MD5, l'attacco presentato è costato 2 123.4 , il che significa che è circa 20 volte più veloce dell'attacco "get lucky". Ma è ancora completamente irrealizzabile nella pratica. Il limite realistico per un potente attaccante (ad esempio, qualcuno con il budget di Google) è di circa 2 invocazioni 80 di MD5.