Perché il tempo di ricerca della forza bruta per gli algoritmi di hashing 2 ^ (num_bits / 2)?

Question

Perché il tempo di ricerca della forza bruta per gli algoritmi di hashing 2 ^ (num_bits / 2)?

#1 da (2 voti)
#2 da (0 voti)

1

Ho notato che i tempi di forza bruta (il tempo necessario per trovare un messaggio che hash per un determinato hash) di vari algoritmi di hashing sembra essere 2^(num_bits / 2) . Ad esempio, le persone dicono che il forzante brutale SHA1 (senza usare la vulnerabilità che riduce il tempo di forza bruta a 2^69 ) è 2^80 . Infatti, se guardi questa tabella , la colonna "Sicurezza (bit)" sembra essere sempre metà del numero di bit, e credo che si riferisca al tempo di ricerca. Come stanno ottenendo questi numeri? Penserei che per forzare un hash a 160 bit, si dovrebbero almeno provare 2^160 messaggi, o forse 2^159 valori in media per trovare un messaggio. Non penso che l'attacco di compleanno sia rilevante qui, dato che sembra essere una collisione, al contrario di una collisione specifica.

brute-force hash sha

posta gsingh2011 09.09.2014 - 21:38

fonte

2 risposte

Leggi altre domande sui tag brute-force hash sha

Che cos'è il contenuto di x-frame? OpenSSL che aggiorna suite di crittografie

score 2 · Answer 1

Quando una funzione di hash ha un output di dimensioni n bit, quindi:

L'algoritmo generico per la ricerca di una preimage (o una seconda preimage) ha un costo medio di 2 ⁿ valutazioni della funzione di hash.
L'algoritmo generico per trovare una collisione ha un costo medio di circa 2 ^{n / 2} valutazioni della funzione di hash.

Per "generico" intendiamo "l'algoritmo che funziona contro ogni funzione di hash, per quanto perfetta possa essere quella funzione". Nel caso di pre-immagini e seconde pre-immagini, l'algoritmo generico è anche noto come "fortuna" (proviamo a inserire messaggi fino a quando non siamo fortunati). Per le collisioni, esistono vari algoritmi intelligenti che sono tutti aspetti del cosiddetto compleanno paradosso . Ho scritto "about" perché questi algoritmi intelligenti comportano anche alcuni costi di RAM o alcune limitazioni al parallelismo, quindi il costo effettivo di trovare una collisione non può essere espresso in un singolo numero; oppure, se preferisci, il costo matematico non si traduce esattamente in un numero proporzionato di dollari, se vuoi davvero fare il calcolo.

Diversi protocolli utilizzano le funzioni hash per vari motivi. È difficile accertare se un determinato protocollo è immune alle collisioni o meno. In alcuni casi, un attacco effettivo può richiedere un calcolo pre-immaginario; o forse è sufficiente una collisione; o la situazione potrebbe essere più complessa. Quindi, giusto per essere sicuri, di solito assumiamo il peggio e quindi osserviamo la resistenza più bassa. Pertanto, valutiamo una funzione di hash con un output a 160 bit per essere di forza "80 bit" (o 2 ⁸⁰). Sappiamo che possiamo essere eccessivamente prudenti qui; essere non possiamo essere sicuri.

score 0 · Answer 2

Non vedo nulla che indichi che "Sicurezza (bit)" stia cercando un attacco preimage contro una collisione, quindi penso che la tua ipotesi che il paradosso del compleanno sia irrilevante probabilmente non è accurato. Le collisioni rappresentano ancora un problema di sicurezza significativo, in realtà sono state utilizzate per falsificare i certificati SSL . Un attacco preimage (trovando un altro input che corrisponde ad un particolare valore) richiede comunque 2 ^ n operazioni (modulo debole nell'algoritmo hash).