Introduzione alla crittografia

L'identità digitale

Gli obiettivi dei sistemi di sicurezza possono essere:

• Autenticazione
• Riservatezza
• Protezione dell'integrità
• Controllo degli accessi
• Non ripudio.

Un sistema di sicurezza può richiedere tutti, alcuni o solo uno di questi obiettivi. Questi non sono tutti gli obiettivi che si possano pensare, ma sono solo una parte. Per gli altri obiettivi, si rimanda alla pagina apposita.

Questi risultati si ottengono applicando in maniera sistematica i protocolli di rete e gli standard. I protocolli di sicurezza possono essere:

• crittografici,
• non crittografici.

Tra i protocolli crittografici, annoveriamo

• funzioni di hash;
• algoritmi di cifratura simmetrici;
• algoritmi di cifratura asimmetrici.

Un attacco può essere mirato ai protocolli crittografici o ai protocolli di rete. Questa distinzione non è fine a se stessa. Esistono protocolli di rete come il WEP che, pur sfruttando protocolli crittografici sicuri, sono totalmente insicuri; al contrario, esistono protocolli di rete che sono sicuri con determinati protocolli crittografici, e non lo sono con altri.

Autenticazione

L'autenticazione è una procedura che viene usata per verificare l'identità di qualcuno o qualcosa. Per raggiungere questo scopo, è necessaria una qualche forma di prova, che può essere:

• qualcosa che si conosce

• una password;
• una passphrase;
• ...

• qualcosa che si possiede

• un'impronta digitale;
• un certificato digitale;
• l'accesso ad una zona;
• una scheda magnetica;

• una qualsiasi combinazione di questi due prove

• un certificato protetto da passphrase;
• ...

L'autenticazione può essere fatta per riconoscere non solo delle persone, ma anche:

• un nodo di rete;
• un'istanza di una certa applicazione;
• un pacchetto IP;
• ...

Controllo degli accessi

Il controllo degli accessi è la capacità di discriminare tra i diritti di ognuno dei partecipanti ad una sessione di comunicazione. Un esempio tipico di controllo degli accessi è la suddivisione in ospiti, utenti registrati ed amministratori presente in Wikipedia.

Ovviamente, per poter fare controllo degli accessi, è necessario prima fare autenticazione.

Confidenzialità, riservatezza

Si tratta di garantire che soltanto gli utenti autorizzati abbiano accesso alle informazioni protette. Anche in questo caso, è necessaria prima l'autenticazione. La protezione deve essere fatta su due diversi tipi di dato:

• dati in transito;
• dati salvati.

La protezione, in questo caso, deve essere valida anche solo per la lettura dei dati.

Protezione d'integrità

Si tratta, semplicemente, di garantire che nessuno abbia modificato il contenuto di un messaggio. In generale, si tratterà di garantire che nessuno possa modificare il messaggio senza essere scoperto.

Non ripudio

Il non ripudio è quella garanzia, che si può dare ad un messaggio, che il mittente non possa negare di aver scritto un messaggio. Nella vita reale, questa caratteristica viene raggiunta attraverso la firma, che sta ad indicare che una persona ha letto o scritto qualcosa (per esempio, un assegno).

Dall'altra parte, il non ripudio può essere visto come la garanzia che il destinatario, una volta ricevuto un messaggio, non abbia la possibilità di dire di non averlo mai ricevuto.

Attacchi

Gli attacchi, come detto, possono essere commessi nei confronti sia dei protocolli di crittografia che di rete. In generale, si distinguono due tipi di attacco:

• attivo, in cui l'attaccante è in grado di generare traffico da immettere nella rete;
• passivo, in cui l'attaccante si limita ad intercettare il traffico in una o entrambe le direzioni, per avere accesso a dati riservati.

Definizione di sicurezza

Anzitutto, la sicurezza assoluta non esiste. La sicurezza è un concetto relativo e si deve rapportare allo scopo che si prefigge. In particolare, la sicurezza di una rete domestica può avere più o meno valore della sicurezza di una transazione bancaria, quindi anche i meccanismi messi in campo devono essere commisurati a ciò che si vuole raggiungere. Si deve quindi dare un valore a ciò che si deve proteggere; per esempio, posso voler proteggere

