Crittografia contemporanea (simmetrica)

Sicurezza nelle applicazioni multimediali: lezione 3, crittografia contemporanea

Crittografia contemporanea


Classificazione dei sistemi crittografici contemporanei

2

• Il criterio di distinzione più importante per i sistemi crittografici contemporanei riguarda il tipo e numero di chiavi usate: nei sistemi a chiave simmetrica viene utilizzata una sola chiave, nei sistemi a chiave asimmetrica ogni utente dispone di due chiavi, una pubblica e una privata.

• Secondariamente, i sistemi crittografici possono essere distinti in base al tipo di dati su cui lavorano: i sistemi a blocchi elaborano i dati in blocchi di dimensione fissa (ad es. 64 bit), i sistemi a flusso elaborano i dati un byte (o bit, o altra unità di informazione) per volta.


Sistemi a chiave simmetrica

3

• In questa lezione parleremo di sistemi a chiave simmetrica (e principalmente di sistemi a blocchi).

X: messaggio in chiaro, Y: messaggio cifrato, K: chiave.X’, K’: stime di X e K da parte di un attaccante


Problemi della cifratura a chiave simmetrica

4

• Il problema principale della cifratura a chiave simmetrica consiste nella diffusione della chiave

• Se n persone devono comunicare tra di loro mediante messaggi crittati, sono necessarie n(n-1)/2 chiavi diverse (ordine di grandezza quadratico!). Ognuna di queste chiavi deve essere concordata tra mittente e destinatario su un canale sicuro…

• Vedremo nelle prossime lezioni come questo problema possa essere mitigato dai sistemi a chiave asimmetrica


Caratteristica fondamentale dell’algoritmo di cifratura

5

• Essere facilmente computabile ed invertibile se la chiave è nota

• Essere difficilmente invertibile in assenza della chiave

• In questo contesto, “facile” e “difficile” si riferiscono alla fattibilità pratica di effettuare una data computazione in tempi ragionevoli con le tecnologie disponibili attualmente o che potranno essere disponibili in un prossimo futuro (sicurezza computazionale).


Principio di Kerckhoffs

6

• un crittosistema deve essere sicuro anche se il suo funzionamento è di pubblico dominio, con l'eccezione della chiave

• In altre parole l’algoritmo non deve essere segreto. Al contrario, renderlo noto al pubblico contribuisce a garantire la sua robustezza in quanto può essere analizzato dalla comunità crittanalitica.


7

OTP e cifrari a flusso


One-Time Pad

8

• OTP (o cifrario di Vernam) è un cifrario di Vigenèrecon chiave lunga quanto il testo (senza ripetizioni), totalmente casuale e utilizzabile una volta sola

• Il testo cifrato non ha più alcuna relazione con quello originario: questa cifratura è inviolabile se l’attaccante ha accesso al solo testo cifrato (sicurezza incondizionata contro attacchi passivi)


Sicurezza di OTP (dim. intuitiva)

9

• Dimostrazione intuitiva dell’inviolabilità di OTP:

• Dato un testo cifrato, per qualsiasi testo in chiaro della stessa lunghezza esiste una chiave (unica ed equiprobabile ) che lo genera. Esempio:

D R E M U F C A

i j l t g o u a

v i t t o r i a

testo cifrato

chiave

testo in chiaro

chiave

testo in chiaro

o d s x q u q m

p o m p e l m o

Esercizio: scrivere un testo cifrato casuale, e trovare almeno due chiavi che lo trasformino in parole di senso compiuto


Sicurezza di OTP (dim. formale)

10

• Shannon: un cifrario è sicuro se il testo cifrato non rivela alcuna informazione riguardo al testo in chiaro.

• Formalmente, si richiede che:

Pr � �,�� Pr � �,��

∀ ∈ �, ∀��, �� ∈ �, �� |��|

• Nel caso di OTP, dato un messaggio m e un testo cifrato c, e ipotizzando che le chiavi siano casuali (distribuite uniformemente su �):

Pr � �,� � �#��.�.� �,� ��

��

�

� (costante ∀�)

�: insieme dei testi cifrati, �: insieme delle chiavi, �: insieme dei testi in chiaro��,��: algoritmo di cifratura applicato sul messaggio m con chiave k


One-Time Pad / 3

11

