Veloce, fattore 1081.

O se preferisci, rispondi a questo: quanto 23 per 47?

Qual è il più facile? È più facile eseguire una moltiplicazione (basta seguire meccanicamente le regole) che recuperare gli operandi dati solo il prodotto. Moltiplicazione. (Questo, tra l'altro, è il fondamento di alcuni algoritmi crittografici come RSA.)

Funzioni hash crittografiche hanno basi matematiche diverse, ma hanno la stessa proprietà: sono facili da calcolare andando avanti (calcolare H (x) dato x), ma praticamente impossibile calcolare andando indietro (dato y, calcolare x tale che H (x) = y). In effetti, uno dei segni di una buona funzione hash crittografica è che non c'è modo migliore per trovare x che provarli tutti e calcolare H (x) fino a trovare una corrispondenza.

Un'altra importante proprietà di funzioni hash è che due diversi input hanno hash diversi. Quindi se H (x ₁ ) = H (x ₂ ), possiamo concludere che x ₁ = x _{2 sub >. Matematicamente parlando, questo è impossibile: se gli input sono più lunghi della lunghezza dell'hash, devono esserci delle collisioni. Ma con una buona funzione hash crittografica, non esiste un modo noto per trovare una collisione con tutte le risorse di elaborazione del mondo.}

Se vuoi saperne di più sulle funzioni di hash crittografico , leggi questa risposta di Thomas Pornin. Avanti, aspetterò.

Nota che una funzione hash non è una funzione di crittografia. La crittografia implica che puoi decrittografare (se conosci la chiave). Con un hash, non esiste un numero magico che ti permetta di tornare indietro.

Le principali funzioni hash crittografiche consigliate sono SHA-1 e la famiglia SHA-2 (disponibile in diverse dimensioni di output, principalmente SHA-256 e SHA-512) . MD5 è più vecchio, ora deprecato perché presenta collisioni note. In definitiva, non vi è alcuna prova matematica che siano effettivamente buone funzioni hash crittografiche, ma solo una credenza diffusa perché molti crittografi professionisti hanno passato anni della loro vita cercando e fallendo di romperle.

Ok, questo è uno parte della storia. Ora un hash della password non è direttamente una funzione di hash crittografica. Una funzione di hash della password (PHF) richiede due input: la password e un salt. Il salt viene generato casualmente quando l'utente sceglie la sua password e viene memorizzato insieme alla password con hash PHF (password, salt). (Ciò che conta è che due account diversi hanno sempre sali diversi e la generazione casuale di un sale sufficientemente grande è un buon modo per avere questa proprietà con una probabilità schiacciante.) Quando l'utente accede di nuovo, il sistema di verifica legge il sale dal database delle password , calcola PHF (password, salt) e verifica che il risultato sia ciò che è memorizzato nel database.

Il punto cruciale è che se qualcuno vuole decifrare una password, devono conoscere l'hash prima di poter iniziare e devono attaccare ogni account separatamente. Il sale rende impossibile eseguire in anticipo molti lavori di cracking, ad es. generando una tabella arcobaleno.

Questo risponde (2) e (3): il verificatore legittimo e l'attaccante scoprono allo stesso modo se la password (inserita dall'utente o indovinata dall'attaccante) è corretta. Un ultimo punto della storia: una buona funzione di hash della password ha una proprietà aggiuntiva, deve essere lenta. Il server legittimo deve calcolarlo solo una volta per tentativo di accesso, mentre un utente malintenzionato deve calcolarlo una volta per ipotesi, quindi la lentezza danneggia maggiormente l'attaccante (il che è necessario, perché l'attaccante ha in genere più hardware specializzato).

Se hai bisogno di hash delle password, non inventare il tuo metodo. Utilizza uno dei metodi standard: scrypt, bcrypt o PBKDF2.

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 su di loro (questo è solo 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.

L'hashing non è crittografia . Non ci sono segreti, né chiavi nell'hashing.

Le funzioni hash hanno molti usi; uno di questi è "archiviazione password". Una funzione hash sembra una buona cosa per l'archiviazione delle password. Non vogliamo memorizzare le password direttamente (altrimenti un'occasionale sbirciatina nei nostri database da parte dell'aggressore gli darebbe troppe informazioni; vedere questo post del blog per una discussione); vogliamo memorizzare i token di verifica della password : qualcosa che consente la verifica di una password (che l'utente presenta) ma non rivela la password stessa. Quindi l'idea è: memorizziamo l'hash 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 (dati che gli esseri umani possono ricordare) , per una sicurezza adeguata, abbiamo bisogno di una funzione hash "rafforzata":

• Vogliamo una funzione hash molto lenta .
• Non vogliamo una funzione hash, ma molte funzioni hash distinte, in modo che ogni password venga sottoposta ad hash 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 salatura.

Vedi questa risposta per una trattazione approfondita dell'argomento di hashing delle password.

L'hashing è una funzione che va da una stringa di bit (di solito di lunghezza variabile) a un'altra stringa di bit (di solito più piccola e di lunghezza fissa).

L'hashing viene utilizzato nei database per il recupero dei dati e in strutture dati di 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 dell'hash collisioni).

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

