Qual è la "complessità computazionale" di un attacco?

13

Sto scrivendo un rapporto in lingua commerciale su MD5. Nella mia ricerca ho trovato un articolo di Yu Sasaki e Kazumaro Aoki che spiega il loro 2 123.4 attacco pre-immagine su MD5.

So che ha qualcosa a che fare con la fattibilità (o in alcuni casi, anche con la possibilità) di un attacco, ma non ho una solida comprensione di quale sia esattamente la complessità computazionale.

Quindi, qual è la complessità computazionale in questo contesto? E a quale limite possiamo dire che questo attacco non fattibile o questo attacco è non possibile ?

    
posta Adi 18.04.2013 - 10:58
fonte

1 risposta

13

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.

    
risposta data 18.04.2013 - 13:29
fonte

Leggi altre domande sui tag