La mia comprensione di SHA1 è corretta?

Hai ragione che SHA1 è deterministico - cioè se assegni lo stesso input allo stesso algoritmo, produrrà lo stesso output indipendentemente dal computer su cui si esegue, dove nel mondo sei, in che anno è, il colore o la tua pelle o il contenuto del tuo personaggio.

C'è un numero infinito di input (qualsiasi stringa), ma solo un numero finito di output (stringa da 160 bit). Dato che le uscite sono finite (solo finite - non esiste qualcosa come "molto finito"), hai ragione che in teoria sarebbe possibile generare un "dizionario" con un input corrispondente per ogni uscita.

Hai anche ragione nell'intuire che ciò potrebbe essere praticamente impossibile anche se è teoricamente possibile, dato che il dizionario dovrebbe avere 2 ^ 160 voci diverse. Ecco due dei problemi:

• Per creare un dizionario del genere, è necessario generare circa 10 ^ 48 hash. L'universo ha circa 10 ^ 17 secondi. Quindi, se hai iniziato dal big bang e hai generato 10 ^ 31 hash al secondo, ora lo faresti.
• Per memorizzare un dizionario di questo tipo, occorrono circa 10 ^ 50 bit di memoria (10 ^ 2 per voce). Questo è grosso modo il numero di atomi sulla terra.

Ovviamente potresti creare un dizionario per un sottotesto, ad esempio le password più comuni, ma realizzarne uno per lo spazio di output completo non è realistico, nemmeno nella fantascienza. E se lo facessi, mapperebbe l'output su uno dei tanti possibili input.

Prima di tutto, sì, SHA1 (così come ogni altro algoritmo di hash) è deterministico ; in altre parole, dato lo stesso input, produrrà sempre lo stesso risultato. (Quell'output può essere formattato in modo diverso, come pura rappresentazione binaria, esadecimale o Base64, ma la formattazione dell'output è irrilevante rispetto al valore dell'output.)

Ciò che descrivi è ciò che è noto come attacco preimage .

Ci sono due varianti di attacchi di pre-immagine:

• In un attacco preimage , un utente malintenzionato ha un hash H (x) e desidera dedurre l'input hash x. In altre parole, dato y e H (x) = y, trova x.
• In un secondo attacco preimage , un utente malintenzionato ha un input x e desidera trovare un input diverso x ', tale che H (x) = H (x' ).

Si noti che x (e x ') possono avere dimensioni arbitrarie, ma l'output della funzione di hash è di dimensioni fisse. Alcune funzioni di hash sono definite per diverse dimensioni di output, ma nello spazio di un singolo hash, la dimensione di output è ancora fissa (e quindi la funzione di hash può essere considerata come se avesse un'uscita di dimensione fissa).

Una funzione di hash (come SHA1) funziona, in linea di principio, iterando sull'input e usando quell'input per modificare lo stato interno, quindi esponendo il pieno o parte dello stato interno (eventualmente dopo un'ulteriore elaborazione finale) come il valore hash. Questo è ciò che è noto come costruzione Merkle-Damgård .

Ci sono due conseguenze di questo:

• Sì, date risorse di calcolo sufficienti, è possibile trovare un input che hash su un determinato output
• No, date infinite risorse di calcolo, non è possibile determinare esattamente quale input è stato usato per ottenere un dato output (sebbene, come conseguenza del punto precedente, è possibile ottenere candidati )

L'ultimo punto potrebbe non essere ovvio, ma deriva dal fatto che se H (x) = y, e x è più lungo di y, può esistere un numero arbitrario di valori per x che danno lo stesso valore per y . Per una funzione di hash ideale, il numero previsto di tali collisioni per una grandezza di input arbitrario X e una dimensione di uscita arbitraria Y (entrambe in bit) sarà 2 ^ (X-Y); quindi, con hashing 192 bit in un hash a 160 bit, se si avesse la possibilità di enumerare l'intero spazio di input a 192 bit, ci si aspetterebbe di trovare su 2 ^ 32 (che è 2 ^ (192-160)) altri valori dando lo stesso valore di hash.

Il caso estremo è un algoritmo hash definito come H (x) = 0. In questo caso è banale determinare che l'hash di un dato valore è 0, ma viene data solo la definizione della funzione hash e il suo valore di uscita 0, non è possibile determinare quale valore ha prodotto 0 come output.

Come già discusso di Anders , i moderni algoritmi di hash hanno spazi di output sufficientemente ampi che generano un dizionario di tutti i possibili le uscite hash non sono fattibili. Inoltre, anche se fosse possibile generare e archiviare un tale dizionario, otterrebbe solo un input candidato . A seconda dello scopo dell'attacco, questo può o potrebbe non essere sufficiente.

Supponiamo che la funzione di hash sia definita come H (x) = (x mod 2) per uno spazio di input intero, ottenendo così 0 se x è pari e 1 se x è dispari. In questo caso, posso dirti che H (65535) = 1, ma dato il valore hash H (x) = 1, tutto quello che puoi dire sull'input x è che è strano, e che uno di questi candidati sarebbe (per esempio) H (3) = 1.