Network Security teoria

Network security

Parte 1: introduzione alla crittografia

1a- Basics

Autenticazione: Procedura che viene usata per verificare l'identità di qualcuno o qualcosa.

Controllo degli accessi: Capacità di discriminare tra i diritti di ognuno dei partecipanti ad una sessione di comunicazione. Per poter fare controllo degli accessi, è necessario prima fare autenticazione.

Confidenzialità, riservatezza: Soltanto gli utenti autorizzati devono avere accesso alle informazioni protette. È necessaria prima l'autenticazione.

Protezione d'integrità: 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: Garanzia che si può dare ad un messaggio, che il mittente non possa negare di aver scritto un messaggio. 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.

Gli attacchi 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.

La crittologia è 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

• è l'alfabeto, un insieme finito di elementi con cui rappresentare un messaggio.
• è l'insieme dei possibili messaggi che si possono voler trasmettere, in chiaro.
• è un elemento di , un messaggio che si vuole trasmettere.
• 1è l'insieme dei possibili messaggi che si possono voler trasmettere, in forma cifrata.
• è il messaggio , ma in forma cifrata. è rappresentato con l'alfabeto .
• è l'insieme di tutte le chiavi possibili.
• è una chiave, .

Lo schema generico è il seguente:

• La coppia è il keypair, la coppia di chiavi che servono per poter comunicare.
• L’algoritmo di cifratura è ed è una biiezione.
• L’algoritmo di decifratura è

In generale, l'algoritmo deve essere una biiezione, in modo tale da garantire che possa essere invertita; ogni elemento deve avere un unico rappresentante , così come deve avere un unico rappresentante .

Block cipher

Un algoritmo di tipo block cipher (cifratura a blocchi) è un algoritmo che accetta soltanto messaggi di una certa lunghezza; se il messaggio è più lungo, quindi, questo dovrà essere spezzettato. Sia che sono messaggi lunghi esattamente bit, che è la lunghezza del blocco, mentre le chiavi e possono avere, in generale, lunghezze diverse. Quando il blocco è lungo , si ha cioè, la lunghezza del blocco incide sul numero massimo di possibili messaggi che ci possono essere (tipicamente, ). Ad ogni coppia corrisponde esattamente un unico , quindi se un certo appare più volte all'interno del messaggio originale, allora anche apparirà più volte nel messaggio cifrato. Si dice, allora, che è un sistema senza memoria.

Stream cipher

Un algoritmo di tipo stream cipher (cifratura a flusso) accetta un messaggio 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 dell'algoritmo, che trasforma il blocco di cifratura in un sistema con memoria. Lo stato può essere funzione del testo, del testo cifrato 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. Quando si vuole progettare un algoritmo di cifratura, si devono rispettare i principi di Kerckhoffs, che dicono:

• L’attaccante conosce , , , e ;
• La sicurezza di un sistema deve risiedere solamente nelle chiavi .

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

• Il messaggio originale ;
• Sia il messaggio originale che la chiave .

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 partendo da senza conoscere a priori.

Entropia

Sia con una variabile casuale discreta, a cui è associata una probabilità. Allora, possiamo definire l'entropia come:

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à, allora l'entropia sarà nulla perché la variabile casuale ha un risultato deterministico, con probabilità .

Si ha:

• Se e soltanto se c'è un per un qualche e c'è, cioè non c'è alcuna incertezza sul risultato della variabile casuale.
• Tutti i risultati sono equiprobabili, non si può predire assolutamente nulla del risultato che si avrà da ogni singolo esperimento.

L'entropia associata ad un messaggio è l'incertezza associata all'osservazione di all'uscita del canale di comunicazione. Con indicheremo, da qui in avanti, l'entropia associata alla chiave 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 (cioè è il numero di bit), l'entropia associata deve essere.

Segretezza perfetta (perfect secrecy)

Un algoritmo di cifratura offre la segretezza perfetta se, e solo se, e sono statisticamente indipendenti. Questa definizione di segretezza perfetta è di Shannon e dice che:

• Osservando non si deve poter dedurre alcuna informazione di ;
• L’incertezza su dopo aver osservato deve essere la stessa che si aveva prima di osservare .

Affinché un algoritmo possa offrire la sicurezza perfetta, è necessario che cioè, l'entropia della chiave deve essere maggiore o almeno uguale a quella del messaggio di partenza. L’unico algoritmo che offre la perfect secrecy è l'algoritmo di Vernam, o one-time-pad.

Tra le ipotesi si ha:

• La chiave è lunga esattamente quanto ;
• La chiave non può essere usata più di una volta;
• Il generatore di numeri casuali usato per generare la chiave è perfetto: ogni singolo bit ha probabilità di valere 1; ed sono statisticamente indipendenti.

