Domanda:
Perché le funzioni hash sono unidirezionali? Se conosco l'algoritmo, perché non posso calcolarne l'input?
Mucker
2012-02-14 17:09:50 UTC
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.

si prega di migrare questo a [crypto.se] o anche a [security.se] perché vedo solo risposte sbagliate che vengono votate e quelle corrette non affrontano realmente la parte del ** perché ** della domanda.
D'accordo, sono un po 'confuso sul motivo per cui queste risposte gravemente errate stanno ricevendo così tanti voti positivi.
Il problema con tutte le risposte fornite di seguito è che sembrano spiegare perché non puoi ottenere la risposta, ma poi solleva il problema "dato questo, avresti più probabilità di ottenere l'accesso rispetto a se memorizzasse la password in testo normale, perché non è più necessaria una corrispondenza esatta ". L'unico modo in cui questo viene coperto è quando le persone dicono "Oh, ma è davvero improbabile". È ancora più probabile che se dovessi ottenere una corrispondenza esatta!
Se un password cracker conosce il processo per trasformare una mucca in carne macinata, significa che può "semplicemente invertire" e trasformare la carne macinata in una mucca?
_ "è proprio come un verme che scende da un ramo di un albero per fare una doccia al fiume, se decide di tornare al ramo esatto che era prima, fallirà miseramente e tutti rideranno di lui" _
Che serie di risposte molto frustranti da trovare. La risposta è semplice: ogni hash può essere il risultato di un numero infinito di stringhe sottoposte a hash, quindi non c'è modo di sapere quale un hash doveva rappresentare - ancor più semplicemente, un hash non rappresenta alcun valore .
Undici risposte:
#1
+243
Dietrich Epp
2012-02-14 21:37:08 UTC
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).

