Come funzionano le funzioni hash unidirezionali?(Modificato)

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

Domanda

Ho letto l'articolo di Wikipedia sugli hash MD5 ma ancora non riesco a capire come un hash non possa essere "ricostituito" nel testo originale.

Qualcuno potrebbe spiegare a qualcuno che sa molto poco di crittografia come funziona?Quale parte della funzione lo rende unidirezionale?

È stato utile?

Soluzione

Dal momento che tutti fino ad ora è semplicemente definito quello che una funzione di hash è stato, sarò morso.

Una funzione a senso unico non è solo una funzione di hash - una funzione che perde le informazioni - ma un f funzione per la quale, data un'immagine y ( "SE" o 294 nelle risposte già esistenti), è difficile da trovare un pre-immagine x tale che f(x)=y.

Questo è il motivo per cui essi sono chiamati a senso unico:. È possibile calcolare un'immagine, ma non riesci a trovare un pre-immagine per una data immagine

Nessuno dei funzione hash ordinaria proposto fino ad ora nelle risposte esistenti hanno questa proprietà. Nessuno di loro sono a senso unico funzione crittografica di hash. Per esempio, dato "SE", si può facilmente raccogliere l'ingresso "SXXXE", un ingresso con la proprietà che X-encode ( "SXXXE") = SE.

Non ci sono funzioni di "semplici" a senso unico. Essi devono mescolare i loro ingressi così bene che non solo non si riconosce l'ingresso a tutti in uscita, ma non si riconosce un altro ingresso sia.

SHA-1 e MD5 usato per essere popolari funzioni unidirezionali ma sono entrambi quasi rotti (specialista sa come creare pre-immagini per determinate immagini, o sono quasi in grado di farlo). C'è un concorso in corso per scegliere un nuovo standard, che prenderà il nome di SHA 3 .

Un approccio ovvio per invertire una funzione unidirezionale sarebbe quello di calcolare molte immagini e tenerli in una tabella che associa ad ogni immagine pre-immagine che lo ha prodotto. Per rendere ciò impossibile in pratica, tutta la funzione unidirezionale ha una grande uscita, di almeno 64 bit ma possibilmente molto più grandi (fino a, diciamo, 512 bit).

EDIT: Come funzionano le funzioni di hash crittografici più

Di solito hanno al loro centro una singola funzione che complicato trasformazioni su un blocco di bit (un cifratura a blocchi ). La funzione dovrebbe essere quasi biunivoca (non dovrebbe mappare troppe sequenze alla stessa immagine, perché ciò causare difetti dopo), ma non deve essere esattamente biunivoca. E questa funzione viene iterata un numero fisso di volte, abbastanza per fare l'ingresso (o l'eventuale ingresso) impossibile riconoscere.

Prendiamo l'esempio di Matassa , uno dei candidati forti per il contesto SHA-3. La sua funzione principale è iterata 72 volte. L'unico numero di iterazioni per cui i creatori della funzione sanno talvolta relazionare le uscite per alcuni input è 25. Essi affermano che abbia un "fattore di sicurezza" di 2,9.

Altri suggerimenti

Pensate ad un hash veramente di base - per la stringa di input, restituire la somma dei valori ASCII di ogni personaggio. 

hash( 'abc' ) = ascii('a')+ascii('b')+ascii('c')
              = 97 + 98 + 99
              = 294

Ora, dato il valore hash di 294, si può dire che cosa la stringa originale era? Ovviamente no, perche 'abc' e 'CBA' (e innumerevoli altri) dare lo stesso valore di hash.

funzione crittografica di hash funzionano allo stesso modo, tranne che, ovviamente, l'algoritmo è molto più complessa. Ci sono sempre sarà collisioni, ma se si sa stringa s hash per h, allora dovrebbe essere molto difficile ( "computazionalmente impossibile") per costruire un'altra stringa che hash anche h.

Qui si cerca una semplice analogia anziché una spiegazione complessa.

Per cominciare, suddividiamo l'argomento in due parti, operazioni unidirezionali e hashing.Che cos'è un'operazione unidirezionale e perché dovresti volerne una?

