Come può essere imansible “decifrare” un hash MD5?

Possibile duplicato:
Come mai i valori hash MD5 non sono reversibili?

Stavo leggendo una domanda su MD5 e mi ha fatto ricordare qualcosa che mi fa impazzire. Domanda molto semplice, e mi dispiace se non è buona. Non riesco a capire come si converte qualcosa in una cosa usando un algoritmo, e non c’è modo di riconvertirlo usando l’algoritmo al contrario.

Quindi, come è ansible?

Inoltre, poiché più stringhe possono creare lo stesso hash MD5, a causa della minore quantità di dati rispetto alla stringa di input, come sarebbe meglio qualsiasi altro sistema di hashing?

Fondamentalmente è perché l’output di MD5 contiene meno informazioni dell’input. Questo è fondamentalmente ciò che distingue un algoritmo hash da un algoritmo di crittografia.

Ecco un semplice esempio: immagina un algoritmo per calcolare l’hash di un numero di 10 cifre. L’algoritmo è “restituisce le ultime 2 cifre”. Se prendo l’hash di 8023798734, ottengo 34, ma se tutto ciò che hai è il 34, non avresti modo di dire quale sia il numero originale perché l’algoritmo di hashing ha scartato 8 cifre di informazioni. È simile a MD5, tranne per il fatto che l’hash è calcolato tramite una procedura complessa invece di tagliare solo una parte dei dati.

Allora, come può un hash essere migliore di un altro? Per prima cosa, diversi algoritmi di hash possono essere più o meno resistenti alle collisioni (quando due input producono lo stesso output). La probabilità di una collisione è inversamente correlata al numero di possibili output hash. Le collisioni sono una caratteristica indesiderabile degli hash perché se i tuoi dati cambiano, vuoi cambiare anche l’hash, quindi un modo per ottenere un algoritmo hash migliore è usare un hash con più output possibili. Nell’esempio delle cifre sopra, prendendo le ultime 4 cifre anziché le ultime 2 cifre si riduce la probabilità di una collisione con un determinato hash (tecnicamente chiamato preimage ) a 1 su 10000 invece di 1 su 100, quindi è più probabile che tutto il I numeri a 10 cifre in qualsiasi set avrai diversi valori hash.

C’è anche il problema della sicurezza crittografica. Quando si desidera utilizzare un hash per assicurarsi che alcuni dati non vengano manomessi, è auspicabile che chi sta effettuando la manomissione non possa prevedere quali input genereranno un determinato output. Se potessero, sarebbero in grado di alterare i dati di input in modo tale che l’output (l’hash) rimanga lo stesso. Tornando all’esempio delle cifre, diciamo che ti invierò un’email con il numero 1879483129 ed è di fondamentale importanza che questo numero ti rimanga inalterato. Potrei chiamarti e dirti l’hash del numero, che sarebbe 29, ma dato che l’algoritmo “ultime 2 cifre” non è crittograficamente sicuro, un hacker malvagio potrebbe cambiare il numero lungo il percorso per, ad esempio, 5555555529 e non vorresti conosco la differenza

È stato dimostrato che MD5 non è crittograficamente sicuro (e anche SHA-1 è compromesso ). Ciò significa che è ansible trovare input diversi che corrispondono a qualsiasi dato output. È ancora un buon algoritmo per proteggersi da bit di bit casuali e simili, ma se c’è una possibilità che qualcuno possa voler intenzionalmente corrompere i tuoi dati, dovresti usare qualcosa di più sicuro, come SHA-256 o superiore, probabilmente come parte di un HMAC schema .

Non riesco a capire come si converte qualcosa in una cosa usando un algoritmo, e non c’è modo di riconvertirlo usando l’algoritmo al contrario.

Puoi trasformare una mucca in un hamburger, ma non puoi trasformare l’hamburger in una mucca.

La trasformazione riduce i dati esistenti distruggendoli e tali dati non possono essere ripristinati.

Ecco un parallelo:

Aggiungi le età di tutti nella tua famiglia. Conserva solo le ultime due cifre.

Ora dimmi l’età di tutti in base a quel numero.

Pensaci:

Ho una stringa numerica, diciamo che è “12345678”.

Ho un algoritmo di hash, restituisce solo la sum di tutti i numeri singoli, chiamiamola f ()

quindi, f (“12345678”) = 1 + 2+ .. + 8 = 36.

Quindi la domanda:

noto f (x) = 36, è ansible ottenere il valore originale di x?

Non possiamo, perché f () è un algoritmo che causa la perdita di informazioni.

L’MD5 è un algoritmo hash come f (), ma molto più complesso.

Ecco una risposta semplice …

Esistono un numero finito di valori hash e un numero infinito di valori di testo in chiaro.

Pertanto, invertendo un dato hash MD5 si otterrebbe un numero infinito di possibili valori di testo in chiaro.

