La tua premessa ha un difetto. Dici di voler "decodificare" la funzione hash. Non è necessario decodificarlo: la sua implementazione è pubblica.

Quello che non puoi fare è invertirlo (forse è quello che intendevi), perché non è invertibile. Si può facilmente dire che non è una funzione invertibile perché la dimensione del dominio (possibile numero di input) è maggiore della dimensione dell'intervallo (possibile numero di output). L'intervallo è 2 ^ 256 (possibili stati di output) e la dimensione dello spazio di input è infinita (tecnicamente 2 ^ (2 ^ 64) apparentemente, ma molto più grande di 2 ^ 256). Ed è esattamente ciò che consente le collisioni (in base al principio del buco di piccione, deve esserci più di un possibile input per ogni output, almeno per uno degli input).

L'intero design della funzione hash lo rende computazionalmente difficile trovare quelle collisioni. Esistono tre proprietà degli hash (prima resistenza pre-immagine, seconda resistenza pre-immagine e resistenza alle collisioni) che descrivono quella proprietà in modo più preciso.

Quindi la risposta alla tua domanda è che il design della funzione rende è volutamente difficile da ottenere anche se sai esattamente come funziona la funzione.

Per i dettagli (in un contesto leggermente diverso) di come le funzioni possono eseguire sorprendentemente (perché ad esempio è impossibile "tornare indietro them "per invertirli), vedere le risposte qui.

Stai mescolando gli attacchi alle funzioni hash. La definizione formale di attacchi generici alle funzioni hash crittografiche può essere trovata in Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance di P. Rogaway e T. Shrimpton. Può essere semplicemente dato come;

• L'attacco pre-immagine : dato un valore hash h , trova un messaggio m tale che h = Hash (m) . Considera l'idea di archiviare gli hash delle password sul server. Per esempio. un utente malintenzionato proverà a trovare una password valida per il tuo account.

• Il secondo attacco pre-immagine (chiamato anche collisione debole) : dato un messaggio m1 , trova un altro messaggio m2 tale che m1 ≠ m2 e Hash (m1) = Hash (m2) . Un esempio sta producendo una contraffazione di un dato messaggio.

• L'attacco di collisione (chiamato anche collisione forte) : trova due input che hanno hash al stesso output: a e b tale che H (a) = H (b) , a ≠ b .

SHA-256 non è ancora rotto per nessuno di questi attacchi generici. Vedi: Cosa rende SHA-256 sicuro? su crypto.stackexchange.

se potessimo prendere l'algoritmo e semplicemente decodificarlo per generare una stringa come 8GN492MD che restituirebbe anche dug84nd8

• Se consideriamo solo questo è l'attacco pre-immagine e il costo è O (2 ^ 256) per SHA-256. Si noti che lo scopo dell'attacco pre-immagine non è trovare l'input originale, ma piuttosto trovare un input che abbia lo stesso valore hash. Se non esiste un test esterno per l'input, non è possibile decidere che la pre-immagine trovata sia la pre-immagine. Inoltre, lo spazio di ricerca effettivo per la pre-immagine può essere molto più grande delle maniglie dell'attacco pre-immagine.

  Esiste una variante dell'attacco pre-immagine, che si verifica quando lo spazio del messaggio è breve, come l'hashing dei numeri di telefono. In questo caso, potrebbe essere molto facile trovare la pre-immagine.

Se potessimo prendere l'algoritmo e semplicemente decodificarlo per generare una stringa come 8GN492MD che restituirebbe anche dug84nd8 , non direbbe che (s2 ("Hello") = s2 ("8GN492MD")) == true) e lasciare che un hacker in?

• Se consideriamo sopra in termini più semplici; dato Hello e dug84nd8 = SHA256 (Hello) e trova un altro messaggio con lo stesso valore hash richiesto, questo è il secondo attacco pre-immagine e il costo è O (2 ^ 256) per SHA256.

La seconda pre-immagine è quello che stai cercando. Questo non è fattibile e non solo SHA-256, ma anche nessuna delle funzioni hash crittografiche viene interrotta in questo modo.