• Ricordiamo che le chiavi devono essere casuali, uniche per ogni messaggio e lunghe (almeno) quanto il messaggio stesso.

– Se la chiave non è lunga quanto il messaggio, l’algoritmo è vulnerabile ad un attacco di Kasiski (già visto per Vigenère)

– Se una stessa chiave viene usata per cifrare più messaggi, si ricade nel caso precedente

– Se la chiave non è casuale, allora alcune chiavi sono più probabili di altre: questo ci permette di discriminare tra due output


One-Time Pad / 3

12

• Due problemi principali limitano l’uso di OTP in pratica:

– Difficoltà di creare chiavi davvero casuali

– Necessità di condivisione delle chiavi tra mittente e destinatario

• Il problema di trasmettere il messaggio non è stato risolto, ma solo trasformato nel problema di condividere una chiave altrettanto lunga.

• Unico vantaggio: condivisione della chiave e trasmissione del messaggio possono avvenire in istanti diversi (es: condivisione iniziale sicura della chiave per proteggere la successiva trasmissione del messaggio su canale insicuro)


Richiamo sull’operatore XOR

13

• L’operatore exclusive-or (XOR, ⊕) è un operatore booleano che assume valore 1 quando due bit sono diversi, e 0 quando sono uguali p q p⊕⊕⊕⊕q

0 0 0

1 0 1

0 1 1

1 1 0

Esempio:110101001 ⊕010011011 =100110010

Proprietà fondamentali:• A ⊕ A = 0• A ⊕ 0 = A• A ⊕ ( B ⊕ C ) = ( A ⊕ B ) ⊕ C


OTP binario

14

• Se volessimo applicare OTP a dati binari?

• L’alfabeto è composto da due soli simboli: 0, 1

• La tabella di Vigenère si semplifica:

• Quindi si può realizzare una cifratura OTP su dati binari combinandoli in XOR con una sequenza casuale di bit

0 1

0 0 1

1 1 0

In altre parole, l’operatore binario di XOR

CIFRATURA: C = M ⊕ KDECIFRAUTRA: M = C ⊕ K

( C ⊕ K = M ⊕ K ⊕ K = M )


Riutilizzo delle chiavi con OTP binario

15

• OTP binario ci permette di capire meglio perché la chiave OTP non può essere riutilizzata:

• C1 = M1 ⊕ K

• C2 = M2 ⊕ K

• C1 ⊕ C2 = M1 ⊕ K ⊕ M2 ⊕ K = M1 ⊕ M2

Lo XOR di due testi cifrati è uguale allo XOR dei rispettivi testi in chiaro. Permette ad esempio di identificare immediatamente porzioni di testo uguali (in quanto il risultato dello XOR è una sequenza di 0)

M1, M2 testi in chiaro, K chiave, C1, C2 testi cifrati


Esempio visuale

16

⊕⊕⊕⊕

⊕⊕⊕⊕

=

=

M1

M2

K

K

C1

C2

⊕⊕⊕⊕


Altri attacchi a OTP

17

• «sicurezza incondizionata» significa che non è possibile decifrare un messaggio cifrato con OTP avendo a disposizione solamente il testo cifrato, perché ogni decifrazione è ugualmente probabile e quindi indistinguibile (sicurezza rispetto agli attacchi passivi)

• Esistono tuttavia altri attacchi possibili a OTP, ad esempio sfruttando la sua malleabilità

• Un cifrario è malleabile se è possibile alterare il testo cifrato in modo da ottenere un risultato specifico in seguito alla decifratura (attacco attivo)


Malleabilità di OTP

18

Cifratura: C = M ⊕ K

Un attaccante intercetta C e lo sostituisce con C’ = C ⊕ N

decifratura: M’ = C’ ⊕ K = M ⊕ K ⊕ N ⊕ K = M ⊕ N

Se l’attaccante conosce M, può scegliere un opportuno N tale che, in fase di decifratura, il testo in chiaro originario M sia sostituito da un testo arbitrario M’, scelto dall’attaccante


OTP e cifrari a flusso

19

• L’idea di OTP binario è alla base di molti cifrari a flusso, in cui i bit da cifrare sono elaborati indipendentemente l’uno dall’altro, senza la necessità di suddividerli in blocchi di dimensioni fisse

• In questo caso i cifrari a flusso sono basati sull’uso di PRG (pseudo-random generators), generatori di sequenze di bit apparentemente casuali

