Come funziona lhashing?

Le funzioni hash crittografiche sono oggetti matematici che possono essere descritti come “un grande miscuglio e rimescolamento di alcuni bit “. Prendono come input una sequenza di bit (possibilmente molto lunga) e offrono un output di dimensione fissa. In parole povere, sono così aggrovigliati che sebbene non ci sia nulla di segreto in loro (questo è solo un codice deterministico), nessuno può capire come “invertirli” (trovare un input corrispondente per un dato output) se non con il metodo di base chiamato “fortuna”: prova input casuali fino a trovare una corrispondenza.

Come può accadere, scientificamente, che le funzioni hash possano esistere è una buona domanda .

Lhashing non è una crittografia . Non ci sono segreti, né chiavi nellhashing.

Le funzioni hash hanno molti usi; uno di questi è “archiviazione password”. Una funzione hash sembra una buona cosa per larchiviazione delle password. Non vogliamo memorizzare le password direttamente (altrimenti unoccasionale sbirciatina nei nostri database da parte dellaggressore gli darebbe troppe informazioni; vedi questo post del blog per una discussione) ; vogliamo memorizzare i token di verifica della password : qualcosa che consente la verifica di una password (che lutente presenta) ma non rivela la password stessa. Quindi lidea è: memorizziamo lhash della password. Quando una password deve essere verificata, calcoliamo semplicemente il suo hash e vediamo se corrisponde al valore memorizzato. Ma indovinare la password solo dal valore hash è difficile, poiché la funzione hash è resiliente contro l “inversione” (vedi sopra).

Poiché le password sono un tipo speciale di dati (cioè dati che gli esseri umani possono ricordare), per una corretta sicurezza, abbiamo bisogno di un “rafforzamento” funzione hash:

• Vogliamo una funzione hash molto lenta .
• Non vogliamo una funzione hash, ma molte funzioni hash distinte, in modo che ogni password venga sottoposta ad hashing con la propria funzione hash; si tratta di scoraggiare gli attacchi paralleli. Questo processo di trasformazione di una singola funzione hash in molte varianti è chiamato salting .

Vedi questa risposta per una trattazione approfondita del tema dellhashing delle password.

Commenti

• Scusa ma sebbene la tua risposta fosse estremamente esauriente e ben composta, ho trovato laltra risposta per essere più simile a quello che stavo cercando.

Lhashing è una funzione di alcuni stringa di bit (di solito di lunghezza variabile) su unaltra stringa di bit (di solito più piccola e di lunghezza fissa).

Lhashing viene utilizzato nei database per il recupero dei dati e nelle strutture di dati in memoria chiamate tabelle hash. Ci consente di ridurre dati arbitrari, come una stringa di caratteri o un oggetto complicato con molti campi, a un numero binario che può quindi essere utilizzato direttamente come indice in un array sparso per recuperare i dati associati (con alcuni dettagli per la gestione dellhash collisioni).

Le funzioni di hashing usate nel modo sopra sono “cugine” delle funzioni di hashing crittografiche. Sono progettati per esigenze diverse. Devono essere veloci da calcolare e ottenere una buona distribuzione.

Nellelaborazione sicura, gli hash crittografici vengono utilizzati per digerire i dati in una piccola stringa di bit rappresentativa. Le funzioni crittografiche hanno requisiti diversi. Sono progettati per essere difficili da invertire (per essere funzioni “botola” o “senso unico”). Non solo, ma un requisito importante è che deve essere difficile trovare, per un dato testo in chiaro e valore hash, un altro testo in chiaro che produca lo stesso hash.

Lhashing può essere utilizzato non solo per le password, ma come checksum per verificare lintegrità dei dati e come parte dellimplementazione delle firme digitali. Per firmare digitalmente un documento di grandi dimensioni, dobbiamo semplicemente eseguire lhash del documento per produrre un “digest” (un nome utilizzato per loutput di una funzione di hashing, quando viene eseguito lhashing di qualcosa di molto lungo). Quindi solo questo digest viene inserito nel sistema crittografico a chiave pubblica per produrre una firma. Puoi vedere la debolezza lì: cosa succede se un attaccante riesce a produrre un documento che ha lo stesso digest? Quindi sembra che la firma originale prodotta sul documento autentico sia in realtà una firma di un documento contraffatto: una falsificazione del trapianto di firma è stata effettivamente perpetrata.

