Come mai i valori di hash MD5 non sono reversibili?

StackOverflow https://stackoverflow.com/questions/330207

Domanda

Un concetto che mi sono sempre chiesto è l'uso di funzioni e valori hash crittografici. Capisco che queste funzioni possono generare un valore di hash che è unico e praticamente impossibile da invertire, ma ecco cosa mi sono sempre chiesto:

Se sul mio server, in PHP produco: 

md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"

Quando si esegue la stessa stringa tramite una funzione MD5, si ottiene lo stesso risultato sull'installazione di PHP. Viene utilizzato un processo per produrre un valore, da un valore iniziale.

Questo non significa che c'è un modo per decostruire ciò che sta accadendo e invertire il valore di hash?

Cosa c'è in queste funzioni che rende impossibile rintracciare le stringhe risultanti?

È stato utile?

Soluzione

Il materiale di input può avere una lunghezza infinita, dove l'output è sempre lungo 128 bit. Ciò significa che un numero infinito di stringhe di input genererà lo stesso output.

Se scegli un numero casuale e lo dividi per 2 ma scrivi solo il resto, otterrai rispettivamente uno 0 o 1 - pari o dispari. È possibile prendere quello 0 o 1 e ottenere il numero originale?

Altri suggerimenti

Se le funzioni hash come MD5 fossero reversibili, sarebbe stato un evento spartiacque nella storia degli algoritmi di compressione dei dati! È facile vedere che se MD5 fosse reversibile, blocchi di dati arbitrari di dimensioni arbitrarie potrebbero essere rappresentati da soli 128 bit senza alcuna perdita di informazioni. In questo modo avresti potuto ricostruire il messaggio originale da un numero di 128 bit indipendentemente dalla dimensione del messaggio originale.

Contrariamente a quanto enfatizzano le risposte più votate qui, la non iniettività (ovvero che ci sono più stringhe che hanno lo stesso valore) di una funzione di crittografia crittografica causata dalla differenza tra grande (potenzialmente infinito) dimensione dell'input e dimensione dell'output fisso non è il punto importante - in realtà, preferiamo le funzioni hash in cui tali collisioni avvengono il più raramente possibile.

Considera questa funzione (nella notazione di PHP, come la domanda): 

function simple_hash($input) {
     return bin2hex(substr(str_pad($input, 16), 0, 16));
}

Questo aggiunge alcuni spazi, se la stringa è troppo corta, quindi accetta i primi 16 byte della stringa, quindi la codifica come esadecimale. Ha le stesse dimensioni di output di un hash MD5 (32 caratteri esadecimali o 16 byte se omettiamo la parte bin2hex). 

print simple_hash("stackoverflow.com");

Questo produrrà: 

737461636b6f766572666c6f772e636f6d

Questa funzione ha anche la stessa proprietà di non iniettabilità evidenziata dalla risposta di Cody per MD5: possiamo passare stringhe di qualsiasi dimensione (purché si adattino al nostro computer) e produrrà solo 32 cifre esadecimali. Ovviamente non può essere iniettivo.

