Crittografia asimmetrica, RSA e TLS

In questa pagina 8

La crittografia asimmetrica

Definizione (crittografia asimmetrica). Detta anche a chiave pubblica. Usa chiavi diverse per cifrare e decifrare. La chiave di cifratura è pubblica e può essere visibile a tutti; la chiave di decifratura è privata, tenuta segreta da ogni nodo e conservata in registri protetti dall'hardware. Le due chiavi sono generate da un metodo che calcola una coppia corrispondente: sono legate matematicamente.

Se il mittente A vuole scrivere a B, indicando con $v_B$ la chiave pubblica di B e con $s_B$ la sua chiave privata:

$C=E_{v_B}(P),\qquad P=D_{s_B}(C).$

Proprietà richieste:

gli algoritmi di cifratura e decifratura sono facili da calcolare;
è computazionalmente facile generare una coppia di chiavi;
è computazionalmente impraticabile ricavare la chiave privata dalla corrispondente chiave pubblica;
dati il testo cifrato e la chiave pubblica, è impraticabile ricostruire il testo in chiaro.

Per cifrare si usa la chiave pubblica (che chiunque può avere): dopo la cifratura il messaggio è rimescolato e nessuno lo capisce senza la chiave privata corrispondente. La riservatezza è garantita perché solo il destinatario B conosce la propria chiave privata. Chi intercetta ottiene il testo cifrato e accede alla chiave pubblica, ma non riesce a ricostruire il messaggio.

Esempio. In una rete di $n=100$ persone servono $100$ coppie di chiavi, una per persona (e non $\binom{100}{2}=\frac{100\cdot99}2=4950$ chiavi segrete come nella crittografia simmetrica, Funzioni hash e crittografia simmetrica: lì ogni coppia di persone ha una chiave segreta propria, e le coppie non ordinate di $100$ persone si contano con il coefficiente binomiale), e ciascuno può pubblicare la sua chiave pubblica su un sito. Ma una chiave pubblica va distribuita e il suo legame con il proprietario va certificato: lo fanno i certificati.

Certificati digitali

Se un messaggio è cifrato con la chiave pubblica di qualcuno, solo la sua chiave privata lo decifra. Le chiavi pubbliche però devono essere distribuite in qualche modo, e il collegamento tra proprietario e chiave deve essere certificato: ci deve essere un rapporto di fiducia tra chiave pubblica e privata. I certificati digitali servono a questo.

Definizione (certificato digitale). Un certificato è gestito da una terza parte, la Certificate Authority (CA). Per ottenerlo, un'entità fornisce alla CA la propria identità e la propria chiave pubblica; la CA convalida l'identità ed emette il certificato. Il certificato contiene: il nome dell'entità proprietaria e la sua chiave pubblica; la validità o scadenza; la CA che l'ha emesso (e molti altri dati). È firmato con la chiave privata della CA: chiunque abbia la sua chiave pubblica può verificare il certificato.

Esempio (come nelle slide). Visitando https://www.google.com, il browser controlla automaticamente il certificato digitale inviato da Google. Un certificato reale contiene: nome del sito www.google.com; chiave pubblica (una lunga stringa casuale); emittente (Google Trust Services LLC, la CA); periodo di validità (per esempio da marzo 2025 a marzo 2026); firma della CA, che prova che è legittimo. Il browser lo controlla: se è valido pensa "questa chiave pubblica appartiene davvero a Google", e può cifrare i dati verso Google in sicurezza.

Il browser verifica la firma con la chiave pubblica della CA, che a sua volta ha un certificato firmato da una CA di livello superiore, fino a una CA radice il cui certificato è già nell'elenco del sistema operativo o del browser (catena di fiducia); controlla anche le date di validità e che il nome del sito corrisponda a quello del certificato.

Firma digitale

Se un messaggio è cifrato con la propria chiave privata, chiunque abbia la chiave pubblica può verificare che sia stato proprio il proprietario a mandarlo. La firma digitale serve a questo e garantisce:

autenticità (il messaggio viene davvero dal mittente);
integrità (il messaggio non è stato alterato);
non ripudio (il mittente non può negare in seguito di averlo mandato).

Definizione (firma digitale). Fase 1, firma: si calcola l'hash del messaggio (con una funzione hash crittografica come SHA-256, Funzioni hash e crittografia simmetrica); si cifra l'hash con la chiave privata: questa è la firma; si manda il messaggio insieme alla firma. Fase 2, verifica: il ricevente calcola da sé l'hash del messaggio; decifra la firma ricevuta con la chiave pubblica del mittente; se hash decifrato == hash calcolato, il messaggio è autentico.

La firma cifra con la chiave privata (e può verificare chiunque); la cifratura riservata usa la chiave pubblica del destinatario (e solo lui legge): i ruoli sono opposti. Si firma l'hash e non l'intero messaggio perché è corto e il calcolo è veloce. Il confronto con il MAC è nella tabella di Funzioni hash e crittografia simmetrica. Un esempio numerico con RSA è più sotto.

Richiami di aritmetica modulare

Un intero $n$ si scrive come $n=q\cdot d+r$ , con $q$ quoziente, $d$ modulo (divisore), $r$ resto: $n\bmod d=r$ .

Esempi (come nelle slide). Addizione: $27\bmod6=3$ . Sottrazione: $6\bmod4=2$ . Moltiplicazione: $21\bmod6=3$ . Esponenziazione: $81\bmod4=1$ .