• delle e-mail aziendali;
• i dati bancari di tutto il personale di un'azienda;
• l'accesso fisico a determinati ambienti di un'azienda.

Tutti questi casi presumono diversi gradi di sicurezza, che deve essere commisurata anche con il costo che questa sicurezza comporta. La sicurezza fisica di un ambiente, per esempio, può essere ottenuta attraverso una scheda a chip, ma questo chip non deve richiedere troppa potenza di calcolo, altrimenti il risultato sarà un sistema sì sicuro, ma estremamente costoso.

La sicurezza può essere dei sistemi, come della rete. Per proteggere un singolo sistema, per esempio un nodo di rete, si dovrà usare una certa tecnica che probabilmente sarà diversa dalla tecnica che si potrà usare per proteggere una rete completa.

Architettura di una rete

Una rete comprende, in generale, degli outsider e degli insider, ovvero dei nodi che sono all'interno della rete da proteggere e nodi che sono fuori da questa rete.

Una rete può, in generale, fare anche da ponte tra due outsider. Per esempio, la rete di un provider può essere considerata insider, mentre i nodi a cui questo provider si collegano possono essere considerati outsider; in questo caso, la rete protetta deve permettere la comunicazione tra nodi esterni.

Una rete, per essere protetta, deve possedere un perimetro di sicurezza, cioè una linea su cui fare controllo degli accessi e statistiche. Il perimetro di una rete è, in generale, determinato da delle strutture fisiche (come possono essere i muri di un ufficio); ciononostante, il perimetro può essere esteso (temporaneamente) ad altri nodi di rete: è il compito delle Virtual Private Network (VPN), le reti private virtuali.

Le risorse devono essere protette, in generale, sia dagli insider che dagli outsider. Questo perché un insider che venga corrotto in qualche modo (si pensi, per esempio, ad un virus) non deve poter mettere in crisi la sicurezza di tutta la rete e di tutti gli altri nodi (propagazione dell'infezione). Per questo, è importante progettare un'architettura di rete adeguata, limitando al minimo le zone demilitarizzate (DMZ).

Disclaimer

In questo corso, si trattano argomenti scottanti. Si tratta di sicurezza e si illustrano i bachi che ci sono in molti sistemi ancor oggi utilizzati per moltissime applicazioni (si pensi, per esempio, al WEP). Le informazioni contenute in questo corso non vogliono e non devono essere usate per procurare danno ad alcuna rete (attività peraltro vietata dalla legge italiana, punita con la reclusione); nonostante questo, l'unico modo per imparare a creare sistemi sicuri è quello di essere in grado di trovare i bachi (più precisamente le vulnerabilità) che questi sistemi presentano. Un protocollo di sicurezza non può essere considerato sicuro definitivamente, la sicurezza non si può dimostrare attraverso alcun procedimento matematico.

Gli algoritmi di crittografia si basano sull'effettiva inefficienza di determinati algoritmi, come per esempio la fattorizzazione di un numero prodotto di due numeri primi. La ricerca è aperta, quindi può essere che un protocollo di cifratura oggi sicuro domani non lo sia. La sicurezza assoluta, non esiste; con una quantità di denaro (mezzi) e tempo sufficiente, qualunque protocollo di cifratura può essere violato.

Crittologia

La crittologia è una scienza, è l'insieme di diverse discipline tra cui

• crittografia, studia gli algoritmi di cifratura, cioè i meccanismi matematici attraverso i quali raggiungere la segretezza;
• crittoanalisi, studia i meccanismi per rompere gli algoritmi di cifratura progettati dalla crittografia.

I protocolli di cifratura sono l'insieme di regole che devono essere applicate affinché un algoritmo di cifratura possa essere sicuro.

Per una trattazione rigorosa della crittografia, si rimanda al corso di matematica discreta; qui si useranno gli strumenti forniti dalla matematica, in maniera non troppo rigorosa.

Notazione

• $A$ è l'alfabeto, un insieme finito di elementi con cui rappresentare un messaggio. Siccome ogni alfabeto può essere rappresentato dall'alfabeto binario, l'informatica utilizza quest'ultimo, che è

$A=\{0,1\}$

Altri tipi di alfabeto possono essere l'insieme delle lettere ASCII

$A=\{A,B,\cdots Z\}$

• $M$ è l'insieme dei possibili messaggi che si possono voler trasmettere, in chiaro.
• $m$ è un elemento di $M$, un messaggio che si vuole trasmettere, rappresentato con l'alfabeto $A_{M}$.
• $C$ è l'insieme dei possibili messaggi che si possono voler trasmettere, in forma cifrata. In generale, si ha

$|M|\neq |C|$

cioè l'insieme dei possibili messaggi in chiaro e cifrati non hanno lo stesso numero di elementi.

• $c$ è il messaggio $m$, ma in forma cifrata. $c\in C$ è rappresentato con l'alfabeto $A_{C}$.
• $K$ è l'insieme di tutte le chiavi possibili.
• $k$ è una chiave, $k\in K$.
• Alice e Bob sono i due partecipanti ad uno scambio di informazioni. A loro si può aggiungere anche Cindy.
• Trudy e Eve sono l'intruso (l'attaccante attivo) e l'eavesdropper (l'attaccante passivo), anche se di solito si usa solo Trudy.