Lhashing della password consente ai sistemi di non memorizzare la versione in testo normale di una password, ma consente loro di verificare se lutente che cerca di ottenere laccesso conosce quella password. Lhashing non solo consente ai sistemi di non memorizzare le password in testo normale (che dovrebbero essere custodite con molta attenzione), ma consente la possibilità che anche se gli hash sono esposti pubblicamente, le password sono ancora sicure (analogamente a come la crittografia della chiave pubblica i sistemi sono in grado di rivelare le chiavi pubbliche). Sebbene in pratica gli hash siano comunque protetti dallaccesso pubblico: ad esempio /etc/shadow file su sistemi Unix, integrando i file /etc/passwd leggibili in tutto il mondo .

La funzione di hashing è tuttaltro che casuale. Tuttavia, la randomizzazione viene utilizzata per contrastare gli aggressori che creano grandi dizionari di password e hash, che consentono loro di cercare un codice hash e recuperare la password corrispondente.

Per hash una password in modo più sicuro, possiamo semplicemente aggiungere alcuni bit casuali ad esso chiamati “sale”. Sali diversi aggiunti alla stessa password, ovviamente, portano a hash diversi (si spera con poche o nessuna collisione).

Se il sale casuale è, diciamo, largo 32 bit, significa che, in teoria, una password può eseguire lhashing in oltre quattro miliardi di modi diversi, rendendo molto poco pratico avere un dizionario precalcolato di tutti gli hash possibili di un gran numero di password.

Ovviamente, quando lutente viene autenticato, non sa nulla di questo sale. Va bene perché il salt viene memorizzato insieme allhash nel profilo dellutente (spesso, combinato con lhash in una singola stringa di bit compatta). Quando la password dellutente viene convalidata, il salt viene aggiunto a qualsiasi password è entrata, in modo che lhashing venga effettuato con il sale corretto. Se la password è corretta, lhash corrisponderà, poiché anche il sale utilizzato è quello giusto, essendo stato estratto dal profilo dellutente.

Quindi è così che la casualità è incorporata nellhash della password, pur permettendogli di funzionare.

Ciò che rende gli hash difficili da decifrare è che sono costruiti da funzioni “botola” o “unidirezionali”. In matematica, ci sono molti esempi di queste cose. Ad esempio , la semplice aggiunta è una trappola. Se aggiungiamo alcuni numeri interi per produrre una somma, è impossibile recuperare i numeri originali, conoscendo solo la somma.

Gli hash delle password non sono password crittografate. Se un utente malintenzionato ha lhash e il salt di una password, e capita di indovinare la password, quindi può facilmente confermarla, esattamente nello stesso modo in cui lo fa il software di autenticazione del login: esegue la password più il sale attraverso la funzione di hashing e vede che il corretto emerge lhash.

Commenti

• Eccellenti capacità di scrittura e un y capire la risposta che è in tutto e per tutto corretta, ma affronta tutti i punti e mantiene un flusso naturale ad essa che lo rende molto più completo. ‘ non è unimpresa facile, grazie mille per la tua risposta!
• molto istruttiva. Hai coperto tutti gli aspetti.

Una delle chiavi dellhashing è che elimina le informazioni. Non puoi invertire un hash perché la conoscenza necessaria è sparita. Ecco alcuni esempi di funzioni di hashing utilizzabili (ma piuttosto inutili). Se mi dai una password potrei fare qualcosa di simile a una delle seguenti:

• Conta il numero di vocali
• Prendi il codice ASCII per ogni lettera e XOR tutte insieme
• Prendi il checksum CRC32 della rappresentazione binaria della password (questo è in realtà un vero hash, ma non crittografico)

In ognuno di questi casi, non posso invertire il processo. Invece, devo rieseguire il processo quando mi fornisci di nuovo la password in seguito per vedere se il calcolo che ho eseguito corrisponde.

Per esempio: se inizialmente mi dai la password “scimmia”, potrei memorizzare il numero 3 (3 vocali). Quindi, in seguito, quando provo ad autenticare la password “drago”, eseguo lo stesso controllo di nuovo e ottengo 2, che non corrisponde a 3. Quindi so che mi hai dato la password sbagliata. Ma se mi dai la password “melissa”, presumo erroneamente che tu abbia digitato la password giusta. Questo è un hash collisione .

Linsieme di regole che applichi per ottenere il numero che rappresenta una determinata password è la tua funzione hash . Queste sono considerate funzioni “unidirezionali” perché non dovresti essere in grado di invertirle. Le funzioni hash di alta qualità sono progettate per limitare il numero di potenziali collisioni, in modo che tu non debba preoccuparti di quel problema. Un ulteriore passo avanti, le funzioni hash crittografiche sono progettate per rendere difficile trovare una stringa che potrebbe corrispondere a un determinato output ( e forse creare intenzionalmente collisioni). Sono inoltre progettati per limitare la quantità di informazioni che è possibile raccogliere su un dato input solo dalloutput hash.