Addizione, sottrazione, moltiplicazione ed esponenziazione si comportano come ci si aspetta (modulo $d$ ).

Perché si può ridurre prima di operare. Se $a=q_1d+r_1$ e $b=q_2d+r_2$ (con $r_1=a\bmod d$ , $r_2=b\bmod d$ ), allora $a\,b=(q_1d+r_1)(q_2d+r_2)=d\,(q_1q_2d+q_1r_2+q_2r_1)+r_1r_2,$ cioè $a\,b$ e $r_1r_2$ hanno lo stesso resto modulo $d$ : $(a\,b)\bmod d=\big((a\bmod d)(b\bmod d)\big)\bmod d$ . Lo stesso vale per la somma. È la regola che permette di non far mai crescere i numeri: dopo ogni prodotto si riduce modulo $d$ e si resta sotto $d$ . Esempio con $N=3233$ : $65^2=4225=1\cdot3233+992$ , quindi $65^2\equiv992$ ; per $65^4$ non si calcola $4225^2$ ma $992^2=984064=304\cdot3233+1232$ , quindi $65^4\equiv1232\pmod{3233}$ . Calcolare $g^a$ vuol dire moltiplicare $g$ per se stesso $a$ volte (non è efficiente in questo modo, ma esistono algoritmi efficienti, come le potenze ripetute).

Potenze ripetute (square-and-multiply). Si scrive l'esponente in binario (Sistemi di numerazione posizionali) e si calcolano i quadrati successivi $g,\,g^2,\,g^4,\,g^8,\dots$ (ciascuno è il quadrato del precedente, ridotto modulo $d$ ); poi si moltiplicano, sempre riducendo, solo i quadrati che corrispondono alle cifre $1$ . Esempio: $17=10001_2=16+1$ , quindi $g^{17}=g^{16}\cdot g^{1}$ , e $g^{16}$ richiede $4$ quadrati: in tutto $5$ moltiplicazioni al posto di $16$ . In generale un esponente di $k$ bit richiede al massimo $2k$ moltiplicazioni modulari: per $2753=101011000001_2$ ( $12$ bit, cinque cifre $1$ ) sono $11$ quadrati e $4$ prodotti, $15$ moltiplicazioni invece di $2752$ ; con un esponente di $2048$ bit sono al massimo circa $4000$ moltiplicazioni invece di un numero di operazioni con più di $600$ cifre decimali. La divisione funziona diversamente: si usa l'inverso modulare.

Definizione (inverso modulare). $b^{-1}$ è l'inverso modulare di $b$ modulo $d$ se $b\cdot b^{-1}\equiv1\pmod d$ . Esiste se $\gcd(b,d)=1$ (cioè se $b$ e $d$ sono coprimi); quindi, se $d=p$ è primo, ogni intero tra 1 e $p-1$ ha un inverso modulo $p$ . La divisione modulare è $(a/b)\bmod d=(a\cdot b^{-1})\bmod d$ .

Come si trova l'inverso: algoritmo di Euclide esteso. L'algoritmo di Euclide dà il $\gcd$ con una sequenza di divisioni con resto; risalendo le divisioni all'indietro si scrive il $\gcd$ come combinazione $1=x\,b+y\,d$ . Riducendo modulo $d$ resta $x\,b\equiv1$ , cioè $x$ è l'inverso. Se il $\gcd$ è diverso da $1$ questa combinazione non esiste e l'inverso non c'è.

Esempio: inverso di $b=17$ modulo $d=3120$ (serve in RSA, sotto).

Divisioni (ciascuna usa come divisore il resto della precedente): $3120=183\cdot17+9$ ; $17=1\cdot9+8$ ; $9=1\cdot8+1$ . L'ultimo resto non nullo è $1$ : $\gcd=1$ , l'inverso esiste.
Si risale: $1=9-8$ ; poiché $8=17-9$ , $1=9-(17-9)=2\cdot9-17$ ; poiché $9=3120-183\cdot17$ , $1=2(3120-183\cdot17)-17=2\cdot3120-367\cdot17$ .
Modulo $3120$ il termine $2\cdot3120$ vale $0$ , quindi $-367\cdot17\equiv1$ e $17^{-1}\equiv-367\equiv3120-367=2753$ .

Esempio. $b=4$ , $d=7$ : deve valere $4\cdot b^{-1}\equiv1\pmod7$ , quindi $b^{-1}=2$ , infatti $4\cdot2=8\equiv1$ . $b=5$ , $d=11$ : $b^{-1}=9$ , infatti $5\cdot9=45=4\cdot11+1\equiv1$ . Divisione: $(8/4)\bmod5=(8\cdot4^{-1})\bmod5$ ; poiché $4^{-1}=4\pmod5$ ( $4\cdot4=16\equiv1$ ), $=(8\cdot4)\bmod5=2$ . Altri: $(8/3)\bmod5=1$ , $(11/4)\bmod5=4$ (verificati con Python). La divisione per 0 non è ammessa.

Definizione (logaritmo discreto). Se $b^a\equiv y\pmod d$ , allora $\log_b y=a$ è il logaritmo discreto. Non si conosce alcun algoritmo in tempo polinomiale per calcolarlo.

Esempio. $b=5$ , $d=7$ , $y=4$ : $5^a\equiv4\pmod7$ . Le potenze di 5 modulo 7 sono $5,4,6,2,3,1$ per $a=1,\dots,6$ : $5^2\equiv4$ , quindi $a=2$ . Con $d$ di 2048 bit non si può più provare.