• Naturalmente questi algoritmi non sono delle vere implementazioni di OTP, in quanto la sequenza di bit non è davvero casuale (è pur sempre generata da algoritmi deterministici… )

• E’ tuttavia sufficiente che tale sequenza sembri casuale da un punto di vista statistico (ovvero, in assenza del seed iniziale è impossibile fare delle previsioni sulla sequenza generata dall’algoritmo)


Cifrari a flusso

20

Chiave casuale

⊕

Testo in chiaro

Testo cifrato

�

sequenza pseudo-casuale

⊕

Testo in chiaro

Testo cifrato

�

chiave PRG

OTP

Cifrario a flusso basato su PRG


21

Cifrari a blocchi


I concetti di confusione e diffusione

22

• Introdotti da Shannon (il padre della teoria dell’informazione!) nel 1949

• Confusione: rendere la relazione tra chiave e testo cifrato quanto più complessa possibile

• Diffusione: rendere la relazione tra testo in chiaro e testo cifrato quanto più complessa possibile


Diffusione

23

• Le anomalie statistiche del testo in chiaro che lo rendono facilmente identificabile (ad es. le frequenze caratteristiche di ogni lettera) devono essere “diffuse” su quanti più caratteri possibili del testo cifrato, in modo da “mischiarle” al punto da renderle irriconoscibili.

• Ad esempio, la cifratura monoalfabetica non ha alcuna diffusione, perché le caratteristiche statistiche di ogni carattere in chiaro si trasmettono inalterate al carattere cifrante.


Criterio di avalanche

24

• Ne consegue che la modifica di anche un carattere del testo in chiaro dovrebbe implicare l’alterazione di tutto il testo cifrato (diffusione)

• Analogamente, la modifica di anche un solo carattere della chiave, dovrebbe implicare l’alterazione di tutto il testo cifrato (confusione)

• Questa proprietà è nota con il nome di

criterio di avalanche


Criterio di avalanche / 2

25

• La crittografia contemporanea si basa sull’uso dei computer, quindi d’ora in poi ci occuperemo di messaggi composti da bit

• Una definizione più formale del criterio di avalanche è la seguente:

In altre parole, il nuovo testo cifrato è apparentemente casuale, non ha

alcuna relazione statistica con il testo cifrato precedente

SAC (Strict Avalanche Criterion): se un bit del messaggio in chiaro o della chiave viene complementato, allora ogni bit del messaggio

cifrato ha una probabilità del 50% di essere complementato

(Complementare un bit: cambiarne il valore. Se vale 1, diventa 0. Se vale 0, diventa 1)


Criterio di avalanche / 3

26

• Perché il criterio di avalanche è così importante?

• Se due testi di input simili (o due chiavi simili) producessero due output simili, l’algoritmo di crittazione sarebbe vunerabileagli attacchi crittanalitici

• Confrontando il testo cifrato da decodificare con il testo cifrato di un testo in chiaro a noi noto, potremmo sapere quanto “vicini” siamo alla soluzione


Reti SP

27

Le reti a sostituzione-permutazione (Substitution-Permutation Networks, SPN) sono costituite da una serie di operazioni matematiche in cascata volte a garantire le proprietà di diffusione e confusione (e quindi a soddisfare il criterio di avalanche).

Composte da due elementi fondamentali:

-Le S-Box (substitution box)- Le P-Box (permutation box)

Cifratura a blocchi!


S-Box

28

• Una Substitution Box (S-Box) è una funzione che sostituisce i bit di input con dei bit di output in modo soddisfare il criterio di avalanche.

• Il cambiamento di un singolo bit di input quindi deve influenzare circa la metà dei bit di output

• Una S-Box è un tipo particolare di cifratura a sostituzione

S-Box

i1 i2 i3 i4

o1 o2 o3 o4

Esempio di S-Box

0001 01001001 1010


P-Box

29

• Una Permutation Box (P-Box) è una funzione che genera in output una permutazione dei bit di input

• E’ quindi un caso particolare di cifratura a

trasposizione

1 0 0 1 0 1 0 1 1 1 0 1 0 0 1 1

0 1 0 1 1 1 1 0 1 0 1 0 1 0 1 0


Reti SP / 2

30

