Appunti completi corso Crittografia

CBC (CIPHER BLOCK CHAINING)

È strettamente sequenziale, l’encryption di un blocco dipende dal precedente (fa uso di un

initialization vector che da quanto ho capito può essere inviato in chiaro ma deve cambiare

sempre, a meno che non usi la chiave una sola volta, in questo modo lo stesso plaintext

viene cifrato in ciphertext diversi). La decryption invece si può parallelizzare perché ogni

blocco m dipende da c e c ma non da altri pezzi decrittati. In particolare:

i i i-1

c = IV m = D (c ) ^ c

0 i k i i-1

c = E (m ^ c )

i k i i-1

Grazie al fatto che ogni blocco dipende dai precedenti, blocchi uguali non verranno cifrati

nello stesso modo. Dal punto di vista degli errori non intenzionali, un bit errato distrugge il

blocco corrispondente, mentre inverte solo un bit in quello successivo, per cui rimane

robusto (si dice che è SELF-RECOVERING). Invece per errori volontari? L’aggiunta o

rimozione di blocchi ti spacca tutto e si vede, per cui è sicuro. Il principale svantaggio è

che non puoi parallelizzare l’operazione di encryption, e se si verificano problemi di

sincronizzazione (con aggiunta o perdita di bit) si spacca tutto.

STREAM BASED MODES (CFB, OFB, CTR)

Essi producono una nuova chiave per ogni blocco, per cui c = m ^ k .

i i i

Vediamone alcuni precisamente.

CFB (CIPHER FEEDBACK MODE)

Il plaintext viene suddiviso in pezzettini di j bit (con j minore di un numero n) e fa uso di

due registri da n bit chiamati ISR (INPUT SHIFT REGISTER) e OSR (OUTPUT SHIFT

REGISTER). L’ISR è inizializzato con un initialization vector. Ad ogni passaggio l’ISR viene

crittato con il block cipher in uso e il risultato viene salvato in OSR. I j bit più significativi

dell’OSR vengono xorati con i j bit di plaintext. Il risultato di quest’operazione è il ciphertext

che viene trasmesso. A questo punto l’ISR viene shiftato a sinistra di j bit e xorato con il

ciphertext dell’iterazione corrente. L’operazione di decrittazione è identica (scambiando

solo ciphertext con plaintext e viceversa). Detto così non si capisce niente, ma le formule

sono più chiare:

ISR = IV

0

OSR = E (ISR )

i k i-1

c = m ^ j leftmost bits of OSR

i i i

ISR = (ISR << j) ^ c

i i-1 i

È utile nelle applicazioni dove serve crittare comunicazioni remote via terminale (tipo non

quelle moderne, ma per esempio comunicazioni satellitari o spaziali, ma pure quegli

strumenti devono essere vecchi). Non è molto robusto, perché se il testo da crittare

contiene degli errori, essi si propagano finché quei bit sbagliati rimangono nell’ISR. Se poi

pezzi di plaintext si perdono, tutto ciò che viene dopo non è recuperabile.

OFB (OUTPUT FEEDBACK MODE)

È praticamente uguale al precedente, con la differenza che il feedback non è dato dal

ciphertext, ma dai j bit più significativi di OSR.

ISR = IV

0

OSR = E (ISR )

i k i-1

c = m ^ j leftmost bits of OSR

i i i

ISR = (ISR << j) ^ j leftmost bits of OSR

i i-1 i

A conti fatti non migliora molto di CFB… sono entrambe delle mode of operation rare.

CTR (COUNTER MODE)

È uno dei più usati, fa uso di un IV che DEVE essere un RANDOM NUMBER

UNPREDICTABLE USED ONLY ONCE (però può essere pubblicamente diffuso senza

problemi). Non è un secret, ma comunque deve venir creato da un ottimo random number

generator :) il blocco i-esimo è crittato come c = m ^ E (IV + i)

i i k

È parallelizzabile sia quando critta che quando decritta, rendendolo ben efficiente. Dei bit

errati nel ciphertext si manifestano solo nei corrispondenti bit del plaintext. Rimane sempre

il fatto che IV DEVE essere usato UNA SOLA VOLTA, mentre l’inserimento o cancellazione

di blocchi spacca tutto. Per quest’ultimo problema vengono maggiormente in soccorso le

mode of operation autenticate, che vedremo più in là.

Dopo aver studiato DES, un block cipher di tipo FN, oggi ne vediamo uno di tipo SPN, cioè

AES, un cifrario tra i più usati attualmente. Poi parleremo di stream cipher, usati per le

applicazioni interattive.

Le SPN sono una tipologia di block cipher, che fanno uso di una strategia in cui ogni round

consiste in tre fasi, è l’applicazione di tre trasformazioni che sono:

- Sostituzione (applicazione di una funzione non lineare, ovvero una funzione booleana in

cui ogni bit in output è composto dal prodotto di più incognite, ed essendo una funzione

complicata da eseguire in genere si implementa come look-up table, sostituendo un

gruppo di bit con un altro gruppo secondo la tabella)

- Permutazione (una permutazione di un insieme di bit, si realizza moltiplicando ogni bit

per una matrice di permutazione binaria, cioè una matrice di bit in cui ogni riga contiene un

solo bit settato a 1, è un modo comune per implementare la permutazione)

- Key mixing (somma tramite xor della chiave del round).

A differenza delle FN, le funzioni di encryption e decryption sono molto diverse.

Anche le SPN seguono il processo di confusione e diffusione, dove la confusione viene

fatta dalla key mixing e dalla sostituzione, mentre la diffusione viene realizzata dalla

permutazione.

AES è un block cipher in cui lo state cipher è composto da 128 bit, la chiave può essere di