Nell'elaborazione 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 "botola" o funzioni "unidirezionali"). 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.

L'hashing può essere utilizzato non solo per le password, ma come checksum per verificare l'integrità dei dati e come parte dell'implementazione delle firme digitali. Per firmare digitalmente un documento di grandi dimensioni, dobbiamo semplicemente eseguire l'hash del documento per produrre un "digest" (un nome utilizzato per l'output di una funzione di hashing, quando viene eseguito l'hashing 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.

L'hashing della password consente ai sistemi di non memorizzare la versione in testo normale di una password, ma consente loro di verificare se l'utente che cerca di ottenere l'accesso conosce quella password. L'hashing 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 comunque sicure (analogamente a come crittografia della chiave pubblica i sistemi sono in grado di rivelare le chiavi pubbliche). Sebbene in pratica, gli hash siano comunque protetti dall'accesso pubblico: ad esempio i file / etc / shadow su sistemi Unix-like, integrando i file / etc / passwd leggibili da tutti.

La funzione di hashing è tutt'altro 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 salt casuale è, diciamo, largo 32 bit, significa che, in teoria, una password può eseguire l'hashing in oltre quattro miliardi di modi diversi, il che rende molto poco pratico avere un dizionario precalcolato di tutti gli hash possibili di un gran numero di password.

Ovviamente, quando l'utente viene autenticato, non sa nulla di questo sale. Va bene perché il sale viene memorizzato insieme all'hash nel profilo dell'utente (spesso, combinato con l'hash in una singola stringa di bit compatta). Quando l'inserimento della password dell'utente viene convalidato, il sale viene aggiunto a qualsiasi password inserita, in modo che l'hashing venga eseguito con il sale corretto. Se la password è corretta, l'hash corrisponderà, poiché anche il sale utilizzato è quello giusto, essendo stato estratto dal profilo dell'utente.

Ecco come la casualità viene incorporata nell'hashing delle password, pur permettendogli di funzionare.

Ciò che rende gli hash difficili da decifrare è che sono costruiti da funzioni "trap door" o "one way" . In matematica, ci sono molti esempi di queste cose. Ad esempio, una semplice aggiunta è una botola. 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 l'hash e il sale di una password e le capita di indovinare la password, può facilmente confermarlo, 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 emerge l'hash corretto.

Una delle chiavi dell'hashing è che elimina le informazioni. Non puoi invertire un hash perché la conoscenza necessaria è andata. Ecco alcuni esempi di funzioni di hashing utilizzabili (ma piuttosto inutili). Se mi dai una password potrei fare qualcosa come 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 dai di nuovo la password più tardi per vedere se il calcolo che ho eseguito corrisponde.

Ad esempio: se inizialmente mi dai la password "scimmia" potrei memorizzare il numero 3 (3 vocali). Poi, più tardi, quando provo ad autenticare la password "dragon", eseguo di nuovo lo stesso controllo e ottengo 2, che non corrisponde a 3. 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 collisione”.

hash L'insieme di regole che applichi per ottenere il numero che rappresenta una data 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 da non doverti preoccupare di quel problema. Un ulteriore passo avanti, le funzioni hash crittografiche sono progettate per rendere difficile trovare una stringa che potrebbe corrispondere a un dato output (e forse creare intenzionalmente collisioni). Sono inoltre progettati per limitare la quantità di informazioni che è possibile raccogliere su un dato input solo dall'output hash.

Quindi, di conseguenza, l'unico modo per dire quale password corrisponde a un dato hash crittografico è provare tutte le possibilità finché 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 hash crittografica lo rende difficile trovare una password funzionante (anche se non è quella originale). Questo è chiamato " attacco preimage ". Nell'esempio banale sopra, inventare "melissa" come password candidata contenente 3 vocali è un esempio di tale attacco.