Le operazioni unidirezionali sono chiamate così perché non sono reversibili.La maggior parte delle operazioni tipiche come l'addizione e la moltiplicazione possono essere invertite mentre la divisione del modulo non può essere invertita.Perché è importante?Perché si desidera fornire un valore di output che 1) è difficile da duplicare senza gli input originali e 2) non fornisce alcun modo per capire gli input dall'output.

Reversibile

Aggiunta: 

4 + 3 = 7

Questo può essere invertito prendendo la somma e sottraendo uno degli addendi

7 - 3 = 4

Moltiplicazione:

4 * 5 = 20

Questo può essere invertito prendendo il prodotto e dividendolo per uno dei fattori

20 / 4 = 5

Non reversibile

Divisione modulo:

22 % 7 = 1

Questo non può essere invertito perché non esiste alcuna operazione che si possa fare sul quoziente e sul dividendo per ricostituire il divisore (o viceversa).

Riesci a trovare un'operazione per compilare dove "?" È? 

1  ?  7 = 22  
1  ?  22 = 7

Detto questo, le funzioni hash unidirezionali hanno la stessa qualità matematica della divisione modulo.

Perché questo è importante?

Diciamo che ti ho dato la chiave di un armadietto in un terminal degli autobus che ha mille armadietti e ti ho chiesto di consegnarlo al mio banchiere.Essendo il ragazzo intelligente che sei, per non dire sospettoso, guarderesti immediatamente la chiave per vedere quale numero di armadietto è scritto sulla chiave.Sapendo questo, ho fatto alcune cose subdole;prima ho trovato due numeri che divisi utilizzando la divisione modulo mi danno un numero compreso tra 1 e 1000, secondo ho cancellato il numero originale e ci ho scritto sopra il divisore della coppia di numeri, secondo ho scelto un capolinea dell'autobus che abbia un guardia che protegge gli armadietti dai malintenzionati permettendo alle persone di provare solo un armadietto al giorno con la loro chiave, terzo il banchiere conosce già il dividendo quindi quando ottiene la chiave può fare i conti e capire il resto e sapere quale armadietto aprire.

Se scelgo oculatamente gli operandi posso avvicinarmi ad una relazione biunivoca tra quoziente e dividendo che obbliga a provare ogni locker perché la risposta distribuisce i risultati dei possibili input nell'intervallo di numeri desiderati, i locker disponibile nel terminale.Fondamentalmente significa che non puoi acquisire alcuna conoscenza del resto anche se conosci uno degli operandi.

Quindi ora posso 'fidarmi' che tu consegni la chiave al legittimo proprietario senza preoccuparti che tu possa facilmente indovinare a quale armadietto appartiene.Certo, potresti perquisire con la forza bruta tutti gli armadietti, ma ci vorrebbero quasi 3 anni, un sacco di tempo perché il mio banchiere potesse usare la chiave e svuotare l'armadietto.

Vedi le altre risposte per maggiori dettagli sulle diverse funzioni hash.

Ecco un esempio molto semplice. Presumo che io sono un crittografo inizio e creo una funzione di hash che fa il seguente: 

int SimpleHash(file) {
    return 0 if file.length is even;
    return 1 if file.length is odd;
}

Ora qui è la prova. SimpleHash(specialFile) è 0. Qual è stato il mio file originale?

Ovviamente, non c'è modo di sapere (anche se si potrebbe probabilmente trovare abbastanza facilmente che il mio hash si basa sulla lunghezza del file). Non v'è alcun modo per "ricostituire" il mio file in base al hash perché l'hash non contiene tutto ciò che ha fatto il mio file.

Un hash è un (molto) codifica lossy.

Per darvi un esempio più semplice, immaginate un fittizio 2 lettere codifica di un 5 lettere parola chiamata X-codifica. L'algoritmo per la X-codifica è semplice:. Prendere la prima e l'ultima lettera della parola 

X-encode( SAUCE ) = SE
X-encode( BLOCK ) = BK

Chiaramente, non è possibile ricostruire sugo sua codifica SE (assumendo la gamma di possibili ingressi viene tutte le parole di 5 lettere). La parola potrebbe facilmente essere SPAZIO.

Per inciso, il fatto che la salsa e spazio sia producono SE come una codifica è chiamato collisione , e si può vedere che la X-ecoding non farebbe una buona hash. :)

In termini semplici, una funzione hash funziona creando un gran pasticcio di dati di input.

