Perché le funzioni hash sono unidirezionali? Se conosco l'algoritmo, perché non posso calcolarne l'input?

Question

view on stackexchange narkive permalink

Perché non è possibile eseguire il reverse engineering di un hash della password?

Ho esaminato questo aspetto secoli fa e ho letto molto su di esso, ma non riesco a trovare la spiegazione del motivo essere fatto. Un esempio renderà più facile capire la mia domanda e per mantenere le cose semplici lo baseremo su un algoritmo di hashing che non utilizza un salt ( LanMan).

Dì il mio la password è "Password". LanMan eseguirà l'hashing e lo memorizzerà nel database. I programmi di cracking possono forzarli con l'hashing delle ipotesi di password fornite. Quindi confronta l'hash generato con l'hash nel database. Se c'è una corrispondenza, risolve la password.

Perché, se il cracker di password conosce l'algoritmo per trasformare una password di testo semplice in un hash, non può semplicemente invertire il processo per calcolare la password dall'hash?

Questa domanda era Domanda della settimana sulla sicurezza IT .
Leggi il 24 febbraio 2012 post di blog per maggiori dettagli o invia la tua domanda della settimana.

Answer 1

view on stackexchange narkive permalink

Lascia che inventi un semplice "algoritmo di hashing della password" per mostrarti come funziona. A differenza degli altri esempi in questo thread, questo è effettivamente fattibile, se riesci a convivere con alcune bizzarre restrizioni sulla password. La tua password è composta da due numeri primi grandi, x e y. Ad esempio:

  x = 48112959837082048697y = 54673257461630679457  

Puoi facilmente scrivere un programma per computer per calcolare xy in tempo O ( N ^ 2), dove N è il numero di cifre in x e y. (Fondamentalmente ciò significa che ci vuole quattro volte di più se i numeri sono due volte più lunghi. Ci sono algoritmi più veloci, ma questo è irrilevante.) Memorizza xy nel database delle password.

  x * y = 2630492240413883318777134293253671517529  

Un bambino in quinta elementare, dato abbastanza fogli di carta , potrebbe capire quella risposta. Ma come invertirlo? Ci sono molti algoritmi che le persone hanno escogitato per fattorizzare grandi numeri, ma anche i migliori algoritmi sono lenti rispetto alla velocità con cui puoi moltiplicare x per y E nessuno di questi algoritmi potrebbe essere eseguito da un selezionatore di quinta elementare, a meno che i numeri non fossero molto piccoli (ad esempio, x = 3, y = 5).

Questa è la proprietà chiave: il calcolo è molto più semplice andando avanti che indietro. Per molti problemi, devi inventare un algoritmo completamente nuovo per invertire un calcolo.