Nelle reti SP si alterna l’uso di S-Box e P-Box, iterando il procedimento più volte(ogni iterazione è detta stadio, o round)

Ad ogni iterazione la chiave viene opportunamente manipolata per estrarre una sottochiave diversa (K0…K3

nell’immagine qui a fianco). La sottochiave viene combinata mediante XOR con il testo in chiaro (all’inizio) o col testo cifrato dopo un determinato stadio.


Reti SP / 3

31

• Le reti SP sono studiate per soddisfare il criterio di avalanche

– Le S-Box sono studiate affinché il cambiamento di un solo bit di input influenzi tutti i loro output

– Le P-Box garantiscono che l’output di una S-Box allo stadio n sia “diffuso” come input di tutte le S-Box dello stadio n+1

• Poiché chiave e testo sono combinate con uno XOR (e quindi influenzano “con lo stesso peso” il risultato di output), le reti SP garantiscono contemporaneamente sia la diffusione che la confusione.


Decifratura nelle reti SP

32

• Per decifrare un testo cifrato, è sufficiente applicare i passi della rete SP a ritroso, dall’ultimo fino al primo

• Questo richiede che le S-Box siano INVERTIBILI, ovvero che, dato un output, sia possibile risalire univocamente al suo input.

Input Output

00 10

01 11

10 11

11 01

Esempio di S-Box non invertibile(qual è l’inverso di 11?)


Esercizio

33

Qual è l’output di questo primo stadio, supponendo che le S-Box siano tutte uguali (si veda la tabella), che la sottochiave K0 valga 1100 1010 0011 0001 e il testo in chiaro valga 0101 1111 0000 1011 ?

Tabella di corrispondenze input-output della S-Box


Le reti di Feistel

34

• Ideate da Horst Feistel, ingegnere della IBM

• Sono un caso particolare di reti SP, con alcune modifiche

• La loro struttura è alla base del funzionamento di molti degli attuali algoritmi di crittazione a chiave simmetrica


Le reti di Feistel / 2

35

• Il testo in chiaro (di dimensione fissa, ad es. 64 bit)viene diviso in due metà, L0 e R0

• Ad ogni stadio i…

• la metà di destra (Ri) diventerà la metà disinistra allo stadio successivo

• la metà di sinistra viene combinata in XOR conF(Ki,Ri), dove Ki è la sottochiave allo stadio i ed F è una funzione complessa, e diventerà lametà destra allo stadio successivo

Li+1 = Ri

Ri+1 = Li ⊕ F(Ri,Ki)


Relazione con le reti SP

36

• Una rete di Feistel può essere vista come una rete SP in cui F è una S-Box e lo scambio delle due metà è una P-Box

• Differenze rispetto alle reti SP: la chiave non è combinata direttamente in XOR col testo da cifrare, ma è un input della funzione F


Reti di Feistel: decifratura

37

• Decifrare un testo generato da una rete di Feistel è molto semplice: è sufficiente applicare lo stesso

algoritmo, avendo cura di invertire solamente l’ordine delle sottochiavi

• Vantaggio notevole, non serve scrivere un programma apposito per la decrittazione


Decifratura di Feistel: dimostrazione

38

• Consideriamo cosa accade nell’ultimo stadio n di cifratura (e di conseguenza nel primo stadio di decifratura):

Testo in input all’ultimo stadio: [Ln, Rn]

Testo cifrato finale:[ Ln ⊕ F(Kn,Rn), Rn ]

Primo stadio di decifratura:[ Ln ⊕ F(Kn,Rn) ⊕ F(Kn,Rn), Rn ] =

[ Ln ⊕ 0, Rn ] =

[ Ln , Rn ] Usando le proprietà

dello XOR!

cifratura decifratura

Ln Rn

Ln Rn

Il primo passo di decifratura “annulla” l’ultimo di cifratura. Applicando lo stesso procedimento a tutti gli stadi, si dimostra che la decifratura permette effettivamente di recuperare il testo in chiaro


Decifratura di Feistel

39

• Proprietà fondamentale del processo di decifratura di Feistel, nonché differenza principale rispetto alle reti SP:

non è necessario che F sia invertibile!

Pertanto F può essere arbitrariamente complessa


Realizzazione di una rete di Feistel

40

Scelte progettuali da considerare:

• Dimensioni del blocco (spesso 64 bit)