Vedere MD5 ad esempio.Elabora i dati di input tramite blocchi da 512 bit.Ogni blocco è suddiviso in 16 parole da 32 bit.Sono presenti 64 passi, ciascuno dei quali utilizza una delle 16 parole di ingresso.Quindi ogni parola viene utilizzata quattro volte nel corso dell'algoritmo.Ecco da dove deriva l’unilateralità:qualsiasi bit di input viene immesso in più punti e tra due di questi input la funzione mescola insieme tutti i dati correnti in modo che ciascun bit di input influenzi la maggior parte dello stato di esecuzione a 128 bit.Ciò impedisce di invertire la funzione o calcolare una collisione osservando solo una parte dei dati.Devi considerare tutti i 128 bit e lo spazio dei blocchi da 128 bit è troppo ampio per essere attraversato in modo efficiente.

Ora MD5 non fa un buon lavoro, poiché è possibile trovare collisioni per quella funzione.Dal punto di vista del crittografo, MD5 è una funzione di crittografia ruotata.L'elaborazione di un blocco di messaggi M (512 bit) utilizza uno stato di ingresso V (un valore di 128 bit) e calcola il nuovo stato V' come V' = V + E(M, V) dove '+' è una parola- saggia aggiunta, e "E" sembra essere una funzione di crittografia simmetrica (nota anche come "cifratura a blocchi") che utilizza M come chiave e V come messaggio da crittografare.Da uno sguardo più attento, E can è una sorta di "rete Feistel estesa", simile al cifrario a blocchi DES, con quattro quarti invece di due metà.I dettagli non sono importanti qui;il mio punto è che ciò che rende una funzione hash "buona", tra le funzioni hash che utilizzano quella struttura (chiamata "Merkle-Damgård"), è simile a ciò che rende "sicuro" un codice a blocchi.Gli attacchi di collisione riusciti contro MD5 utilizzano la crittoanalisi differenziale, uno strumento progettato innanzitutto per attaccare i codici a blocchi.

Da un buon codice a blocchi a una buona funzione hash, c'è un passaggio che non deve essere ignorato.Con la struttura Merkle-Damgård, la funzione hash è sicura se il cifrario a blocchi sottostante è resistente agli "attacchi con chiave correlata", una proprietà piuttosto oscura contro la quale i cifrari a blocchi sono raramente rafforzati perché, per la crittografia simmetrica, gli attacchi con chiave correlata difficilmente hanno alcun valore pratico. impatto.Ad esempio, la crittografia AES si è rivelata non così resistente agli attacchi delle chiavi come si sarebbe potuto sperare, e ciò non ha scatenato il panico generale.Tale resistenza non rientrava tra le proprietà ricercate al momento della progettazione dell'AES.Impedisce semplicemente di trasformare l'AES in una funzione hash.Esiste una funzione hash chiamata Whirlpool, che si basa su un derivato di Rijndael, "Rijndael" è il nome iniziale di quello che divenne AES;ma Whirlpool si prende cura di modificare le parti di Rijndael che sono deboli ai relativi attacchi chiave.