Questo non ha nulla a che fare con funzioni iniettive o biiettive. Quando decifri una password, spesso non importa se ottieni la stessa password o se ottieni una password diversa con lo stesso hash. La funzione hash è progettata in modo che sia difficile invertirla e ottenere qualsiasi risposta anche una password diversa con lo stesso hash. In criptovaluta: una funzione hash vulnerabile a un attacco preimage è completamente inutile. (L'algoritmo di hashing della password sopra è iniettivo se hai una regola che x < y. )

Cosa fanno gli esperti di crittografia? A volte, cercano di trovare nuovi algoritmi per invertire una funzione hash (pre-immagine). Fanno esattamente quello che dici: analizza l'algoritmo e prova a invertirlo. Alcuni algoritmi sono stati invertiti in precedenza, altri no.

Esercizio per il lettore: supponiamo che il database delle password contenga la seguente voce:

  3521851118865011044136429217528930691441965435121409905222808922963363310303627 

Qual è la password? (Questo in realtà non è troppo difficile per un computer.)

Nota a piè di pagina: a causa del numero limitato di password che le persone scelgono in pratica, un buon hash della password non è solo difficile per calcolare all'indietro ma richiede anche tempo per calcolare in avanti, per rallentare gli attacchi ai dizionari. Come ulteriore livello di protezione, il sale randomizzato impedisce l'uso di tabelle di attacco precalcolate (come "tabelle arcobaleno").

Nota a piè di pagina 2: come sappiamo che è difficile invertire una funzione hash? Purtroppo no. Semplicemente non conosciamo modi semplici per invertire le funzioni hash. Realizzare una funzione hash che sia dimostrabilmente difficile da invertire è il Santo Graal del design della funzione hash e non è stato ancora raggiunto (forse non accadrà mai).

Answer 2

view on stackexchange narkive permalink

Questa è una buona domanda.

Dobbiamo prima dare una precisione: molte funzioni unidirezionali, in particolare la funzione hash come comunemente usata in crittografia, accettano input da uno spazio che è molto più grande di lo spazio dei valori di output. Ad esempio, SHA-256 è definito per ingressi che sono stringhe fino a 18446744073709551615 bit; ci sono 2 ^{18446744073709551616} -1 possibili ingressi, ma poiché l'uscita è sempre una sequenza di 256 bit, ci sono solo 2 ²⁵⁶ possibili uscite per SHA-256. Necessariamente, alcuni input distinti producono lo stesso output. Pertanto, per un dato output di SHA-256, non è possibile recuperare in modo univoco l'input che è stato utilizzato, ma, forse, potrebbe essere possibile calcolare un input che restituisce il valore di output dato. Preimage resistance riguarda questo: la difficoltà di trovare un input corrispondente per un output (indipendentemente da come tale output è stato ottenuto in primo luogo).

Quindi parliamo di una funzione che tutti possono calcolare su qualsiasi input (utilizzando un programma pubblicamente noto, nessun valore segreto coinvolto - non stiamo parlando di crittografia).

---

Cosa dicono gli accademici

Non è chiaro se le funzioni unidirezionali possano effettivamente esistere. In questo momento, abbiamo molte funzioni che nessuno sa come invertire; ma questo non significa che siano impossibili da invertire, in senso matematico. Nota, tuttavia, che non è dimostrato che le funzioni unidirezionali non possano esistere, quindi la speranza rimane. Alcune persone sospettano che se le funzioni unidirezionali possano esistere o meno potrebbe essere una di queste fastidiose asserzioni matematiche che non possono essere né provate né confutate (il teorema di Gödel dimostra che tali cose devono esistere). Ma non c'è nemmeno una prova di questo.

Pertanto, non c'è nessuna prova che una data funzione hash sia davvero resistente alle preimmagini.

Ci sono alcune funzioni che possono essere collegate a noti problemi difficili. Ad esempio, se n è il prodotto di due grandi numeri primi, la funzione x ⟼ x² mod n è difficile da invertire: essere in grado di calcolare radici quadrate modulo un numero intero non primo n (in generale) equivale a essere in grado di fattorizzare n , e questo problema è noto per essere difficile. Non dimostrato di essere duro, intendiamoci; solo che i matematici hanno cercato di fattorizzare in modo efficiente grandi numeri interi per (almeno) gli ultimi 2500 anni, e sebbene siano stati compiuti alcuni progressi, nessuna di queste persone intelligenti ha trovato un algoritmo davvero killer per questo. Il record mondiale per la fattorizzazione di un "modulo RSA" (un prodotto di due grandi numeri primi scelti a caso di lunghezze simili) è un intero a 768 bit.

Alcune funzioni hash basate su tali sono stati proposti "problemi difficili"; vedi ad esempio MASH-1 e MASH-2 (sul problema RSA) e ECOH (con curve ellittiche). Esistono solo poche di queste funzioni, perché:

• Trasformare un "problema difficile" in una funzione hash sicura non è facile; ci sono molti problemi complicati. Ad esempio, mentre l'estrazione di radici quadrate modulo un n non primo è di solito difficile, ci sono valori per i quali l'estrazione della radice quadrata è facile.

• Le prestazioni di tali funzioni hash tendono ad essere, diciamo, non ottimali. Come essere 100 volte più lento di uno SHA-1 più comunemente usato.

Il modo più "standard" di costruire una funzione hash è riunire i crittografi e farli rosicchiare alcuni progetti proposti; le funzioni che sopravvivono a tentativi crittoanalitici per alcuni anni sono quindi considerate "probabilmente robuste". Il concorso SHA-3 è un tale sforzo; il vincitore dovrebbe essere annunciato entro la fine dell'anno. Dei 51 candidati (quelli che hanno superato la fase amministrativa), 14 sono stati selezionati per il "round 2" e questi 14 sono stati esaminati relativamente da vicino da molti crittografi, e nessuno di loro ha trovato qualcosa che valesse la pena di dire sulle funzioni. L'elenco è stato ridotto a 5 e sarà ulteriormente ridotto a 1 "presto", ma non per motivi di sicurezza (la maggior parte dei dati effettivi riguardava le prestazioni, non la resistenza).

---

Cosa rende difficile invertire MD5

Dato che non sappiamo come provare che una funzione è difficile da invertire, il meglio che possiamo fare è darla una prova su una funzione specifica, in modo da avere una "intuizione" di come la funzione raggiunge la sua apparente resistenza.

Scelgo MD5, che è ben noto. Sì, MD5 è "rotto", ma è per le collisioni, non per le preimmagini. Esiste un noto attacco preimage che è, almeno in teoria, più veloce del modo generico (il "modo generico" è "fortuna", vale a dire provare gli input finché non viene trovata una corrispondenza trovato, per un costo medio di 2¹²⁸ valutazioni poiché MD5 ha un'uscita a 128 bit; l ' attacco Sasaki-Aoki ha un costo 2 ^123.4 , che è più basso, ma ancora troppo alto per essere effettivamente provato, quindi il risultato è ancora teorico). Ma MD5 è relativamente semplice e ha resistito agli attacchi per un bel po 'di tempo, quindi è un esempio interessante.

MD5 consiste in una serie di valutazioni di una "funzione di compressione" su blocchi di dati. Il messaggio di input viene prima riempito, in modo che la sua lunghezza diventi un multiplo di 512 bit. Viene quindi suddiviso in blocchi da 512 bit. Uno stato di esecuzione a 128 bit (contenuto in quattro variabili a 32 bit chiamate A , B , C e D ) viene inizializzato su un valore convenzionale, quindi elaborato con la funzione di compressione . La funzione di compressione prende lo stato di esecuzione e un blocco di messaggi a 512 bit e li mescola in un nuovo valore per lo stato di esecuzione. Quando tutti i blocchi di messaggi sono stati così elaborati, il valore finale dello stato di esecuzione è l'output hash.

Quindi concentriamoci sulla funzione di compressione. Funziona in questo modo:

• Input: lo stato di esecuzione ( A B C D ) e un blocco di messaggi M . Il blocco del messaggio è di 512 bit; lo abbiamo diviso in 16 parole a 32 bit M₀ , M₁ , M ₂ , ... M₁₅.
• Risultato: il nuovo valore dello stato di esecuzione.

• Elaborazione:

  1. Salva lo stato corrente in alcune variabili: A → A ', B → B' , C → C ' e D → D'
  2. Fai 64 round che assomigliano a questo:
     • Calcola T = B + ((A + f _i (B, C, D) + M _k + X _i ) <<< s _{i sub>)} . Si legge così: calcoliamo una data funzione f_i (una semplice funzione bit per bit, che dipende dal numero tondo i ) su B , C e D . Aggiungi a ciò il valore di A , una parola del messaggio M_k e una costante X _i (le aggiunte vengono fatte modulo 2³² ). Ruota il risultato a sinistra di alcuni bit (la quantità di spostamento dipende anche dal round). Infine, aggiungi B : il risultato è T.
     • Ruota le parole di stato: D → A , C → D , B → C , T → B .
  3. Aggiungi i valori di stato salvati alle variabili di stato correnti: A + A '→ A , B + B' → B , C + C '→ C , D + D '→ D .

Il punto importante è che ci sono 64 round, ma solo 16 parole del messaggio. Ciò significa che ogni parola del messaggio entra in elaborazione quattro volte . Lo scrivo in grassetto perché è il punto centrale; la resistenza alle preimmagini deriva da quella caratteristica. La parola del messaggio utilizzata in ogni round è descritta nella specifica MD5 (RFC 1321); la specifica descrive anche le funzioni f_i , la rotazione conta s_i e le costanti a 32 bit X _i .

Ora supponi di voler "invertire" MD5; si parte dall'output e si aumenta lentamente la funzione di compressione. Per prima cosa, devi decidere l'output del round 64. In effetti, l'output della funzione di compressione è la somma dell'output del round 64 e lo stato salvato (il A 'B' C Valori "D" ). Non hai nessuno dei due, quindi devi scegliere. La tua speranza è che sarai in grado di trovare valori per le parole del messaggio che ti consentiranno di ottenere per l'input del primo round dei valori coerenti con la tua decisione arbitraria su A ' e sui suoi fratelli.

Vediamo come vanno le cose quando cammini indietro nella funzione di compressione. Hai l ' output di un round (le variabili A , B , C e D dopo il round) e vuoi ricalcolare l ' input di quel round. Conosci già i valori precedenti di B , C e D , ma per A e M k hai molta scelta: ogni valore a 32 bit è possibile per A e ognuno ha un corrispondente M _{k sub >} . All'inizio sei contento di questo; chi rinnegherebbe tale libertà? Basta scegliere un M_k casuale e questo produce il corrispondente A con poche operazioni (provalo!).

Ma dopo aver invertito in questo modo 16 round (i round da 49 a 64, poiché stai lavorando all'indietro), la libertà scompare. Hai "scelto" i valori di tutte le parole del messaggio. Quando si tenta di invertire il round 48, si desidera ricalcolare il valore di A appena prima di quel round; secondo la specifica MD5, la parola del messaggio M₂ viene utilizzata nel round 48 e hai già scelto il valore di M ₂ (quando si inverte il round 63). Quindi c'è solo una scelta per A . Quindi cosa, diresti. Una scelta è sufficiente per continuare la camminata all'indietro. Quindi continui.

Ora sei all'inizio della funzione di compressione. Ricorda che, inizialmente, hai fatto una scelta arbitraria dei valori di A 'B' C 'D' : questo ti ha permesso di calcolare l'output del round 64 e iniziare il cammino all'indietro. Ora hai ottenuto l'input del round 1, che dovrebbe essere identico a A 'B' C 'D' ... e non corrisponde. È abbastanza normale: hai scelto arbitrariamente A 'B' C 'D' e hai anche scelto arbitrariamente le parole del messaggio M_k , quindi ci si può aspettare che non funzioni per la maggior parte del tempo. Quindi provi a riparare il calcolo, alterando retrospettivamente la tua scelta iniziale di A 'B' C 'D' , o una o più scelte casuali per M _k . Ma ogni modifica su qualsiasi M_k implica modifiche altrove, perché ogni M_k viene utilizzata quattro volte. Quindi hai bisogno di altre modifiche per cancellare le altre, e così via ...

A quel punto inizi a capire il problema dell'inversione di MD5: ogni volta che tocchi un solo bit, si innesca un terribile molte modifiche in tutto l'algoritmo, che è necessario annullare toccando altri bit, e ci sono troppe interazioni. Fondamentalmente, giochi con 2¹²⁸ palline contemporaneamente, e questo è troppo per tenerne traccia di tutte.

Se ogni blocco di messaggio era lungo 2048 bit, suddiviso in 64 parole e ogni parola di messaggio veniva utilizzata solo una volta in MD5, è possibile invertirla facilmente. Fai come sopra: selezione arbitraria di LA 'B' C 'D' , selezione arbitraria delle parole del messaggio per i round 64-5; e per i primi quattro round, considera solo il valore che desideri ottenere per l'input del round (il valore che corrisponde alla tua scelta arbitraria di A ', B' , C ' o D' ) e trova la parola del messaggio corrispondente. Facile come una torta. Ma MD5 non elabora i dati per blocchi da 2048 bit, ma per blocchi da 512 bit e ogni parola di messaggio viene utilizzata quattro volte.

---

Alcuni colpi di scena aggiuntivi

La struttura della funzione di compressione di MD5 è in realtà una generalizzazione di un cifrario Feistel. In un cifrario Feistel, i dati sono divisi in due metà e, per ogni round, ne alteriamo una metà aggiungendola / xorandola a un valore intermedio che viene calcolato dall'altra metà e dalla chiave; e poi scambiamo le due metà. Estendi questo schema a una divisione in quattro parti e ottieni la stessa struttura dei round MD5 - con una rotazione di 90º: MD5 sembra la crittografia dello stato corrente usando il blocco dei messaggi come chiave (e c'è l'aggiunta extra dell'output del round 64 con lo stato salvato, che allontana MD5 da un cifrario ruotato).

Quindi forse possiamo costruire funzioni hash fuori blocco cifre? In effetti possiamo: questo è ciò di cui parla Whirlpool. Una funzione hash costruita su un cifrario a blocchi ruotato (il blocco del messaggio è la chiave); il codice a blocchi di Whirlpool è "W", un derivato di Rijndael, meglio conosciuto come AES. Ma W ha blocchi più grandi (512 bit invece di 128 bit) e una pianificazione delle chiavi riforgiata.

Quando si crea una funzione hash da un cifrario a blocchi ruotato, gli attacchi preimage alla funzione hash sono in qualche modo equivalenti agli attacchi di ricostruzione chiave sul cifrario a blocchi; quindi c'è qualche speranza che se il cifrario a blocchi è sicuro, lo è anche la funzione hash. Anche in questo caso, ci sono dettagli irriverenti. Inoltre, per una tale struttura, le collisioni sulla funzione hash sono come gli attacchi con chiave correlata al cifrario a blocchi; gli attacchi con chiave correlata sono generalmente considerati non fatali e spesso ignorati (ad esempio, non facevano parte dei criteri di valutazione per la competizione AES, e Rijndael è reputato un po 'instabile sotto questo aspetto, motivo per cui W ha una chiave nuova di zecca pianificazione).

