Crittografia e Hashing

Introduzione

Esamineremo in questa nota i concetti principali di crittografia e hashing, a cosa servono, come vengono usati e le best practice in ambito di sicurezza dei dati.

Occorre innanzitutto distinguere due tipi di funzioni che possono essere applicate ai dati: la cifratura e l'hashing. Entrambi trasformano un testo "in chiaro" in un testo completamente diverso, ma con differenze sostanziali: la cifratura produce una serie di caratteri che può essere, mediante la decifratura, ritrasformata nel testo iniziale, mentre l'hashing non è una funzione invertibile.

La dimensione di un file criptato è in generale molto simile alla dimensione del file originale, mentre l'hashing occupa molto meno spazio (a meno che il file originale non sia di pochi caratteri).

La cifratura serve a trasmettere un file in modo che sia leggibile solo a chi sappia come decifrarlo. Durante la seconda guerra mondiale la decifratura di messaggi ha consentito di intercettare molte rotte di sommergibili e attacchi sia via terra sia via mare. La possibilità di veicolare dati in modo che non siano accessibili a tutti è essenziale oggi, quando dati di ogni genere viaggiano e giacciono su server lontani migliaia di chilometri da chi li utilizza.

Viceversa l'hashing produce una sequenza di byte che è una "sintesi" di un file in chiaro, in modo che leggendo l'hash del messaggio sia possibile stabilire se il messaggio sia stato modificato dopo il calcolo dell'hash.

Un altro utilizzo degli algoritmi di hashing è la memorizzazione delle password. In questo caso è memorizzato direttamente l'hash della password e non la password stessa: quando l'utente fornisce la password, ne è calcolato l'hash e confrontato con quello memorizzato per vedere se coincidono.

Prima di addentrarci nei dettagli dei vari algoritmi, consideriamo un aspetto importante sulla sicurezza.

Principio di Kerckhoffs

La conoscenza dell'algoritmo non deve causare un indebolimento della sua robustezza crittografica

In sostanza la sicurezza non deve dipendere dal nascondere l'algoritmo con cui è implementata, ma solo dalla chiave crittografica utilizzata in esso.

Questo principio è diametralmente opposto a quello della "sicurezza tramite segretezza", che già dal 1851 è stato sconfessato dagli esperti di sicurezza. Oggi è ampiamente accettato dalla comunità scientifica che gli algoritmi open source siano molto più robusti: grazie alla collaborazione delle comunità, le falle di un algoritmo pubblico possono essere scoperte più facilmente e corrette più rapidamente rispetto a quelle di algoritmi segreti e manutenuti da un singolo attore.

Il NIST (National Institute of Standards and Technology) negli Stati Uniti sconsiglia espressamente questa pratica. A tal proposito si veda "Guide to General Server Security", sezione 2.4 Open Design: System security should not depend on the secrecy of the implementation or its components.

Dunque è inutile e sbagliato, quando si tratta di sicurezza, inventarsi algoritmi propri per crittografare i dati: è meglio utilizzare algoritmi pubblici e ben collaudati, e preoccuparsi piuttosto di nascondere le chiavi in modo corretto.

Crittografia

La crittografia serve dunque a "offuscare" un messaggio, in modo che solo chi è autorizzato possa decodificarlo. Oltre al messaggio, il ricevente dovrà conoscere, per altre vie, la chiave necessaria a decodificarlo, senza la quale non è possibile risalire al messaggio originale.

Possiamo dunque ragionare degli algoritmi crittografici come di funzioni che siano in qualche modo invertibili. Distinguiamo in tal senso due grandi famiglie: quelli simmetrici e quelli asimmetrici.

Crittografia simmetrica

Nella crittografia simmetrica c'è una sola chiave segreta, usata sia per la cifratura sia per la decifratura di un messaggio. Considerata una coppia di funzioni cypher/decypher e un segreto secret, il procedimento sarà del tipo:

Cifratura:    obfuscated_message = cypher(message, secret)
Decifratura:  message = decypher(obfuscated_message, secret)

Il segreto è lo stesso sia in cifratura sia in decifratura, e deve essere noto a priori a chi riceve il messaggio da decodificare.

Alcuni algoritmi di crittografia simmetrica sono:

• DES (Data Encryption Standard): a 16 stadi, si basa su una chiave a 56 bit e cifra sequenze di 64 bit. Da molto tempo, con le potenze di calcolo disponibili, è possibile forzarlo in poche ore o minuti.
• 3DES: a 48 stadi, si basa sulla triplice applicazione del DES con 3 chiavi distinte, per cui in totale la chiave è di 168 bit e il blocco cifrato è di 64 bit. La sicurezza garantita è però solo di 112 bit, ossia il doppio del DES. È ai fini pratici un algoritmo molto sicuro, poiché il migliore attacco conosciuto richiede circa \(2^{32}\) parole conosciute, \(2^{113}\) passi, \(2^{90}\) cifrature DES e memoria per \(2^{88}\) byte. Di fatto, se usato solo all'interno di una singola sessione, non è praticamente attaccabile.
• AES (Advanced Encryption Standard), o anche Rijndael: a 10/12/14 stadi, si basa su una chiave a 128/192/256 bit e codifica sequenze di 128 bit. Sta sostituendo il 3DES in tutti gli usi: è più veloce da applicare, è facilmente cablabile in circuiti fisici, richiede poca memoria e fornisce un ottimo livello di sicurezza, che varia a seconda della dimensione della chiave usata. Non esistono al momento attacchi praticamente attuabili contro questo cifrario.
• IDEA, CAST5, Blowfish, Twofish: altri algoritmi, meno usati, poiché l'AES è stato quello scelto dal NIST nel 1997 per rimpiazzare il 3DES.

Un punto debole del 3DES rispetto all'AES è che codifica blocchi di 64 bit anziché 128, e questo lo rende maggiormente vulnerabile a un certo tipo di crittoanalisi.

Ai fini pratici, il 3DES o l'AES sono ottimi algoritmi di crittografia simmetrica. Ovviamente vanno poi fatte alcune considerazioni:

• Per quanto tempo si desidera nascondere le informazioni? Se supponiamo di nascondere un'informazione che sarà resa pubblica tre giorni dopo, e supponiamo che con la massima potenza di calcolo disponibile sia possibile decifrare il messaggio in 30 anni, l'algoritmo è assolutamente sicuro. Viceversa, se si vuole nascondere un'informazione per periodi molto più lunghi, bisogna considerare che in futuro la potenza di calcolo potrebbe aumentare e rendere la cifratura meno sicura.
• Quanto è importante quell'informazione, e quanto chi ha interesse a decifrarla potrebbe essere disposto a spendere per riuscirci.

Questi algoritmi sono presenti in tutte le librerie standard, per cui non saranno forniti qui i dettagli di funzionamento, già descritti ampiamente altrove.

Crittografia asimmetrica, o "a chiave pubblica"

In questo caso nella cifratura e nella decifratura del messaggio sono usate chiavi diverse, una pubblica e una privata. La forza del metodo risiede nel fatto che non è praticamente possibile ottenere la chiave privata dalla conoscenza della chiave pubblica, e tutto questo si basa sulla difficoltà di decomporre in fattori primi numeri molto grandi.

I fondamenti matematici affondano le radici nel piccolo teorema di Fermat e nel teorema cinese del resto, in sintesi sul fatto che

$$m^{ed} \equiv m \pmod{pq}$$

ove \(p, q\) sono numeri primi; detto \(n = pq\) e \(T = (p-1)(q-1)\), l'esponente pubblico \(e\) è un numero coprimo con \(T\) e più piccolo di \(T\), e l'esponente privato \(d\) è tale che \(ed \equiv 1 \pmod{T}\).

In questo caso il procedimento è dunque:

Cifratura:    obfuscated_message = cypher(message, chiave_pubblica)
Decifratura:  message = decypher(obfuscated_message, chiave_privata)

ossia

decypher(cypher(message, chiave_pubblica), chiave_privata) = message

Le due chiavi, pubblica e privata, sono in un certo senso una l'inversa dell'altra: usando la chiave privata nell'algoritmo di cifratura, il risultato può essere decifrato con la chiave pubblica. Vale cioè anche:

decypher(cypher(message, chiave_privata), chiave_pubblica) = message

Garanzia sul mittente mediante RSA

È possibile anche garantire al ricevente che il messaggio sia autentico, ossia proveniente dal giusto mittente e non manipolato, se il mittente, prima di inviare il file, lo cifra con la propria chiave privata.