Ma in questo caso, è banale trovare una stringa che si associ allo stesso hash (basta applicare hex2bin sul tuo hash e ce l'hai). Se la tua stringa originale aveva la lunghezza 16 (come nel nostro esempio), otterrai anche questa stringa originale. Nulla di questo tipo dovrebbe essere possibile per MD5, anche se sai che la lunghezza dell'input era piuttosto breve (a parte provare tutti gli input possibili fino a quando non ne troviamo uno corrispondente, ad esempio un attacco a forza bruta).

I presupposti importanti per una funzione hash crittografica sono:

  • è difficile trovare una stringa che produca un determinato hash (resistenza preimage)
  • è difficile trovare una stringa diversa che produca lo stesso hash di una determinata stringa (seconda resistenza preimmagini)
  • è difficile trovare una coppia di stringhe con lo stesso hash (resistenza alle collisioni)

Ovviamente la mia funzione simple_hash non soddisfa nessuna di queste condizioni. (In realtà, se restringiamo lo spazio di input a "stringhe di 16 byte", allora la mia funzione diventa iniettiva, e quindi è persino provabile resistente al secondo preimage e resistente alle collisioni.)

Ora esistono attacchi di collisione contro MD5 (ad es. è possibile produrre una coppia di stringhe, anche con un dato prefisso, che hanno lo stesso hash, con un po 'di lavoro, ma non impossibile molto lavoro), quindi non dovresti usare MD5 per qualsiasi cosa critica. Non esiste ancora un attacco preimage, ma gli attacchi andranno meglio.

Per rispondere alla domanda effettiva:

  

Che cos'è queste funzioni che rendono il   stringhe risultanti impossibili da ripercorrere?

Ciò che MD5 (e altre funzioni hash si basano sulla costruzione Merkle-Damgard) fa effettivamente applicare un algoritmo di crittografia con il messaggio come chiave e un valore fisso come "testo semplice", usando il testo cifrato risultante come hash . (Prima di ciò, l'ingresso è riempito e diviso in blocchi, ciascuno di questi blocchi viene utilizzato per crittografare l'output del blocco precedente, XORed con il suo input per impedire calcoli inversi.)

I moderni algoritmi di crittografia (inclusi quelli utilizzati nelle funzioni hash) sono fatti in modo da rendere difficile il recupero della chiave, anche dato sia il testo in chiaro che il testo cifrato (o anche quando l'avversario ne sceglie uno). Lo fanno generalmente eseguendo molte operazioni di shuffle (bit shuffle) in modo che ciascun bit di output sia determinato da ciascun bit di chiave (più volte) e anche da ciascun bit di input. In questo modo puoi semplicemente ripercorrere facilmente ciò che accade dentro se conosci la chiave completa e l'input o l'output.

Per le funzioni hash simili a MD5 e un attacco preimage (con una stringa hash a blocco singolo, per semplificare le cose), hai solo input e output della tua funzione di crittografia, ma non la chiave (questo è quello che stai cercando per).

La risposta di Cody Brocious è quella giusta. A rigor di termini, non puoi "invertire". una funzione hash perché molte stringhe sono associate allo stesso hash. Si noti, tuttavia, che trovare una stringa che viene mappata su un determinato hash o trovare due stringhe che vengono mappate sullo stesso hash (ovvero una collisione ), sarebbero importanti innovazioni per un crittografo. La grande difficoltà di entrambi questi problemi è la ragione per cui le buone funzioni di hash sono utili nella crittografia.

MD5 non crea un valore hash univoco; l'obiettivo di MD5 è produrre rapidamente un valore che cambia in modo significativo in base a una modifica minore alla fonte.

Ad esempio, 

"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"

(Ovviamente non si tratta della crittografia MD5 effettiva)

Anche la maggior parte degli hash (se non tutti) sono non unici; piuttosto, sono abbastanza unici, quindi una collisione è altamente improbabile, ma ancora possibile.

Un buon modo di pensare a un algoritmo di hash è pensare di ridimensionare un'immagine in Photoshop ... dire che hai un'immagine che è di 5000x5000 pixel e poi ridimensionala a soli 32x32. Quello che hai è ancora una rappresentazione dell'immagine originale ma è molto più piccola e ha effettivamente "gettato via". alcune parti dei dati dell'immagine per adattarle alle dimensioni più piccole. Quindi, se dovessi ridimensionare l'immagine 32x32 fino a 5000x5000, tutto ciò che otterrai sarebbe un pasticcio sfocato. Tuttavia, poiché un'immagine 32x32 non è così grande sarebbe teoricamente concepibile che un'altra immagine possa essere ridimensionata per produrre esattamente gli stessi pixel!

Questa è solo un'analogia ma aiuta a capire cosa sta facendo un hash.

Una collisione di hash è molto più probabile di quanto si pensi. Dai un'occhiata al paradosso del compleanno per avere una maggiore comprensione del perché.

Poiché il numero di possibili file di input è maggiore del numero di output a 128 bit, è impossibile assegnare in modo univoco un hash MD5 a ciascuno di essi.

Le funzioni di hash crittografico vengono utilizzate per verificare l'integrità dei dati o le firme digitali (l'hash viene firmato per efficienza). La modifica del documento originale dovrebbe quindi significare che l'hash originale non corrisponde al documento modificato.

Questi criteri vengono talvolta utilizzati:

  1. Preimage resistenza: per una data funzione hash e data hash, dovrebbe essere difficile trovare un input che abbia l'hash data per quella funzione.
  2. Seconda resistenza preimage: per una data funzione e input di hash, dovrebbe essere difficile trovare un secondo, diverso, input con lo stesso hash.
  3. Resistenza alla collisione: per un dato ha funzione, dovrebbe essere difficile trovare due input diversi con lo stesso hash.

Questi criteri vengono scelti per rendere difficile la ricerca di un documento che corrisponda a un determinato hash, altrimenti sarebbe possibile falsificare i documenti sostituendo l'originale con uno corrispondente a quello dell'hash. (Anche se la sostituzione è incomprensibile, la semplice sostituzione dell'originale può causare interruzioni.)

Il numero 3 implica il numero 2.

In particolare per MD5, è stato dimostrato che è difettoso: Come rompere MD5 e altre funzioni hash .

Ma è qui che entrano in gioco i tavoli arcobaleno. Fondamentalmente è solo una grande quantità di valori con hash separati e quindi il risultato viene salvato su disco. Quindi il bit di inversione è " solo " per effettuare una ricerca in una tabella molto grande.

Ovviamente questo è possibile solo per un sottoinsieme di tutti i possibili valori di input ma se si conoscono i limiti del valore di input potrebbe essere possibile calcolarlo.

Lo scienziato cinese ha trovato un modo chiamato "collisioni del prefisso scelto". per creare un conflitto tra due stringhe diverse.

Ecco un esempio: http://www.win .tue.nl / HashClash / fastcoll_v1.0.0.5.exe.zip
Il codice sorgente: http://www.win.tue.nl/hashclash /fastcoll_v1.0.0.5_source.zip

Come molti hanno già detto, MD5 è stato progettato per lo streaming di flussi di dati a lunghezza variabile su un blocco di dati a lunghezza fissa, quindi un singolo hash è condiviso da molti flussi di dati di input.

Tuttavia, se hai mai avuto bisogno di scoprire i dati originali dal checksum, ad esempio se hai l'hash di una password e hai bisogno di scoprire la password originale, è spesso più veloce semplicemente google (o qualunque ricercatore preferisci ) l'hash per la risposta che per forzarla bruta. Ho scoperto con successo alcune password usando questo metodo.

Il modo migliore per capire cosa significano tutte le risposte più votate è in realtà provare a ripristinare l'algoritmo MD5. Ricordo di aver provato a ripristinare l'algoritmo MD5crypt alcuni anni fa, non per recuperare il messaggio originale perché era chiaramente impossibile, ma solo per generare un messaggio che avrebbe prodotto lo stesso hash dell'hash originale. Questo, almeno teoricamente, mi fornirebbe un modo per accedere a un dispositivo Linux che memorizzava l'utente: password nel file / etc / passwd usando il messaggio generato (password) invece di usare quello originale. Poiché entrambi i messaggi avrebbero lo stesso hash risultante, il sistema riconoscerebbe la mia password (generata dall'hash originale) come valida. Non ha funzionato affatto. Dopo diverse settimane, se ricordo bene, l'uso di sale nel messaggio iniziale mi ha ucciso. Ho dovuto produrre non solo un messaggio iniziale valido, ma un messaggio iniziale valido salato, che non sono mai stato in grado di fare. Ma la conoscenza che ho acquisito da questo esperimento è stata buona.

per definizione Funzione hash (crittografia hash): non dovrebbe essere invertibile, non dovrebbe avere collisioni (il meno possibile).

regd la tua domanda: è un modo hash. input (indipendentemente dalla lunghezza) genererà un output di dimensioni fisse (sarà riempito in base ad algo (limite di 512 bit per MD5)). Le informazioni sono compresse (perse) e praticamente non è possibile generare da trasformazioni inverse.

informazioni aggiuntive su MD5: è vulnerabile alle collisioni. esaminato di recente questo articolo, http://www.win.tue.nl/hashclash/Nostradamus/

apre il codice sorgente per le implementazioni di hash crypto (MD5 e SHA) può essere trovato nel codice Mozilla. (libreria freebl).

Ora un giorno gli hash MD5 o qualsiasi altro hash per quella materia sono pre-calcolati per tutte le stringhe possibili e memorizzati per un facile accesso. Sebbene in teoria MD5 non sia reversibile, ma usando tali database potresti scoprire quale testo ha prodotto un particolare valore di hash.

Ad esempio, prova il seguente codice hash su http://gdataonline.com/seekhash.php per scoprire quale testo ho usato per calcolare l'hash 

aea23489ce3aa9b6406ebb28e0cda430

f (x) = 1 è irreversibile. Le funzioni hash non sono irreversibili.

Questo è in realtà richiesto per svolgere la loro funzione di determinare se qualcuno possiede una copia non corrotta dei dati con hash. Questo porta suscettibilità agli attacchi di forza bruta, che sono abbastanza potenti in questi giorni, in particolare contro MD5.

C'è anche confusione qui e altrove tra le persone che hanno una conoscenza matematica ma una conoscenza poco criptica. Numerosi cifrari semplicemente XORano i dati con il flusso di chiavi, e quindi potresti dire che un testo cifrato corrisponde a tutti i testi in chiaro di quella lunghezza perché avresti potuto usare qualsiasi flusso di chiavi.

Tuttavia, questo ignora che un ragionevole testo in chiaro prodotto dal seme password è molto, molto più probabile di un altro prodotto dal seme Wsg5Nm ^ bkI4EgxUOhpAjTmTjO0F! VkWvysS6EEMsIJiTZcvsh @ WI $ IHK TYqiW! % & amp; Ue & amp; nk55ak% BX% 9! NnG% 32ftud% YkBO $ U6o nella misura in cui qualcuno che afferma che la seconda era una possibilità verrebbe deriso.

Allo stesso modo, se stai cercando di decidere tra le due potenziali password password e Wsg5Nm ^ bkI4EgxUO , non è così difficile da fare come farebbero alcuni matematici hai creduto.

Mi piacciono tutti i vari argomenti. È ovvio che il vero valore dei valori con hash è semplicemente quello di fornire segnaposto illeggibili per stringhe come le password. Non ha alcun vantaggio specifico in termini di sicurezza. Supponendo che un utente malintenzionato abbia ottenuto l'accesso a un tavolo con password con hash, può:

  • Hash una password di sua scelta e inserire i risultati nella tabella delle password se ha diritti di scrittura / modifica della tabella.
  • Genera valori con hash delle password comuni e verifica l'esistenza di valori con hash simili nella tabella delle password.

In questo caso le password deboli non possono essere protette dal semplice fatto che sono state hash.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top