Alcuni progetti più recenti sono costruiti su un cifrario a blocchi che non viene ruotato, in modo che la sicurezza della funzione hash possa essere derivata più direttamente dalla sicurezza del cifrario a blocchi; si veda ad esempio il candidato SHA-3 Skein, definito su un cifrario a blocchi chiamato Threefish.

Al contrario, si potrebbe provare a creare un cifrario a blocchi da una funzione hash. Vedi ad esempio SHACAL, che è SHA-1 "impostato in posizione verticale". E, al momento giusto, SHACAL ha alcune debolezze chiave correlate che sono abbastanza simili alle debolezze note di SHA-1 per quanto riguarda le collisioni (non è stata calcolata alcuna collisione effettiva, ma abbiamo un metodo che dovrebbe essere quasi un milione di volte più veloce del algoritmo generico di ricerca delle collisioni).

Pertanto, contrariamente a quanto ho detto nell'introduzione di questo post, abbiamo sempre parlato di crittografia . C'è ancora molto da scoprire e studiare sui collegamenti tra le funzioni hash e la crittografia simmetrica.

---

TL; DR: non c'è TL; DR per questo messaggio . Leggi tutto o vattene.

Answer 3

view on stackexchange narkive permalink

Il primo passo per arrivare alla risposta qui è vedere esempi, come quello simpatico di @Dietrich, di funzioni che sono molto più difficili da eseguire in una direzione rispetto all'inverso, e hanno resistito a molti tentativi di trovare una svolta di velocità. Ma il problema è complesso, quindi cercherò di rimpolparlo ancora.