Quindi, di conseguenza, lunico modo per dire quale password corrisponde a un dato hash crittografico è provare tutte le possibilità fino a quando non ne trovi una che funzioni. Ulteriori contromisure (sale, BPKDF2, ecc.) Rendono questo processo di indovinare ancora più difficile, facendo sì che la persona che indovina la password salti più volte per ogni tentativo.

Nota che ho completamente sorvolato su come una funzione di hash crittografica lo rende difficile trovare una password funzionante (anche se non è quella originale). Questo è chiamato “ preimage attack “. Nel banale esempio sopra, inventare” melissa “come password candidata contenente 3 vocali è un esempio di tale attacco.

Le funzioni di hash crittografiche tipicamente lo fanno eseguendo linput anche se diverse” round “di un dato processo, in cui loutput di ogni round diventa parte dellinput di quello successivo.Per calcolare linput del primo round, devi calcolare linput del secondo round, che a sua volta richiede di calcolare linput del terzo round, ecc., Il che significa che ogni ipotesi di ciascun componente deve essere controllato attraverso una lunga e complessa serie di calcoli. Thomas Pornin ha una spiegazione esaustiva di come funziona questa resistenza; lettura piuttosto utile se vuoi davvero capiscilo.

1. Determina il valore costante di z che soddisfa questa equazione: xy ^ 7 + yz ^ 5 + x ^ 3z = 0. Serve aiuto? OK, x = 32. Non riesci ancora a risolverlo? Allora non dovresti conoscere la risposta in primo luogo.

   Il valore di y, che lo ridurrà a una singola equazione variabile, rendendo la soluzione per quella singola variabile banale per qualsiasi studente di 6a elementare (possibilmente bisogno di una calcolatrice), è un segreto che ho condiviso solo con persone di cui mi fido. Senza di esso, z potrebbe essere qualsiasi cosa; il suo valore dipende da y e quindi non può essere risolto in modo soddisfacente senza una costante, nota y. Se non lo fai ” Non conosco il tuo valore, è perché non mi sono fidato abbastanza di te da dartelo in privato.

   Questo è il principio di base della crittografia; la formula matematica o altro processo deterministico va bene -documentato, e una o più delle possibili variabili della formula possono anche essere conosciute pubblicamente, consentendo alle due parti di concordare un modo per impostare le loro cifre in modo che ciascuna possa decriptare ciò che laltra crittografa. Tuttavia, due variabili rimani segreto, se ne conosci uno, puoi scoprire laltro, quello che dovresti conoscere è la chiave e quello tu può scoprire con la chiave è il messaggio.

   Per un hash, è un po diverso. Un hash non richiede la conservazione di un segreto per mantenerne un altro. Al contrario, gli hash funzionano sulla base di una trasformazione matematica irreversibile; per ogni H (x) = y, non cè H ^{-1 (y) = x tranne per provare H (x) per tutti i possibili x fino a ottenere y. Di solito, questo perché diversi risultati intermedi dellequazione sono ambigui; per esempio, il calcolo della radice quadrata di un numero positivo produce tecnicamente entrambi un risultato positivo e negativo, poiché entrambi i numeri potrebbero essere moltiplicati per se stessi per produrre il risultato. Linverso di un modulo è similmente ambiguo; il numero 1, prodotto da x mod 3, potrebbe essere stato prodotto da qualsiasi x = 3k + 1. Questi tipi di trasformazioni “unidirezionali” sono combinati in modo tale che il tentativo di calcolare la funzione hash inversa genera infinite possibilità; il modo più semplice (più semplice) per risolverli è quindi semplicemente provare ogni possibile input fino a quando un output non corrisponde. Questo richiede ancora molto tempo.}

2. Gli hash non sono casuali. Come ho affermato in precedenza, gli hash sono il risultato di unoperazione matematica irreversibile. Quelloperazione deve essere ancora deterministica; dato un input costante, luscita è costante indipendentemente da quante volte si esegue loperazione. Non esiste un componente casuale.

   Dove potresti essere stato confuso è nel termine per ciò che simula un hash, che è un oracolo casuale . Immagina una scatola nera, allinterno della quale cè un piccolo uomo con una memoria fotografica e un metodo mistico per generare numeri perfettamente casuali. Scrivi qualcosa su un pezzo di carta e lo fai passare attraverso una fessura dove lo prende luomo. Lo legge e succede una delle due cose. O non lha letto prima, nel qual caso genererà un nuovo numero casuale e te lo darà, memorizzando sia il tuo messaggio che il numero. Oppure ha letto esattamente questo messaggio precedente, nel qual caso ricorda il numero che ha generato la prima volta che lo ha letto e ti dà il numero. Il generatore di numeri casuali non genererà mai un numero che ha già generato, ha una grandezza infinita possibile, e lomino “s la memoria è illimitata e infallibile. Pertanto, lomino non penserà mai di aver letto un messaggio prima se non lo ha fatto, non dimenticherà mai di aver letto un messaggio prima, e così non produrrà mai, mai, due numeri diversi per lo stesso identico messaggio né lo stesso numero per due messaggi diversi.

   Questo è ciò che le funzioni hash cercano di simulare. Non possono modellare questo omino con la memoria fotografica, perché ciò richiederebbe spazio di archiviazione infinito e disponibilità illimitata e universale, anche per dispositivi che non sono collegati a nessun altro dispositivo in alcun altro modo. Invece, si basano su un calcolo deterministico ma casuale che “digerisce” il messaggio nel suo valore hash. La stessa funzione hash, dato lo stesso messaggio, produrrà lo stesso digest; tuttavia, queste funzioni sono limitate nel numero di valori hash che possono restituire. Ciò crea la possibilità di ciò che chiamiamo collisioni hash; ci sono più messaggi possibili che valori hash, quindi prima o poi (si spera dopo), due me diversi ssages produrrà lo stesso hash.