• Dimensioni della chiave (le più comuni oggigiorno sono a 128 bit, le chiavi fino a 64 bit sono ormai considerate insicure)

• Numero di stadi (tipicamente 16)

• Algoritmo di generazione delle sottochiavi

• Scelta della funzione F

Altri aspetti da considerare:

• Velocità di cifratura/decifratura software

• Facilità di analisi


Cifrari basati sul modello di Feistel

41

• Il modello di Feistel è alla base della struttura di molti cifrari contemporanei:

Blowfish, Camellia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST_28147-89, CAST-256, MacGuffin, RC2, RC6, Skipjack, SMS4 …

• Studieremo ora nel dettaglio uno dei più importanti: il DES


DES – Data Encryption Standard

42

• Sviluppato da IBM, deriva dal precedente Lucifer, ad opera dello stesso Feistel

• Nel 1976 è diventato uno standard negli USA per la protezione di dati sensibili

• Scelta inizialmente controversa…

– per la lunghezza della chiave, che pare sia stata ridotta a 56 bit (rispetto ai 128 di Lucifer) per imposizione della NSA

– Per la segretezza di alcuni dettagli implementativi (violazione del principio di Kerckhoffs), in seguito resi pubblici


DES / 2

43

• E’ un algoritmo di cifratura simmetrico a blocchi

• La struttura è quella di una rete di Feistel

• I blocchi sono di 64 bit

• La chiave è di 64 bit, ma ne vengono usati solo 56

• Ad oggi non è più considerato sicuro. E’ stato sostituito dal nuovo standard AES


Struttura generale di DES

44

• Due permutazioni, IP e FP, una l’inversa dell’altra (non hanno alcun valore crittografico, servivano solo a rendere più efficiente l’implementazione in hardware)

• L’input viene diviso in due blocchi da 32 bit…

• …elaborati secondo il classico schema delle reti di Feistel in 16 stadi (round)


La funzione F

45

• Una funzione complessa e non invertibile

• E è un blocco di espansione, che trasforma i 32 bit di input in 48 bit di output, duplicando alcuni degli input

• S1 … S8 sono delle S-Box

• P è una P-Box

• Usando la chiave a 56 bit viene generata una sottochiave a 48 bit (diversa per ogni stadio)


S-Box e P-Box nella funzione F

46

• Le S-Box ricevono 6 bit di input e hanno 4 bit di output

• Esempio di S-Box usata da DES:

• La P-Box:

Fonte: http://en.wikipedia.org/wiki/DES_supplementary_material


Generazione delle sottochiavi

47

• PC1 è una permutazione che estrae solo 56 dei 64 bit di chiave

• I 56 bit sono divisi in due gruppi di 28 bit

• Ad ogni stadio i due gruppi vengono ruotati di uno o due bit (a seconda dello stadio)…

• …e una ulteriore permutazione (PC2) estrae 24 bit da ognuno dei due gruppi ruotati, generando così una sottochiave da 48 bit


Attacchi a forza bruta al DES

48

• Nel 1977 Diffie e Hellman stimarono che il DES potesse essere violato in un solo giorno con una macchina dal costo stimato di $20M

• Nel 1993 Wiener stimò che si potesse raggiungere lo stesso risultato in 7 ore con una macchina da $1M

• Nel 1998 una macchina da $250.000 realizzata da EFF (Electronic Frountier Foundation) violò effettivamente un crittogramma DES in 2 giorni


Altri algoritmi basati su reti di Feistel: 3DES

49

• Triple DES migliora sensibilmente la sicurezza di DES, ed è ancora considerato valido (si stima fino al 2030)

• Sono necessarie tre chiavi DES (per un totale di 168 bit)

Encrypt Decrypt Encrypt

K1 K2 K3

Decrypt Encrypt Decrypt

K3 K2 K1

codifica

decodifica

Usato, in diverse varianti, nelle transazioni commerciali elettroniche (circuiti VISA, Mastercard…)


3DES keying options

50

• Opzione 1: le chiavi K1, K2 e K3 sono diverse e indipendenti

• Opzione 2: K1 = K3, K2 diversa

• Opzione 3: K1 = K2 = K3


3DES keying option 1

51


K1 K2 K3

• K1, K2 e K3 indipendenti

• Lunghezza totale della chiave: 56 x 3 = 168 bit