• Il costo di un attacco di collisione di SHA-256 è O (2 ^ 128 ) a causa dell ' attacco del compleanno con una probabilità del 50%. Nell'attacco di collisione, gli aggressori sono liberi due scelgono a e b . Questo non è il tuo caso poiché inizi con un messaggio fisso.

La conclusione , nessuno di questi attacchi non è fattibile per SHA-256 a partire dal 2020.

Gli errori nella risposta più in alto

L'intervallo è 2 ^ 256 (possibili stati di output ) e la dimensione dello spazio di input è infinita (tecnicamente 2 ^ (2 ^ 64) apparentemente, ma molto più grande di 2 ^ 256). Ed è esattamente ciò che consente le collisioni (in base al principio della buca delle lettere, deve esserci più di un possibile input per ogni output, almeno per uno degli input).

Lo spazio di input SHA256 è limitato a causa dello standard di imbottitura del NIST. Si può eseguire l'hashing al massimo di 2 ^ 64 bit quindi ci sono al massimo 2 ^ (2 ^ 64) messaggi diversi poiché la dimensione del messaggio è codificata alla fine del riempimento in 64 bit.

Il principio della casella dice solo che esiste almeno una casella contenente più di una casella. Non parla di altri che possono essere vuoti o meno. Con questo, possiamo dire che almeno ci deve essere una collisione. È interessante notare che non sappiamo che un SHA256 limitato a 64 bit raggiunge tutti i valori a 64 bit. Quello che ci aspettiamo da SHA256 è che sia indistinguibile da uniformemente casuale.

Puoi facilmente dire che non è una funzione invertibile perché la dimensione del dominio (numero possibile di input) è maggiore della dimensione di l'intervallo (possibile numero di output).

Anche questo non è corretto. Prendi modulo 2 ^ 256 come hash, quindi non è invertibile. Uno, tuttavia, dato un valore hash può calcolare facilmente una pre-immagine, dato x , a ;; x + k 2 ^ 265 sono pre-immagini. In altre parole, abbiamo invertito la mappa. La definizione corretta è una funzione che non è computazionalmente possibile invertire

e far entrare un hacker?

Certo. Ma il fatto è che in realtà non sappiamo come trovare un'altra stringa che produca lo stesso hash in modo efficiente. Almeno per SHA-256 e altri algoritmi di hashing ampiamente utilizzati. Nota che questi algoritmi sono pubblici, non è necessaria alcuna ingegneria inversa, il che non cambia nulla. Questo è semplicemente troppo difficile, e in effetti quegli algoritmi sono deliberatamente progettati in questo modo.

L'intero problema si riduce alla risoluzione dell'equazione f (x) = y per alcune funzioni f e alcune y. Una possibilità è scansionare tutte le x, assumendo che il dominio sia enumerabile. Ma è inefficiente e funziona solo se sappiamo già che esiste una soluzione (che non sono sicuro che tutti i valori di SHA siano raggiunti più volte). Altre possibilità spesso non sono note.

Forse questo è un problema educativo. A scuola ci viene spesso detto di risolvere le equazioni. Lineare, polinomiale, logaritmica, seno, ecc. Quello che non ti dicono è che scelgono queste equazioni in modo tale che siano risolvibili e in modo relativamente facile. Ma in effetti anche adesso le menti più brillanti non sanno come risolvere la maggior parte delle equazioni là fuori. E qui ti sei imbattuto in uno di questi esempi (estremamente importanti).

Nota che la situazione potrebbe (e lo è già successo per altre funzioni hash) cambiare in futuro.

Credo che la risposta di @ kelalaka sia la più accurata, ma volevo aggiungere un esempio che, si spera, possa far luce sul problema.

Prima di tutto, sei assolutamente preciso che potresti segui tutta la logica nel circuito e alla fine ottieni una collisione. Tuttavia , una delle caratteristiche di una buona funzione hash crittografica è che questo esercizio è sostanzialmente difficile quanto solo indovinare casualmente.

Considera il seguente circuito . M1-M3 sono i bit del messaggio. Dato un messaggio 101 e un seme di 1 , otteniamo un output di 1.