Chiamiamo \(M_{pub}\) e \(M_{priv}\) le chiavi pubblica e privata del mittente, e \(R_{pub}\) e \(R_{priv}\) quelle del ricevente. Il mittente cifra prima il messaggio con la chiave pubblica del ricevente e poi con la propria chiave privata:

obfuscated_message = cypher(cypher(message, Rpub), Mpriv)

Il ricevente decifra prima con la chiave pubblica del mittente e poi con la propria chiave privata, e sa che il mittente è l'unico che può aver cifrato il messaggio con \(M_{priv}\):

message = decypher(decypher(obfuscated_message, Mpub), Rpriv)

Per ottenere un buon livello di sicurezza è necessario utilizzare chiavi di almeno 2048 bit. Una chiave di 1024 bit può essere decomposta in circa un anno di tempo al costo di circa un milione di dollari.

Protocollo di Diffie-Hellman

Sviluppato da Diffie e Hellman nel 1976, permette a due utenti di stabilire una chiave condivisa segreta utilizzando un canale non sicuro. Questo è di solito usato nella procedura di handshake che precede una comunicazione con uno schema di crittografia simmetrica.

La chiave così concordata è usata come chiave di sessione, temporanea, per cifrare i dati con un algoritmo simmetrico — che è molto più veloce di uno asimmetrico e per questo preferibile sul grosso del traffico.

In sostanza i due interlocutori \(A\) e \(B\), che si sono preventivamente messi d'accordo su un gruppo ciclico \(G\) pubblico e su un generatore \(g\), generano rispettivamente due numeri casuali \(a\) e \(b\). \(A\) invia \(g^a\) a \(B\), e \(B\) invia \(g^b\) ad \(A\). Allora \(A\) calcola \((g^b)^a\) e \(B\) calcola \((g^a)^b\), che sono uguali:

$$(g^b)^a = g^{ab} = (g^a)^b$$

e questo valore costituisce la chiave condivisa per una crittografia simmetrica.

L'algoritmo può essere reso più sicuro se l'invio di \(A\) è effettuato usando un algoritmo RSA, facendo in modo che \(A\) invii a \(B\) un dato crittografato con la propria chiave privata, e viceversa.

Crittografia ellittica, o ECC

È un tipo di crittografia a chiave pubblica basata sulle curve ellittiche definite su campi finiti.

A differenza degli algoritmi RSA, che si basano sulla difficoltà di decomporre in fattori primi numeri grandi, questi algoritmi si basano sulla difficoltà di risolvere l'equazione \(a^x = b\) in un gruppo finito: in altre parole sulla difficoltà di calcolare il logaritmo discreto di un elemento. A parità di sicurezza le chiavi sono molto più corte di quelle RSA — una chiave ECC di 256 bit è considerata equivalente a una RSA di 3072 — il che la rende preferibile dove la banda o la memoria contano. Al momento gode di una buona reputazione ed è inserita tra gli algoritmi consigliati dalla NSA.

Digital Signature Algorithm (DSA)

È uno standard per la firma digitale, che si basa sul calcolo dello SHA (che vedremo tra poco) del messaggio e sulla firma di esso mediante una chiave privata, in modo tale che per chi riceve il messaggio sia possibile, con un calcolo inverso, verificare che la firma presente contenga effettivamente lo SHA del messaggio cifrato con la chiave privata del firmatario. I principi alla base del DSA sono sostanzialmente quelli dell'algoritmo RSA.

Hashing

Una funzione di hashing mappa una stringa di lunghezza qualsiasi in una stringa di dimensione predefinita.

La caratteristica principale di una funzione di hashing è che non deve essere computazionalmente trattabile il problema di cercare una stringa avente un hash dato. La differenza tra i vari algoritmi sta in quanto sia probabile avere delle collisioni. Le principali funzioni di hash sono l'MD5, lo SHA e il RIPEMD.

SHA

Lo SHA è una famiglia di algoritmi — SHA-1, SHA-224, SHA-256, SHA-384, SHA-512 — ognuno dei quali produce un hash di tanti bit quanti indicati dal nome, tranne lo SHA-1 che produce un digest di 160 bit.

Lo SHA-1 è stato "craccato" da algoritmi di crittoanalisi, quindi sono da preferirsi i fratelli maggiori. Opera su blocchi di 512 bit (64 byte) e produce un digest di 20 byte.

Lo SHA-256 e lo SHA-512 sono quelli attualmente ritenuti sicuri, e restituiscono digest rispettivamente di 32 e 64 byte.