Molte persone sembrano cadere nella trappola (eh) di pensare che le funzioni hash siano in realtà in qualche modo magico - che sono davvero "funzioni unidirezionali" assolute che matematicamente non possono essere eseguite all'indietro, solo perché sono chiamate hash. Questo non è un modo sano di pensarci in un forum sulla sicurezza. Spesso è sbagliato in pratica. Ed è sempre sbagliato in teoria, data la definizione matematica di base di una funzione come mappatura da un dominio a un'immagine.

Tutti gli hash possono essere invertiti, in linea di principio. Può essere disordinato e brutale (come nella forza bruta), potrebbe richiedere molto tempo in modo non pratico con l'hardware di oggi, e potrebbe anche reggere nel lungo periodo, ma matematicamente è semplicemente una questione di tempo. Come ha notato @mucker, tutte le informazioni sono lì per trovare la password originale (o, almeno, una password che funzioni). Se lo dimentichiamo, dimentichiamo il pericolo di un'euristica intelligente per selezionare le password probabili, che fanno notizia regolarmente. L'hashing è un problema di ingegneria e la sfida principale è l'efficienza: come rendere costoso trovare la password data l'hash. Uno dei principali risultati di questo tipo di pensiero è l'importanza di rendere gli hash delle password lenti

E la scienza e la matematica dell'hashing stanno diventando solo lentamente meglio. Non ci sono davvero prove che gli hash siano davvero difficili. La risposta di @ Dietrich è un bel modo per illustrare come le funzioni hash ideali potrebbero essere possibili. Ma guarda i veri esperti che descrivono come non abbiamo prove per nessuno dei migliori algoritmi crittografici: Qual è il modello matematico dietro le affermazioni di sicurezza di cifrari simmetrici e algoritmi digest?