In risposta alla seconda parte della domanda (una risposta alla prima parte è stata più che adeguatamente data da altri sopra): MD5 è considerato debole a causa delle prove degli attacchi contro il cifrario (cioè, i cambiamenti che possono essere fatti nella pianura -testo che non comporta cambiamenti nella sum MD5). Altre tecniche di hashing potrebbero non essere facilmente suscettibili a collisioni hash essenzialmente arbitrarie (almeno tali collisioni arbitrarie non sono ancora state dimostrate possibili con l’insieme di hash SHA-2, e quindi, un attaccante è meno probabilità di essere in grado di replicare un hash hash in una tecnica non MD5 (teoricamente, naturalmente, gli attacchi di collisione hash sono possibili contro qualsiasi funzione di hashing, altrimenti non funzionerebbe come funzione di hashing se non fosse così; con quanta facilità un attacker può riuscire a “fingere” un testo in chiaro “corretto”, cioè uno che esegue lo hash allo stesso valore di hash).

Per inciso, la sum MD5 di un testo in chiaro non è necessariamente sicura perché contiene “meno” dati o è “lossy”, ma perché, da un testo in chiaro arbitrario, calcola un valore-sum all’interno di un intervallo fisso (per i testi in chiaro <128 bit, la somma MD5, infatti, contiene più informazioni rispetto al testo in chiaro ...), e quindi un numero (teoricamente infinito) di testo in chiaro potrebbe allinearsi allo stesso hash MD5.

Hmm, non essere scortese, ma mi sembra che tutte le risposte su “meno informazioni che escono che entrare” mancano il punto.

L’uso principale di MD5 e codici hash crittografici simili è quello di crittografare le password. In tal caso, non mi interessa se sia ansible ribuild la stringa originale. Tutto quello che mi interessa è se posso build qualsiasi stringa che abbia hash allo stesso valore.

Prendiamo un esempio semplificato: supponiamo che il nostro algoritmo di hash fosse “prendi le ultime due cifre”. Quindi se la mia password è “12345678”, il codice hash è “78”. C’è un modo per passare da “78” a “12345678”? No. Ma se sto hackerando le password, non mi interessa se so quale sia la tua password originale. Voglio solo una password per farmi entrare. Quindi se sapessi che questo era l’algoritmo, direi fantastico, userò la password “99978”. Ha hash su “78”, quindi l’algoritmo di convalida della password lo supererà, e io ci sto.

Ovviamente MD5 è molto più difficile da invertire, anche in questo senso “tutto ciò che avrà un hash al valore giusto”, quindi un algoritmo semplicistico come “prendi le ultime due cifre”. Ma è letteralmente imansible? Anche questo mi imbarazza. Così sicuro, le informazioni vengono scartate lungo il percorso. Ma non potrei invertire ad un valore “qualsiasi”, inserendo qualsiasi valore casuale in qualsiasi punto in cui le informazioni vengono scartate? Non ho guardato l’algoritmo attuale per MD5. Presumo che non sia qualcosa di facile da decifrare, come cambiare tutti i vantaggi con i minuti o qualcosa di banale come quello, o qualcuno lo avrebbe fatto molto tempo fa. Dal fatto che ci sono milioni di hacker là fuori che hanno provato a rompere questo, anche se è teoricamente ansible, deve essere incredibilmente difficile.

Si consideri la seguente funzione: f (x) = x x. Ora, dato che conosci f (x) = 25, cos’è x? Bene, la risposta potrebbe essere 5 o la risposta potrebbe essere -5. Non è ansible recuperare l’input in f, perché esiste un valore nell’intervallo di f tale che più di un elemento del dominio di f si mapperà a quel valore sotto f. Di conseguenza, la funzione f non è invertibile. Lo stesso concetto si applica a MD5; ci sono più input per l’algoritmo MD5 che, nonostante siano input diversi, producono come risultato lo stesso valore di hash. In altre parole, l’algoritmo MD5, come f (x) = x x, non è uno-a-uno e quindi non è una funzione invertibile.

Tuttavia, ciò non significa che non è ansible ripristinare l’input su un MD5. Significa semplicemente che non è ansible ripristinare l’input e MD5 con certezza del 100%. Per renderlo più concreto, vediamo di nuovo la funzione f (x) = x * x. Ora, cosa succede se ti dicessi che per ogni dato input per la probabilità che sia positivo è del 99%? In tal caso, potresti fare un’ipotesi che un hash di 25 provenga da un valore di 5 e non da -5. Questo è, in effetti, il modo in cui le persone sono in grado di interrompere le funzioni hash (incluso MD5, che risulta essere una funzione hash crittografica molto buona). Quando si tratta di password, ci sono alcune password che vengono utilizzate molto più frequentemente rispetto ad altre password. Tutto quello che devi fare è prendere l’MD5 di quelle password e confrontarlo con un hash, e se corrispondono, allora è un’ipotesi abbastanza ragionevole che provenga da quella password.

Potresti anche essere interessato a leggere le funzioni one-to-one , le funzioni Injective , le funzioni hash crittografiche , MD5 , SHA1 e Do not Hash Secrets dal blog Benlog Security .

Inoltre, poiché più stringhe possono creare lo stesso hash MD5, a causa della minore quantità di dati rispetto alla stringa di input, come sarebbe meglio qualsiasi altro sistema di hashing?

È noto un attacco contro MD5 che consente all’hacker di creare più documenti con contenuti diversi, ma lo stesso hash MD5. Questo attacco è computazionalmente fattibile, e come dimostrazione, è stato usato per “prevedere” il risultato di un’elezione presidenziale. (L’attaccante ha pubblicato un hash prima delle elezioni, poi ha rivelato un documento con quell’hash che indicava il nome del vincitore, ma in realtà l’autore dell’attacco aveva un documento per ogni candidato, il tutto con lo stesso hash.)

Un sistema migliore fornirebbe una garanzia crittografica, che è computazionalmente intrattabile per creare due documenti distinti con hash allo stesso valore. SHA-1 può essere un tale sistema.

Un sistema ancora peggiore consentirebbe un attacco in base al quale l’accesso a qualsiasi hash è ansible, è ansible creare un documento con quell’hash. Il venerabile sistema CRC, che è ancora utilizzato in molti sistemi hardware (pensa Ethernet), è vulnerabile a questo attacco. Come MD5, è una funzione di hash in cui l’output non è ricostruibile dall’input, ma dato qualsiasi output, è banale build un documento con una data firma CRC-32 o CRC-64. Peggio ancora, puoi inserire qualsiasi testo che ti piace in tale documento, quindi ottenere il CRC che desideri semplicemente aggiungendo della spazzatura alla fine.

Non è un caso che CRC-32 possa essere calcolato molto rapidamente, MD5 richiede molto più tempo e SHA-1 richiede un po ‘più di tempo. Sia i modelli di costo che i modelli di fiducia sono difficili.

Una funzione di hash davvero buona sarebbe veloce da calcolare come CRC e difficile da build due hashing di documenti con lo stesso valore di SHA-1. Non trattenere il respiro …

Inoltre, poiché più stringhe possono creare lo stesso hash MD5, a causa della minore quantità di dati rispetto alla stringa di input, come sarebbe meglio qualsiasi altro sistema di hashing?

Se è vero che devono esistere più messaggi (anche infiniti) che hanno lo stesso hash, l’objective di un hash crittografico è rendere imansible trovare tali collisioni.

Potresti pensare che si possano trovare collisioni semplicemente calcolando gli hash dei messaggi casuali fino a quando non ottieni lo stesso risultato due volte. Tuttavia, starebbe sottovalutando la dimensione dello spazio dei possibili valori hash.

Per MD5, la dimensione dell’hash è di 128 bit. Lo spazio a 128 bit è, per parafrasare Douglas Adams, grande. Veramente grande. Semplicemente non crederai a quanto sia enormemente incredibilmente grande. Il numero di possibili hash è 2 128 o 3.40282367 × 10 38 . Questo è un 34 seguito da 37 zero! Se potessi contare fino a un trilione in un secondo, ti richiederebbero ancora 10 miliardi di millenni per contare attraverso tutti i numeri a 128 bit.

Tuttavia, alcuni algoritmi di hash come MD5 hanno punti deboli che consentono agli aggressori di invertire la rotta (cioè trovare un messaggio con un determinato hash) con uno sforzo significativamente inferiore rispetto ai soli tentativi di forza bruta. MD5 è considerato completamente rotto in questo senso.

Essenzialmente, le operazioni di bit implicate significano che l’inversione sarebbe tecnicamente imansible. Al fine di build un insieme di output, si richiederebbe una folle complessità temporale e un’enorme complessità della memoria. Non è assolutamente imansible – ma non deve essere, solo oltre il potere dei nostri migliori supercomputer di un miglio.

La maggior parte delle risposte non colpisce il vero punto della domanda: le trasformazioni di hashing non sono lineari , e come tali sono molto difficili (ma non impossibili, dato abbastanza potere e tempo di calcolo) da invertire.

Pensa alla difficoltà relativa di quadrare un numero e ottenere la radice quadrata. Aggiungete a ciò che avete solo informazioni parziali e tutti i bit mancanti sono importanti per fornire la risposta corretta (non come nell’esempio di ritaglio di un numero).

Se dopo tutto non sei ancora sicuro, prova da solo a invertire i passaggi di MD5 o qualsiasi altra funzione di hash crittografica 😉

L’entropia della stringa aumenta, poiché alcune informazioni vengono perse durante il processo di hashing. Ciò significa che non ci sono abbastanza informazioni disponibili per ribuild la stringa originale.