Le funzioni hash crittografiche in genere lo fanno eseguendo l'input attraverso diversi "round" di un dato processo, dove l'output di ogni round diventa parte dell'input del successivo. Per capire l'input del primo round, dovresti calcolare l'input del secondo round, che a sua volta richiede di capire l'input del terzo round, ecc., Il che significa che ogni ipotesi di ciascun componente deve essere verificato attraverso una lunga e complessa serie di calcoli. Thomas Pornin ha una spiegazione esauriente di come funziona questa resistenza; lettura piuttosto utile se vuoi capirlo davvero.

1. Determina il valore costante di z che soddisfa questa equazione: xy ^ 7 + yz ^ 5 + x ^ 3z = 0. Hai bisogno di 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 (che potrebbe aver 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 y nota. Se non conosci il valore di y, è 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 è ben 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 decifrare ciò che l'altro crittografa. Tuttavia, due variabili rimangono segrete; se ne conosci uno, puoi scoprire l'altro. Quella che dovresti conoscere è la chiave e quella che puoi scoprire con la chiave è il messaggio.

   Per un hash, è un po 'diverso. Un hash non richiede che un segreto venga mantenuto per mantenerne un altro. Al contrario, gli hash funzionano sulla base di una trasformazione matematica irreversibile; per ogni H (x) = y, non esiste H ^-1 (y) = x noto tranne che per provare H (x) per tutti i possibili x finché non ottieni y. Di solito, questo perché diversi risultati intermedi dell'equazione sono ambigui; per esempio, il calcolo della radice quadrata di un numero positivo produce tecnicamente un risultato sia positivo che negativo, poiché entrambi i numeri potrebbero essere moltiplicati per se stessi per produrre il risultato. L'inverso di un modulo è altrettanto 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 provare semplicemente ogni input possibile finché un output non corrisponde. Ciò richiede ancora molto tempo.

2. Gli hash non sono casuali. Come ho affermato in precedenza, gli hash sono il risultato di un'operazione matematica irreversibile. Quell'operazione deve essere ancora deterministica; dato un input costante, l'output è costante indipendentemente da quante volte si esegue l'operazione. Non ci sono componenti casuali.

   Dove potresti essere stato confuso è nel termine per ciò che simula un hash, che è un oracolo casuale . Immagina una scatola nera, all'interno 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 l'uomo. Lo legge e succede una delle due cose. O non l'ha 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 questo messaggio esatto prima, nel qual caso si 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 la memoria dell'omino è illimitata e infallibile. Pertanto, l'omino non penserà mai di aver letto un messaggio prima se non l'ha fatto, non dimenticherà mai di aver letto un messaggio prima, e quindi non produrrà mai e poi mai due numeri diversi per lo stesso identico messaggio né lo stesso numero per due diversi messaggi.

   Questo è ciò che le funzioni hash cercano di simulare. Non possono modellare questo ometto con la memoria fotografica, perché ciò richiederebbe uno spazio di archiviazione infinito e una disponibilità illimitata e universale, anche a dispositivi che non sono collegati a nessun altro dispositivo in nessun altro modo. Invece, si basano su un calcolo deterministico ma dall'aspetto 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. Questo crea la possibilità di ciò che chiamiamo collisioni di hash; ci sono più messaggi possibili che valori hash, quindi prima o poi (si spera dopo), due messaggi diversi produrranno lo stesso hash.

3. Gli hash possono essere violati per tre ragioni fondamentali. Primo, 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 l'hash risultante, questo è un problema diverso. Se in effetti c'è un modo per invertire l'hash, producendo un messaggio dall'hash che, quando ri-hash, produce lo stesso hash, questo è 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 all'infinito.

   Infine, mentre ci sono molti messaggi possibili, c'è un numero molto inferiore di messaggi probabili . 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 dell'informazione, che i messaggi convertiti in hash spesso hanno entropia inferiore alla funzione hash stessa; in parole povere, 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 l'attacco, allora saranno mai visti solo 10.000 dei 2 ^ 256 possibili valori hash e, cosa più importante, un L'aggressore dovrebbe, nel peggiore dei casi, provare tutti i 10.000 possibili input per trovare quello che produce il valore hash che sta cercando.