Il fatto che LanMan sia stato citato nella domanda è un'ulteriore prova che dobbiamo evitare di idealizzare gli hash. LanMan è tutt'altro che una funzione hash ideale, facilmente sconfitta da una combinazione di un po 'di analisi e un po' di forzatura bruta. Per un altro esempio popolare di un'orrida funzione hash vedi MySQL OLD_PASSWORD cryptanalysis?.

Quindi tirati fuori dalla trappola: caderci non deve essere un viaggio di sola andata . Riconosci che gli hash sono reversibili e mantieni attiva quella fidata mentalità di sicurezza mentre cerchi il modo migliore per invertirli. Questo è spesso il modo migliore per trovare quelli che sono davvero difficili da invertire. Non sto cercando di lanciare critiche sulle migliori pratiche là fuori, come bcrypt o PBKDF2 o scrypt. Ma l'evidenza è chiara che anche i bravi programmatori sbagliano troppo spesso, quindi fai attenzione a come li usi e non cercare di inventarne uno tuo.

Answer 4

view on stackexchange narkive permalink

Poiché è così che funzionano le funzioni hash crittografiche, sono funzioni matematiche unidirezionali (dal semplice all'hash). Gli algoritmi sono realizzati e testati specificamente per evitare ciò, e anche evitare collisioni (2 diversi testi semplici generano lo stesso hash).

Puoi leggere di più su wikipedia, ma il punto principale dell'articolo è:

La funzione hash crittografica ideale ha quattro proprietà principali o significative:

• è facile (ma non necessariamente veloce) calcolare l'hash valore per un dato messaggio
• nonè possibile generare un messaggio che ha un dato hash
• nonè possibile modificare un messaggio senza cambiare l'hash
• non è possibile trovare due messaggi diversi con lo stesso hash

La maggior parte degli attacchi alle funzioni hash si basano sulla ricerca di collisioni (quindi 2 diversi testi semplici corrisponderanno allo stesso hash) o pre-generare milioni di hash e confrontarli fino a trovare la pianura che lo ha generato.

Breve storia lunga: se un algoritmo di hash è decodificabile o può essere attaccato che modo, non è una sostanza appiccicosa d hash algoritmo.

Per le password, che indagano utilizzando BCrypt, questo post contiene molte informazioni.

Answer 5

view on stackexchange narkive permalink

Immagina una funzione hash che utilizzi un singolo bit per l'hash. Quindi il tuo hash può essere 0 o 1.

E diciamo che la funzione hash somma ogni byte di dati e se i dati erano pari, il valore hash è 0. Se i dati erano dispari, l'hash è 1.

Capisci perché non hai potuto recuperare i tuoi dati decodificando la funzione hash?

È lo stesso per gli algoritmi hash effettivi, solo le formule sono significativamente migliori di la funzione che ho appena descritto.

La tua difficoltà potrebbe essere che stai prendendo in considerazione l'hash per quanto riguarda il loro utilizzo per le password. Non è ovvio il motivo per cui non è possibile recuperare una password di 8 caratteri da un hash a 128 bit. Ma la funzione hash che usi per le password può essere utilizzata anche per calcolare l'hash di un intero terabyte di dati e l'hash richiederà comunque solo 128 bit di dati. Ovviamente, non puoi decodificare quell'hash a 128 bit e recuperare il tuo terabyte di dati.

Inoltre, supponendo che tu abbia ogni possibile permutazione di un singolo terabyte di dati, ci sarebbe un'enorme quantità di dati diversi che generano lo stesso hash. Dopo tutto, se hai più di 2 ^ 127 diverse permutazioni di dati, è probabile che tu incontri due diversi dati con lo stesso hash.

Answer 6

view on stackexchange narkive permalink

Esistono algoritmi intrinsecamente non reversibili; cambiano un input A in un output B in modo tale che anche se conosci i passi esatti dell'algoritmo, non puoi recuperare A da B.

Un esempio molto semplice: converti ogni carattere in la password al suo valore ASCII e somma tutti i valori. Non è possibile recuperare la password originale dal risultato.

Answer 7

view on stackexchange narkive permalink

C'è un aspetto del problema che manca alle persone nelle risposte precedenti. Questa è la natura molti-a-uno delle funzioni hash. Poiché (la maggior parte) delle funzioni hash sono output a lunghezza fissa (ad esempio, 256 bit), tecnicamente ci sono infinite stringhe che hanno tutte lo stesso valore.

Ad esempio, se prendi tutte le stringhe a 512 bit (di cui ci sono 2 ^ 512). Ci sono solo 2 ^ 256 output della funzione hash. Pertanto, per ogni output della funzione hash, ci sono circa 2 ^ 256 stringhe da 512 bit che hanno un hash a quel valore. Dico approssimativamente perché non sappiamo se la funzione hash sia effettivamente una funzione casuale, potrebbe avere lievi pregiudizi.

Quindi, dato un digest, ci sono molte stringhe che hanno lo stesso valore. Pertanto, se definisci "inversione di una funzione hash" come output della password degli utenti, come affronterà la tua funzione di inversione con il numero potenzialmente infinito di stringhe che risultano nel digest dato?

Answer 8

view on stackexchange narkive permalink

Ti stai chiedendo "perché è importante che le funzioni hash siano unidirezionali?" È una proprietà di sicurezza.

Esistono due tipi di "hash" (o "message digest" come vengono chiamati) di uso comune oggi. Uno è un semplice messaggio digest, che potresti avere familiarità con un algoritmo di checksum, come CRC32. L'algoritmo è progettato in modo che una modifica di un singolo bit nell'ingresso produca un valore digest diverso. Lo scopo principale di ciò è garantire che un messaggio non sia stato danneggiato accidentalmente. I checksum CRC32 sono presenti su ogni pacchetto TCP / IP e una mancata corrispondenza risulta nella ritrasmissione per correggere l'errore.

I digest dei messaggi sono spesso usati in crittografia come parte della "firma" di un messaggio. Il messaggio viene crittografato dal mittente con la sua chiave privata e chiunque può utilizzare la chiave pubblica per verificare che sia stato crittografato solo dal mittente. Ma la crittografia a chiave pubblica RSA può crittografare solo i messaggi di dimensioni inferiori alla dimensione della chiave (256 byte), che sono molto più brevi dei messaggi più utili. Gli algoritmi di digest del messaggio producono valori inferiori alle chiavi RSA. Quindi crittografando il digest invece del messaggio, le firme RSA possono essere utilizzate su messaggi di qualsiasi dimensione.

Ma un normale messaggio digest non è protetto contro un aggressore. Considera un checksum molto semplice che somma solo i valori dei caratteri. Se hai firmato un tale checksum, potrei scambiare qualsiasi altro messaggio che restituisce lo stesso checksum e le firme corrisponderebbero, ingannando la vittima.

Un altro uso comune per i digest dei messaggi è la protezione con password durante l'archiviazione. Se si crittografano le password prima di memorizzarle nel sistema, un amministratore di sistema che conosce la chiave potrebbe decrittografarle tutte. (Potresti aver notato questo problema di recente quando alcuni siti web sono stati compromessi.)

Per evitare questi problemi, è necessario un diverso tipo di hash, uno che sia "crittograficamente sicuro". Un algoritmo hash sicuro ha due proprietà aggiuntive, resistenza alle collisioni e non reversibilità .

La resistenza alle collisioni significa che non dovrei essere in grado di trovare un messaggio che produca lo stesso digest. In questo modo non posso scambiare il mio messaggio malvagio con il tuo buon messaggio.

La proprietà di non reversibilità significa che non posso trasformare un digest di nuovo in un testo in chiaro, quindi non posso decrittografare il messaggio originale, come la password dell'utente.

La creazione di un digest è un problema molto simile alla crittografia, in quanto devi codificare i dati in modo tale che non trapelino informazioni sui dati originali. È ancora più difficile, perché la stessa matematica non deve fornire alcun indizio su come creare con successo una collisione.

Answer 9

view on stackexchange narkive permalink

Altri hanno spiegato perché è difficile invertire una buona funzione hash crittografica, ma secondo questo articolo di Wikipedia, LanMan è mal progettato e può essere invertito in modo relativamente semplice:

Sebbene sia basato su DES, un codice a blocchi ben studiato, l'hash LM non è una vera funzione unidirezionale poiché la password può essere determinata dall'hash a causa di diversi punti deboli nella sua implementazione ... Montando una forza bruta attacco su ciascuna metà separatamente, le moderne macchine desktop possono rompere gli hash LM alfanumerici in poche ore ... Nel 2003 è stata pubblicata Ophcrack, un'implementazione della tecnica della tabella arcobaleno. Si rivolge specificamente ai punti deboli della crittografia LM e include dati precalcolati sufficienti per crackare praticamente tutti gli hash LM alfanumerici in pochi secondi.

Answer 10

view on stackexchange narkive permalink

Penso che ci siano molte ragioni, ma una è ovvia: un digest prodotto da una funzione hash non può mai contenere informazioni infinite, poiché il digest ha bit finiti. Ma la funzione hash può essere utilizzata per hash input di informazioni infinite. L'input può effettivamente essere qualsiasi cosa.

La difficoltà di scoprire una collisione non è la risposta. La vera difficoltà è dimostrare che i tuoi dati originali sono in realtà l'unico input possibile che corrisponde a un determinato digest. Penso che potresti non calcolare mai un input e affermare che è l'unica risposta al digest.

Answer 11

view on stackexchange narkive permalink

Invertire un mod hash è semplice. Es: - (sommatoria di byte) mod (d) = hash . Quindi se vuoi generare tutti gli input per un hash è int bytes summatory = int n * int d + int hash che ne dici?

Ff è lo XOR tra due blocchi è semplice, supponiamo che il bit sia uno, o block 1 = 0 e block 2 = 1 , o block 1 = 1 e blocco 2 = 0 . Supponiamo che il bit sia 0 o (b1 = 0 ^ b2 = 0) o (b1 = 1 ^ b2 = 1) . Queste sono le risposte corrette per lo stesso output.