Questo algoritmo consiste nel porre in XOR e . 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. 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.

1b- Crittografia simmetrica

Nel caso di algoritmi di crittografia simmetrici, Alice e Bob sono in possesso della stessa chiave di cifratura k che condividono: questa chiave permette loro di comunicare attraverso un canale insicuro. Il problema principale di questo approccio è la distribuzione della chiave.

Symmetric block cipher

Scopi principali della cifratura a blocchi sono:

• Fare in modo che ciascun bit di dipenda da tutti i bit di e di.
• Rendere il più difficile possibile trovare una qualsiasi relazione statistica tra ed senza conoscere .
• Cambiare un singolo bit di dovrebbe significare che ogni singolo bit di ha il 50% di probabilità di essere cambiato.
• Cambiare un singolo bit di dovrebbe significare un cambiamento di .

Substitution cipher

Sono una sottoclasse semplice degli algoritmi a blocchi. Si usa la chiave come indice delle possibili permutazioni su . Imponendo i messaggi di lunghezza, ogni chiave sarà lunga bit, con .

• è il keyspace e ha dimensione 2 !.

Un algoritmo a sostituzione perfettamente casuale (random substitution cipher) è un algoritmo a sostituzione che utilizza un keyspace di dimensione e chiavi lunghe, scegliendovi 2 ! all'interno una chiave perfettamente casuale.

Transposition cipher

Stiamo cercando di ridurre la dimensione dello spazio delle chiavi, per renderle gestibili. Un algoritmo per permutazione lavora permutando (spostando) i bit tra di loro, all'interno di un blocco di cifratura. Siccome bit possono essere trasposti in maniere, allora la dimensione dello spazio delle chiavi diventa e la lunghezza della chiave risulta. Ad esempio, con b=64 abbiamo l=384. In questa maniera otteniamo una chiave di lunghezza ragionevole, ma ci stiamo allontanando sempre di più dalla segretezza perfetta; in particolare, un algoritmo di questo tipo preserva il numero di zeri e uno all'interno dei singoli blocchi e diventa, quindi, molto semplice da crittanalizzare.

Composition of ciphers

Siccome i substitution cipher richiedono una chiave troppo grande per lavorare su blocchi grandi abbastanza per evitare analisi statistica e i transposition cipher, nonostante richiedano chiavi più corte, sono anche più facili da rompere, un buon compromesso è comporre i cipher (ovvero usare contemporaneamente transposition e substitution).

Un prototipo può essere il seguente:

Un algoritmo come quello in figura accetta in ingresso un messaggio lungo, che è la dimensione del blocco. Quello che viene fatto è separare questo blocco in sottoblocchi più piccoli, ai quali si applica un algoritmo di cifratura per sostituzione. In questa maniera, i blocchetti avranno bisogno di una chiave più corta. A questo punto, i blocchetti cifrati vengono ricomposti in un'unica parola, alla quale viene applicato una cifratura per permutazione; siccome la cifratura per permutazione richiede una chiave più corta, allora si può applicare l'algoritmo a tutta la parola nella sua interezza.

Questo algoritmo, quindi, usa una singola chiave ripetutamente: volte per gli algoritmi a sostituzione ed un'altra volta per l'algoritmo a permutazione. Per migliorare ancora di più la protezione, si può decidere di ciclare più volte la parola all'interno dell'algoritmo composizione, in modo tale da amplificare l'effetto valanga: infatti, se si facesse lavorare l'algoritmo per una sola volta, un bit cambiato avrebbe effetto soltanto su bit (il singolo blocchetto su cui è operata la sostituzione); al contrario, a noi interessa che, se viene cambiato un solo bit della parola originale, tutti i bit del testo cifrato risultino invertiti con probabilità.

Data Encryption Standard (DES)

L'algoritmo di cifratura DES è simmetrico a blocchi, in cui:

• Il numero di bit del blocco è bit;
• La lunghezza della chiave è bit, più altri 8 bit di ridondanza (che servono per proteggere la chiave da errori).

Questo algoritmo è stato pensato per essere molto efficiente se implementato in hardware, e molto inefficiente se implementato in software; infatti, il DES lavora sui singoli bit, mentre i processori devono gestire almeno 8 bit per volta (nei processori moderni, 32 o 64). Il primo e l'ultimo stadio, le permutazioni, sono indipendenti dalla chiave, ed hanno come unico scopo quello di rendere meno efficiente l'implementazione in software dell'algoritmo. L'algoritmo, inoltre, può essere usato sia per cifrare che per decifrare, cambia soltanto il modo con cui si devono derivare le sottochiavi. Il generatore di sottochiavi si occupa di derivare delle chiavi da 48 bit, una per ogni step dell'algoritmo. Nel caso in cui si stia decifrando invece che cifrare, allora le chiavi andranno usate in ordine inverso per i vari step. Le permutazioni iniziale e finale, che non sono casuali, sono una lo speculare dell'altro, cioè si annullano a vicenda. Questa loro proprietà fa sì che la stessa implementazione possa essere usata sia per cifrare che per decifrare il testo.

