Strumenti per sviluppatori · SHA calcolatore hash
Merkle–Damgård spiegato: la costruzione dietro SHA-1 e SHA-2
· Sfondo
sha-256 crittografia API del browser
Una funzione di compressione a dimensione fissa non può eseguire da sola l'hashing di un input arbitrario. Merkle–Damgård lo incatena blocco per blocco; questo post spiega la costruzione, la sua idea di prova e i punti deboli che comporta.
Input arbitrario, output fisso: il problema che ogni funzione hash deve risolvere per primo
Una funzione hash deve mappare un input arbitrario su un output fisso. Un messaggio di tre byte e un messaggio di tre megabyte devono entrambi produrre esattamente 256 bits di output per SHA-256. L'hash deve essere deterministico, quindi lo stesso input produce sempre lo stesso output. L'output deve apparire casuale; la modifica di un singolo bit di input dovrebbe modificare circa la metà dei bit di output.
A prima vista questi sono requisiti contraddittori, perché un singolo algoritmo veloce non può gestire messaggi di lunghezza arbitraria e produrre un output uniforme a larghezza fissa. La costruzione Merkle-Damgård risolve questo problema utilizzando ripetutamente una funzione di compressione di dimensione fissa, inserendo l'output di ciascuna applicazione nell'input di quella successiva. Questa costruzione è utilizzata da SHA-1 e tutti SHA-2 (SHA-256, SHA-384 e SHA-512).
La funzione di compressione: un mixer di dimensione fissa che accetta uno stato e un blocco e restituisce un nuovo stato
Una funzione di compressione è la primitiva crittografica principale che alimenta un hash Merkle-Damgård. Richiede uno stato di dimensione fissa, in genere 256 bits per SHA-256 o 512 bits per SHA-512, e un blocco di input di dimensione fissa, in genere 512 bits per SHA-256 o 1024 bits per SHA-512. La funzione di compressione li mescola insieme utilizzando operazioni bit per bit, rotazioni e ricerche nelle tabelle, producendo un nuovo stato della stessa dimensione. Questa funzione deve essere resistente alle collisioni: trovare due coppie diverse (stato, blocco) che producono lo stesso output deve essere difficile.
La stessa funzione di compressione non è una funzione hash completa: non gestisce la lunghezza arbitraria dell'input e non gestisce nemmeno il primo input, che non ha uno stato precedente. Si tratta invece dell’elemento portante attorno al quale viene costruita una costruzione più ampia. La funzione di compressione è l'unica operazione crittografica che viene eseguita ripetutamente; tutto il resto è contabilità che collega questa funzione a un hash completo.
Concatenamento e vettore di inizializzazione: come i blocchi si alimentano a vicenda da uno stato iniziale fisso
Il vettore di inizializzazione è lo stato iniziale fisso, scelto con attenzione per evitare simmetrie o debolezze. Per SHA-256, l'IV è costituito da otto parole 32 bit derivate dalle parti frazionarie delle radici quadrate dei primi otto numeri primi. Questi valori sono arbitrari ma deterministici, quindi ogni implementazione produce lo stesso risultato. Il primo blocco di messaggi viene mescolato con l'IV utilizzando la funzione di compressione, producendo un nuovo stato. Il secondo blocco di messaggio viene mescolato con quello stato, producendo un altro nuovo stato e così via per ogni blocco del messaggio.
Questo concatenamento è la parte cruciale: l'output di un blocco dipende da tutti i blocchi precedenti, quindi la modifica di qualsiasi bit di qualsiasi blocco precedente modifica tutti i blocchi successivi. Nel momento in cui viene elaborato il blocco finale, lo stato contiene informazioni su ogni bit dell'input. L'imbottitura è il trucco che fa suonare questa costruzione. Un messaggio non è sempre suddiviso equamente in blocchi. La costruzione Merkle-Damgård utilizza il rafforzamento MD: aggiungi un singolo bit al messaggio, quindi aggiungi zeri fino a quando rimane quasi un blocco completo, quindi aggiungi la lunghezza del messaggio originale.
Imbottire con la lunghezza del messaggio: perché il rafforzamento MD è ciò che fa suonare la costruzione
L’argomentazione di sicurezza a favore di Merkle–Damgård afferma che se la funzione di compressione è resistente alle collisioni, allora l’intero hash è resistente alle collisioni. La prova è una riduzione: se potessi trovare una collisione nell'hash, potresti estrarre una collisione nella funzione di compressione, il che contraddice l'ipotesi che la funzione di compressione sia difficile da scontrarsi. L'intuizione è che qualsiasi collisione nell'hash deve eventualmente produrre una collisione in una delle chiamate alla funzione di compressione, poiché lo stato viene riportato completamente.
I punti deboli di Merkle–Damgård sono stati scoperti nel tempo, anche se la costruzione di base è solida. L'estensione della lunghezza è una: un utente malintenzionato che vede il digest di un messaggio può estendere il messaggio e calcolare un digest valido per il messaggio più lungo senza sapere nulla dell'input. I secondi attacchi preimmagine sono un altro: dato un messaggio, trovare un messaggio diverso con lo stesso hash è più semplice di quanto dovrebbe essere per alcuni tipi di messaggi. Questi punti deboli hanno motivato la progettazione di SHA-3, che utilizza un approccio diverso chiamato costruzione a spugna.
Il riempimento della codifica della lunghezza separa i messaggi riempiti; una prova di sicurezza completa è una prova esterna al repository
La funzione di compressione per SHA-256 accetta uno stato di 256 bit (otto parole di 32 bit) e un blocco di 512 bit. L'operazione utilizza cicli 64, ciascuno dei quali mescola lo stato con una costante e una parola dal blocco. Il mixaggio utilizza operazioni bit a bit: XOR, AND, NOT. Utilizza rotazioni e spostamenti che spostano i bit senza modificare i bit impostati. Utilizza ricerche di tabelle che forniscono una miscelazione non lineare che XOR da solo non può ottenere.
SHA-512 utilizza la stessa costruzione di SHA-256 ma con operazioni a 64 bit anziché a 32 bit. Lo stato è 512 bits (otto parole da 64 bit) e la dimensione del blocco è 1024 bits. La funzione di compressione prevede cicli 80 invece di 64 e le costanti e le ricerche nelle tabelle sono diverse. Per SHA-384, lo stato e la funzione di compressione sono gli stessi di SHA-512, ma viene emesso solo il primo 384 bits dello stato finale. Gli ultimi 128 bits vengono scartati. Questo troncamento è il motivo per cui SHA-384 è resistente all'estensione della lunghezza.
L'estensione in lunghezza è il confine di costruzione verificato; le affermazioni di motivazione multicollisione e SHA-3 vengono omesse
La sicurezza di un hash Merkle-Damgård dipende dal possesso di diverse proprietà. La funzione di compressione deve essere resistente alle collisioni, quindi attaccarla direttamente è impossibile. Lo schema di riempimento deve garantire che messaggi diversi producano forme imbottite diverse, quindi ogni collisione nell'hash deve comportare una collisione della funzione di compressione. La dimensione del blocco e la dimensione dello stato devono essere sufficientemente grandi da rendere impossibile la forza bruta. Uno stato più ampio amplia lo spazio di ricerca generico, ma questo articolo non allega un conteggio delle operazioni o una data di fattibilità senza una derivazione in linea e una fonte rivista.
Se un utente malintenzionato rileva un punto debole nella funzione di compressione o se i computer quantistici diventano pratici e possono eseguire ricerche in uno spazio non strutturato in tempo sqrt(2^n) anziché in tempo 2^n, i margini di sicurezza si erodono. La debolezza che ha motivato SHA-3 non è stata un'interruzione nella funzione di compressione, ma il problema dell'estensione della lunghezza e altre vulnerabilità strutturali. Una costruzione spugna li evita non pubblicando mai il suo stato interno completo.
Ciò che questo non copre: le funzioni rotonde specifiche di SHA-256, trattate in un post separato
Il modo in cui la costruzione Merkle–Damgård gestisce ogni dimensione di input è la conseguenza pratica del suo design. Suddividi il messaggio in blocchi 512 bit, riempi l'ultimo blocco, elabora ogni blocco attraverso la funzione di compressione in sequenza e genera lo stato finale. Per un input da un byte, il riempimento produce un blocco 512 bit (un byte di messaggio, un bit di riempimento, 447 bits di zeri e 64 bits per la lunghezza). Il numero di compressioni corrisponde al numero di blocchi 512bit, proporzionale alla lunghezza del messaggio.
Ogni digest prodotto dal calcolatore hash ToolAcre SHA proviene da questa costruzione. Il digest 64-carattere SHA-256 è lo stato finale di 256 bit stampato in esadecimale. Il digest 128 di caratteri SHA-512 è lo stato finale di 512 bit stampato in esadecimale. Il digest 96 di caratteri SHA-384 è il primo 384 bits dello stato finale di 512 bit. Il riempimento dietro le quinte garantisce che ogni possibile messaggio produca esattamente il giusto numero di blocchi e la giusta larghezza digest. Questa è la costruzione Merkle–Damgård standard in esecuzione nel browser.
Conclusione: lo stesso scheletro dietro quattro algoritmi: ogni digest prodotto dal calcolatore di hash ToolAcre SHA proviene da questa costruzione
Comprendere la costruzione è utile per sapere perché i digest hanno sempre la stessa larghezza e perché la modifica di un bit dell'input modifica l'intero digest. La proprietà di concatenamento significa che ogni bit dell'input influenza ogni bit dell'output attraverso una serie di operazioni di mixaggio. Una modifica di un bit all'inizio del messaggio si propagherà attraverso tutte le compressioni successive, quindi il digest finale è completamente diverso. Questa proprietà è chiamata effetto valanga ed è la firma di una funzione hash sonora.
La costruzione Merkle–Damgård è in uso da decenni e costituisce la base delle funzioni hash più diffuse. SHA-1 e SHA-2 si basano su questa struttura e molti sistemi distribuiti fanno affidamento sui loro risultati. La costruzione è consolidata e non sperimentale, ma quella storia non rende sicuro ogni utilizzo; l'estensione della lunghezza è un limite documentato. Comprendere questa costruzione aiuta gli sviluppatori a capire perché valgono determinate proprietà di sicurezza e perché esistono determinati vettori di attacco.