Lo SHA-1 è tuttavia ancora usato in molti protocolli e applicazioni, tra cui TLS, SSL, PGP, S/MIME e IPsec.

MD5

L'MD5 (message-digest algorithm) lavora su blocchi di 512 bit (64 byte) e produce un hash di 16 byte. Nel 2012 è stato craccato e la sua debolezza usata dal malware Flame, pertanto non dovrebbe più essere usato. In particolare è stato trovato un algoritmo in grado di trovare in pochi secondi messaggi aventi un determinato hash. Questo rende l'algoritmo inutilizzabile, poiché potrebbe essere facile per un utente maligno lasciare intatta la firma (si veda il DSA) e cambiare il messaggio con un altro avente lo stesso hash, per far credere al ricevente che sia un messaggio genuino.

RIPEMD

Ne esistono varie versioni, che producono digest di lunghezza diversa: 128, 160, 256, 320 bit. Sviluppati per risolvere i problemi dell'MD5, sono però meno sicuri degli SHA, per cui si raccomanda l'uso di questi ultimi.

Memorizzazione delle password

Un problema ricorrente per chi scrive software è memorizzare le password degli utenti, per poter in seguito verificare se quella che inseriscono è corretta.

Senz'altro non vanno memorizzate in chiaro, e bisogna fare in modo che chi dovesse venire in possesso del file o del database in cui sono memorizzate le password "criptate" non possa ottenere le password in chiaro, e possibilmente nemmeno collegarle agli utenti.

Per oscurare la password il metodo principe è senz'altro l'hash: è stato a lungo usato l'MD5, ma oggi si preferisce lo SHA-256 o lo SHA-512.

Attacchi a dizionario e sicurezza delle password

È una tecnica di attacco a una password che ne confronta l'hash con gli hash contenuti in uno o più dizionari di password già calcolate. Per le proprietà della funzione di hash non è possibile risalire in maniera diretta a un testo avente lo stesso hash, ma se la password è semplice o già usata da altri, è facile che sia presente in un dizionario di hash.

I dizionari sono spesso costruiti a partire da dizionari veri e propri di lingua, ricavando dalle parole in essi contenute delle varianti con l'inserimento di uno o più numeri o altri caratteri.

Tuttavia, tanti più caratteri si considerano, tanto meno un attacco a dizionario ha modo di riuscire. Se consideriamo una password di 16 caratteri, scelti a caso da un set di 80 tra lettere maiuscole, minuscole, cifre e caratteri speciali, le combinazioni possibili sono

$$80^{16} \approx 2{,}8 \times 10^{30}$$

Uno dei più grandi database esistenti di password contiene circa \(1{,}5 \times 10^{10}\) hash, ossia 15 miliardi. Da un rapido calcolo si evince che la probabilità che una password così generata sia contenuta in un simile database è di circa

$$\frac{1{,}5 \times 10^{10}}{2{,}8 \times 10^{30}} \approx \frac{1}{1{,}8 \times 10^{20}}$$

ossia una possibilità ogni duecento miliardi di miliardi.

Ora, se tutti usassimo password così sicure, e ne usassimo una diversa per ogni sito o programma a cui ci iscriviamo, magari cambiandole periodicamente, nessun attacco a dizionario avrebbe mai successo. In sostanza 15 miliardi di password in un dizionario possono sembrare tante, ma rispetto alle possibilità combinatorie con 16 caratteri sono meno di un granello di sabbia nel deserto.

È inoltre da notare che, se si volesse tentare di violare una simile password anche con tutta la potenza di calcolo dei processori più potenti, e anche potendo testare un miliardo di hash al secondo (quelli attuali non superano qualche centinaio di migliaia al secondo), ci vorrebbero circa \(2{,}8 \times 10^{21}\) secondi, ossia intorno ai \(10^{14}\) anni. Si consideri che si prevede che il Sole si spegnerà tra soli 5-7 miliardi di anni.

Tuttavia molti utenti scelgono password ben più semplici e le utilizzano in più occasioni: tali password diventano allora sicure quanto il meno sicuro dei siti in cui vengono usate. E ci sono siti che addirittura le memorizzano in chiaro, perché non gestiti da professionisti.

Hashing ripetuto e salt

Per proteggere le password degli utenti, soprattutto di quelli che malauguratamente abbiano usato una password semplice o l'abbiano riusata su più database, si adottano tecniche di key stretching e di salt.