varie dimensioni (128, 196, 256 bit). In base alla lunghezza della chiave, parliamo di

AES128, AES196 oppure AES256. È un block cipher pubblico che vinse il contest

internazionale di standardizzazione NIST nel 2000. Ha un round structure facile da

analizzare, è immune alla crittanalisi lineare e differenziale (gli strumenti più potenti e sono

più intrattabili di un bruteforce), si può implementare in modo efficiente sia via hardware

che via software.

I 128 bit del blocco si possono pensare come una matrice 4*4 di byte. Il round standard ha

uno strato di sostituzione con 16 S-box che sostituiscono da 8 bit a 8 bit. Sono 16 S-box

distinte. La permutazione è implementata con bytewise rotation (anche se si chiama

ShiftRows) ed una operazione di xor lungo le colonne (MixColumns). La key mixing è

un normale xor con la chiave del round. I round sono 10, 12 o 14 in base alla lunghezza

della chiave. Quindi ogni round segue le fasi sub_bytes + shift_rows + mix_columns +

add_material, con la differenza che l’ultimo round non ha la mix_columns perché non

aggiunge sicurezza, mentre il primo ha un add_material iniziale.

Nella fase di SubBytes abbiamo un criterio per sostituire 8 bit con altri 8 bit in modo

biettivo secondo una look-up table. È una funzione non lineare, le sostituzioni sono

descritte matematicamente secondo la teoria di Galois, cioè i bit di ogni byte sono i

coefficienti di un polinomio di grado al più 7. Di questo polinomio si cerca l’inverso (nel

campo di Galois) e su questo inverso si fa un prodotto con una matrice a 8 bit * 8 bit e uno

xor con un vettore b di 8 bit (questa sarebbe l’esecuzione di una S-box). Il polinomio del

8 4 3

campo per le moltiplicazioni è x + x + x + x + 1. Calcolare l’inverso in un campo finito

sembrerebbe non problematico computazionalmente, è la relazione inversa della S-box ad

-1

essere difficile. Se i è un byte d’ingresso, l’output è o = ai ^ b. Tutta questa procedura

rende il cifrario immune alla crittanalisi lineare e differenziale.

Nella ShiftRows abbiamo sempre la matrice 4 byte * 4 byte e molto semplicemente la

prima riga rimane invariata, la seconda ruota di una posizione, la terza di due posizioni, la

quarta di tre posizioni. Via hardware basta collegare correttamente dei fili, in software si fa

con istruzioni di rotazione.

In MixColumns consideriamo ogni colonna della matrice come coefficiente di un

3 2 4

polinomio di grado al più 3 e tutta la matrice la moltiplichiamo per 3x + x + x + 2 mod x +

1. Siccome il cifrario dev’essere chiaramente invertibile, questo polinomio ha un inverso

3 2

che è 17x + 19x + 9x + 20.

La fase AddRoundKey semplicemente fa lo xor fra il cipher state e la sottochiave.

Le prime tre fasi (che non usano la chiave) si possono unire in unico passo, e si ottengono

così quattro matrici giganti dette T-Tables. L’applicazione di un round in AES così diventa

O = T i ^ T i ^ T i ^ T i ^ K dove T è una T-Table e i una colonna della matrice 4*4. Per

0 0 1 1 2 2 3 3

questa implementazione ti serve chiaramente più memoria per le T-Tables, è un’alternativa

che si sfrutta spesso in hardware e qualche volta pure in software.

Il key-schedule prende la chiave principale, la divide in gruppi da 32 bit e genera le chiavi

dei round con dei calcoli assurdi ma non particolarmente interessanti. Ciò che importa è il

fatto che la key schedule è invertibile. Se hai abbastanza byte di qualsiasi sottochiave,

riesci a ricavare la cipher key originaria. È importante per un side channel attack, ma pure

nella crittanalisi lineare. Non si ricava direttamente la chiave principale, ma una parte delle

sottochiavi, e una volta che hai quelle, se la key schedule è invertibile, riesci ad ottenere la

chiave principale. In AES tutto il key schedule è invertibile se almeno s parole consecutive

di sottochiavi sono note (con s dipendente dalla lunghezza della chiave principale).

La decryption esegue le fasi di ogni round al contrario, quindi è sì una funzione diversa

dall’encryption, ma neanche così tanto eh… cioè te lo aspetti.

Un singolo bit flip nel plaintext, modifica il cipher state dopo solo due round, cioè metà dei

bit sono già invertiti dopo due round. AES è completamente immune alla crittanalisi lineare

126

e differenziale. Tramite known plaintext attack, servono 2 coppie ptx-ctx per rompere

189 254

AES128, 2 coppie per AES196 e 2 coppie per AES256 (non molto meglio di un

bruteforce… è impraticabile). Attenzione che un known plaintext attack con key related

(una tecnica sofisticata laddove le coppie ptx-ctx sono crittate con chiavi diverse ma simili,

cioè che differiscono per pochi bit, a quella che cerchiamo) ROMPE AES192 e AES256

176 99

con rispettivamente 2 coppie e 2 coppie WHAT THE FUCK. Cioè AES256 che ha una

chiave lunghissima si rompe teoricamente in meno tempo di AES128 con un bruteforce?

Proprio così, addirittura AES128 è immune a questo attacco perché lì cipherstate e key

hanno la stessa lunghezza (non possono esserci collisioni di chiavi). Quindi teoricamente

99

AES256 è più debole di AES128, però per memorizzare 2 coppie serve una quantità di

memoria che non si vede nemmeno con il telescopio Hubble e ci sono di mezzo tantissime

assunzioni per cui questa tecn