• Ma in realtà sono necessari meno di 2168 tentativi per un attacco a forza bruta! La sicurezza di 3DES con keyingoption 1 è pari a quella di un algoritmo con chiave di 112 bit a causa del…

meet-in-the-middle attack


Meet-in-the-middle attack

52

• Supponiamo di avere una coppia nota di testo in chiaro / testo cifrato…

• Calcolare tutte le cifrature possibili dei primi due passi dell’algoritmo, eseguendo in totale di 256 x 256 = 2112 cifrature

• Calcolare tutte le decifrature possibili per l’ultimo passo, per un totale di 256 decifrature

• Cercare una coppia di risultati uguali

• Complessità totale dell’attacco: 2112 + 256 cifrature/decifrature (quindi nell’ordine di grandezza di 2112 )


K1 K2 K3

256 256

2112

256

Ecco perché non si usa 2DES

m c



53

• Due chiavi da 56 bit -> sicurezza a 112 bit

• La sicurezza è quindi comparabile a quella della keyingoption 1, ma col vantaggio di usare chiavi più piccole

• Sarebbe una pessima idea usare solo due DES encryptconsecutivi (meet-in-the-middle attack)


K1 K2 K1



54

• Usato esclusivamente per garantire la compatibilità con DES: i primi due passi si annullano, per cui l’applicazione di 3DES con keying option 3 è equivalente a quella di DES normale (è il motivo per cui il blocco centrale è una decrittazione!)

• Sicurezza della chiave: 56 bit, come DES


K1 K1 K1


Blowfish

55

• Sviluppato da Bruce Schneier, uno dei guru della crittografia contemporanea

• Blocchi da 32 bit, chiavi fino a 448 bit, 16 stadi

Schema generaleLa funzione F

(il simbolo rappresenta la somma modulo 232)


RC5

56

• Sviluppato da Ronald Rivest, uno dei padri della crittografia a chiave asimmetrica

• Blocchi da 32, 64 o 128 bit, chiavi fino a 2040 bit (solitamente: 128), numero di stadi fino a 255 (solitamente: 12).

• Estremamente semplice e veloce, ha introdotto la novità dei data-dependentshifts

2 stadi di RC5


TEA

57

• Famoso soprattutto per essere suscettibile a diversi tipi di attacchi crittanalitici, che hanno portato nel 2002 alla possibilità di “hackerare” la console da gioco Xbox affinché potesse eseguire codice arbitrario

(sfruttato per eseguire Linux su una Xbox)


AES

58

• Nel 1997 il NIST (National Institute of Standards and Technology) USA organizzò un “concorso” per sostituire l’ormai insicuro DES e definire un nuovo standard crittografico, l’Advanced Encryption Standard (AES)

• 15 candidati: CAST-256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER+, Serpent, Twofish

• Gli algoritmi furono sottoposti alle più rigorose analisi crittografiche, finché nel 2000 Rijndael divenne ufficialmente il nuovo standard, grazie alle sue caratteristiche di robustezza alla crittanalisi e velocità di esecuzione.


AES / 2

59

• Blocchi di 128 bit, chiavi da 128, 192 o 256 bit

• Basato una combinazione di permutazioni e sostituzioni (analogo ad una rete SP), ma non è una rete di Feistel.

• L’input viene organizzato in una griglia di 4x4 byte che subisce 4 trasformazioni ad ogni stadio (gli stadi sono 10 nel caso di chiavi a 128 bit)


AES / 3

60

Prima trasformazione: ogni byte viene trasformato da una S-Box

Seconda trasformazione: le righe della matrice subiscono uno shift(equivalente ad una P-Box)


AES / 4

61

Terza trasformazione: ogni colonna viene trasformata secondo una procedura equivalente ad una S-Box

Quarta trasformazione: ogni byte viene combinato in XOR con la sottochiave


Tecniche di cifratura

62

• Gli algoritmi di cifratura a blocchi lavorano su blocchi di dimensione fissa (es. 64 bit). Ma come cifrare dei dati più lunghi della dimensione del blocco?

Modalità Descrizione Applicazioni

Electronic Codebook(ECB)

Ciascun blocco è cifrato in maniera indipendente, usando la stessa chiave

Trasmissione di datimolto brevi

Cipher Block Chaining(CBC)

Ogni blocco in input è combinato in XOR con l’output del passo precedente