Scenario tipico

Sistema sorgente-canale-ricevitore

• la coppia $(k_{1},k_{2})$ è il keypair, la coppia di chiavi che servono per poter comunicare.
• l'algoritmo di cifratura è $E_{k_{1}}(m)=c$ ed è una biiezione.
• l'algoritmo di decifratura è $D_{k_{2}}(c)=\left(E_{k_{1}}(m)\right)^{-1}=m$

In generale, l'algoritmo $E_{k_{1}}(m):M\rightarrow C$ deve essere una biiezione, in modo tale da garantire che possa essere invertita; ogni elemento $m\in M$ deve avere un unico rappresentante $c\in C$, così come $c\in C$ deve avere un unico rappresentante $m\in M$.

Block cipher

Un algoritmo di tipo block cipher (cifratura a blocchi) è un algoritmo che accetta soltanto messaggi $m\in M$ di una certa lunghezza; se il messaggio è più lungo, quindi, questo dovrà essere spezzettato. Sia $m$ che $c$ sono messaggi lunghi esattamente $b$ bit, che è la lunghezza del blocco, mentre le chiavi $k_{1}$ e $k_{2}$ possono avere, in generale, lunghezze diverse.

Quando il blocco è lungo $b$, si ha

$|M|=2^{b}$

cioè, la lunghezza del blocco incide sul numero massimo di possibili messaggi che ci possono essere (tipicamente, $b=64{\text{ bit}}$). Ad ogni coppia $(m_{i},k_{1})$ corrisponde esattamente un unico $c_{i}$, quindi se un certo $m_{i}$ appare più volte all'interno del messaggio originale, allora anche $c_{i}$ apparirà più volte nel messaggio cifrato. Si dice, allora, che $E_{k_{1}}$ è un sistema senza memoria.

Stream cipher

Un algoritmo di tipo stream cipher (cifratura a flusso) accetta un messaggio $m$ di lunghezza arbitraria; questo tipo di algoritmi può essere visto come un caso particolare degli algoritmi block cipher, dove la lunghezza del blocco è molto piccola e si ha uno stato che, evolvendo nel tempo, continua a modificare la chiave.

La componente fondamentale di questi algoritmi è proprio lo stato $S_{i}$ dell'algoritmo, che trasforma il blocco di cifratura in un sistema con memoria. Lo stato può essere funzione del testo $m$, del testo cifrato $c$ o del tempo.

Crittoanalisi

La crittoanalisi è lo studio delle tecniche matematiche che permettono di bucare gli algoritmi crittografici e, più in generale, tutti i servizi che hanno lo scopo di proteggere le informazioni. La crittoanalisi è utile per studiare i sistemi e le proprietà degli algoritmi matematici. La crittoanalisi, comunque, non è l'unico metodo che si può usare per rompere la segretezza dei dati: un delinquente può costringere le persone a rivelargli le proprie chiavi, con l'uso della forza o delle minacce.

Quando si vuole progettare un algoritmo di cifratura, si devono rispettare i principi di Kerckhoffs, che dicono:

• l'attaccante conosce $E$, $D$, $C$, $M$ e $c$;
• la sicurezza di un sistema deve risiedere solamente nelle chiavi $k$.