Il key stretching consiste nel rafforzare la password inserita dall'utente applicando l'algoritmo di hash ripetutamente, anziché una volta sola. In questo modo, perché il confronto fra hash riesca, nel dizionario di ricerca dovrà essere presente la stessa password a cui è stato applicato l'algoritmo lo stesso numero di volte. Questo comporta che il database dell'attaccante debba contenere una quantità di dati tanto maggiore, linearmente, quante sono le volte in cui è stato applicato l'algoritmo.

Se si pensa che un algoritmo si può applicare facilmente 100 volte, questo significa che l'attaccante dovrà avere un database 100 volte più grande e tempi 100 volte più lunghi.

Ovviamente sarà poi necessario ricordarsi quante volte va applicato l'algoritmo di hashing — o in alternativa provarlo iterativamente fino a un numero massimo prefissato — quando si verifica la corrispondenza in fase di autenticazione.

Un'altra tecnica, sempre per prevenire attacchi a dizionario, è aggiungere alla password dell'utente dei caratteri casuali, il cosiddetto salt. Il salt è diverso da utente a utente e viene generato in maniera casuale ogni volta che è salvata una nuova password.

Tali caratteri sono aggiunti prima di applicare l'algoritmo di hashing, con il risultato di rendere non confrontabili gli hash memorizzati nei database-dizionario. Se si pensa che l'aggiunta di un solo bit raddoppia le combinazioni, aggiungendo soli due byte si ottiene che le combinazioni possibili per ogni password — volendo provare tutti i salt collegati — sono 65 mila volte maggiori, e 4 miliardi di volte se aggiungiamo 4 byte di salt.

Se il database fosse quello a cui facevo riferimento prima, di 15 miliardi di hash, calcolare per ogni hash 4 miliardi di varianti sarebbe fisicamente impossibile.

Dunque è buona prassi, per rendere inefficaci gli attacchi a dizionario, aggiungere dei byte di salt e memorizzarli separatamente dalle password — stessa cosa per il numero di ripetizioni visto nel key stretching. In questo modo, anche se il file delle password dovesse finire in mano a un attaccante, gli sarà impossibile risalire alle password in chiaro se non munito anche del file dei salt e del numero di ripetizioni.

Idea: PIN come salt

Il salt e il numero di iterazioni andrebbero memorizzati, come detto, in un luogo diverso rispetto al database delle password. Un'idea è di non memorizzarli affatto, e di utilizzare in alternativa un PIN come quello richiesto in accesso da alcune banche.

Considerato per esempio un PIN di 6 cifre, queste possono essere considerate il salt. In fase di login sarebbero chieste solo 3 cifre, in posizioni casuali del PIN, e per le restanti tre si effettuerebbe un mini attacco a forza bruta di massimo 1000 tentativi, quindi abbastanza veloce da attuare.

Si otterrebbe così il vantaggio che un dizionario, per includere quelle 6 cifre aggiuntive, dovrebbe essere un milione di volte più grande: quello visto prima dovrebbe contenere, invece di 15 miliardi, 15 milioni di miliardi di hash e relative password. Cosa molto più costosa e fisicamente inattuabile — anche la sola dimensione passerebbe da qualche gigabyte a petabyte, ossia migliaia di terabyte.

Conclusioni

Abbiamo esaminato diverse tecniche di crittografia e hashing, elencato i livelli di sicurezza di ognuna e annotato quelle ormai da non usare perché craccate o non più abbastanza sicure. Abbiamo esaminato alcuni tipi di attacco e le best practice su come memorizzare le password, oltre a proporre un modo di conservare il salt in modo sicuro: non conservandolo affatto.

Si conclude ricordando che, quando si usano delle password, non bisogna mai riusarle su più siti o applicazioni, e che devono sempre essere di più di 10 caratteri presi a caso tra maiuscoli, minuscoli, numeri e caratteri speciali, in modo da ampliare il set che dovrà essere usato per un eventuale attacco a forza bruta. Per dare un'idea, la differenza fra

$$26^{10} \approx 1{,}41 \times 10^{14} \qquad\text{e}\qquad 80^{10} \approx 1{,}07 \times 10^{19}$$

è già dell'ordine di \(10^5\).

Per un'applicazione dell'hashing a un problema concreto — riconoscere posizioni già analizzate in un motore scacchistico — si veda Hashing applicato: lo Zobrist hashing.