Fondamenti di sicurezza - introduzione alla crittografia

La crittoanalisi è lo studio dei metodi per decifrare il testo cifrato senza conoscere la chiave

Def. Preliminari

- testo in chiaro “plaintext” (messaggio originale)

- testo cifrato “ciphertext” (messaggio codificato prodotto come output, dipende dal testo in chiaro e dalla

chiave)

- algoritmo di cifratura “cipher” (algoritmo che trasforma il testo in chiaro in testo cifrato)

- chiave (usata come input dell’ algoritmo di cifratura, valore indipendente dal testo in chiaro)

- algoritmo di decifratura (algoritmo che trasforma il testo cifrato in testo in chiaro)

Cifrature:

La cifratura classica la tecnica di sostituzione (ogni simbolo del testo in chiaro veniva sostituito da un altro

simbolo, se il testo è visto come una sequenza di bit, alcune combinazioni di bit vengono sostituite con

altre) essa comprende:

 La cifratura di Cesare sostituisce ogni lettera dell’alfabeto con la lettera che si trova a “n” posizioni

di distanza (assegnando a ogni lettera un numero, una volta deciso il valore n è sufficiente

sommare/sottrarre n alla lettera e trovarne la corrispondente).

Con la cifratura di Cesare attraverso la crittoanalisi ci sono solo 26 possibili chiavi, con un attacco a

forza bruta è facile provare tutte le sostituzioni per il simbolo.

 La cifratura monoalfabetica ogni lettera del testo in chiaro viene mappata (collegata) su una lettera

scelta in modo casuale (ma comunque univoco), in questo modo si hanno 26! possibili chiavi, ma

sfruttando degli attacchi che operano sulla regolarità del linguaggio (lettere più utilizzate, meno

utilizzate, ricorrenze…) anche questa cifratura non è sicura, esistono infatti delle tabelle che

indicano le frequenze di utilizzo di una lettera, coppie di lettere o triple di lettere, procedendo per

ipotesi di sostituzione si può risalire al testo in chiaro. Le cifrature monoalfabetiche sono facili da

violare perché conservano le frequenze dell’alfabeto originario.

 La cifratura Playfair (a poligrammi) crittografa più lettere insieme. Il testo in chiaro è cifrato 2

lettere alla volta (diagramma).

Funzionamento: 1. In una matrice 5x5 si inserisce una parola chiave priva di duplicati e si

completano le celle libere con le restanti lettere dell’alfabeto in ordine

2. se la coppia di lettere cadono nella stessa riga, esse vengono sostituite con le

lettere che seguono a destra (nella matrice)

3. se la coppia di lettere cade nella stessa colonna, esse vengono sostituite con le

lettere sottostanti

4. se la coppia non è nella stessa colonna/riga, ciascuna lettera viene sostituita con

quella che si trova sulla stessa riga e nella colonna della compagna

5. per le coppia di doppie (cc, tt…) viene aggiunta una lettera di riempimento tra le

2 e vengono tradotte separatamente

Con questa cifratura playfair ogni lettera ha più sostituti omofoni e in un alfabeto di 26 lettere vi

sono 26x26 = 676 possibili diagrammi, ma il testo cifrato contiene ancora diverse informazioni sulla

struttura del testo originale.

 La cifratura Polialfabetica utilizza più alfabeti, si utilizzano diverse sostituzioni monoalfabetiche

durante la cifratura (ossia un insieme di regole di sostituzione monoalfabetica determinate di volta

in volta da una chiave differente). La più nota è la cifratura di Vigenère il cui insieme di regole è

costituito da 26 cifrature di cesare con scorrimento da 0 a 25 e la sostituzione è decisa dalla lettera

della chiave

La decifratura è il processo inverso, la lettera della chiave indica la riga, la lettera del chipertext

indica una cella di tale riga e la lettera in chiaro è l’intestazione di tale colonna.

Unico difetto è che la chiave si ripete e quindi comporta informazioni sulla struttura.

 La cifratura ideale è quella di utilizzare una chiave lunga quanto il messaggio e utilizzabile una sola

volta.

Il cifrario di Vernam prevede l’utilizzo di una chiave casuale lunga quanto il messaggio applicata al

cifrario di Vigenère. (al testo cifrato corrispondono 2 messaggi diversi ricavati con 2 chiavi

differenti)

One time pad (cifrario perfetto – teorema di Shannon) prevede messaggio in chiaro M e chiave K

casuale (sequenza di bit) lunga quanto M in cui la cifratura consiste nello “xorare” il messaggio con

la chiave e la decifratura nello “xorare” il testo cifrato con la chiave per ottenere il messaggio. (Il

problema è la generazione di una chiave casuale e la distribuzione della chiave lunga quanto il

testo)