Nella vita di tutti i giorni, inoltre, bisogna considerare la possibilità che l'attaccante abbia a disposizione anche $m$, il messaggio in chiaro. L'attaccante, tipicamente, si prefigge lo scopo di recuperare, dato $c$,

• il messaggio originale, $m$;
• sia il messaggio originale che la chiave $k$.

Un protocollo di cifratura viene detto rotto (compromesso) quando, data una certa quantità di tempo ed una certa potenza di calcolo, l'attaccante è in grado di calcolare il messaggio originale $m$ partendo da $c$ e senza conoscere $k$ a priori. Questa distinzione non è assoluta, perché bisogna definire i limiti desiderati di

• tempo;
• potenza computazionale.

Fare una ricerca esaustiva nello spazio delle chiavi delle chiavi (l'unico attacco possibile su un protocollo sicuro) è un lavoro che richiede un tempo direttamente proporzionale alla lunghezza della chiave stessa. Quindi, nella lunghezza della chiave stessa risiede una buona parte degli algoritmi di cifratura.

Alcuni tipi di protocollo di cifratura sono vulnerabili ad attacchi molto dannosi perché, oltre a non impedire la segretezza del messaggio $m$, dato un certo numero di osservazioni della coppia $<m,c>$ permettono di trovare anche la chiave di cifratura $k$; se possibile, questa è una vulnerabilità ancora più grave.

Attacco al solo testo cifrato

Nel caso dell'attacco al solo testo cifrato, l'attaccante ha la possibilità di osservare $c$ (di lunghezza arbitraria) ed ha soltanto questo per risalire al messaggio originale. Un tipo di attacco potrebbe essere l'analisi della frequenza di ripetizione di un blocco $c_{i}$. Se un protocollo si espone a questo rischio, allora non è un buon protocollo di cifratura.

Attacco con testo noto

In questo tipo di attacco, l'attaccante non solo conosce $c$, ma è in grado di conoscere anche $m$ e di mettere le due sequenze in correlazione. Questo attacco è solo un po' più difficile da impostare rispetto al caso precedente, ma non per questo meno improbabile; inoltre, col passare del tempo è ragionevole ritenere che prima o poi qualcuno riuscirà a mettere in relazione il testo $c$ ed il messaggio $m$.

Attacco con testo scelto

Tra tutti gli attacchi visti, questo è il più pericoloso, perché permette all'attaccante non solo di mettere in correlazione due testi, ma può proprio sceglierli, per esempio con lo scopo di fare analisi su proprietà note. Questo attacco non è nemmeno così improbabile. Si pensi, ad esempio, ad un attaccante che spedisce una mail ad una cavia, $B$. La mail, contenente il testo scelto, giungerà al destinatario in forma cifrata, quindi prima o poi Trudy riuscirà a sniffare anche il traffico che ha generato.

Teoria dell'informazione, le fondamenta

Sia $x\in X$ con $X=\{x_{1},x_{2},\cdots ,x_{q}\}$ una variabile casuale discreta, a cui è associata una probabilità $0\leq p_{i}\leq 1$, Allora, possiamo definire l'entropia come

$H(X)=\sum _{i=1}^{q}p_{i}\log _{2}\left({\frac {1}{p_{i}}}\right)$

L'entropia è una grandezza che definisce il livello di incertezza a cui è soggetta una variabile casuale, indica qual è il grado di casualità associata ad un fenomeno. Se per esempio ad un evento è associata tutta la probabilità ($p_{j}=1$), allora l'entropia sarà nulla perché la variabile casuale ha un risultato deterministico.

Si ha:

• $0\leq H(m)\leq \log _{2}q$
• $H(m)=0$ se e soltanto se c'è un $p_{j}=1$ per un qualche $j$ e c'è $p_{k}=0\ \forall k\neq j$, cioè non c'è alcuna incertezza sul risultato della variabile casuale.
• $H(m)=\log _{2}q\Leftrightarrow p_{i}=q^{-1}\ \forall i$, cioè tutti i risultati sono equiprobabili, non si può predirre assolutamente nulla del risultato che si avrà da ogni singolo esperimento.

L'entropia $H(m)$ associata ad un messaggio $m$ è l'incertezza associata all'osservazione di $m$ all'uscita del canale di comunicazione. Non potendo fare uno studio deterministico (non possiamo sapere a priori quali messaggi saranno mandati nella rete), dobbiamo per forza affidarci alla statistica.

Con $H(k)$ indicheremo, da qui in avanti, l'entropia associata alla chiave $k$ dell'algoritmo di cifratura. Vedremo che la chiave migliore è quella con la massima casualità nei bit, il che significa che tutti i bit sono equiprobabili nella scelta della chiave: questo fenomeno è strettamente legato all'entropia; in particolare, cercheremo la chiave ottima attraverso la massimizzazione dell'entropia. Nel caso di uno spazio di chiavi grande $|K|=2^{b}$ (cioè $b$ è il numero di bit), l'entropia associata deve essere

$H(K)=\log _{2}(2^{b}!)\simeq b\cdot 2^{b}$

Questo, soltanto se le chiavi sono scelte davvero in maniera casuale.

Nel caso degli algoritmi di cifratura, si afferma che l'algoritmo migliore è quello che porta $H(C)$ il più vicino possibile a $\log _{2}(|C|)$, indipendentemente dal testo di partenza.

Segretezza perfetta

Definizione: Segretezza perfetta

Un algoritmo di cifratura offre la segretezza perfetta se, e solo se, $c$ ed $m$ sono statisticamente indipendenti.

Questa definizione di segretezza perfetta è di Shannon e dice che:

• osservando $c$ non si deve poter dedurre alcuna informazione di $m$;
• l'incertezza su $m$ dopo aver osservato $c$ deve essere la stessa che si aveva prima di osservare $c$.

Shannon ha dimostrato che, affinché un algoritmo possa offrire la sicurezza perfetta, è necessario che

$H(k)\geq H(m)$

cioè, l'entropia della chiave deve essere maggiore o almeno uguale a quella del messaggio di partenza.

Algoritmo di Vernam

L'algoritmo di Vernam, o one-time-pad è l'unico algoritmo che offre la sicurezza perfetta definita da Shannon. Tra le ipotesi si ha:

• la chiave $k$ è lunga esattamente quanto $m$;
• la chiave $k$ non può essere usata più di una volta;
• il generatore di numeri casuali usato per generare la chiave è perfetto: ogni singolo bit ha probabilità $0,5$ di valere 1;
• $c$ ed $m$ sono statisticamente indipendenti.

Questo algoritmo consiste nel porre in XOR la chiave $k$ e il messaggio $m$. Si deve poi trasmettere la chiave attraverso un canale sicuro, mentre il messaggio può essere trasmesso su un canale insicuro. Il ricevitore non dovrà far altro che porre nuovamente in XOR le due stringhe (ora perfettamente casuali) per ottenere nuovamente il messaggio originale.

Schema dell'algoritmo di Vernam

Questo tipo di algoritmo è l'unico che offre veramente la segretezza assoluta, ma c'è un problema: la trasmissione della chiave. Per trasmettere un'immagine da 2 MB avrò bisogno di una chiave lunga almeno 2 MB. A questo punto, se si ha a disposizione un canale sicuro con così tanta banda, conviene spedire direttamente il messaggio all'interno del canale sicuro ed abbandonare quello insicuro.

Il problema della chiave non è secondario; ancora oggi, esiste il problema di distribuzione delle chiavi (di cui parleremo più avanti), che è una grossa limitazione all'utilizzo della crittografia.

Appurato che la sicurezza perfetta non si può ottenere, possiamo però pensare che questa possa essere un limite superiore a cui far tendere un generico algoritmo di cifratura. In alcuni casi ci si può avvicinare, in altri casi è praticamente impossibile: è il caso della cifratura a blocchi, dove una ripetizione di una parte del messaggio si traduce obbligatoriamente in una ripetizione in $c$, cioè vi è correlazione tra $m$ e $c$ che non possono quindi più essere considerati statisticamente indipendenti.

Catalogazione degli algoritmi di cifratura

Gli algoritmi di cifratura possono essere di tre tipi:

• algoritmi simmetrici, dove la chiave di cifratura e di decifratura è la stessa (è il caso dell'algoritmo di Vernam);
• algoritmi asimmetrici (o a chiave pubblica), dove la chiave per cifrare il messaggio non è la stessa della chiave che si dovrà usare per leggere il messaggio cifrato.
• funzioni di hash, algoritmi senza chiave.