RSA

Il Diffie-Hellman (Funzioni hash e crittografia simmetrica) serve a far concordare due parti sulla stessa chiave condivisa, e poi si cifra con un cifrario simmetrico. Nella crittografia a chiave pubblica c'è una seconda idea, la cifratura a chiave pubblica (Public Key Encryption, PKE). L'algoritmo RSA prende il nome dagli inventori Rivest, Shamir e Adleman (1978). Come Diffie-Hellman si appoggia sulla difficoltà del logaritmo discreto, RSA si appoggia sulla difficoltà della fattorizzazione di numeri grandi.

Situazione: il mittente Alice, il ricevente Bob. Obiettivo: generare una chiave pubblica con cui Alice cifra i messaggi per Bob e una chiave privata che aiuta Bob a decifrarli.

Formula (generazione delle chiavi RSA).

Si scelgono due numeri primi grandi $p$ e $q$ .

Si calcola $N=p\,q$ .

Si calcola il totiente $\varphi(N)=(p-1)(q-1)$ , cioè quanti interi tra $1$ e $N-1$ sono coprimi con $N$ (motivazione sotto).

Si trova un intero positivo $e<\varphi(N)$ coprimo con $\varphi(N)$ , cioè $\gcd(e,\varphi(N))=1$ .

Si calcola $d=e^{-1}\bmod\varphi(N)$ .

$e^{-1}$ esiste, perché $e$ e $\varphi(N)$ sono coprimi; $e$ e $d$ sono uno l'inverso modulare dell'altro: $d\,e\equiv1\pmod{\varphi(N)}$ (per costruzione: proprietà P1).

Chiave pubblica di Bob: $PK=(N,e)$ , comunicata a chiunque voglia scrivergli. Chiave segreta: $SK=(N,d)$ ; le informazioni segrete sono la quaterna $SI=(p,q,d,\varphi(N))$ , che non va condivisa con nessuno.

Formula (cifratura e decifratura RSA). Bob manda a Alice $PK=(N,e)$ . Alice cifra il messaggio $m$ (con $m<N$ ): $c=\text{Enc}(m,PK)=m^e\bmod N$ . Bob decifra con la chiave segreta: $m=\text{Dec}(c,SK)=c^d\bmod N$ . Il blocco di messaggio può essere al massimo lungo quanto $N$ .

Perché $\varphi(N)=(p-1)(q-1)$ . Gli interi da $1$ a $N-1$ non coprimi con $N=pq$ sono quelli divisibili per $p$ o per $q$ (gli unici divisori primi di $N$ ). I multipli di $p$ sono $p,2p,\dots,(q-1)p$ : sono $q-1$ ; i multipli di $q$ sono $p-1$ ; nessun numero è multiplo di entrambi (sarebbe multiplo di $pq=N$ ). Quindi i coprimi sono $(N-1)-(q-1)-(p-1)=pq-p-q+1=(p-1)(q-1)$ . Con $p=61$ , $q=53$ : $3232-52-60=3120$ .

Perché funziona (teorema di Eulero). Per ogni intero (messaggio) $m$ coprimo con $N$ vale $m^{\varphi(N)}\equiv1\pmod N$ . Idea della dimostrazione: siano $u_1,\dots,u_\varphi$ gli interi coprimi con $N$ (modulo $N$ ). Moltiplicarli per $m$ (coprimo) li rimescola senza ripetizioni né uscite dall'insieme: $m\,u_1,\dots,m\,u_\varphi$ sono ancora gli stessi numeri, in un altro ordine. Il prodotto di tutti è quindi lo stesso, $m^{\varphi}U\equiv U$ con $U=u_1\cdots u_\varphi$ , e siccome $U$ è coprimo con $N$ si può dividere per $U$ (inverso modulare), ottenendo $m^\varphi\equiv1$ . Esempio con $N=15$ ( $\varphi=8$ , coprimi $1,2,4,7,8,11,13,14$ ): moltiplicando per $m=2$ si ottiene $2,4,8,14,1,7,11,13$ , gli stessi numeri; e infatti $2^8=256=17\cdot15+1\equiv1$ . Per $N=p$ primo è il piccolo teorema di Fermat, $m^{p-1}\equiv1$ . Poiché $d\,e\equiv1\pmod{\varphi(N)}$ per P1, si ha $d\,e=1+k\,\varphi(N)$ per un certo $k$ , e quindi

$c^d\equiv\left(m^e\right)^d=m^{ed}=m^{1+k\varphi(N)}=m\cdot\left(m^{\varphi(N)}\right)^k\equiv m\cdot1^k=m\pmod N.$

Passaggi: la prima uguaglianza sostituisce $c\equiv m^e$ ; $(m^e)^d=m^{ed}$ per le regole delle potenze (Esponenziale e logaritmo); $ed=1+k\varphi(N)$ viene da $ed\equiv1\pmod{\varphi(N)}$ ; $m^{1+k\varphi}=m\cdot(m^{\varphi})^k$ ; e $m^\varphi\equiv1$ per Eulero.

