Funzioni hash e crittografia simmetrica

La crittografia

Definizione (crittografia). La crittografia è la cifratura (encryption) e la decifratura (decryption) di messaggi in codice segreto. Può dare riservatezza, integrità e autenticazione. Converte un messaggio (testo in chiaro, plaintext) in un codice segreto (testo cifrato, ciphertext) usando una chiave, in modo che senza la chiave giusta non si possa fare la conversione inversa.

Lo schema è: il mittente cifra con la chiave di cifratura $k_e$, il testo cifrato passa per il canale, il destinatario decifra con la chiave di decifratura $k_d$:

$$C=E_{k_e}(P),\qquad P=D_{k_d}(C).$$

Attacchi ai sistemi crittografici.

• Solo testo cifrato (ciphertext only): l'attaccante intercetta il traffico e deve analizzare i dati cifrati con tecniche di crittoanalisi.
• Testo in chiaro noto (known plaintext): l'attaccante ha accesso al testo in chiaro e al corrispondente testo cifrato.
• Testo in chiaro scelto (chosen plaintext): l'attaccante riesce a far inserire nel sistema sorgente un messaggio scelto da lui.
• Forza bruta (brute force): il testo cifrato viene analizzato al computer provando velocemente molte (o tutte) le combinazioni di chiavi, aiutandosi con debolezze note (per esempio le regolarità di una lingua).

Proprietà (ricerca esaustiva). Provare tutte le chiavi di $k$ bit richiede in media $2^{k-1}$ tentativi: ogni bit in più raddoppia il lavoro.

Perché $2^{k-1}$: le chiavi possibili sono $2^k$ (ogni bit vale $0$ o $1$, $2$ scelte per $k$ bit, principio di moltiplicazionele scelte indipendenti si moltiplicanoCalcolo combinatorio per la probabilità →) e quella giusta è, con uguale probabilità, in una qualunque delle posizioni dell'elenco: provando le chiavi in ordine, in media la si trova a metà, dopo $\frac{2^k+1}{2}\approx2^{k-1}$ tentativi (Valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso → di una posizione uniforme su $2^k$ valori). Nel caso peggiore sono $2^k$.