La cifratura classica la tecnica di trasposizione (cifratura basata su una permutazione delle lettere del testo

in chiaro, non vengono modificate le lettere utilizzate, per questo motivo l’uso di trasposizione non cambia

la frequenza delle lettere da testo in chiaro a testo cifrato)

 Rail Fence il testo in chiaro viene scritto come una sequenza di diagonali e poi letto in riga

 Schema simile ma più complesso è quello di scrivere il messaggio riga per riga in una matrice e poi

leggerlo colonna per colonna, permutando l’ordine delle colonne (che è quindi la chiave). La

crittoanalisi è semplice dato che non cambia la frequenza delle lettere, per renderlo più sicuro si

può eseguire più volte la trasposizione (ri-crittografare il testo con lo stesso algoritmo), questa

tecnica può essere utilizzata anche con la sostituzione.

Macchine a Rotazione

Utilizzata nella seconda guerra mondiale, tale macchina contiene un numero variabile di cilindri a rotazione

indipendente, ognuno di questi cilindri ha 26 caratteri in ingresso e 26 caratteri in uscita questi caratteri

connessi tra loro da dei circuiti che cambiano ad ogni rotazione del cilindro (ad ogni tasto premuto il

cilindro effettua una sostituzione monoalfabetica del carattere, poi ruota cambiando i circuiti e quindi

l’alfabeto di output). In questa macchina ogni uscita di un cilindro è l’input del cilindro successivo (il primo

cilindro ruota ad ogni input, quello successivo ruota ad ogni giro di quello precedente e così via), con soli 3

cilindri si hanno 26^3 alfabeti = 17576.

Tecniche di Cifratura

La cifratura più efficace risulta quella di combinare trasposizioni e sostituzioni, l’utilizzo di una o più

sostituzioni seguite o intervallate da trasposizioni producono una maggiore complessità nella decriptazione

(è il principio della crittografia moderna).

- Cifratura simmetrica, composta da un'unica chiave privata che viene condivisa da mittente e ricevente. Il

testo in chiaro viene inserito con la chiave privata nell’algoritmo di criptazione, il testo cifrato viene inviato

insieme alla chiave privata e viene decriptato dall’ algoritmo grazie alla chiave.

Garantisce riservatezza e integrità dei dati cifrati.

Requisiti:

- l’algoritmo di cifratura deve essere pubblico (la robustezza non deve dipendere dalla segretezza

del codice dell’ algoritmo) e forte (deve resistere agli attacchi noti)

- la chiave segreta deve essere nota solo al mittente e al ricevente (questo comporta la necessità di

un canale sicuro per distribuire la chiave)

- Cifratura asimmetrica, in cui ogni utente genera una coppia di chiavi (chiave pubblica/privata), quella

pubblica viene distribuita, quella privata è segreta. Quello che viene cifrato con chiave pubblica (privata)

può essere decifrato con la rispettiva chiave privata (pubblica).

Garantisce riservatezza, integrità, autenticità dei dati cifrati, non ripudiabilità.

(segretezza: se A cifra con la chiave pubblica di B, solo B può decifrare il mex con la sua chiave privata)

(autenticazione: se A cifra con la sua chiave privata, B può decifrare il testo solo con la chiave pubblica di A)

Sistemi Crittografici

I sistemi crittografici vengono distinti in base a:

- numero di chiavi utilizzate (cifratura simmetrica, 1 chiave / cifratura asimmetrica, 2 chiavi)

- operazioni usate per la cifratura (sostituzione / trasposizione / funzioni matematiche)

- metodo con cui viene elaborato il testo in chiaro (a blocchi / a flusso, stream)

Cifratura a blocchi

Il testo in chiaro viene suddiviso in blocchi da 64 o 128 bit, ognuno di questi blocchi viene cifrato in maniera

univoca. Questo tipo di cifratura è il più utilizzato (utilizzato da DES data encryption standard, AES adavnced

encryption standard e RSA).

Cifratura a flusso

Questo tipo di cifratura elabora il messaggio bit a bit (o byte a byte), non è quindi necessario avere l’intero

messaggio per poterlo cifrare.

Tipi di attacchi nei Sistemi crittografici:

Attacco con Crittoanalisi

La crittoanalisi sfrutta le caratteristiche dell’ algoritmo e la conoscenza dei testi in chiaro e cifrati per

tentare di individuare la chiave o il testo cifrato. Le tipologie di attacco con crittoanalisi sono:

- solo testo cifrato (ciphertext only) in cui si conosce solo l’algoritmo e il testo cifrato

- testo in chiaro conosciuto (known plaintext) si conoscono alcune coppie di testo in chiaro e il rispettivo