Generatore di sottochiavi

Gli step dell'algoritmo

Inner function

La funzione interna, inner function, è quella deputata principalmente a creare l'effetto valanga, grazie ai box di espansione.

Box di sostituzione

Ogni box di sostituzione, S-box, è una funzione che lavora su simboli da 4 bit, con una chiave da 2 bit, dove la chiave sono il primo e l'ultimo bit della parola da 6 bit che viene passata al box. Queste funzioni sono implementate attraverso una look-up table, cioè una tabella prestabilita. La parte più importante di tutto l'algoritmo sta proprio in queste funzioni. Se, infatti, le tabelle di corrispondenza fossero state diverse da quelle decise dall'NSA in fase di progettazione, oggi il DES sarebbe stato rotto, proprio grazie all'invenzione della crittoanalisi lineare, del 1992. Tutto l'algoritmo DES è basato soltanto su funzioni lineari, tranne che per questi box di sostituzione. È dimostrato che, se un algoritmo non ha funzioni non lineari, il suo cifrato è facilmente recuperabile a partire da attacchi a testo noto, cioè è possibile ricavare la chiave di cifratura a partire dai testi cifrato e in chiaro, fatto molto pericoloso.

Note finali su DES

Le chiavi scelte possono essere di tre tipi:

• Weak: Cioè ad un certo punto le sottochiavi generate diventano composte di soli "1".
• Semi-weak: Cioè ad un certo punto le sottochiavi diventano composte da "101010".
• Sicure: Se non ci sono regole.

Si può dimostrare che le permutazioni iniziali non aumentano la sicurezza dell'algoritmo. Infatti, siccome le permutazioni sono deterministiche, queste possono essere tolte senza conoscere la chiave. Eseguendo la permutazione dal testo cifrato, si ottiene un nuovo testo, che ovviamente non può essere meno sicuro di quello permutato. Se ne ricava che l'unico motivo per cui esistono le permutazioni iniziale e finale è rendere meno efficiente l'implementazione software rispetto all'implementazione hardware; infatti, in quest'ultimo caso, fare una permutazione deterministica dei bit è una cosa estremamente semplice. Al contrario, le permutazioni che si trovano all'interno dei vari step dell'algoritmo sono sicuramente importanti per amplificare l'effetto valanga: grazie a loro, infatti, si è potuto ridurre il numero di iterazioni da fare per far in modo che la modifica di un bit interessi tutti i bit del cifrato con probabilità.

Perché per decriptare basta utilizzare le chiavi in senso opposto a quello usato in fase di criptazione?

Nell’ultimo round di E:== ⊕ ( , )

Nel primo round di D:=( )== ⊕ , ⊕( )⊕ ( )=, , ⊕0=

3DES

Dal momento che la chiave del DES è troppo corta, considerando il fatto che DES è comunque un algoritmo sicuro, si è deciso di standardizzare un uso diverso del DES: il 3DES. Come il suo predecessore, il 3DES lavora su blocchi di 64 bit, ma utilizza una chiave lunga il doppio, la chiave totale è la concatenazione di due chiavi DES, quindi la lunghezza totale della chiave è bit, da cui lo spazio delle chiavi ha dimensione .

Le chiavi e nel 3DES sono usate in cascata:

• Si cifra il testo con DES e con la chiave .
• Si decifra il risultato con e con la chiave .
• Si cifra nuovamente con DES e con la chiave .

Questo utilizzo delle chiavi permette la compatibilità con il DES originale: infatti, basta usare ed il risultato è un DES (3 volte più lento) compatibile con l'originale. Questo fatto è possibile grazie proprio alla natura simmetrica del DES.

Stream ciphers

Gli algoritmi di cifratura a flusso sono un particolare tipo di algoritmo di cifratura a blocco, in cui abbiamo dei blocchi molto piccoli (di solito, da 1 bit fino a 8 bit), ma l'algoritmo è detto statefull, cioè viene preso in considerazione uno stato, una condizione dell'algoritmo, dovuto a ciò che è stato cifrato precedentemente. Con un algoritmo di questo tipo, non si può più creare un attacco di tipo probabilistico, perché la stessa sequenza di bit nel messaggio sarà codificata con due blocchi.