Esempio. Con $10^{12}$ chiavi al secondo, il DES ($2^{56}=7{,}2\cdot10^{16}$ chiavi) richiede in media $2^{55}/10^{12}=3{,}6\cdot10^{4}$ s, circa 10 ore ($3{,}6\cdot10^4/3600=10$); AES-128 ($2^{128}=3{,}4\cdot10^{38}$) richiede in media $2^{127}/10^{12}=1{,}7\cdot10^{26}$ s, cioè $1{,}7\cdot10^{26}/(3{,}15\cdot10^7\ \text{s/anno})\approx5{,}4\cdot10^{18}$ anni (per confronto, l'universo ha $1{,}4\cdot10^{10}$ anni). Il rapporto tra i due è $2^{72}$: ogni bit in più raddoppia, $72$ bit in più moltiplicano per $2^{72}\approx4{,}7\cdot10^{21}$.

Due famiglie. La crittografia asimmetrica (a chiave pubblica) usa chiavi diverse per cifrare e decifrare, e dalla chiave pubblica è computazionalmente impossibile ricavare la privata (Crittografia asimmetrica, RSA e TLSCrittografia asimmetrica (a chiave pubblica): chiave di cifratura pubblica v_B, chiave di decifratura privata s_B, matematicamente legate; C = E_vB(P), P = D_sB(C); dà riservatezza. I certificati digitali, emessi da una Certificate Authority e firmati con la sua chiave privata, legano un'identità a una chiave pubblica. Firma digitale: hash del messaggio cifrato con la chiave privata; garantisce autenticità, integrità e non ripudio. RSA: si scelgono due primi grandi p e q, N = pq, phi(N) = (p-1)(q-1), e coprimo con phi(N), d = e^(-1) mod phi(N); chiave pubblica (N, e), segreta (N, d); cifratura c = m^e mod N, decifratura m = c^d mod N con m < N (teorema di Eulero); sicura finché la fattorizzazione è difficile (N di almeno 2048 bit); il padding casuale (PKCS#1 v1.5: 00 02 [casuale] 00 [m]) difende da malleabilità e determinismo. La firma RSA è s = m^d mod N, verificata con s^e mod N. TLS (su TCP) autentica gli estremi con il certificato, cifra i dati con una chiave di sessione simmetrica e garantisce l'integrità con i MAC; da TLS 1.0 a 1.3 la chiave si ricava con Diffie-Hellman e l'handshake si accorcia. DTLS è la versione per UDP.Crittografia asimmetrica, RSA e TLS →). La crittografia simmetrica (a chiave privata o segreta) usa la stessa chiave per cifrare e decifrare: la chiave deve restare segreta e serve un meccanismo aggiuntivo per distribuirla in modo sicuro (un canale separato o uno scambio di chiavi).

Funzioni hash

Le funzioni hash sono mattoni fondamentali della crittografia. Producono una firma di lunghezza fissa che si può usare per identificare un file. Casi d'uso: autenticazione con password, conservazione dell'integrità, blockchain.

Definizione (funzione hash). Qualsiasi funzione che mappa dati di dimensione arbitraria in dati di dimensione fissa. I valori restituiti si chiamano valori hash, digest o hash.

Esempio. $f(x)=x\bmod1000$ è una funzione hash: porta qualunque $x$ in un numero di $\lceil\log_2 1000\rceil=10$ bit (da 0 a 999: $2^{9}=512<1000\le2^{10}=1024$, Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →): $1234\to234$ e $2234\to234$. Però non è one-way, perché dato $h=234$ si trovano subito tutti gli $x=234+1000k$.

Definizione (funzione hash one-way). Una funzione hash che soddisfa due proprietà:

• proprietà one-way: dato $h$, è "difficile" trovare $m$ tale che $\text{hash}(m)=h$. La funzione non è invertibile (la corrispondenza è molti-a-uno), ma deve essere difficile trovare un qualsiasi $m$ valido;
• resistenza alle collisioni: è "difficile" trovare $m_1$ e $m_2$ diversi tali che $\text{hash}(m_1)=\text{hash}(m_2)$.

Un'applicazione: il gioco pari e dispari. Versione 1: io scelgo un numero e tu scegli un numero; tu mi dici per primo il tuo; poi io ti dico il mio; se la somma è pari vinco io. Non è equo: io posso scegliere il mio numero dopo aver sentito il tuo, e quindi vinco sempre.

Versione 2, con l'hash: io scelgo $x$, tu scegli $y$.

1. Io ti dico $\text{hash}(x)$.
2. Tu mi dici il tuo numero $y$.
3. Io ti dico $x$; tu verifichi che sia coerente con $\text{hash}(x)$.
4. Se la somma è pari vinco io.

Io devo rivelare l'hash prima di te, ma la proprietà one-way mi rende il gioco equo: tu non sai trovare il numero che ha generato quell'hash, e io non posso cambiare $x$ dopo (per la resistenza alle collisioni). Rischio: la forza bruta: provare tutti i numeri finché si trova quello giusto. Per questo il numero va scelto grande (per esempio di 256 bit): con $x$ tra $1$ e $M$ il lavoro medio di chi indovina è circa $M/2$ tentativi, e con $M=2^{256}$ è fuori portata (stesso conto della ricerca esaustiva sopra).

Esempio. Se $x=7$ e l'hash è SHA-256 della stringa 7, che inizia con 7902699b…, e i numeri possibili sono da 1 a 100, chi riceve l'hash prova i 100 candidati e trova $x=7$ al primo colpo (verificato con Python): serve uno spazio di scelta enorme.

Funzioni hash popolari.

• Serie MD (Message Digest, di Ron Rivest): MD2, MD4, MD5, MD6. MD2 e MD4 sono stati rotti e sono obsoleti. MD5 è diventato una delle più usate, ma la sua resistenza alle collisioni è stata rotta nel 2004; si usa ancora quando serve solo la proprietà one-way. MD6 non è diventato popolare. MD5 dà 128 bit.
• Serie SHA (Secure Hash Algorithm, del NIST): SHA-0, SHA-1, SHA-2 e SHA-3. SHA-0 e SHA-1 sono stati rotti. SHA-2 non è mai stato rotto; ma poiché il suo principio di funzionamento è lo stesso di SHA-1 e MD5, è stato sviluppato SHA-3. Nonostante SHA-3 sia uno standard, oggi il più usato è SHA-2 (per esempio SHA-256, che dà 256 bit = 32 byte).

Come funzionano: la costruzione di Merkle-Damgård. MD5, SHA-1 e SHA-2 usano lo stesso metodo di costruzione.

1. I dati d'ingresso sono divisi in blocchi di dimensione fissa (l'ultimo blocco è completato con un riempimento, padding).
2. Ogni blocco e l'uscita dell'iterazione precedente entrano in un blocco di compressione (la prima iterazione usa un vettore iniziale, IV).
3. L'uscita dell'ultima iterazione è l'hash.
4. Gli standard differiscono per la specifica funzione di compressione.

Esempio (SHA-256). I blocchi sono di 512 bit; il riempimento aggiunge un bit 1, degli zeri e la lunghezza del messaggio su 64 bit. Un messaggio di $L$ bit richiede $L+1+64$ bit tra dati, bit 1 e lunghezza, e questi vanno distribuiti in blocchi interi da $512$: il numero di blocchi è $\lceil(L+1+64)/512\rceil$ (il simbolo $\lceil\cdot\rceil$ è l'arrotondamento per eccesso, perché l'ultimo blocco si riempie di zeri). Un messaggio abc ($3$ byte $=24$ bit) sta in $\lceil(24+1+64)/512\rceil=\lceil89/512\rceil=1$ blocco; un file di 1000 byte ($8000$ bit) richiede $\lceil(8000+1+64)/512\rceil=\lceil8065/512\rceil=\lceil15{,}75\rceil=16$ blocchi, e l'hash resta di 256 bit.

Verifica dell'integrità. Cambiare un solo carattere (o anche un solo bit) dei dati originali cambia completamente l'hash, e nessuno può dire quanto siano vicini i due ingressi. Invece di conservare un file grande, si può conservare il suo hash, di dimensione fissa (32 byte per SHA-256): conservare l'hash equivale a conservare un duplicato sicuro. Molte fonti affidabili pubblicano l'hash insieme al file: dopo lo scaricamento si può verificarlo.

Esempio. SHA-256 della stringa ciao inizia con b133a0c0e9bee3be…; SHA-256 di ciap (una lettera diversa) inizia con 433a76b7fe6e8c73…: i due digest differiscono in 135 bit su 256, circa metà (verificato con Python). Perché metà: un buon hash si comporta come se ogni bit dell'uscita cambiasse con probabilità $\frac12$ in modo indipendente (effetto valanga), quindi il numero di bit diversi è una variabile binomialenumero di successi in n prove indipendenti con la stessa probabilitàProve ripetute e modello binomiale → con $n=256$, $p=\frac12$: media $np=128$, deviazione standard $\sqrt{np(1-p)}=\sqrt{64}=8$, e $135$ dista solo $135-128=7<1\sigma$ dalla media. Trovare una preimmagine costa circa $2^{256}$ tentativi: ogni tentativo indovina con probabilità $2^{-256}$, e il numero di tentativi fino al primo successo ha distribuzione geometricail numero di prove fino al primo successo, con media 1/pDistribuzione geometrica → con media $1/p=2^{256}$. Trovare una collisione costa invece circa $2^{128}$, per il paradosso del compleanno (sezione seguente).

Password. Per accedere a un account l'utente deve dire un segreto (la password), ma questa non si può conservare in chiaro. Serve un hash per conservare le password in modo che nessuno possa sapere qual è (Linux le conserva in /etc/shadow); quando l'utente fornisce una password, si verifica confrontando l'hash della password data con quello della password memorizzata.

Il paradosso del compleanno e le collisioni

Una collisione è una coppia $m_1\ne m_2$ con lo stesso hash. Se l'hash ha $b$ bit, i valori possibili sono $M=2^b$. Quanti messaggi bisogna provare per trovare una qualsiasi coppia che collide? Meno di quanto si pensi: è lo stesso conteggio del paradosso del compleanno ($n$ persone, $M=365$ giorni).

Si calcola la probabilità del complementare, cioè che tutti gli $n$ valori siano distinti. Il primo valore è libero; il secondo deve evitare il primo: probabilità $1-\frac1M$; il terzo deve evitare i primi due: $1-\frac2M$ (le scelte sono indipendenti, quindi le probabilità si moltiplicano: Indipendenza di eventiA e B sono indipendenti se P(A ∩ B) = P(A) P(B), cioè se sapere che uno si è verificato non cambia la probabilità dell'altro; l'indipendenza passa ai complementari, non va confusa con l'incompatibilità, e per più eventi va richiesta su ogni sottofamiglia.Indipendenza di eventi → e Probabilità condizionataLa probabilità di A sapendo che si è verificato B è P(A ∣ B) = P(A ∩ B) / P(B), con P(B) > 0; è una nuova misura di probabilità, e da essa seguono la regola del prodotto e la regola della catena.Probabilità condizionata → con la formula del prodotto), e così via: $$P(\text{nessuna collisione})=\left(1-\frac1M\right)\left(1-\frac2M\right)\cdots\left(1-\frac{n-1}M\right),\qquad P(\text{collisione})=1-P(\text{nessuna collisione}).$$ Per $n$ piccolo rispetto a $M$ si usa $1-x\approx e^{-x}$ per $x$ piccolo (Sviluppi di Mac-Laurin notevoliTabella degli sviluppi di Mac-Laurin da sapere a memoria (e^x, sin, cos, log(1+x), (1+x)^alpha, arctan, sinh, cosh, tan) e regole per combinarli: algebra degli o piccoli, prodotti, funzioni composte, quanti termini tenere.Sviluppi di Mac-Laurin notevoli →: $e^{-x}=1-x+\dots$): ogni fattore diventa $e^{-i/M}$ e il prodotto $e^{-(1+2+\dots+(n-1))/M}$. La somma $1+2+\dots+(n-1)=\frac{n(n-1)}2$ (SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →) dà $$P(\text{collisione})\approx1-e^{-n(n-1)/(2M)}\approx1-e^{-n^2/(2M)}.$$ Si impone $P=\frac12$: $e^{-n^2/(2M)}=\frac12$, quindi $\frac{n^2}{2M}=\ln2$ e $$n\approx\sqrt{2\ln2\cdot M}\approx1{,}18\sqrt M.$$ Il numero di valori necessari è dell'ordine della radice di $M$, non di $M$. Questo spiega la differenza tra preimmagine e collisione: $\sqrt{2^{b}}=2^{b/2}$. Esempi:

Con $23$ persone: $\frac{23\cdot22}{2\cdot365}=0{,}693=\ln2$, quindi $e^{-0{,}693}=0{,}5$. Con $50$ persone la probabilità è già $97\%$ (esatta $0{,}9704$). Con $2^{64}$ tentativi a $10^{12}$ hash al secondo servirebbero $1{,}8\cdot10^{7}$ s, circa $213$ giorni: ecco perché 128 bit non bastano più per resistere alle collisioni, mentre $2^{128}$ è irraggiungibile. Per questo un hash di $b$ bit offre sicurezza $2^{b/2}$ contro le collisioni e $2^b$ contro la preimmagine. La stessa matematica descrive le collisioni nelle Tabelle hashTabella hash per implementare una mappa: funzione hash = hash code + compression function, bucket array, separate chaining; hash code per numeri e stringhe (polynomial, cyclic shift), division e MAD; load factor, complessità al caso pessimo Theta(n) e medio O(1+lambda), rehashing; esempio svolto con inserimenti e collisioni.Tabelle hash → a $N$ bucket: dopo circa $\sqrt N$ inserimenti è probabile che due chiavi condividano un bucket.

Per un hash qualsiasi la curva è la stessa se l'asse orizzontale è $n/\sqrt M$ (circa $1{,}18$ per il $50\%$, circa $2{,}4$ per il $94\%$).

Crittografia simmetrica

Definizione (crittografia simmetrica). Detta anche a chiave privata. Usa la stessa chiave $K$ per cifrare e decifrare: $C=E_K(P)$, $P=D_K(C)$. Garantisce riservatezza, integrità e autenticazione dei messaggi. I nodi che comunicano devono condividere una chiave segreta.

La crittografia simmetrica usa il principio del progetto aperto (open design): il nodo mittente A usa un algoritmo di cifratura concordato con la sua copia della chiave condivisa; il nodo ricevente B decifra con l'algoritmo corrispondente e la sua copia della chiave; cifratura e decifratura sono funzioni inverse; chiunque altro non ha la chiave e non può ricostruire il testo in chiaro. La segretezza sta tutta nella chiave, non nell'algoritmo.

Cifrari storici

La storia della cifratura risale al 1900 a.C. (geroglifici egizi).

Cifrario di Cesare. Secondo Svetonio, Giulio Cesare cifrava i messaggi militari con uno spostamento di tre lettere. Si può usare qualsiasi spostamento, ruotando l'alfabeto come un buffer circolare. Per una lettera in posizione $x$ (A = 0, ..., Z = 25; il $\bmod26$ riporta il risultato nell'alfabeto, come nell'aritmetica modulareil resto della divisione per 26: dopo la Z si ricomincia da ACrittografia asimmetrica, RSA e TLS → delle note sulla crittografia a chiave pubblica):

$$E_n(x)=(x+n)\bmod26,\qquad D_n(x)=(x-n)\bmod26.$$

Esempio. Con $n=3$: ATTACCO $\to$ DWWDFFR ($A=0\to3=D$, $T=19\to22=W$, $C=2\to5=F$, $O=14\to17=R$); per decifrare si sposta di $-3$ (la $W=22$ torna a $22-3=19=T$; per una lettera come $A=0$ si ha $(0-3)\bmod26=23=X$, cioè si prende il resto non negativo). Provando la chiave sbagliata $n=-3$ al posto di $+3$ sulla stessa parola si ottiene XQQXZZL, senza senso. Le chiavi possibili sono solo 25: si provano tutte. Un cifrario a sostituzione monoalfabetica (una lettera qualunque al posto di un'altra) ha $26!\approx4{,}03\cdot10^{26}\approx2^{88}$ chiavi ($26$ scelte per la prima lettera, $25$ per la seconda, ... : le permutazioni, Fattoriale e coefficienti binomialiFattoriale, permutazioni, disposizioni, combinazioni e coefficiente binomiale n su k, con il triangolo di Tartaglia.Fattoriale e coefficienti binomiali →; $\log_2(26!)=88{,}4$), troppe per provarle tutte, ma si rompe lo stesso con l'analisi delle frequenze delle lettere.

Il complotto di Babington. Maria, regina di Scozia nel XVI secolo, era prigioniera della cugina Elisabetta I d'Inghilterra. Anthony Babington progettava di liberarla e di assassinare Elisabetta; scrisse a Maria una lettera cifrata con un nomenclator (sostituzione + parole in codice). Ma il matematico Phelippes, assoldato da Sir Walsingham, decifrò il codice e il complotto fu scoperto: Maria fu decapitata nel 1587.

Vigenère: "le chiffrage indéchiffrable". Nel Rinascimento dominavano i decifratori, grazie all'analisi delle frequenze: spostamento e sostituzione erano facili da rompere. Da Leon Battista Alberti (1404) l'idea di usare più di un cifrario; raffinata da Giovan Battista Bellaso (1553) e Blaise de Vigenère, con 26 codici possibili e una chiave che deve essere nota alla destinazione.

Esempio. Con chiave LEMON ripetuta, ATTACKATDAWN $\to$ LXFOPVEFRNHR: ogni lettera è spostata del valore della lettera corrispondente della chiave ($A+L=L$, $T+E=X$, $T+M=F$, $A+O=O$, $C+N=P$, $K+L=V$, ...). La stessa lettera A diventa L, O, E: l'analisi delle frequenze semplice non funziona più.

Enigma. La crittografia ebbe un ruolo importante nella seconda guerra mondiale: gli storici dicono che ne abbreviò la durata e ne cambiò perfino l'esito. Arthur Scherbius iniziò a sviluppare Enigma nel 1918, combinando le idee di Alberti e di Vigenère. La prima versione funzionante fu violata nel 1932 dal controspionaggio polacco con la Bomba, una macchina di Marian Rejewski; i tedeschi migliorarono la macchina aggiungendo combinazioni; la ricerca passò a Bletchley Park, nel Regno Unito, dove il giovane Alan Turing contribuì a modificare e migliorare la Bomba.

DES e AES

DES (Data Encryption Standard) è un cifrario a blocchi: elabora i dati in blocchi di 64 bit, con chiave di 56 bit (la chiave in ingresso è di 64 bit, ma 8 sono per il controllo degli errori e vengono scartati). Approvato come standard nel 1976, progettato da NSA e IBM. La chiave corta fa sì che oggi si possa rompere con la forza bruta: nel 1999 un gruppo lo violò in una gara in 22 ore, usando molti PC. Il Triple DES (DES applicato tre volte) risolve il problema della lunghezza della chiave, ma è costoso in calcolo; è stato sostituito dall'AES.

AES (Advanced Encryption Standard) è stato definito pubblicamente (senza NSA) nel 1997: cifrario a blocchi simmetrico adattabile a più lunghezze di chiave. Blocco fisso da 128 bit (contro i 64 del DES); chiavi da 128, 192 o 256 bit.

Modi di cifratura

Usare i blocchi, nella versione ingenua, non sembra sicuro: due blocchi di testo in chiaro uguali danno due blocchi cifrati uguali. Bisogna rendere diversi i blocchi cifrati anche se i blocchi in chiaro sono uguali: bisogna rendere diverso almeno uno degli ingressi. Esistono molte soluzioni, i modi di cifratura: Electronic Codebook (ECB), Cipher Block Chaining (CBC), Propagating CBC (PCBC), Cipher Feedback (CFB), Output Feedback (OFB), Counter (CTR), ...

Notazione: $P_i$ blocco in chiaro $i$, $C_i$ blocco cifrato $i$, $C_{i-1}$ blocco cifrato precedente, $E_k$ funzione di cifratura con chiave $k$, $C_0=\text{IV}$ vettore di inizializzazione.

• ECB: ogni blocco è mappato in un codice specifico senza altro, $C_i=E_k(P_i)$ (ricorda il DES o l'AES usati da soli). Due blocchi in chiaro uguali danno blocchi cifrati uguali; nessuna casualità tra i blocchi (la struttura del testo in chiaro si vede); molto vulnerabile ad alcuni attacchi, specialmente per grandi insiemi di dati come immagini e dati strutturati. Insicuro.
• CBC: invece di cifrare ogni blocco da solo, concatena i blocchi: $C_i=E_k(P_i\oplus C_{i-1})$. Ogni blocco in chiaro è messo in XOR con il blocco cifrato precedente (il primo con l'IV, casuale). Anche se due blocchi in chiaro sono uguali, i cifrati sono diversi; lo stesso testo cifrato con IV diversi dà testi diversi; l'IV deve essere imprevedibile e unico per ogni sessione di cifratura. La cifratura è sequenziale (non parallelizzabile).
• CFB: cifra il blocco cifrato precedente (o l'IV all'inizio) e lo mette in XOR con il testo in chiaro: $C_i=P_i\oplus E_k(C_{i-1})$. Diventa un cifrario a flusso (lo XOR è bit a bit e viene dopo la cifratura); può cominciare senza aspettare l'intero messaggio (bene per il tempo reale); cifra dati di qualsiasi lunghezza, non solo multipli del blocco. Un errore di trasmissione si propaga su più blocchi; difficile da parallelizzare, come il CBC.
• OFB: invece di cifrare il blocco cifrato precedente, cifra l'uscita precedente della funzione di cifratura (partendo dall'IV): $O_i=E_k(O_{i-1})$, $O_0=\text{IV}$, $C_i=P_i\oplus O_i$. Resistente agli errori di trasmissione (è colpito solo il blocco corrente); cifratura e decifratura usano entrambe la sola funzione di cifratura; il flusso di chiave (keystream) si può precalcolare, perché non dipende da testo in chiaro e cifrato; l'IV deve essere unico e imprevedibile.
• CTR: nessuna correlazione con il blocco seguente. Cifra i blocchi separatamente, usando ogni volta un IV diverso (che cresce di uno a ogni blocco: per questo si chiama counter): $C_i=P_i\oplus E_k(\text{IV}+i-1)$. Un errore di trasmissione colpisce solo il blocco corrispondente; è parallelizzabile (ogni blocco si cifra e decifra da solo).

Esempio (giocattolo). Cifrario a blocchi di 8 bit $E(x)=(5x+17)\bmod256$ (non è un cifrario sicuro, serve solo per vedere come lavorano i modi), testo in chiaro a blocchi $10,10,10,20$ e $\text{IV}=7$. Il simbolo $\oplus$ è lo XOR bit a bit (Algebra di Boole e porte logicheVariabili booleane, operatori AND, OR, NOT e derivati (NAND, NOR, XOR, XNOR) con tabelle di verità; assiomi e teoremi dell'algebra di Boole, De Morgan; porte logiche e completezza di NAND e NOR; semplificazione algebrica con esempio.Algebra di Boole e porte logiche →: $1$ se i due bit sono diversi, $0$ se uguali), per esempio $10\oplus7=1010_2\oplus0111_2=1101_2=13$ (Sistemi di numerazione posizionaliNotazione posizionale in base b; conversioni tra base 10, 2, 8 e 16 per interi (divisioni successive) e per parti frazionarie (moltiplicazioni successive); numeri periodici in binario.Sistemi di numerazione posizionali →).

Passaggi, blocco per blocco (ciascun risultato alimenta il successivo):

• ECB: $E(10)=5\cdot10+17=67$ per tutti e tre i blocchi uguali; $E(20)=117$.
• CBC: $C_1=E(10\oplus7)=E(13)=82$; $C_2=E(10\oplus82)=E(88)=457\bmod256=201$; $C_3=E(10\oplus201)=E(195)=992\bmod256=224$; $C_4=E(20\oplus224)=E(244)=1237\bmod256=213$.
• CFB: $C_1=10\oplus E(7)=10\oplus52=62$; $C_2=10\oplus E(62)=10\oplus327\bmod256=10\oplus71=77$; $C_3=10\oplus E(77)=10\oplus146=152$; $C_4=20\oplus E(152)=20\oplus9=29$.
• OFB: il flusso di chiave non dipende dal testo: $O_1=E(7)=52$, $O_2=E(52)=21$, $O_3=E(21)=122$, $O_4=E(122)=115$; poi $C_i=P_i\oplus O_i$: $10\oplus52=62$, $10\oplus21=31$, $10\oplus122=112$, $20\oplus115=103$.
• CTR: $E(7)=52$, $E(8)=57$, $E(9)=62$, $E(10)=67$; $C_i=P_i\oplus E(\text{IV}+i-1)$: $10\oplus52=62$, $10\oplus57=51$, $10\oplus62=52$, $20\oplus67=87$.

In ECB i tre blocchi uguali si vedono; negli altri modi i blocchi cifrati sono tutti diversi anche se i primi tre blocchi in chiaro sono uguali. (Calcolati e riverificati con Python, anche la decifratura.)

Come scambiarsi la chiave

I nodi che usano la crittografia simmetrica devono stabilire in modo sicuro le chiavi segrete. Con $n$ persone che vogliono parlare a coppie in modo riservato servono $\frac{n(n-1)}2=\binom n2$ chiavi: ogni persona ne condivide una con ciascuna delle altre $n-1$, e ogni chiave è contata due volte (una da ciascun estremo), quindi si divide per $2$ (Fattoriale e coefficienti binomialiFattoriale, permutazioni, disposizioni, combinazioni e coefficiente binomiale n su k, con il triangolo di Tartaglia.Fattoriale e coefficienti binomiali →); per $n=100$ sono $4950$. La crescita è quadratica, mentre la crittografia asimmetrica richiede una sola coppia di chiavi per persona, $n$ in tutto:

Per $n=30$: $435$ chiavi segrete contro $30$ coppie. Due strade:

• scambiare la chiave con la crittografia a chiave pubblica, prima della trasmissione vera e propria; ma implementare un sistema a chiave pubblica può essere troppo oneroso se serve solo per lo scambio della chiave;
• costruire insieme la chiave (Diffie e Hellman): si esegue passo passo un algoritmo specificato, scambiando risultati intermedi e parametri su un canale insicuro; conoscendo i risultati intermedi dell'altro, entrambi i nodi calcolano la stessa chiave segreta, senza averla mai scambiata.

Scambio di chiavi Diffie-Hellman. Alice e Bob si accordano su:

• un gruppo ciclico di ordine $p$: un grande numero primo (per esempio di 2048 bit);
• un generatore $g$: un piccolo numero primo (per esempio 2 o 3).

Generare questi parametri è costoso, quindi si fa in anticipo e gli stessi $p$ e $g$ si riusano più volte; spesso si usano anche parametri standardizzati (RFC 3526, 2003, e RFC 5114, 2008). Poi A e B scelgono a caso interi positivi $x<p$ e $y<p$.

Formula (Diffie-Hellman). A manda a B $L=g^x\bmod p$; B manda ad A $M=g^y\bmod p$. A calcola $K=M^x\bmod p$, B calcola $K'=L^y\bmod p$. Si ha $K=K'=g^{xy}\bmod p$: la stessa chiave condivisa.

Esempio ($p=23$, $g=5$). $x=6$: $L=5^6\bmod23=8$. $y=15$: $M=5^{15}\bmod23=19$. Alice calcola $K=19^6\bmod23=2$; Bob calcola $K'=8^{15}\bmod23=2$. Chiave condivisa $K=2$ (verificato con Python). Passaggi con le potenze ripetute (si riduce modulo $23$ a ogni prodotto): $5^2=25\equiv2$, $5^4\equiv2^2=4$, $5^8\equiv16$; $5^6=5^4\cdot5^2\equiv4\cdot2=8$; $5^{15}=5^8\cdot5^4\cdot5^2\cdot5\equiv16\cdot4\cdot2\cdot5=640=27\cdot23+19\equiv19$. Poi $19\equiv-4\pmod{23}$, quindi $19^6\equiv(-4)^6=4096=178\cdot23+2\equiv2$; e $8^{15}$: $8=2^3$, $8^{15}=2^{45}$, con $2^{11}=2048=89\cdot23+1\equiv1$ si ha $2^{45}=(2^{11})^4\cdot2\equiv2$. Le due strade danno lo stesso $K$ perché $(g^y)^x=g^{xy}=(g^x)^y$. Un ascoltatore conosce $p=23$, $g=5$, $L=8$, $M=19$; per ottenere $K$ dovrebbe ricavare $x$ da $5^x\equiv8\pmod{23}$, cioè il logaritmo discreto ($x=6$ qui, trovato provando tutti i valori: con $p$ da 2048 bit non è fattibile).

Per un osservatore che vede il protocollo, l'informazione è molta, ma non può calcolare $g^{xy}\bmod p$ senza conoscere $x$ o $y$. Se conoscessimo $g$ e la potenza intera, ricavare $x$ da $g^x$ sarebbe facile; farlo da $g^x\bmod p$ è il problema del logaritmo discreto, per il quale non si conosce alcun algoritmo in tempo polinomiale (le slide lo descrivono come un problema NP-hard). Diffie-Hellman da solo non autentica le parti: serve la firma o il certificato (Crittografia asimmetrica, RSA e TLSCrittografia asimmetrica (a chiave pubblica): chiave di cifratura pubblica v_B, chiave di decifratura privata s_B, matematicamente legate; C = E_vB(P), P = D_sB(C); dà riservatezza. I certificati digitali, emessi da una Certificate Authority e firmati con la sua chiave privata, legano un'identità a una chiave pubblica. Firma digitale: hash del messaggio cifrato con la chiave privata; garantisce autenticità, integrità e non ripudio. RSA: si scelgono due primi grandi p e q, N = pq, phi(N) = (p-1)(q-1), e coprimo con phi(N), d = e^(-1) mod phi(N); chiave pubblica (N, e), segreta (N, d); cifratura c = m^e mod N, decifratura m = c^d mod N con m < N (teorema di Eulero); sicura finché la fattorizzazione è difficile (N di almeno 2048 bit); il padding casuale (PKCS#1 v1.5: 00 02 [casuale] 00 [m]) difende da malleabilità e determinismo. La firma RSA è s = m^d mod N, verificata con s^e mod N. TLS (su TCP) autentica gli estremi con il certificato, cifra i dati con una chiave di sessione simmetrica e garantisce l'integrità con i MAC; da TLS 1.0 a 1.3 la chiave si ricava con Diffie-Hellman e l'handshake si accorcia. DTLS è la versione per UDP.Crittografia asimmetrica, RSA e TLS →).

Simmetrica e asimmetrica a confronto

Autenticazione: MAC e HMAC

Definizione (MAC). Un codice di autenticazione del messaggio (Message Authentication Code) realizza l'autenticazione con una chiave segreta condivisa (anche diversa da quella di cifratura). Il nodo mittente lo calcola con una funzione nota e la chiave segreta, ottenendo un valore breve e di lunghezza fissa, l'autenticatore (detto anche tag), che viene aggiunto al messaggio.

Gli algoritmi che generano il MAC hanno la proprietà che non si può alterare il messaggio senza cambiare il tag. Alla ricezione B usa la chiave segreta di autenticazione per calcolare il MAC sul contenuto del messaggio e lo confronta con quello ricevuto. Se coincidono, il ricevente sa che il messaggio non è stato manomesso e che A è l'unica altra parte che possiede la chiave usata per generare il MAC. Per la sicurezza dell'autenticazione deve essere computazionalmente impossibile calcolare un tag valido di un messaggio senza conoscere la chiave; per essere utile, il calcolo deve essere relativamente semplice conoscendo la chiave. Una via comune per calcolare un MAC è l'hash.

Formula (HMAC). L'HMAC (Keyed-Hash MAC) è l'algoritmo standard per il MAC basato su hash. Con $B$ la dimensione del blocco usato dalla funzione hash $H$ (di solito 64 byte) e $K$ la chiave di lunghezza variabile (completata con zeri fino a $B$), si usano due hash combinati:

$$\text{HMAC}_K(m)=H\big((K\oplus\text{opad})\,\|\,H\big((K\oplus\text{ipad})\,\|\,m\big)\big),$$

dove $\text{ipad}$ (hash interno) e $\text{opad}$ (hash esterno) sono valori fissi ($\texttt{0x36}$ e $\texttt{0x5c}$) ripetuti $B$ volte. Perché due hash e non semplicemente $H(K\,\|\,m)$: con le funzioni costruite alla Merkle-Damgård (MD5, SHA-1, SHA-2) chi conosce $H(K\,\|\,m)$ può calcolare l'hash di $K\,\|\,m\,\|\,\text{padding}\,\|\,m'$ continuando la catena dallo stato finale, senza conoscere $K$ (length extension); l'hash esterno dell'HMAC chiude la catena e lo impedisce. Con $\text{ipad}$ e $\text{opad}$ diversi, le due chiavi usate nei due hash sono diverse anche se partono dalla stessa $K$.

Esempio. Con $K=$ chiave-segreta e $m=$ bonifico:100:IT60, HMAC-SHA256 $=$ bc838925c97eca28…; per $m'=$ bonifico:900:IT60 si ottiene dadd0ebe877f0fc5…. Chi cambia 100 in 900 non sa ricalcolare il tag giusto senza $K$. Con il solo SHA-256 (4a8354a1a8c53cb1… per $m$) l'avrebbe saputo ricalcolare. (La formula è stata verificata calcolando a mano ipad, opad e i due SHA-256: coincide con la libreria standard.)

Proprietà (MAC contro firma digitale).

aspetto	MAC	firma digitale
si basa su	chiave simmetrica (segreto condiviso)	chiavi asimmetriche (privata e pubblica)
proprietà della chiave	condivisa tra mittente e destinatario	privata del mittente, pubblica di tutti
come funziona	mittente e destinatario usano la stessa chiave segreta per generare e verificare	il mittente firma con la chiave privata, il destinatario verifica con la pubblica
scopo principale	integrità + autenticazione	integrità + autenticazione + non ripudio

La firma è spiegata in Crittografia asimmetrica, RSA e TLSCrittografia asimmetrica (a chiave pubblica): chiave di cifratura pubblica v_B, chiave di decifratura privata s_B, matematicamente legate; C = E_vB(P), P = D_sB(C); dà riservatezza. I certificati digitali, emessi da una Certificate Authority e firmati con la sua chiave privata, legano un'identità a una chiave pubblica. Firma digitale: hash del messaggio cifrato con la chiave privata; garantisce autenticità, integrità e non ripudio. RSA: si scelgono due primi grandi p e q, N = pq, phi(N) = (p-1)(q-1), e coprimo con phi(N), d = e^(-1) mod phi(N); chiave pubblica (N, e), segreta (N, d); cifratura c = m^e mod N, decifratura m = c^d mod N con m < N (teorema di Eulero); sicura finché la fattorizzazione è difficile (N di almeno 2048 bit); il padding casuale (PKCS#1 v1.5: 00 02 [casuale] 00 [m]) difende da malleabilità e determinismo. La firma RSA è s = m^d mod N, verificata con s^e mod N. TLS (su TCP) autentica gli estremi con il certificato, cifra i dati con una chiave di sessione simmetrica e garantisce l'integrità con i MAC; da TLS 1.0 a 1.3 la chiave si ricava con Diffie-Hellman e l'handshake si accorcia. DTLS è la versione per UDP.Crittografia asimmetrica, RSA e TLS →. Il MAC garantisce integrità e autenticazione tra chi condivide la chiave, ma non il non ripudio: anche il destinatario avrebbe potuto generare lo stesso tag.

Errori comuni

• Credere che un hash sia una cifratura: non si inverte e non ha chiave. Né lo è base64 (Posta elettronica - SMTP, POP3 e IMAPLa posta elettronica è una transazione a senso unico: non ha senso che il destinatario tenga un server sempre acceso, quindi si usano server intermedi. Servono due User Agent (UA, il programma dell'utente), due programmi client/server di spinta (MTA, protocollo SMTP: mittente-suo server e server-server) e un programma client/server di tiro (MAA, POP3 o IMAP4: server del destinatario-destinatario). SMTP usa TCP porta 25, comandi HELO, MAIL FROM, RCPT TO, DATA, QUIT e risposte a tre cifre (220 pronto, 250 ok, 354 inizia il testo, 221 chiusura, 421 non disponibile) in tre fasi: apertura, trasferimento, chiusura. POP3 (porta 110): utente e password, poi elenca e scarica i messaggi uno a uno; non organizza la posta sul server. IMAP4 aggiunge intestazioni prima del download, ricerca, download parziale, cartelle sul server. MIME permette di spedire dati non ASCII (immagini, video, lettere accentate) traducendoli in ASCII a 7 bit, per esempio in base64 (3 byte diventano 4 caratteri).Posta elettronica - SMTP, POP3 e IMAP →).
• Usare ECB: i blocchi uguali danno cifrati uguali. Usare lo stesso IV più volte in CBC, OFB o CTR.
• Pensare che cifrare dia anche integrità: serve un MAC (o una firma).
• Dire che MD5 e SHA-1 sono sicuri: le collisioni sono note.
• Confondere la chiave di 56 bit del DES con quella di 64 bit in ingresso (8 bit servono al controllo).
• Credere che Diffie-Hellman cifri dei messaggi: stabilisce solo una chiave condivisa, e da solo non autentica.