Ora, proviamo a trovare un messaggio diverso che si scontri con 101 ricalcando il circuito. Dall'output, sappiamo che M3 potrebbe essere 1 o 0 . Scegliamo 0 ; ciò significa che l'altra gamba deve essere 1 ( 1 XOR 0 è 1 ). Veniamo ora a M2. Inoltre selezioneremo di nuovo 0 . Ora guardiamo M1. Sceglieremo 1 per M1. Ma, uh-oh. Il seme ora dovrebbe essere 0 . 100 funziona solo come messaggio se il seme è 0.

Ovviamente, in questo esempio molto semplicistico, avremmo potuto banalmente assegnare M1 come 0 , quindi il valore iniziale sarebbe stato 1 come previsto. Ma il punto di questo esempio è evidenziare gli elementi di feedback e concatenamento che rendono questo semplice approccio "basta ripercorrere il circuito" molto più complicato in un vero algoritmo di hashing crittografico. Il "circuito" richiesto per implementare questi algoritmi è estremamente complicato, perché consiste in moltiplicazione, esponenziazione, aritmetica modulare, ecc. E la natura ricorsiva di alcuni di questi calcoli fa del tracciare il circuito all'indietro un enorme esercizio di ramificazione. Ancora una volta, non è impossibile; piuttosto è difficile quanto indovinare a caso.

"Prova a caso finché non trovi un input che produca l'hash corretto." Sì, ma è comunque un attacco di forza bruta. Questa è la premessa di un attacco alla tabella arcobaleno. Pre-calcola i valori in modo da avere un input per ogni output possibile. Quindi, invece di provare tutti gli input possibili, puoi provare solo un sottoinsieme di input che producono hash univoci. Non importa se ottieni l'esatto input che era la password originale perché il sistema non è in grado di capire la differenza.

Ecco i problemi:

1. Hai per trovare l'input per ogni hash. Come altre risposte hanno detto, questo è "abbastanza lento" con le moderne funzioni di hashing poiché è solo forza bruta. (A meno che tu non abbia un computer quantistico in giro.) Il vantaggio principale di una tabella arcobaleno è che per le funzioni in cui PUOI calcolarlo, puoi calcolarle tutte una volta e riutilizzare i risultati più e più volte senza ricalcolare (scambiando lo spazio di archiviazione tutti quei valori per il risparmio di tempo di non doverli ricalcolare).
2. Non si ottiene la password effettiva. In molti casi, le persone stanno attaccando sistemi meno sicuri non perché vogliono entrare in quei sistemi, ma per approfittare di persone che riutilizzano password / login su altri sistemi più interessanti.
3. Se l'attaccante non lo fa conoscere l'hash di destinazione e deve confrontarsi con il sistema di destinazione, quindi può essere bloccato limitando il numero di tentativi errati. (L'autore dell'attacco che conosce l'hash di destinazione può essere bloccato da altre pratiche di sicurezza di base.)
4. Salt. Aggiunta di un'altra stringa univoca per l'utente alla password prima dell'hashing. Ad esempio, supponiamo di aggiungere il nome utente alla fine della password prima di eseguirne l'hashing. Ora dobbiamo trovare una stringa che, quando il nome utente viene aggiunto alla fine, calcola un hash. Poiché il nome utente è unico per ogni utente, non possiamo precalcolarlo in blocco, siamo tornati a farlo uno per uno ... molto inefficiente, ovvero richiede tempi incredibilmente lunghi.

Probabilmente mescoli "ingegneria inversa" e trova una "funzione inversa". Questi sono concetti diversi.

Il reverse engineering sta deducendo l'algoritmo dalla sua implementazione (chiusa). L'algoritmo SHA-256 è pubblico e puoi saltare del tutto la parte di reverse engineering. Basta guardare in Wikipedia, o il codice sorgente di qualche libreria crittografica open source.

Per rompere la crittografia (nel tuo caso, per trovare una "collisione di hashing"), devi trovare un " funzione inversa "- nello stesso senso matematico in cui la radice quadrata è la funzione inversa del quadrato.

Gli algoritmi di hash utilizzati per la crittografia sono progettati specificamente per resistere alla ricerca di collisioni e funzioni inverse. Se qualcuno trova un modo semplice per trovare le collisioni, la funzione hash corrispondente viene considerata compromessa e le persone smettono di usarla. Questo è quello che è successo alle funzioni MD5 o SHA-1.

Ci sono altre funzioni di hashing (ad esempio create per l'uso nelle tabelle hash del database) che NON sono fatte per essere molto resistenti alle collisioni, ma sono meno costose dal punto di vista computazionale e / o avere altri vantaggi. Si chiamano ancora hash, ma vengono utilizzati nei rispettivi campi e non in crittografia.

Distruzione delle informazioni

Quando si calcola una funzione hash, le informazioni vengono distrutte in determinate fasi dell'algoritmo. Questa è la chiave per cui non è possibile "eseguire l'algoritmo al contrario".

Se inizi con l'hash ccb92793f8a87a695fa3f2e805779da8 , lavorando all'indietro, potrebbero esserci miliardi di possibilità di come la fase precedente ti ha portato a quel valore. Nessun problema: scegline uno e passa alla fase successiva; stesso affare. Dopo diverse tappe si raggiunge un punto in cui si rimane bloccati e non si può andare oltre; hai raggiunto uno stato intermedio impossibile. Quindi devi tornare indietro e fare una scelta diversa ei tuoi miliardi iniziano a moltiplicarsi. Se ci sono abbastanza stadi, questo diventa più difficile che forzare brutalmente gli input, quindi potresti farlo semplicemente.

Tutte le altre risposte sono tutte corrette e coprono alcuni aspetti, tuttavia voglio mostrare un altro approccio.

Quello che tu - più o meno casualmente - hai scoperto è l'inevitabile connessione tra funzioni hash e il principio dei casellari .

Se guardi le definizioni, è abbastanza ovvio:

• Una funzione hash è una mappatura da un dominio contenente dati di dimensione arbitraria su dati (un array di bit) di dimensione fissa.
• Il principio della casella dice: se ce ne sono di più piccioni che buchi, quindi deve esserci almeno un buco con almeno due piccioni all'interno.

Per il dominio di input, potresti avere password più lunghe e di lunghezza variabile, e il set di simboli è tipicamente più grande (lettere minuscole e maiuscole, cifre, alcuni simboli). Questi sono i piccioni.

Il numero di possibili valori hash è facile da calcolare: se la lunghezza è n su b simboli, allora ci sono b ^ n possibili hash (puoi impostare b = 2 per contare bit). Queste sono le buche dei piccioni.

Quindi, hai più piccioni (possibili dati di input) che buche (possibili valori hash), quindi deve esserci almeno un piccione ( possibili dati di input) inseriti in (mappati su) un buco (un valore hash).

Ovviamente in questo caso la funzione non è mai iniettiva, e quindi non biiettiva, e quindi non invertibile.

È troppo per un commento, quindi lo aggiungerò come risposta:

Un piccolo trucco che potrebbe aiutare: supponiamo che il tuo algoritmo sia $ a * $ b , se hai 3 e 4, ottieni 3 * 4 = 12 . Ora hai il risultato che non puoi invertire (era 1&12, 2&6, 3&4, 4&3, 6&2 o 12&1?), Ma ha più collisioni. In questo caso 6 diversi input risulterebbero nello stesso risultato, quindi abbiamo 6 collisioni.

Un 'trucco' per ridurre al minimo questa possibilità (che non sarà mai zero se hai un numero finito di caratteri del risultato hash) sta aggiungendo più bit. Ciò significa che il risultato sarà, ad esempio, 1862534 per 3&4 come input e 2&6 potrebbe diventare 6793439 .

Supponiamo di avere un algoritmo di hashing separato chiamato s2 e che converte Hello in dug84nd8.

.. una stringa come 8GN492MD che produrrebbe anche dug84nd8 ...

Ciò che descrivi è una "collisione hash".

E sì: in questo caso sia Hello che 8GN492MD verrebbero accettate come password valide.

Mi sembra che mi manchi qualcosa , ma non so cosa sia.

Primo:

non hai scritto che l'attaccante conosce il valore hash ( dug84nd8 codice>). Tuttavia, sembra ovvio che volevi scriverlo.

Secondo:

ipoteticamente sarebbe sempre possibile trovare una stringa come 8GN492MD che ha dug84nd8 come output se si dispone di una potenza di calcolo sufficiente (forse un grande computer quantistico).

Tuttavia, le funzioni utilizzate per calcolare la stringa 8GN492MD dalla stringa dug84nd8 sono le cosiddette "funzioni unidirezionali".

Queste sono funzioni che possono essere calcolate abbastanza facilmente su un computer "normale"; tuttavia, non è noto se sia possibile calcolare la funzione inversa (trovare la stringa 8GN492MD quando la stringa dug84nd8 è nota) in un tempo realistico (ad esempio meno di 10 anni).

E ovviamente non si sa nemmeno come farlo se fosse possibile.

In effetti, a volte capita che qualche matematico trovi un modo come trovare una collisione. Ciò significa che il matematico trova un modo per trovare la stringa Hello o 8GN492MD quando viene fornita la stringa dug84nd8 .

Se questo accade, non puoi più usare la funzione hash (la funzione che calcola il valore dug84nd8 dal valore Hello ) e devi sostituire la funzione hash con un'altra . Altrimenti avrai un problema di sicurezza.

Altri hanno menzionato l'uso dei termini "ingegneria inversa" e "attacco" ecc., quindi non risponderò a questo. Ma per la tua domanda:

considera hash (a) = x;

Ora conosci x . Supponiamo che tu abbia accesso a un'immensa potenza di calcolo, come una botnet o forse una gigantesca server farm. Ora, in teoria, potresti iniziare a produrre hash, cioè hash (b) = y; hash (c) = z e così via. Con abbastanza tempo, potresti probabilmente trovare una funzione hash (something) = x . Quindi, in un certo senso, confronteresti gli output l'uno con l'altro finché non trovi una coppia corrispondente.

Personalmente non so quanto tempo ci vorrebbe, ma penso che sarebbe possibile. Ma immagino che ci siano modi migliori per rubare una password, come un tentativo di ingegneria sociale, o intromettersi sulla macchina del client piuttosto che sul server.

Ci sono molte ottime risposte tecniche. Cercherò di fornire qualcosa di più accessibile: un esempio.

Immagina, il mio algoritmo segreto è questo:

• Prendo un numero di input,
• aggiungi tutte le cifre,
• moltiplica la somma per ogni cifra,
• quindi ripeti il ​​processo.

Quindi 234 sarebbe (2 + 3 + 4) + 2 * 3 * 4 = 216. (2 + 1 + 6) * 2 * 1 * 6 = 108. Quello 108 è l'hash. Con la tua comprensione del mio algoritmo , puoi calcolare un numero che finisce per essere 108? Se non puoi, devi indovinare. Sembra facile qui, ma immagina che questi numeri siano lunghi migliaia di cifre ...

Disclaimer: faccio schifo in matematica, probabilmente puoi davvero decifrare quello. SHA è un'altra bestia.

La maggior parte degli algoritmi di hashing sono unidirezionali perché se inverti il ​​funzionamento degli algoritmi di hashing funzionerà anche come un algoritmo di hashing (forse non buono).

Supponiamo ad esempio di avere un algoritmo chiamato SHA256 () . E poi si implementa una funzione con esattamente l'operazione inversa chiamata REVERSE_SHA256().

Quello che accadrà è che l'output di REVERSE_SHA256 (SHA256 (INPUT)) non corrisponderà a INPUT:

  INPUT = "some string" HASH = SHA256 (INPUT); OUTPUT = REVERSE_SHA256 (HASH); OUTPUT! = INPUT  

Non solo, ma per una funzione di hashing crittograficamente sicura, OUTPUT non può essere rielaborato allo stesso valore:

  HASH2 = SHA256 (OUTPUT); HASH2! = HASH  

Che un tale algoritmo possa esistere è il motivo per cui esistono funzioni di hashing crittografico.