Trasmissione a blocchi

Counter(CTR)

Ogni blocco in input è combinato in XOR con un contatore crittografato

Trasmissione a blocchi. Particolarmente veloce


ECB – Electronic Codebook

63

• Ogni blocco è cifrato con la stessa chiave e trasmesso in maniera indipendente dagli altri

• Estremamente insicuro. Blocchi uguali hanno codifiche uguali (violazione del criterio di diffusione)


ECB / 2

64


CBC – Cipher Block Chaining

65

• Risolve i problemi di ECB combinando ogni blocco con l’output della cifratura precedente

Note: -IV (initialization vector) è un vettore di inizializzazione casuale datrasmettere assieme alla chiave-nella fase di decifratura si sfruttano le proprietà dello XOR, inparticolare: A ⊕ B ⊕ B = A


CTR - Counter

66

• Studiato per la trasmissione a blocchi

• Più robusto agli errori CBC (un errore nella trasmissione di un crittogramma non influisce su quello successivo)

• Particolarmente veloce (si possono eseguire più decrittazioni in parallelo se più dati arrivano contemporaneamente)


67

• Osservazione: si noti come in CTR l’algoritmo di cifratura non è applicato direttamente al testo da cifrare, ma al contatore

• Il testo in chiaro viene poi combinato in XOR con il risultato della cifratura

→ E’ sufficiente a garan�re la sicurezza dell’algoritmo? Rileggere le

considerazioni fatte a suo tempo su OTP binario…


Crittanalisi contemporanea

68

Rompere un cifrario significa semplicemente trovare una

debolezza nello stesso che può essere sfruttata con una

complessità minore della forza bruta. Non importa che

forza bruta richieda 2128 cifrature: un attacco che

richiedesse 2110 cifrature sarebbe considerato una rottura.

La rottura potrebbe anche richiedere quantità irrealistiche

di testi in chiaro noti o di memoria disponibile. In parole

povere, una rottura può essere semplicemente una

debolezza certificabile: la prova che il cifrario non si

comporta come previsto.

Bruce Schneier


Scenari di crittanalisi

69

• solo testo cifrato: l'attaccante ha accesso solo ad una collezione di testi cifrati.

• Testo in chiaro noto: l'attaccante ha un insieme di testi cifrati dei quali conosce i corrispondenti testi in chiaro.

• Testo in chiaro scelto: l'attaccante può ottenere i testi cifrati corrispondenti ad un insieme arbitrario di testi in chiaro di sua scelta.

• Attacco alle chiavi correlate: l'attaccante può ottenere uno stesso testo in chiaro cifrato con due differenti chiavi. Le chiavi sono ignote ma la relazione fra esse è nota: ad esempio, due chiavi che differiscono solo di 1 bit.


Risultati della crittanalisi

70

• violazione totale: l'attaccante deduce la chiave segreta

• deduzione globale: l'attaccante scopre un algoritmo funzionalmente equivalente per la cifratura e la decifratura, ma senza conoscere la chiave;

• deduzione locale: l'attaccante scopre testi in chiaro non noti in precedenza;

• deduzione dell'informazione: l'attaccante ottiene alcune informazioni di Shannon sui testi in chiaro (o sui testi cifrati) non note precedentemente;

• algoritmo discriminante: l'attaccante può distinguere il cifrario da una permutazione casuale.


Tecniche di crittanalisi

71

Esistono diverse tecniche di crittanalisi, le più famose sono:

• Crittanalisi differenziale: è una tecnica a testo in chiaro scelto. Si crittano due testi in chiaro con differenze note e si analizza come tali differenze si propagano fino all’output, alla ricerca di eventuali regolarità (in un buon algoritmo invece la relazione tra testo in chiaro e testo cifrato è sempre apparentemente casuale – confusione e diffusione!).

• Crittanalisi lineare: si cercano delle funzioni lineari che mettano in relazione testo in chiaro, testo crittato e chiave


Esempio: crittanalisi di DES

72

• Mediante tecniche di crittanalisi differenziale, DES può essere violato conoscendo 243 testi in chiaro scelti

• Mediante tecniche di crittanalisi lineare, DES può essere violato conoscendo 241 testi in chiaro

Crittografia contemporanea (simmetrica)

Documents

Transcript of Crittografia contemporanea (simmetrica)