02 Crittografia convenzionale

[Lezione del 8 ott 2019]

Definizioni di base

plaintext

messaggio in chiaro da inviare;

ciphertext

messaggio criptato, il contenuto non è interpretabile direttamente;

crittografare (encryption)

il processo di convertire un plaintext in ciphertext;

decrittare (decryption)

il processo di ricostruire il plaintext a partire dal ciphertext;

crittografia (cryptography)

lo studio dei diversi schemi utilizzati per crittografare;

cifra (cipher)

uno schema per crittografare;

cryptanalysis

le tecniche utilizzate per decrittare un messaggio senza una conoscenza completa della cifra 1;

cryptology

la somma di criptography e cryptanalysis.

Il seguente diagramma mostra graficamente le relazioni sopra definite:

criptology vs critpography & criptoanalysis

Principi di crittografia convenzionale

La crittografia simmetrica è conosciuta anche come crittografia convenzionale, o crittografia a chiave singola.

Consiste nell’eseguire sostituzioni e trasposizioni nel plaintext ottenendo il ciphertext.

L’algoritmo di crittografia accetta in input il plaintext da elaborare e una chiave segreta (secret key). Questa chiave fissa le sostituzioni e trasposizioni da effettuare. Ogni chiave individua sostituzioni e trasposizioni diverse, dando luogo a ciphertext diversi.

Mittente e destinatario devono avere la stessa chiave 2, in tal modo il destinatario può decrittare il ciphertext ricevuto rovesciando l’algoritmo di cifratura.

Tipicamente l’algoritmo di cifratura non è segreto, mentre lo è la chiave utilizzata.

Utilizzare algoritmi di cifratura conosciuti, ha permesso lo sviluppo di hardware specializzato acquistabile a basso costo, rendendo pervasiva la diffusione della crittografia convenzionale.

In passato vi sono state pratiche di security by oscurity, ovvero non divulgando neanche gli algoritmi utilizzati, ma non si sono dimostrate efficaci. Viceversa, l’uso di algoritmi conosciuti si è dimostrato in grado di riparare rapidamentele eventuali falle di sicurezza scoperte.

Violare il codice

Esistono due diversi modi per ottenere il plaintext originale da un ciphertext senza avere la secret key:

  • attacco con forza bruta (brute force attack);

  • cryptanalysis.

Nel caso di brute force attack si provano tutte le possibili chiavi per ottenere un plaintext comprensibile.

Nel caso di cryptanalysis si analizzano le caratteristiche del ciphertex e quelle del possibile linguaggio del plaintext. Unendo questa analisi con le caratteristiche dell’algoritmo di cifratura, si cerca di dedurre il plaintext originale, o, più spesso, la secret key.

Brute force attacks.

Per avere una idea dei tempi richiesti nel caso di brute force attack, si può considerare la storia di DES 3. Al tempo della sua ideazione, con una chiave di 56 bits, si riteneva non attacabile. Oggi, ipotizzando una capacità di decrittazione pari a un milione di tentativi al microsecondo, abbiamo la seguente tabella:

key size (bits)

n.of possible keys

time required at 10^6 decryption/microsec

32

2^32 = 4.3 x 10^9

2.15 msec 4

56

2^56 = 7.2 x 10^16

10 hours

128

2^128 = 3.4 x 10^38

5.4 x 10^18 years

168

2^168 = 3.7 x 10^50

5.9 x 10^30 years

Come si vede oggi è possibile decifrare con brute force una cifra DES con chiave a 56 bit. D’altro canto una chiave a 128 bit attualmente sarebbe irragionevole tentare di decrittarla con brute force: si consideri che l’età della Terra è stimata in 4.5 x 10^9 years.

Cryptoanalytic attacks.

Supponendo siano validi questi aspetti:

  • si conosce l’algoritmo utilizzato per crittografare il plaintext;

  • e che vi siano tracce di struttura o ripetizioni che sopravvivono al processo di crittografia.