Ok, quindi dimmi la risposta all'esercizio che mi hai dato? Non ho idea di come risolverlo, come farei ?? E cosa è iniettivo e biettivo?
@Mucker: Una funzione f (x) è iniettiva se f (x) = f (y) implica x = y, cioè non ci sono due input che hanno lo stesso output. Una funzione biiettiva è una funzione iniettiva che è anche suriettiva, cioè per ogni possibile output c'è un input corrispondente. Quando le persone dicono "biettivo" in questo thread, dovrebbero davvero dire "iniettivo". Entrambi i concetti non sono realmente rilevanti per la sicurezza dell'hash delle password. Dire la risposta all'esercizio del lettore vanifica il suo scopo, comunque non ho mai scritto la risposta (esiste, solo che non so cosa sia).
@DietrichEpp potresti aggiungere alla tua risposta che la maggior parte delle funzioni di hashing crittografico utilizza effettivamente operazioni semplici come `add, and, or, xor, rotate, mod` per fare l'hashing e non i numeri primi? (solo per renderlo più chiaro)
@Mucker: Ovviamente fattore di 1451730470513778492236629598992166035067 x 2425967623052370772757633156976982469681 (in realtà, sono stati necessari circa dieci minuti di CPU utilizzando il metodo SIQS su un singolo core a 3GHz).
@drjimbob: Nice! Ora ecco un collegamento che ho usato: http://primes.utm.edu/lists/small/small.html
Ecco il link che ho usato: http://www.alpertron.com.ar/ECM.HTM
Vorrei aggiungere che anche gli hash sono compressione. È possibile eseguire l'hash di un file GiB x (alta entropia) e ricevere un digest a 160 bit. Le informazioni vengono perse (anche se len (m)
@Tie-fighter: Compressione molto, molto con perdita di dati: come noti, la quantità di informazioni perse è così enorme che si tratta di compressione solo in senso molto tecnico, sono tentato di aggiungere.
"spesso non importa se ottieni la stessa password o se ottieni una password diversa" - Ma lo fa quando l'input non è completamente arbitrario ma deve soddisfare alcuni requisiti, come una password + sale noto o un messaggio in un certo protocollo. Ciò rende l'aspetto della distruzione dei dati degli hash vantaggioso per la sicurezza. (Ovviamente, se provi abbastanza a lungo puoi trovare un input che segue i requisiti, ma che richiede anche più tempo)
@BartvanHeukelom: In realtà non è vero. Distruggere i dati è irrilevante, l'unica rilevanza è il costo di un attacco preimage. L'uso del sale non aumenta il costo di un attacco preimage, ma impedisce solo agli aggressori di eseguire attacchi preimage in parallelo o in anticipo. Non fraintendete, il sale è essenziale, ma qui non ci sono vantaggi reali per le funzioni non iniettive.
@juanpastas: La tua modifica non è corretta. Se utilizzi il prodotto xy come password, lo schema non funziona. La password è composta da entrambi i numeri e il prodotto è memorizzato nel database delle password.
Ho una domanda, come scegliamo 2 numeri primi? Se ho una tabella hash per memorizzare un valore come 6 (2 * 3), 63 (7 * 9), ovviamente, un valore molto più grande del prodotto di 2 numeri primi. E facciamo 'reverse engineering', possiamo ottenere i 2 numeri primi molto più velocemente? e se continuiamo a costruire questa tabella come la tabella 9x9 (tabella di moltiplicazione), è possibile questo metodo rompere questo meccanismo di hash?
@Timeless: Il metodo della tabella hash non funzionerebbe mai, perché la tabella hash sarebbe troppo grande e richiederebbe troppo tempo per creare la tabella hash. La tecnica più avanzata per la fattorizzazione di grandi numeri è il * setaccio del campo dei numeri generali * che è ancora troppo lento per i grandi numeri.
#2
+131
Thomas Pornin
2012-09-03 07:17:09 UTC
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 256 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 x2 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 2128 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 M0 , M1 , M 2 , ... M15.
  • 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 fi (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 Mk e una costante X i (le aggiunte vengono fatte modulo 232 ). 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 fi , la rotazione conta si 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 Mk 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 M2 viene utilizzata nel round 48 e hai già scelto il valore di M 2 (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 Mk , 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 Mk implica modifiche altrove, perché ogni Mk 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 2128 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.

Miglior TL; citazione DR mai. Penso di aver bisogno di creare un nuovo stack nel mio evernote solo per le tue risposte. Autori articoli o libri per caso?
Non mi interessa che sia tardi, devo dire questo: una spiegazione davvero buona che mostra davvero la complessità che puoi creare usando gli algoritmi. Avevo questo pensiero ignorante che tutto potesse essere fatto facilmente all'indietro se sapessi come farlo in avanti (usando i computer), e questo mostra chiaramente che non è così facile. Anche l'esempio con MD5 è stato ottimo, poiché ti consente di vedere effettivamente la complessità per quello che è (a differenza delle analogie [che sono anche grandi, non fraintendermi]). Ancora una volta, articolo davvero fantastico e illuminante; spero di leggere altro da te.
Affascinante. Questa dovrebbe essere la risposta.
"x ⟼ x2 mod n è difficile da invertire" ... Questo sembra improbabile, soprattutto perché tu (o chiunque lo usi all'interno di una funzione hash da loro progettata, ad esempio, l'NSA) hai accesso a quei grandi numeri primi.
Ciao, quando dici "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", A cosa ti riferisci?Ad esempio, se guardiamo alla funzione "floor", affermiamo che "non è impossibile invertire"?Grazie!
@AsheKetchum Una funzione unidirezionale è per definizione resistente all'immagine, quindi il significato non è esattamente quello che ti aspetteresti.Se hai "floor (n) = 7", posso "invertirlo" con "n = 7.2".Anche se questo non è il valore originale, l'ho comunque "invertito".Non ho scoperto il valore originale di `n` che potresti aver avuto in mente, ma ho scoperto _a_ valore che risolve l'equazione, dimostrando che non è unidirezionale in senso crittografico.
@cnd Quell'equazione era solo un esempio di una funzione unidirezionale chiamata "funzione trapdoor".Le funzioni di quel tipo sono _normalmente_ unidirezionali, ma non se hai accesso a determinate variabili segrete utilizzate nella creazione della funzione, in quel caso i numeri primi moltiplicati insieme per derivare _n_.Gli hash reali non utilizzano funzioni trapdoor, quindi la loro unidirezionale è incondizionata e non dipende dalla segretezza di un certo valore.
anni dopo la tua risposta (e alcuni prima di questo commento), [è stata calcolata una collisione SHA-1 effettiva] (https://shattered.io)
#3
+18
nealmcb
2012-02-16 21:56:33 UTC
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.

Sto cercando di capire cosa potresti intendere con "tutte le informazioni sono lì per trovare la password originale". Vuoi dire "tutte le informazioni sono lì per trovare una password che genererà lo stesso valore hash con l'algoritmo hash dato"? Perché il primo non è vero ... molti hash perdono informazioni.
@LarsH hai ragione, la maggior parte degli hash perde informazioni e potresti non essere in grado di trovare la password originale. Ma la maggior parte delle volte hai solo bisogno di una password che risulti nello stesso hash, e questo è sempre possibile, date abbastanza risorse, così a lungo è un hash valido. Ho aggiornato un po 'la mia risposta.
#4
+12
coredump
2012-02-14 17:19:39 UTC
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.

Sì. Sono difficili da invertire per definizione.
Gli hash non sono progettati per evitare collisioni. Le collisioni sono sempre presenti, in abbondanza, poiché ci sono molti più possibili valori di input rispetto ai valori di output. Come dice Wikipedia, l'obiettivo è semplicemente quello di rendere impossibile _trovare_ le collisioni. E come noto nella mia risposta, il fatto sfortunato è che solo un piccolo numero di funzioni hash ha un track record di soddisfare effettivamente i requisiti stabiliti, nonostante i molti che sono stati progettati e resi popolari.
Questa risposta fondamentalmente dice "le funzioni hash sono unidirezionali perché le funzioni hash sono unidirezionali". Potresti voler fornire una spiegazione matematica più rigorosa di come funziona una funzione hash per descrivere meglio il _perché_ di questo fatto.
Per quanto riguarda "evitare collisioni", dipende da cosa si intende per "fatto per evitare". Gli hash (almeno alcuni, a seconda dello scopo) sono progettati per * minimizzare * le collisioni, perché ciò rende più difficile trovarli. Ma in generale non * eliminano * le collisioni.
#5
+8
user1068775
2012-02-18 20:20:36 UTC
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.

Perché qualcuno ha votato in modo negativo? È una risposta perfettamente ragionevole alla domanda del titolo, "perché le funzioni hash sono unidirezionali?"
#6
+4
Massimo
2012-02-14 17:19:32 UTC
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.

Ma ... non hai bisogno della password originale, hai solo bisogno di una password il cui hash è lo stesso. In altre parole, hai bisogno di una stringa la cui somma dei valori ASCII sia uguale al valore hash, e questo è facile.
Concordato. Ma la domanda è "perché non può semplicemente invertire il processo per calcolare la password dall'hash", non "come posso abbinare l'hash anche se non conosco la password".
Come spiegato in altre risposte, le funzioni hash crittografiche sono difficili da invertire perché sono progettate in modo tale che invertirle sia computazionalmente molto costoso, non perché ci siano più risposte possibili. Nel tuo esempio, sebbene sia impossibile essere certi di quale fosse esattamente la password originale, è banale restringerla a un insieme relativamente piccolo di password, che è un enorme difetto di sicurezza oltre a quello spiegato da Neil G.
Penso che sia un buon esempio. Sì, è un algoritmo banale che non è affatto sicuro, ma illustra il punto di algoritmi non reversibili in modo molto semplice.
#7
+2
mikeazo
2012-02-15 20:21:32 UTC
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?

cosa divertente: poche ore fa (probabilmente prima di leggere le risposte) abbiamo avuto il problema delle risposte concentrandoci solo su quell'aspetto della funzione di hashing ignorando completamente gli altri punti (più importanti). Ad ogni modo, penso che le risposte attuali non si concentrino su questo perché l'utente sta parlando di password che _usualmente_ hanno molte meno combinazioni possibili rispetto all'output della maggior parte delle funzioni di hashing crittografico.
Una funzione di inversione non può sapere quale preimage è la password originale utilizzata dall'utente, anche se spesso sarà abbastanza chiara in base alle pratiche di password comuni. Ma non è necessario, poiché una qualsiasi delle immagini preliminari funzionerà come password.
@nealmcb, vero tranne che in alcune circostanze. Ad esempio, se viene utilizzato un sale. Funzionerà solo l'immagine preliminare con il sale corretto (un altro motivo per usare i sali). Ma sì, con un'incredibile probabilità sarà possibile distinguere la corretta immagine preliminare. Se, tuttavia, ci sono 2 ^ 256 immagini preliminari, sarebbe una quantità di dati impossibile da cercare.
@mikeazo Un sale non aiuta a contrastare un attacco preimmagine. Se il tuo database è stato compromesso, l'hacker ha sia gli hash che i sali, quindi il suo carico di lavoro è identico a se stesse operando su un hash senza salt. Invece di calcolare "preimage (hash)" egli calcola "preimage (hash || salt)". Ciò che un sale aiuta a contrastare sono gli attacchi al dizionario (l'hacker dovrà lanciare un attacco dizionario separato su ciascuna password, anziché uno per l'intero database) e le tabelle arcobaleno (la tabella arcobaleno non avrà incluso il sale nel calcolo ).
Questo non è "un aspetto del problema". È l'intera risposta. Questa è la domanda più frustrante che abbia mai incontrato, perché tutte le risposte sono sbagliate, tranne la tua. Non ho letto la tua intera risposta solo il primo paragrafo, che risponde a tutto.
#8
+1
John Deters
2012-08-14 00:14:14 UTC
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.

#9
  0
James
2012-02-15 17:55:31 UTC
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.

Questo non risolve davvero la domanda reale. Inoltre, non è vero che può essere invertito: la forza bruta non è il contrario (o inverso) di una funzione hash.
Risponde a una parte della domanda: Mucker ha chiesto specificamente di LanMan, in cui _è_ abbastanza facile trovare una password corrispondente con un hash. Il punto è che questo particolare algoritmo ha dei punti deboli (dividere la password in due parti e convertire le lettere minuscole in maiuscole) che rendono molto facile la forza bruta. Puoi spiegare la distinzione che stai facendo tra l'inversione della funzione hash e la forzatura bruta - definirei il secondo un caso speciale del primo?
Poiché l'OP sta chiedendo informazioni sugli interni delle funzioni hash, sta chiedendo perché la funzione non può essere semplicemente invertita * matematicamente * parlando. La forza bruta è ortogonale all'inversione dell'hash, non importa quale sia la funzione effettiva * *. Fondamentalmente gira intorno all'hash, non lo backup.
Non capisco davvero la distinzione che stai cercando di fare. Il punto centrale di un algoritmo di forza bruta è invertire l'hash. Ha esattamente gli stessi ingressi e uscite di qualsiasi altro metodo (corretto) per invertire la funzione. Non è nemmeno _necessariamente_ il metodo più lento. Se stai sottolineando che - se la funzione hash è multivalore - non può essere invertita in senso strettamente matematico (perché non è un'iniezione) - allora sono d'accordo ma non è realmente rilevante: una funzione hash può essere iniettiva , infatti è auspicabile che le collisioni siano rare.
@James - no, una forza bruta non inverte nulla. Prova l'intero spazio degli indirizzi con un algoritmo e fornisce l'intero spazio di output. Dove c'è una corrispondenza, puoi fare alcune ipotesi.
Penso che ci stiamo fraintendendo. Sto usando la parola 'invertire' in senso matematico - cioè, 'trova l'input di una funzione dato il suo output' (e sto usando 'reverse' come sinonimo). Un metodo di forza bruta è solo un modo per farlo - non importa che generiamo molti altri output della funzione nel processo - la maggior parte degli algoritmi produce spazzatura inutile lungo il percorso. L'OP ha chiesto perché la password non può essere ottenuta dato l'hash e l'algoritmo - e la risposta è che può esserlo - è solo computazionalmente difficile, anche se nel caso di LanMan, non abbastanza difficile.
Concordo con il tuo punto di fondo secondo cui nel caso LanMan, una combinazione di matematica intelligente e forza bruta produce una funzione inversa che è più che abbastanza veloce per il mondo reale. Ma anche se non ci fosse un'analisi della funzione coinvolta per accelerare un approccio di forza bruta, da un punto di vista matematico chiamerei comunque una funzione di forza bruta stupida una funzione "inversa". E certamente una funzione di ingegneria inversa. Solo non abbastanza ingegneristico ...
@avid e io abbiamo parlato molto delle questioni semantiche e pedagogiche nella chat room DMZ, e ora ho cercato di chiarire come la vedo un po 'di più nella mia risposta.
#10
  0
Lucifer Orichalcum
2012-07-17 20:22:14 UTC
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.

#11
-2
gimenez
2012-08-02 01:17:32 UTC
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.

C'è una differenza tra invertire un hash e trovare una collisione di hash. A seconda del caso d'uso, i risultati potrebbero essere gli stessi, ma i concetti coinvolti e le implicazioni di farlo non lo sono sicuramente.


Questa domanda e risposta è stata tradotta automaticamente dalla lingua inglese. Il contenuto originale è disponibile su stackexchange, che ringraziamo per la licenza cc by-sa 3.0 con cui è distribuito.
Loading...