Strumenti per sviluppatori · SHA calcolatore hash
L'effetto valanga: perché un personaggio cambiato riscrive un hash SHA
· Come funziona
sha-256 crittografia sicurezza convalida
Cambia una lettera e circa la metà dei bit di output si invertono. Questo post spiega la proprietà della valanga, perché è essenziale per il rilevamento delle manomissioni e come i colpi di SHA-2 la ottengono.
Aspettarsi che l'hash cambi leggermente: l'intuizione portata dalla maggior parte delle persone e il motivo per cui il design la rompe deliberatamente
La maggior parte delle persone si aspetta che input simili producano output simili. Cambia un carattere in un file e il digest dovrebbe cambiare leggermente. Invece, gli hash crittografici sono progettati per fare il contrario: una modifica di un singolo bit nell’input dovrebbe invertire circa la metà dei bit di output, in modo imprevedibile. Questa proprietà è chiamata effetto valanga ed è intenzionale. Il design ha uno scopo specifico: il rilevamento delle manomissioni.
L'effetto valanga è il motivo per cui "quasi corrispondente" non è un concetto nel mondo dell'hashing. Un hash corrisponde esattamente oppure no. Non esiste un "abbastanza vicino". Questa proprietà rende l'hashing utile per i controlli di integrità e l'indirizzamento del contenuto e rende gli algoritmi di hashing deboli inutilizzabili per scopi di sicurezza.
Avalanche significa ampia diffusione della produzione; questo articolo non fa alcuna affermazione di probabilità esatta senza fonti
Formalmente, l'effetto valanga significa che per due input che differiscono di un singolo bit, i digest di output dovrebbero differire di circa il 50% dei loro bit. Per SHA-256 (256 bits di output), la modifica di un bit di input dovrebbe invertire all'incirca 128 bit di output. L'effetto non è esatto; è una proprietà statistica. Ma è forte: in pratica, ogni parte dell’input è completamente mescolata con ogni parte dell’output.
Perché circa la metà? Perché un output veramente casuale differirebbe da un altro output casuale in media esattamente per la metà dei suoi bit (secondo il principio della casella e le statistiche di base). Una buona funzione hash si avvicina alla casualità; produce un output che sembra non avere uno schema distinguibile. La metà dei bit che si ribaltano in media è il segno distintivo della casualità. Se un hash invertisse solo il 10% dei bit, un utente malintenzionato potrebbe trovare schemi e sfruttarli.
Perché è necessario il rilevamento delle manomissioni: piccole modifiche a un documento non devono produrre un hash quasi identico che una rapida occhiata accetterebbe
Il rilevamento delle manomissioni si basa sulla valanga. Se scarichi un file e calcoli il suo SHA-256, il digest previsto è ba7816... (come esempio). Un utente malintenzionato modifica il file modificando un byte. Il nuovo digest cambia da ba7816... a qualcosa come 3d4e92... (completamente diverso). Quando si verifica il file rispetto al digest previsto, la mancata corrispondenza è immediata e totale. Non c'è spazio per interpretazioni errate: il file è stato manomesso.
Senza valanga, un utente malintenzionato potrebbe modificare un byte e il digest potrebbe spostarsi solo leggermente, in ba7817... (una cifra esadecimale diversa). Un confronto casuale potrebbe non cogliere la differenza. Un utente malintenzionato potrebbe persino cercare input che producono un digest che inizia con ba78, sostenendo che il file è autentico. Avalanche rende tutto ciò proibitivamente costoso: trovare anche due input in cui i digest iniziano con le stesse quattro cifre esadecimali richiede più lavoro di quanto consentito dal progetto.
Come i round diffondono il cambiamento: rotazioni, addizioni e funzioni non lineari che trasportano l'influenza di un bit nell'intero stato
I round in SHA-256 (e i round in SHA-512) sono progettati per diffondere le modifiche. Ogni round mescola i dati utilizzando funzioni non lineari (scegli, maggioranza) e rotazioni. Una modifica di un singolo bit nell'input entra nella pianificazione del messaggio e si propaga attraverso i round. Le rotazioni spostano le posizioni dei bit. Le funzioni non lineari nascondono l'influenza del bit: la modifica di un bit di controllo in un'operazione di scelta può invertire qualsiasi bit di output, a seconda dei dati selezionati.
Le costanti hash iniziali, le costanti della pianificazione dei messaggi, gli importi di rotazione e il numero di round sono stati tutti scelti per massimizzare l'effetto valanga. Questi numeri non sono arbitrari; provengono dalla specifica SHA-2 e sono stati ampiamente crittografati. Qualsiasi modifica alle costanti o al conteggio dei round produrrebbe un algoritmo diverso (probabilmente più debole).
Esempio pratico: eseguire l'hashing di due input che differiscono di un carattere e confrontare i digest bit per bit
Testare una valanga è semplice. Hashing l'input abc e annota il digest. Poi cancella abc seguito da uno spazio, oppure sostituisci un carattere con qualcos'altro: abd. Confronta gli output esadecimali. Per SHA-256, circa la metà delle cifre esadecimali 64 saranno diverse. Contali. Il vettore di test dal post ToolAcre: abc produce ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad. Una stringa vuota produce e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855. Questi digest non hanno cifre esadecimali in comune.
Provalo sulla calcolatrice ToolAcre con qualsiasi input. Hash una frase. Quindi cambia una lettera e cancella di nuovo. Contare le diverse cifre esadecimali. Scoprirai che circa la metà (32 su 64, nella maggior parte dei casi) differisce. Questo è l'effetto valanga in azione. È una proprietà della progettazione dell'algoritmo, non una coincidenza.
Avalanche non fornisce la ricerca di similarità né quantifica da solo la resistenza alle collisioni
Avalanche non crea ricerche di somiglianza o corrispondenze approssimative. Se hai un digest ba7816... e vuoi trovare un digest simile, non hai scorciatoie. È necessario indovinare o forzare gli input dei candidati, eseguire l'hashing di ciascuno e verificare la corrispondenza esatta. L’effetto valanga rende ogni ipotesi con la stessa probabilità di produrre un risultato simile o completamente diverso. Alcuni algoritmi di hashing (chiamati hashing sensibili alla località) sono progettati per preservare la somiglianza; sono utili per il rilevamento e il clustering di quasi duplicati, ma non sono hash crittografici.
Avalanche non protegge nemmeno da una determinata ricerca di collisioni. Un crittoanalista può ancora cercare due input diversi che producono lo stesso digest, ma lo spazio di ricerca è enorme. Una ricerca determinata di collisione è una questione diversa dalla diffusione visiva. Questo articolo non cita una cifra legata al compleanno o una sequenza temporale dell'hardware perché non ne ha ricavata una qui. Il confine difendibile è che la valanga da sola non dimostra né quantifica la resistenza alla collisione.
Conclusione: nessun incidente mancato: prova l'esperimento con un carattere nel calcolatore di hash ToolAcre SHA e osserva l'intero cambiamento del digest
Il calcolatore dell'hash ToolAcre SHA esegue gli algoritmi SHA attraverso l'implementazione Web Crypto del browser. Puoi usarlo per verificare la valanga da solo. Ogni minimo dettaglio dell'algoritmo viene inserito nell'output e l'implementazione di Web Crypto viene controllata e mantenuta dal fornitore del browser. Stai vedendo il vero algoritmo eseguito su input reali. La proprietà controintuitiva secondo cui un cambiamento di carattere riscrive l'intero digest non è un difetto; è la funzionalità che fa funzionare l'hashing.
Quando usi un hash per il controllo dell'integrità, fai affidamento su una valanga. Quando lo usi per l'indirizzamento del contenuto (come i digest di immagini del contenitore), dipendi dalla proprietà secondo cui piccole modifiche producono digest molto diversi. Quando lo si utilizza in una firma digitale (dove la firma viene calcolata su un hash del messaggio), l'effetto valanga garantisce che la manomissione del messaggio produca un cambiamento rilevabile. La proprietà è il fondamento della sicurezza basata su hash.