Allora possiamo ipotizzare tre scenari di attacco:

  • chiphertext only - l’attaccante ha a disposizione il solo ciphertext;

  • known plaintext - l’attaccante ha sia il ciphertext che il (o parte del) plaintext;

  • chosen plaintext - l’attaccante può decidere quale plaintext studiare ed è in grado di produrre il relativo ciphertext.

In questi casi, l’attaccante può analizzare il chiphertext per scoprire le strutture del messaggio originale sopravvissute alla crittografia, e da qui cercare di risalire alla chiave utilizzata.

Principi di crittografia convenzionale

Si dice che il ciphertext è incondizionatamente sicuro (unconditionally secure) se non contiene informazioni sufficienti per risalire univocamente al plaintext. Questa condizione è estremamente rara.

Più frequentemente si cerca di arrivare ad essere computazionalmente sicuri (computationally secure), ovvero:

  • il costo per violare la cifra eccede il valore dell’informazione crittografata;

  • e il tempo richiesto per la violazione eccede la vita utile dell’informazione stessa.

I requisiti minimi per un algoritmo di crittografia sono:

  • algoritmo di crittografia forte - (strong encryption algorithm) un attaccante che conosce l’algoritmo ed ha accesso a parte del ciphertext non deve essere in grado di decifrarlo per ottenere la chiave;

  • algoritmo di cifratura più forte - (stronger encryption algorithm) l’attaccante non può scoprire il plaintext o la chiave anche se conosce parte del ciphertext e il relativo plaintext.

Tecniche di sostituzione

Codice di Cesare

Giulio Cesare fu un generale e uomo politico romano, vissuto dal 100 a.c. al 44 a.c.

Nelle sue campagne militari inventò e utilizzò un codice di cifratura per proteggere il contenuto di messaggio militarmente importanti. sostituiva ogni lettera del messaggio (plaintext) con una lettera la cui posizione in alfabeto era spostata in avanti di N posizioni. Se si raggiungeva la lettera z, si ripartiva dalla a.

Ad esempio, usando 3 posizioni, avremmo:

e

v

e

r

y

o

n

e

a

t

t

a

c

k

n

o

w

f

b

g

c

h

y

h

u

b

r

q

h

d

w

w

d

f

n

q

r

z

Chi riceveva il messaggio doveva ricostruire il plaintext utilizzando le lettere con una posizione spostata indietro di N posizioni.

Questa cifra è facilmente attaccabile con il metodo della forza bruta. Infatti le lettere utilizzabili nell’alfabeto inglese sono solo 26 (21 in quello latino) quindi basta provare al massimo 25 possibili sostituzioni (ovvero 20 per il latino) per essere certi di ottenere il plaintext.

Cifra monoalfabetica

Un miglioramento rispetto la cifra di Cesare consiste nell’usare la cifra monoalfabetica.

In pratica si utilizza una permutazione di caratteri dell’alfabeto. Ad esempio una chiave può essere il seguente schema, in cui la seconda linea indica la lettera che sostituisce la equivalente presente nella prima linea:

abcdefghijklmnopqrstuvwxyz
ctaxqhjfkgilvzpoesrbwmudyn

Usando questa chiave avremmo (ciphertext nella seconda riga):

everyone attack now
qmqsypzq cbbcai zpu

Questa cifra si basa su 26! possibili chiavi 5, eliminando la possibilità di attacchi brute force.

Ma sono possibili attacchi in criptoanalisi perché la struttura del linguaggio sopravvive alla cifratura. Ad esempio, se si sa che il linguaggio utilizzato nel messaggio è l’inglese, è possibile utilizzare le frequenze delle lettere e dei digrammi 6 nel ciphertext, confrontandoli con le frequenze del linguaggio standard. In tal modo è possibile ipotizzare quali lettere del ciphertext sostituiscano quelle del plaintext, costruendo la chiave di encrypt e il relativo plaintext.

Quindi si capisce che per avere un algoritmo di crittografia forte è necessario che l’algoritmo nasconda la struttura del linguaggio usato nel plaintext.

Cifra di Hill

Per evitare la sopravvivenza della struttura del linguaggio, nella cifra di Hill si trasformano blocchi di lettere (multiple-letter cipher).