3. Gli hash possono essere violati per tre ragioni fondamentali.Innanzitutto, poiché sono una derivazione matematica deterministica del loro messaggio, i matematici (e quindi gli aggressori) alla fine trovano una relazione matematica tra un messaggio e il suo hash, o tra due messaggi e gli hash risultanti. Quello che una volta era un aspetto casuale non lo è più. Ciò consentirebbe una serie di attacchi basati sulla natura della debolezza riscontrata; se esiste un modo algoritmico, dato un messaggio e il suo hash, per generare un messaggio in collisione, questo è un problema. Se esiste un modo per manipolare un messaggio e prevedere lhash risultante, il problema è diverso. Se in effetti cè un modo per invertire lhash, producendo un messaggio dallhash che, quando ri-hash, produce lo stesso hash, quello “è un problema serio .

   Secondo, poiché gli hash hanno una dimensione digest limitata, prima o poi due messaggi produrranno lo stesso hash. Ciò significa che un utente malintenzionato non deve trovare il messaggio che utilizzi per produrre un determinato hash ; tutto ciò che deve fare è trovare un messaggio che produca lo stesso hash. Le probabilità di questo sono scarse, in teoria una possibilità su quanti hash possibili ci sono, ma comunque migliori di una allinfinito.

   Infine, mentre ci sono molti messaggi possibili, ce ne sono molto più piccoli numero di probabili messaggi. I messaggi che tipicamente diamo alle funzioni hash di solito hanno una struttura (basata su lingua, argomento, formattazione elettronica e scopo), il che significa che, data una parte del messaggio, possiamo indovinare più accuratamente altre parti del messaggio. Ciò significa, in termini di scienza dellinformazione, che i messaggi convertiti in hash spesso hanno entropia inferiore alla funzione hash stessa; In poche parole, una funzione hash che produce digest a 256 bit può teoricamente produrre qualsiasi permutazione di quei bit, 2 ^ 256. Tuttavia, se ci sono, diciamo, solo 10.000 possibili messaggi che potrebbero mai essere inseriti in questa funzione hash da un sistema in fase di studio per lattacco, allora solo 10.000 dei 2 ^ 256 possibili valori hash saranno mai visti e, cosa più importante, un Lautore dellattacco, nel peggiore dei casi, dovrebbe solo provare tutti i 10.000 possibili input per trovare quello che produce il valore hash che sta cercando.

Commenti

• E questo …. è il motivo per cui amo la sicurezza IT ‘ la cosa del sito di scambio di stack.
• Anche la tua spiegazione di # 1 è esattamente ciò di cui avevo bisogno. Tuttavia ho una domanda. Sembra che gli ” hash ” siano come le versioni numeriche di una determinata cosa (password in questo caso). Quindi, se ho un sito web e 100000 persone si iscrivono. Quindi il 50% usa la password ” password ” Sono in grado di risparmiare un sacco di spazio semplicemente memorizzando il valore hash di ” password ” invece di password un sacco di volte?
• Bene, se ‘ stai utilizzando un hash sicuro (> = dimensione digest a 256 bit) quindi memorizza il valore hash di ” password ” aumenterà la dimensione dello spazio di archiviazione. Inoltre, se un utente malintenzionato dovesse mai vedere che il 50% degli account utente ha lo stesso hash della password, ‘ saprebbe che tutti ‘ non deve fare altro che crackare una password e ha accesso al 50% degli account utente. Dovresti ” saltando ” gli hash delle tue password; esistono diversi metodi, ma il risultato finale è che la stessa password con hash dello stesso algoritmo produce un digest diverso, a causa di un valore salt univoco aggiuntivo per ogni account.