Inoltre, esistono altre strutture che possono essere utilizzate per creare una funzione hash.Le attuali funzioni standard (MD5, SHA-1 e la famiglia "SHA-2", ovvero SHA-224, SHA-256, SHA-384 e SHA-512) sono funzioni Merkle-Damgård, ma molte di quelle potenziali i successori no.È in corso un concorso, organizzato dal NIST (l'organizzazione federale statunitense che si occupa di questo genere di cose), per selezionare una nuova funzione hash standard, denominata "SHA-3".Vedere questa pagina per dettagli.Al momento, sono scesi a 14 candidati dai 51 iniziali (senza contare una dozzina extra che non hanno superato il test amministrativo di invio di una presentazione completa con codice compilato e eseguito correttamente).

Diamo ora uno sguardo più concettuale.Una funzione hash sicura dovrebbe assomigliare a a oracolo casuale:un oracolo è una scatola nera che, quando viene dato un messaggio M come input, restituisce una risposta h(M) che viene scelto casualmente, uniformemente, nello spazio di output (cioèTutto N-bit stringhe se la lunghezza dell'output della funzione hash è N).Se viene dato lo stesso messaggio M ancora una volta come input, l'oracolo restituisce lo stesso valore di prima.A parte questa restrizione, l'output dell'oracolo su un input non utilizzato in precedenza M è imprevedibile.Si può immaginare l'oracolo come un contenitore per uno gnomo che lancia i dadi e registra attentamente i messaggi di input e i corrispondenti output in un grande libro, in modo da onorare il suo contratto di oracolo.Non c'è modo di prevedere quale sarà il prossimo risultato poiché lo gnomo stesso non lo sa.

Se esiste un oracolo casuale, invertire la funzione hash ha un costo 2^n:per avere un dato output, non esiste strategia migliore dell'utilizzo di messaggi di input distinti finché non si ottiene il valore atteso.A causa della selezione casuale uniforme, la probabilità di successo è 1/(2^n) ad ogni tentativo, e il numero medio di richieste allo gnomo lancia-dadi sarà 2^n.Per le collisioni (trovare due input distinti che producono lo stesso valore hash), il costo è di circa *1,4*2^(n/2)* (in parole povere, con *1,4*2^(n/2)* output, possiamo riunirsi su 2^n coppie di output, ciascuna avente una probabilità di 1/(2^n) di corrispondenza, cioèavere due ingressi distinti che hanno lo stesso output).Queste sono le cose migliori che si possono fare con un oracolo casuale.

Pertanto, cerchiamo funzioni hash che siano valide quanto un oracolo casuale:devono mescolare i dati di input in modo tale che non possiamo trovare una collisione in modo più efficiente di quanto costerebbe invocare semplicemente la funzione 2^(n/2) volte.La rovina della funzione hash è la struttura matematica, ad es.scorciatoie che consentono all'aggressore di visualizzare lo stato interno della funzione hash (che è almeno grande N bit) come variazione di un oggetto matematico che vive in uno spazio molto più breve.30 anni di ricerca pubblica sui sistemi di crittografia simmetrici hanno prodotto tutto un armamentario di nozioni e strumenti (diffusione, valanga, differenziali, linearità...) che possono essere applicati.Il punto, tuttavia, è che non abbiamo prove che un oracolo casuale possa effettivamente esistere.Noi Volere una funzione hash che non può essere attaccata.Cosa noi Avere sono candidati alla funzione hash, per i quali attualmente non è previsto alcun attacco conosciuto, e, meglio ancora, abbiamo alcune funzioni per le quali Alcuni È possibile dimostrare che i tipi di attacco non funzionano.

C'è ancora qualche ricerca da fare.

array
 Con un po 'strabico, gli array associativi assomigliano molto hash. Le principali differenze erano la mancanza del simbolo% sui nomi hash, e che si poteva assegnare solo a loro un tasto alla volta. Così, si direbbe $foo{'key'} = 1;, ma solo @keys = keys(foo);. funzioni familiari come ogni, chiavi e valori lavorato come fanno ora (e cancellare è stata aggiunta in Perl 2).

Perl 3 aveva tre tipi di dati interi: aveva il simbolo% sui nomi di hash, ha permesso un intero hash per essere assegnato a un tratto, e ha aggiunto dbmopen (ora deprecato a favore della cravatta). Perl 4 utilizzati chiavi hash separati da virgole emulare array multidimensionali (che sono ora meglio trattate con riferimenti ad array).

Perl 5 ha preso il salto gigante di riferirsi a array associativi come hash. (Per quanto ne so, è la prima lingua ad aver di cui la struttura dei dati in tal modo, piuttosto che "hash table" o qualcosa di simile.) Un po 'ironicamente, ma ha anche spostato il relativo codice da hash.c in hv.c.

nomenclatura
Dizionari, come spiegato in precedenza, sono collezioni non ordinate di valori indicizzati da chiavi univoche. Essi sono a volte chiamati array associativi o mappe. Essi possono essere implementate in vari modi, uno dei quali è quello di utilizzare una struttura dati nota come una tabella hash (e questo è ciò che Perl si riferisce come una hash).

l'uso del Perl del termine "hash" è la fonte di un certo potenziale confusione, perché l'uscita di una funzione di hashing viene a volte chiamato anche un hash (soprattutto in contesti crittografici), e perché le tabelle hash non sono di solito chiamato hash ovunque il resto.

Per essere sul sicuro, fare riferimento alla struttura dati come una tabella hash, e usano il termine "hash" solo in ovvie, contesti Perl-specifici.

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