L’algoritmo di Hill si basa sul prodotto matriciale:

\[C = K\; P\; mod 26\]

dove:

  • C è il blocco cifrato di m lettere;

  • K è la chiave: una matrice m x m;

  • P è il blocco di m lettere da crittografare.

Il plain text si ottiene con:

\[P = K^{-1}\;C\; mod 26\]

dove \(K^{-1}\) è la matrice inversa di K.

Un esempio di uso, con blocchi di due lettere, può essere il seguente.

  • Alfabeto inglese codificato con i numeri da 0 (lettera A) a 25 (lettera Z).

  • Plaintext friday -> 5 17 8 3 0 24

  • \(K = \bigl( \begin{smallmatrix} 7&8\\ 19&3 \end{smallmatrix} \bigr)\)

Usando due lettere di plaintext per volta si ottiene il ciphertext pqcfku. Di seguito vediamo per esempio la prima coppia, fr, divenire pq:

\[\begin{split}C = K\; P\; mod 26 = \begin{pmatrix} 7&8 \\ 19&3 \end{pmatrix} \begin{pmatrix} f=5 \\ r=17 \end{pmatrix} = \begin{pmatrix} 15 \\ 16 \end{pmatrix} = pq\end{split}\]

L’algoritmo di Hill nasconde la struttura del linguaggio, ma ha una debolezza. Se si conosce parte del plaintext e il relativo ciphertext, risalire alla chiave è facile perchè vi è una relazione lineare tra chiave, plaintext e ciphertext

Infatti, dato il ciphertext Y e il plaintext equivalente X, vale \(Y = K\; X\). Quindi possiamo affermare: \(Y\; X^{-1} = K\). Ovvero basta calcolare l’inversa di X e moltiplicarla per Y per avere la chiave K.

Quindi un algoritmo di crittografia forte non deve avere una relazione lineare tra chiave, plaintext e ciphertext. DES è un esempio di questo tipo di algoritmo: lavora su blocchi di lettere, quindi perde la struttura del linguaggio, e utilizza relazioni non lineari tra chiave, plaintext e ciphertext.

One time pad

Si può pensare di utilizzare una chiave casuale lunga quanto il messaggio, utilizzando la somma modulo lunghezza dell’alfabeto. Nel caso di alfabeto binario la somma modulo 2 è l’operazione di XOR:

\[\begin{split}\begin{matrix} p&q&p\oplus q \\ 0&0&0 \\ 1&0&1 \\ 0&1&1 \\ 1&1&0 \end{matrix}\end{split}\]

Indicando con C la matrice ciphertext, P la matrice plaintext e K la matrice della chiave one time pad, abbiamo:

\[\begin{split}\begin{align} C& = P \oplus K\\ P& = C \oplus K \end{align}\end{split}\]

Con le condizioni che la chiave:

  • sia lunga almeno quanto il plaintext,

  • sia usata una sola volta,

  • e sia rigorosamente randomica,

si dimostra che lo schema del one time pad è incondizionatamente sicuro.

Lo schema del one time pad, pur attraente perché sicuro, non è utilizzato universalmente per due motivi:

  • se il plaintext da trasmettere è grande, lo è anche la chiave da utilizzare, di conseguenza dando luogo a problemi per la sua comunicazione in forma sicura;

  • non è facile assicurare la rigorosa randomicità della chiave.


1

Ovvero come violare la cifra.

2

Quando la chiave per crittografare è usata anche per decrittare, si parla di algoritmo di cifratura a chiave simmetrica.

3

DES è un algoritmo di cifratura a chiave simmetrica. Sviluppato da IBM negli anni “70, e, con alcune modifiche, successivamente adottato dal NIST (National Institute of Standards and Technology).

4

Secondo lo scrivente: (2^32)/1e6 ~ 4.3e3 microsec ~ 4.3 msec

5

Sempre perché l’alfabeto inglese ha 26 lettere. 26! ~ 4 x 10^26.

6

Digramma: due lettere affiancate.