Il caso di $m$ non coprimo con $N$ è rarissimo con $N$ grande (vuol dire che $m$ è un multiplo di $p$ o di $q$ ), ma il risultato vale lo stesso. Se $p$ divide $m$ : modulo $p$ si ha $m\equiv0$ e quindi $m^{ed}\equiv0\equiv m$ ; modulo $q$ , $m$ è coprimo con $q$ e per Fermat $m^{q-1}\equiv1$ , perciò $m^{ed}=m\cdot(m^{q-1})^{k(p-1)}\equiv m$ . Poiché $m^{ed}-m$ è divisibile sia per $p$ sia per $q$ , lo è per $N=pq$ .

Esempio completo (numeri piccoli). $p=61$ , $q=53$ : $N=3233$ , $\varphi(N)=60\cdot52=3120$ . Si prende $e=17$ (coprimo con $3120=2^4\cdot3\cdot5\cdot13$ , perché $17$ è primo e non compare tra i fattori) e $d=e^{-1}\bmod3120=2753$ (calcolato con Euclide esteso nella sezione sopra), perché $17\cdot2753=46801=15\cdot3120+1\equiv1$ . Messaggio $m=65$ : $c=65^{17}\bmod3233$ . Con le potenze ripetute ( $17=10001_2=16+1$ , ogni valore è il quadrato del precedente ridotto modulo $3233$ ): $65^2\equiv992$ , $65^4\equiv1232$ , $65^8\equiv1547$ , $65^{16}\equiv789$ , quindi $65^{17}=65^{16}\cdot65\equiv789\cdot65=51285=15\cdot3233+2790\equiv\mathbf{2790}$ (per esempio l'ultimo quadrato è $1547^2=2393209=740\cdot3233+789$ ). Decifratura: $2790^{2753}\bmod3233=65$ (verificato con Python; verificato anche $65^{3120}\equiv1$ ). Chiave pubblica $(3233,17)$ , segreta $(3233,2753)$ ; il messaggio deve essere minore di 3233.

Sicurezza.

Se un attaccante riuscisse a fattorizzare $N$ in $p$ e $q$ , potrebbe calcolare la chiave segreta. RSA è sicuro se e solo se la fattorizzazione degli interi è difficile per quelle scelte di interi.
$p$ e $q$ si scelgono a caso, devono essere primi e grandi, e $N$ deve superare i 2048 bit (circa 617 cifre decimali: $2^{2048}=10^{2048\log_{10}2}\approx10^{616{,}5}$ , Esponenziale e logaritmo) per evitare gli algoritmi di fattorizzazione oggi noti.
La struttura del modulo è scelta per evitare attacchi ovvi e non ovvi: per esempio, fare di $N$ il prodotto di due primi della stessa dimensione evita alcuni attacchi noti (primi da 1500 a 3000 bit).
Come per Diffie-Hellman, ci sono molte altre proprietà sottili della generazione delle chiavi e della decifratura che, se implementate male, creano vulnerabilità anche se l'algoritmo sembra semplice.

Padding casuale. Una caratteristica da implementare obbligatoriamente è un riempimento casuale (random padding). Per esempio con RSA PKCS #1 v1.5 il messaggio completato è $m_p=\texttt{00}\;\texttt{02}\;[\text{stringa casuale}]\;\texttt{00}\;[m]$ . La dimensione utile del messaggio diminuisce, per lasciare posto alla stringa di riempimento (il blocco massimo resta $N$ ). Il padding risolve l'attacco a testo cifrato scelto adattivo e dà sicurezza semantica; PKCS #1 v1.5 è molto usato oggi.

Autenticazione con RSA

Si vuole una prova certificata dell'identità di un server o, più formalmente, che (i) un certo documento digitale sia stato generato da un'entità legittima e (ii) non sia stato modificato strada facendo. Il server manda un pacchetto $P=[\,m\mid s\,]$ con un messaggio $m$ in chiaro (per esempio un certificato di identità) con in coda una firma digitale $s$ .

il server ottiene la firma $s$ del messaggio $m$ usando la chiave segreta $SK=(N,d)$ : $s=m^d\bmod N$ ;
il client verifica che la firma sia corretta con la chiave pubblica $PK=(N,e)$ : calcola $s^e\bmod N$ .

Se il risultato è uguale a $m$ , è una prova certificata (per la struttura algebrica) che il messaggio è stato firmato dall'entità legittima, l'unica che conosce la chiave segreta.

Esempio (chiavi sopra). Il server firma $m=100$ : $s=100^{2753}\bmod3233=1391$ . Il client calcola $1391^{17}\bmod3233=100=m$ : firma valida. Se il messaggio arrivasse cambiato in $m'=101$ , il client calcolerebbe $1391^{17}\bmod3233=100\ne101$ e scarterebbe il pacchetto. Con la firma sull'hash (come nella sezione "Firma digitale") si firma $h=H(m)$ al posto di $m$ : con un hash di valore $42$ si ha $s=42^{2753}\bmod3233=3065$ e $3065^{17}\bmod3233=42$ .

Attacchi a RSA semplice (appendice)

Malleabilità (attacco a testo cifrato scelto adattivo). Con l'RSA "nudo", Mallory può farsi decifrare il messaggio di Alice.

Mallory intercetta il messaggio cifrato $c=m^e\bmod N$ .
Sceglie un numero casuale $a$ .
Calcola un nuovo testo cifrato (con la chiave pubblica) $c'=c\cdot a^e\bmod N=(m\,a)^e\bmod N=\text{Enc}(m\,a,PK)$ .
Manda $c'$ a Bob, che lo decifra e ritorna $m\,a$ a Mallory.
Mallory calcola $(m\,a)\cdot a^{-1}\bmod N=m$ : ha ottenuto il messaggio.

Il passo 4 dipende dal contesto e dall'applicazione (il server può restituire o no il testo in chiaro), ma ci sono casi pratici in cui succede; la robustezza a questo attacco è oggi un requisito standard per un algoritmo di sicurezza.

Esempio ( $N=3233$ , $e=17$ , $m=65$ , $c=2790$ ). Con $a=2$ : $c'=2790\cdot2^{17}\bmod3233=3017$ . Bob decifra $3017^{2753}\bmod3233=130=65\cdot2$ . Mallory ottiene $130\cdot2^{-1}\bmod3233=65=m$ .

Determinismo. L'RSA nudo non è semanticamente sicuro: con la stessa chiave pubblica $(N,e)$ e lo stesso messaggio $m$ il testo cifrato $c=m^e\bmod N$ è sempre lo stesso, a ogni cifratura successiva.

Contromisura. Alice costruisce $m_p=m+p$ con un riempimento casuale $p$ . Mallory intercetta $c=m_p^e\bmod N$ , sceglie $a$ e produce $c'=(m_p\,a)^e\bmod N$ ; Bob lo decifra, elimina il riempimento dal risultato e restituisce un $m'\ne m\,a$ ; quindi $(m')\,a^{-1}\bmod N\ne m$ : il riempimento ha distrutto la struttura algebrica.

Attacco alle firme RSA semplici. Un attaccante vuole ottenere da un server la firma $s(m)$ di un messaggio $m$ (conosce $PK=(N,e)$ ).

Calcola un messaggio apparentemente innocuo $m'=(m\,a^{e})\bmod N$ per qualche $a$ .
Chiede al server di firmare $m'$ , ottenendo $s(m')=(m')^d\bmod N$ .
Calcola $s(m')\cdot a^{-1}\bmod N=(m^d\cdot a^{ed})\cdot a^{-1}=m^d\bmod N=s(m)$ , perché $a^{ed}\equiv a$ (stessa dimostrazione della decifratura; $a^{-1}$ esiste perché $a$ è coprimo con $N$ ).

Esempio ( $m=7$ , $a=2$ ). $m'=7\cdot2^{17}\bmod3233=2565$ ; il server firma: $s(m')=2565^{2753}\bmod3233=2101$ ; l'attaccante ottiene $2101\cdot2^{-1}\bmod3233=2667$ , che è proprio $s(7)=7^{2753}\bmod3233=2667$ : ha una firma su $m=7$ senza averla mai chiesta. Per questo si firma l'hash con padding (PSS) e non il messaggio nudo.

Dove si mette la sicurezza: applicazione o trasporto

Alcuni protocolli ISO/OSI non offrono funzioni di sicurezza: queste sono realizzate dall'applicazione o da uno dei livelli sotto.

Sicurezza a livello applicazione: si può garantire una protezione end-to-end; semplifica i requisiti dei livelli sotto e riduce il costo in dimensione dei pacchetti ed elaborazione, perché l'overhead è introdotto per dato e non per pacchetto.
Sicurezza a livello trasporto o rete: lo stesso meccanismo di sicurezza può essere condiviso da più applicazioni.

TLS e SSL

Definizione (SSL/TLS). SSL e TLS (Secure Socket Layer, Transport Layer Security) sono protocolli crittografici che garantiscono una comunicazione affidabile in rete. SSL (3.0) è ancora usato ma ha vulnerabilità note (POODLE) e se ne sconsiglia l'uso; TLS è la versione più recente e più sicura, ed è quella raccomandata. Sono progettati per funzionare con TCP (TCP - connessione, affidabilità e controllo di flusso) e usano i certificati per stabilire un collegamento cifrato tra client e server.

Le funzioni principali:

autenticare gli estremi e definire l'insieme delle chiavi crittografiche;
scambiare dati riservati con la cifratura simmetrica;
autenticare i messaggi con un hash sicuro.

Il certificato contiene una chiave pubblica che autentica l'identità del sito o server e permette il trasferimento cifrato dei dati con la crittografia asimmetrica.

Come funziona.

Il client chiede l'accesso a una risorsa protetta su un server.
Il server risponde con il proprio certificato, che include la chiave pubblica e la sua firma.
Il client verifica che il certificato sia valido e fidato (emesso da una CA, non scaduto, firma del server valida): così il server è autentico.
Il client genera una chiave di sessione simmetrica e la cifra con la chiave pubblica del server: la chiave di sessione arriva al server in modo sicuro.
Il server decifra la chiave di sessione con la propria chiave privata.
Le due parti usano la chiave di sessione simmetrica per trasmettere e ricevere i dati su un canale cifrato.

I messaggi (TLS 1.0): (1) ClientHello (cifrari supportati); (2) ServerHello (cifrario scelto); (3) certificato del server + firma; (4) il client verifica il certificato; (5) client key exchange, cifrato con la chiave pubblica del server; (6) il server ottiene la chiave di sessione con la sua chiave privata; (7) Client finished; (8) Server finished; poi i messaggi scambiati sono cifrati con la chiave di sessione condivisa.

Client                                                          Server
  |--(1) ClientHello: cifrari supportati --------------------------->|
  |<-(2) ServerHello: cifrario scelto ------------------------------|
  |<-(3) certificato del server + firma ----------------------------|
  | (4) verifica il certificato                                      |
  |--(5) client key exchange (cifrato con la chiave pubblica) ------>|
  |                          (6) ricava la chiave di sessione con la chiave privata
  |--(7) Client finished ------------------------------------------>|
  |<-(8) Server finished -------------------------------------------|
  |<=============== dati cifrati con la chiave di sessione ==========>|

Chiavi usate.

Chiave asimmetrica: la coppia pubblica/privata identifica il server e avvia la sessione cifrata. La chiave privata è nota solo al server; la pubblica è condivisa con il certificato.
Chiave di sessione simmetrica: chiavi usa e getta generate per ogni connessione, usate per cifrare e decifrare i dati trasmessi. Sono scambiate in modo sicuro con la cifratura asimmetrica.

Servizi offerti.

Autenticazione: i certificati sono emessi da una CA fidata, firmati e verificati dal client: prova dell'identità.
Cifratura: asimmetrica per stabilire la connessione sicura, simmetrica per trasmettere i dati: riservatezza.
Integrità dei dati: a tutti i messaggi sono aggiunti codici di autenticazione (MAC, Funzioni hash e crittografia simmetrica) per assicurare che i dati non siano alterati in transito.

Da TLS 1.0 a TLS 1.3

Usare la stessa coppia di chiavi (pubblica, privata) sia per l'autenticazione sia per generare poi la chiave condivisa non si fa più. Motivo: se un attaccante registra tutta la transazione (leggendo i pacchetti che viaggiano in rete), con calma riesce a rompere la chiave (cioè a recuperare la chiave privata del server) e ottiene l'accesso a tutte le transazioni cifrate successive, e anche a quelle già registrate. L'approccio attuale:

si usa Diffie-Hellman per generare la chiave condivisa (così la chiave privata del server serve solo a firmare);
si riduce la latenza: l'accordo sulle suite crittografiche non è più fatto in un passo a parte.

TLS 1.3
Client                                                            Server
  |--(1) ClientHello [Random, g^c mod p] ------------------------->|
  | (2) K = (g^s mod p)^c           |<-(3) ServerHello [Random, g^s mod p]
  |                                   (4) K = (g^c mod p)^s
  |<-(5) Certificate + Sign(Ks, handshake (1)+(3)), Finished, dati applicativi
  |--(6) Finished ---------------------------------------------------->|
  |--(7) dati applicativi ============================================>|

La chiave Diffie-Hellman $K$ è generata dopo i primi due messaggi; il certificato (5) è cifrato con $K$ e la firma contiene i messaggi (1)+(3); i numeri casuali (nonce) nei messaggi Hello garantiscono l'unicità; $K_s$ è la chiave privata del server (la pubblica è nel certificato). Con autenticazione del client, il server aggiunge una richiesta di certificato in (5) e il client risponde in (6) con il proprio certificato e una firma $\text{Sign}(K_c,\text{handshake})$ , dove $K_c$ è la chiave privata del client.

Esempio numerico (DH nell'handshake, $p=23$ , $g=5$ ). Il client sceglie $c=6$ e manda $g^c\bmod p=5^6\bmod23=8$ ; il server sceglie $s=15$ e manda $5^{15}\bmod23=19$ . Il client calcola $K=19^6\bmod23=2$ ; il server $K=8^{15}\bmod23=2$ . Passaggi con le potenze ripetute: $5^2=25\equiv2$ , $5^4\equiv4$ , $5^6=5^4\cdot5^2\equiv4\cdot2=8$ ; $5^8\equiv16$ e $15=8+4+2+1$ , quindi $5^{15}\equiv16\cdot4\cdot2\cdot5=640=27\cdot23+19\equiv19$ ; infine $19\equiv-4$ , $19^6\equiv(-4)^6=4096=178\cdot23+2\equiv2$ (e i due calcoli concordano perché $(g^s)^c=g^{sc}=(g^c)^s$ ). Da $K$ si ricavano le chiavi simmetriche dei record. In TLS reale $p$ è di almeno 2048 bit (oppure si usa Diffie-Hellman su curve ellittiche). Poiché $K$ è effimero (diverso a ogni connessione e buttato via), la compromissione futura della chiave privata del server non permette di decifrare il traffico registrato (forward secrecy).

Esempio (numero di RTT). Nell'handshake TLS 1.0 ci sono due scambi (messaggi 1-3 e 5-8) prima che i dati siano protetti: 2 RTT; in TLS 1.3 il client manda già la propria parte Diffie-Hellman nel primo messaggio: 1 RTT. Una prima richiesta HTTPS (Livello applicazione - HTTP) con $\text{RTT}=100$ ms costa quindi: TCP 1 RTT + TLS 1.3 1 RTT + richiesta 1 RTT $=3$ RTT $=0{,}3$ s; con TLS 1.0, $1+2+1=4$ RTT $=0{,}4$ s.

Le due parti del protocollo.

Protocollo di handshake: negozia modi e parametri crittografici, autentica le parti, stabilisce il materiale della chiave condivisa. Il Server Hello include il livello di protocollo di sicurezza, i parametri crittografici scelti dall'elenco del client, un numero casuale combinato con data e ora, l'identificatore di sessione, i metodi di compressione, il certificato digitale (con identità e chiave pubblica di cifratura).
Protocollo di record: usa i parametri stabiliti dall'handshake per proteggere il traffico tra gli estremi, dividendolo in una serie di record, ognuno protetto in modo indipendente con le chiavi di traffico.

DTLS (Datagram TLS) è il progetto per funzionare con UDP (Protocollo UDP). Problema: l'overhead di DTLS, perché i protocolli sotto hanno dimensione di pacchetto limitata, e si usano ottimizzazioni dei pacchetti e compressione. DTLS crea un'associazione sicura punto-punto (con un handshake simile a quello di TLS): non è compatibile con le comunicazioni IP multicast. Tre modi di sicurezza: PreSharedKey (i dispositivi conservano chiavi simmetriche pre-condivise), RawPublicKey (i dispositivi hanno una coppia di chiavi pubblica-privata senza certificato), Certificate (i dispositivi conservano un certificato X.509).

La sicurezza a livello di rete (IPsec) è nella nota VPN.

Errori comuni

Cifrare con la chiave sbagliata: riservatezza = chiave pubblica del destinatario; firma = chiave privata del mittente.
Usare RSA senza padding (deterministico, malleabile), o credere che RSA cifri un file intero: si cifra una chiave di sessione e i dati vanno in simmetrica.
Scegliere $e$ non coprimo con $\varphi(N)$ (non esiste $d$ ), o dimenticare $m<N$ .
Dimenticare che i certificati servono a legare l'identità alla chiave pubblica: senza, un uomo in mezzo può dare la propria chiave.
Pensare che in TLS la chiave di sessione sia sempre cifrata con la chiave pubblica del server: da TLS 1.3 si ricava con Diffie-Hellman.
Confondere TLS (su TCP) con DTLS (su UDP).

Versione ripasso

Asimmetrica (a chiave pubblica). Chiavi diverse per cifrare e decifrare, legate matematicamente: $v_B$ pubblica (cifra), $s_B$ privata (decifra). Formule: $C=E_{v_B}(P)$ , $P=D_{s_B}(C)$ . Riservatezza: solo B conosce $s_B$ ; dalla chiave pubblica non si ricava la privata. Esempio: $n=100$ persone servono $100$ coppie, contro $\frac{100\cdot99}{2}=4950$ chiavi segrete della simmetrica (Funzioni hash e crittografia simmetrica).
Certificato digitale. Emesso da una Certificate Authority (CA) dopo aver verificato l'identità del richiedente. Contiene nome del titolare, chiave pubblica, validità, emittente, ed è firmato con la chiave privata della CA. Il browser verifica la firma, le date, il nome del sito, e risale la catena di fiducia fino a una CA radice presente nel sistema operativo o nel browser.
Firma digitale. Firma: hash $H(m)$ (es. SHA-256) cifrato con la chiave privata del mittente, inviato insieme a $m$ . Verifica: il ricevente calcola $H(m)$ , decifra la firma con la chiave pubblica del mittente e confronta. Garantisce autenticità, integrità, non ripudio. Ruoli opposti rispetto alla cifratura riservata, che usa la pubblica del destinatario.
Aritmetica modulare. $n=q\,d+r$ , $n\bmod d=r$ : $27\bmod6=3$ , $6\bmod4=2$ , $21\bmod6=3$ , $81\bmod4=1$ . Inverso: $b\,b^{-1}\equiv1\pmod d$ , esiste se $\gcd(b,d)=1$ : $4^{-1}\bmod7=2$ , $5^{-1}\bmod11=9$ . Divisione modulare: $(a/b)\bmod d=(a\,b^{-1})\bmod d$ ; es. $(8/4)\bmod5=2$ , $(8/3)\bmod5=1$ . Divisione per 0 non ammessa.
Logaritmo discreto. Se $b^a\equiv y\pmod d$ , $\log_b y=a$ . Esempio: $5^2\equiv4\pmod7$ , quindi $\log_5 4=2$ . Non esiste algoritmo polinomiale noto: con $d$ di 2048 bit non si riesce a provare.
Generazione chiavi RSA. 1) $p,q$ primi grandi; 2) $N=pq$ ; 3) $\varphi(N)=(p-1)(q-1)$ ; 4) $e<\varphi(N)$ con $\gcd(e,\varphi(N))=1$ ; 5) $d=e^{-1}\bmod\varphi(N)$ , quindi $d\,e\equiv1\pmod{\varphi(N)}$ . Chiave pubblica $PK=(N,e)$ , segreta $SK=(N,d)$ ; $p,q,d,\varphi$ non si condividono.
Cifratura e decifratura RSA. $c=m^e\bmod N$ , $m=c^d\bmod N$ , con $m<N$ . Eulero: $m^{\varphi(N)}\equiv1$ , quindi $m^{ed}=m^{1+k\varphi}\equiv m$ .
Esempio completo. $p=61$ , $q=53$ : $N=3233$ , $\varphi=60\cdot52=3120$ , $e=17$ , $d=2753$ (perché $17\cdot2753=46801=15\cdot3120+1$ ). Messaggio $m=65$ : $c=65^{17}\bmod3233=2790$ ; decifratura $2790^{2753}\bmod3233=65$ . Calcolo con potenze ripetute: $65^2\equiv992$ , $65^4\equiv1232$ , $65^8\equiv1547$ , $65^{16}\equiv789$ , poi $789\cdot65\equiv2790$ .
Sicurezza RSA. Sicuro finché fattorizzare $N$ è difficile: $N$ di almeno 2048 bit (circa 617 cifre), $p$ e $q$ casuali, primi, della stessa dimensione.
Padding casuale (obbligatorio, es. PKCS#1 v1.5: 00 02 [casuale] 00 [m]). Dà sicurezza semantica e rompe la struttura algebrica usata dagli attacchi sotto. Il blocco massimo resta $N$ , ma il messaggio utile si riduce.
Firma RSA. $s=m^d\bmod N$ (con la privata), verifica $s^e\bmod N=m$ (con la pubblica). Esempio: $m=100$ , $s=100^{2753}\bmod3233=1391$ , verifica $1391^{17}\bmod3233=100$ . Se il messaggio diventa $101$ la verifica fallisce. Nella pratica si firma l'hash $h=H(m)$ : con $h=42$ , $s=3065$ .
Malleabilità (RSA nudo). Mallory intercetta $c$ , calcola $c'=c\,a^e\bmod N=\text{Enc}(m\,a)$ , Bob decifra e restituisce $m\,a$ , Mallory ottiene $m=(m\,a)\,a^{-1}$ . Esempio: $N=3233$ , $m=65$ , $c=2790$ , $a=2$ : $c'=3017$ , decifrato $130$ , quindi $130\cdot2^{-1}=65$ .
Determinismo. Senza padding lo stesso $m$ dà sempre lo stesso $c$ . Contromisura: $m_p=m+p$ con $p$ casuale.
Firma RSA nuda. Attacco: $m'=m\,a^e$ , il server firma $m'$ , l'attaccante ottiene $s(m')\,a^{-1}=s(m)$ . Esempio: $m=7$ , $a=2$ , $s(7)=2667$ ottenuta senza chiederla.
Dove sta la sicurezza. A livello applicazione la protezione è end-to-end e l'overhead è per dato; a livello trasporto o rete lo stesso meccanismo è condiviso da più applicazioni.
TLS (su TCP) e SSL. Autentica gli estremi con il certificato, cifra i dati con una chiave di sessione simmetrica (usa e getta, una per connessione), garantisce integrità con MAC (Funzioni hash e crittografia simmetrica). SSL 3.0 ha vulnerabilità note (POODLE): si sconsiglia; TLS è la versione raccomandata (TCP - connessione, affidabilità e controllo di flusso).
Sequenza TLS 1.0. 1) ClientHello (cifrari supportati); 2) ServerHello (cifrario scelto); 3) certificato del server + firma; 4) il client verifica il certificato; 5) client key exchange: chiave di sessione cifrata con la pubblica del server; 6) il server la decifra con la privata; 7) Client finished; 8) Server finished. Poi tutto è cifrato con la chiave di sessione.
TLS 1.3 (Diffie-Hellman). Non si usa più la stessa coppia per autenticare e generare la chiave: un attaccante che registra il traffico e rompe la chiave privata del server leggerebbe tutte le sessioni. Con DH la privata serve solo a firmare. $K=(g^s)^c=(g^c)^s$ si genera dopo i primi due messaggi; il certificato è cifrato con $K$ ; la firma copre i messaggi (1)+(3). Esempio con $p=23$ , $g=5$ , $c=6$ , $s=15$ : $5^6\equiv8$ , $5^{15}\equiv19$ , $K=19^6\equiv2\equiv8^{15}$ . In TLS reale $p$ è di almeno 2048 bit (o curve ellittiche).
Forward secrecy. $K$ è effimero e buttato via: la compromissione futura della chiave privata non rivela il traffico registrato.
Costo in RTT. TLS 1.0: 2 RTT prima dei dati protetti; TLS 1.3: 1 RTT. HTTPS con $\text{RTT}=100$ ms: TCP 1 + TLS 1.3 1 + richiesta 1 = 3 RTT $=0{,}3$ s (con TLS 1.0 $=0{,}4$ s). Vedi Livello applicazione - HTTP.
Handshake e record. L'handshake negozia parametri, autentica e stabilisce le chiavi; il protocollo di record protegge i dati in record indipendenti.
DTLS (per UDP, Protocollo UDP): overhead maggiore, non compatibile con il multicast IP. Modi: PreSharedKey, RawPublicKey, Certificate (X.509). IPsec: VPN.
Servizi TLS. Autenticazione: certificati di una CA fidata, verificati dal client. Cifratura: asimmetrica per stabilire la connessione, simmetrica per i dati (riservatezza). Integrità: un MAC su ogni messaggio (Funzioni hash e crittografia simmetrica).
Server Hello. Contiene il livello di protocollo, i parametri crittografici scelti dall'elenco del client, un numero casuale con data e ora, l'identificatore di sessione, il metodo di compressione e il certificato con identità e chiave pubblica.
Sicurezza RSA: scelte di generazione. $p$ e $q$ si scelgono a caso e della stessa dimensione (primi da 1500 a 3000 bit) per evitare attacchi noti; molte altre proprietà della generazione e della decifratura, se implementate male, aprono vulnerabilità.
Errori tipici: chiavi pubblica e privata scambiate (riservatezza = pubblica del destinatario; firma = privata del mittente); RSA senza padding; $e$ non coprimo con $\varphi(N)$ ; dimenticare $m<N$ ; dimenticare che il certificato lega identità e chiave (senza, un uomo in mezzo offre la propria chiave); credere che in TLS 1.3 la chiave di sessione sia cifrata con la pubblica del server; confondere TLS (TCP) con DTLS (UDP); pensare che RSA cifri un file intero (si cifra la chiave di sessione).