Crittografia simmetricaIng. Michela Cancellaro Ing. Federica Battistig g

One-Time Pad• Se viene usata una chiave casuale lunga come il messaggio il

cifrario sarà sicuro

Esempio:

Ciphertext= ankyodkyurepfjbyojdsplreyiunofdoiuerfpluytdl d f l b d hf l ihKey= pxlmvmsydofyrvzwc tnlebnecvgdupahfzzlmnyih

Plaintext= Mr mustard with the candlestick in the hall

Ciphertext= ankyodkyurepfjbyojdsplreyiunofdoiuerfpluytdKey= mfugmiydgaxgoufhklllmhsqdqogtewbqfgyovuhwtPlainte t Miss scarlet ith the knife in the librarPlaintext= Miss scarlet with the knife in the library

One-Time Pad• Vantaggi:

– Non è violabile dato che il ciphertext non ha relazioni statiscticheNon è violabile dato che il ciphertext non ha relazioni statisctiche con il plaintext

– Per ogni plaintext e ogni ciphertext esiste una chiave che li mappa l’ l’ ltl’uno con l’altro

• Svantaggi:• Svantaggi:– La chiave può essere usata una sola volta– Si ha il problema di una distribuzione sicura delle chiavip

Cifrari a trasposizione• Consideriamo i classici cifrari a trasposizione o permutazione

• Permettono di nascondere il messaggio riordinando le lettere del messaggio senza alterare le lettere utilizzatemessaggio senza alterare le lettere utilizzate

• Si può facilmente riconoscere perchè presenta la stessa• Si può facilmente riconoscere perchè presenta la stessa distribuzione in frequenza di lettere dell’originale

Cifratura a ‘staccionata’• Si scrivono le lettere del messaggio diagonalmente su un certo

numero di righenumero di righe

• Il messaggio cifrato viene letto riga per riga• Il messaggio cifrato viene letto riga per riga

• Esempio: con il messaggio ‘meet me after the toga party’:• Esempio: con il messaggio meet me after the toga party :m e m a t r h t g p r ye t e f e t e o a a t

• Si ottiene il testo cifratoMEMATRHTGPRYETEFETEOAAT

Cifrari a trasposizione di riga• Schema più complesso

• Si scrivono le lettere del messaggio in righe su un numero specificato di colonne

• Si riordinano le colonne secondo una certa chiave

Key: 4 3 1 2 5 6 7

Plaintext: a t t a c k pPlaintext: a t t a c k po s t p o n ed u n t i l tw o a m x y zw o a m x y z

Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ

Cifrari a prodotto• Cifrari che utilizzano sostituzioni o trasposizioni non sono sicuri

a causa delle caratteristiche del linguaggioa causa delle caratteristiche del linguaggio

• É quindi possibile pensare di utilizzare più cifrari in successione• É quindi possibile pensare di utilizzare più cifrari in successione per rendere il sistema più robusto ma:– Due sostituzioni costituiscono una sostituzione più complessa p p– Due trasposizioni costituiscono una trasposizione più complessa– Una sostituizione seguita da una trasposizione rende il sistema g p

molto più robusto

• Questa è l’idea che ha portato alla cifratura moderna

Steganografia• É un’alternativa alla cifratura

• Nasconde l’esistenza del messaggioUsando un subset di lettere o parole in un supporto multimediale– Usando un subset di lettere o parole in un supporto multimediale

– Usando inchiostro invisibile– Nascondendo le informazioni in un’immagine in un video o in un– Nascondendo le informazioni in un immagine, in un video o in un

file audio

• Ha degli svantaggi– Non è sempre possibile inserire un grande quantitativo di bit

Cifrari a blocchi e a stream

Cifrari a blocco e a flussoCifrari a blocco

• I cifrari a blocco processano blocchi di informazione ognuno dei• I cifrari a blocco processano blocchi di informazione ognuno dei quali è ci\decifrato indipendentemente

• Il plaintext è considerato come una sequenza di blocchi di p qlunghezza n bit

• Il ciphertext ha la stessa lunghezza del plaintext• Opera come una sostituzione su caratteri molto grandi (64-bit o

più)Cif i tCifrari a stream

• Processano i messaggi un bit o byte per voltaSpesso sono più semplici da anali are matematicamente• Spesso sono più semplici da analizzare matematicamente

• Molti cifrari utilizzati sono a blocchi• Molti cifrari utilizzati sono a blocchi

Cifrari a blocco• L’algoritmo di cifratura converte un blocco di plaintext in uno

cifratocifrato

• Quanto deve essere lungo un blocco di plaintext?• Quanto deve essere lungo un blocco di plaintext?– Se il blocco è troppo piccolo (un byte come per i cifrari

monoalfabetici), potrebbe essere più semplice costruire una tavola ), p p pdi decifratura a partire da una coppia <plaintext,ciphertext>

– Se il blocco è troppo lungo si hanno degli svantaggi legati ll’ di l i àall’aumento di complessità

– Spesso si scelgono blocchi da 64 bitÉ difficile ottenere 264 coppie (attacco k l i t t)– É difficile ottenere 264 coppie (attacco known plaintext)

Esempio di cifrario a blocco

Blocco di testo in chiaroBlocco di testo cifrato

Testo originaleTesto originale

k k k k

Testo cifratoTesto cifrato

Cifrari a blocco• Se sono usati blocchi da 64 bit, 264 possibili input sono mappati

in 264 outputin 2 output

• Il modo più generale per cifrare è specificare completamente la• Il modo più generale per cifrare è specificare completamente la tavola per la mappatura– Necessità di tavole di 264 entrate per blocchi di 64 bitp– Sarebbero troppo grandi– Si creano tabelle per piccoli blocchi

• I sistemi crittografici a chiave segreta sono progettati per avere d ll hi i di l h i l ( 64 bit)delle chiavi di lunghezza ragionevole (es. 64 bit) e per generare un mapping uno a uno che appaia completamente casuale a chi non conosce la chiavenon conosce la chiave

Crittografia a blocchi di 4 bit

m

4 bit

mi

4 bitEncryption

ci

ci

4 bitDecryption

mi

Cifrari a blocco• Le principali trasformazioni usate sono:

sostituzione– sostituzione• Specifica per ognuno dei 2k possibili input l’output di lunghezza

k-bitk bit • Non è un metodo pratico per blocchi da 64 bit ma è possibile per

blocchi più piccoli (es. 8 bit)• Per effettuare una sostituzione su un blocco di k bit sono

necessari k.2k biti– permutazione

• Specifica per ognuno dei k bit di input la corrispondente posizione dell’inputposizione dell input

• Una permutazione è un caso speciale di sostituzione in cui ogni bit dell’output è generato da un solo bit di input p g p

• Per effettuare una permutazione su blocchi di k bit sono necessari k. log2k bit

Cifrari a blocco• Un modo possibile per realizzare un algoritmo è

Suddividere l’input in gruppi di grandezza definita (es 8 bit)– Suddividere l input in gruppi di grandezza definita (es.8 bit),– Effettuare una sostituzione su ogni blocchetto – Prendere l’uscita di tutte le sostituzioni e darle in input a unPrendere l uscita di tutte le sostituzioni e darle in input a un

permutatore (grande quanto l’input)– Il processo è quindi ripetuto per ogni bit– Ogni ripetizione si chiama round

S1 S2 S3 S4 Substitutions

n r

ou

nd

s

Permutation

oo

p w

ith

nLo

Cifrari a sostituzione e permutazione

• Nel 1949 Claude Shannon ha introdotto l’idea di reti a sostituzione-permutazionesostituzione-permutazione

• Queste reti sono la base della crittografia moderna • Le reti S P sono basate sulle due primitive di cui abbiamo appena• Le reti S-P sono basate sulle due primitive di cui abbiamo appena

parlato: – sostituzione (S-box)sostituzione (S box)– permutazione (P-box)

• Fornisce confusione e diffusione di un messaggio• Fornisce confusione e diffusione di un messaggio• L’operazione deve essere reversibile!

Confusione e diffusione• L’algoritmo di cifratura deve riuscire ad oscurare completamente

le proprietà statistiche del messaggio originalep p gg g

• Il one-time pad fa essattamente questo

• Shannon ha suggerito di combinare gli elementi per ottenere:– diffusione

• ‘sparge’ la struttura statistica del plaintext su tutto il ciphertextf i– confusione

• Rende la relazione tra ciphertext e chiave il più complesso possibilep

Cifrario di Feistel• Horst Feistel ha realizzato il cifrario di Feistel basato sul

concetto di cifrari a prodotto invertibilep

• I blocchi di input sono divisi in due parti– Questi sono processati con round multipli che effettuano

sostituzione sulla parte sinistra dei dati tramite una funzione di arrotondamendo sulla parte destra dei dati e una successivaarrotondamendo sulla parte destra dei dati e una successiva operazione di XOR con la parte sinistra dei dati. Si ha quindi una permutazione che inverte parte destra e sinistraL’ d è ff i d hi h bi– L’arrotondamento è effettuato a partire da una chiave che cambia adogni round

• Si basa sul concetto della rete di sostituzione- permutazione di Shannon

Cifrario di Feistel

⊕

⊕

⊕⊕

Principi di progettazione• Dimensione del blocco

– L’aumento della grandezza del blocco aumenta la sicurezza ma grallenta l’algoritmo

• Dimensione della chiave• Dimensione della chiave– L’aumento della lunghezza della chiave aumenta la sicurezza e

rende la ricerca esaustiva più difficile ma rallenta l’algortimo

• Numero di round– Aumento del numero di round aumenta la sicurezza ma rallentaAumento del numero di round aumenta la sicurezza ma rallenta

l’algoritmo

• Funzione di round– L’aumento di complessià rende l’analisi più difficile ma rallenta

l’algoritmog

• Velocità del software di ci\decifratura e semplicità nell’analisi

Decifratura di Feistel

⊕

⊕ ⊕

⊕

⊕ ⊕

⊕ ⊕

Data Encryption Standard (DES)

Data Encryption Standard (DES)• Cifrario a blocchi più utilizzato al mondo • Pubblicato nel 1977 dal National Bureau of Standards (ora NIST• Pubblicato nel 1977 dal National Bureau of Standards (ora NIST

National Institute of Standards and Technology) per uso commerciale e applicazioni del Governo degli U.S.commerciale e applicazioni del Governo degli U.S.

• Cifra blocchi di 64-bit usando chiavi lunghe 56-bit• Ha un ampio impiegoHa un ampio impiego• Ci sono state molte controversie sulla sicurezza dell’algoritmo a

causa dela ridotta lunghezza della chiaveg

Storia DES• Basato su un algortimo noto come Lucifer cipher (1971)

– Da un gruppo IBM guidato da Horst Feistel– Da un gruppo IBM guidato da Horst Feistel– Usa blocchi di 64-bit con una chiave lunga 128-bit

• Risviluppato in seguito come cifrario commerciale pp g• Nel 1973 NBS (National Bureau of Standard) ha richiesto

proposte per un algoritmo di cifratura standard nazionale• IBM ha sottomesso la versione rivisitata di Lucifer accettata

come DESDES è l t tili t i l t i li i i• DES è largamente utilizzato specialmente in applicazioni finanziarie

• Nel 1999 il NIST ha pubblicato una nuova versione chiamata• Nel 1999 il NIST ha pubblicato una nuova versione chiamata triple DES (3DES) o TDEA

Data Encryption Standard (DES)• Il DES consiste di

Una permutazione iniziale dei 64 bit– Una permutazione iniziale dei 64 bit– 16 round identici in cui i dati sono confusi e diffusi con la chiave e

il round precedentep– Una permutazione finale

• DES può essere efficientemente implementato in hardwarep p• Relativamente lento se implemetato in software

– Non era questa l’intenzione!q

Perchè chiavi da 56 bit?• 8x7 bits + 8 bit per il controllo di parità• Comunque 8 bit per il controllo di parità sono pochi• Comunque 8 bit per il controllo di parità sono pochi

– 64 bits non validi hanno una possibilità su 256 di sembrare una chiave validachiave valida

• È stato suggerito di ridurre la lunghezza della chiave da 64 a 56 bit

• 56 bit corrispondono a 256 possibili chiavi che corrispondono ad un valore di circa 7.2 x 1016 chiavi

DES• Usa chiavi di lunghezza 64 bit che viene ridotta a 56 bit per il

controllo di paritàcontrollo di parità– La chiave a 56 bit è trasformata in sottochiavi, una per round

• Transforma i blocchi di input M da 64 bit in blocchi di output CTransforma i blocchi di input M da 64 bit in blocchi di output C da 64 bit

• L’algortimo di cifratura è identico a quello di decifratura, la g q ,differenza sta nell’uso delle sottochiavi che sono usate in ordine inverso

DES• Consiste in

– Una permutazione inizialeUna permutazione iniziale (P)

– Una trasformazione della chiave

– 16 rounds in cui:• I 32 bit dell’input a destra

sono spostati nei 32 bit più a i i t d ll’ t tsinistra dell’output

• Una funzione f() è realizzata sulla parte destra sulla partesulla parte destra, sulla parte sinistra e sulla chiave

• La chiave è shiftata ad ogni round

– Una permutazione finale (P-1)

Initial Permutation IP• È il primo passo dell’algoritmo • IP riordina gli inputIP riordina gli input • I bit della metà destra metà sinistra e viceversa• Questo è l’unico passo che rende DES diverso dal cifrario diQuesto è l unico passo che rende DES diverso dal cifrario di

Feistel • La struttura è regolare e quindi semplice da implementare in

h dhardware• Esempio

IP(675a6967 5e5a6b5a) = (ffb2194d 004df6fb)

• Non serve ad incrementare la sicurezza• Legato al processo di caricamento del plaintext nei chip

DES Round

64-bit input 64-bit outputp

32-bit L 32-bit R

p

32-bit L 32-bit R32 bit Ln 32 bit Rn

ManglerFunction

Kn

32 bit Ln 32 bit Rn

ManglerFunction

Kn

32-bit Ln+1 32-bit Rn+1 32-bit Ln+1 32-bit Rn+1

64-bit output 64-bit input

EncryptionEncryption DecryptionDecryption

DES Round• Utilizza le due metà destra e sinistra da 32 bit

• Dettagli della funzione manglePrende 48 bit della chiave shiftata– Prende 48 bit della chiave shiftata

– Espande i 32 bit di destra in 48 bitXOR della chiave e dei 48 bit e la invia in input alla “S Box”– XOR della chiave e dei 48 bit e la invia in input alla “S-Box”

– La S-BOX è una tabella di sostituzione predefinitaL S BOX d 32 ‘ i’ bit h i i XOR– La S-BOX produce 32 ‘nuovi’ bit, che vengono messi in XOR con la metà sinistra

• Questo processo è reversibile!

DES Round: funzione Mangle DES Round: S-box

Example:S(18 09 12 3d 11 17 38 39) = 5fd25e03

Effetto valanga • Una propietà deisderabile per un algoritmo di cifratura è:

Un cambiamento di un solo bit nell’input o nella chiave– Un cambiamento di un solo bit nell’input o nella chiave comporta una modifica di almeno metà dei bit di uscita!!Tentare di indovinare la chiave diventa impossibile– Tentare di indovinare la chiave diventa impossibile

• DES presenta un forte effetto valanga• DES presenta un forte effetto valanga

Grandezza della chiave • Chiavi a 56-bit hanno 256 = 7.2 x 1016 valori• L’algoritmo non è mai stato violato ma attaccato con successo• L’algoritmo non è mai stato violato ma attaccato con successo

con attacco a forza bruta• Recentemente si è mostrato come l’algoritmo può essere violato• Recentemente si è mostrato come l algoritmo può essere violato

con un attacco a forza bruta– nel 1997 su Internet in pochi mesi p– nel 1998 con un HW dedicato($250K) in pochi giorni (Electronic

Frontier Foundation) • Necessità che il plaintext sia riconoscibile

3-DES, IDEA, AES

Triple DES: Perchè?• Il keyspace della DES è troppo piccolo• Necessità di un algortimo per sostituire il DES:• Necessità di un algortimo per sostituire il DES:

– Teoricamente puo’ essere violatoE’ stato portato con successo l’attacco con ricerca esaustiva delle– E stato portato con successo l attacco con ricerca esaustiva delle chiavi

• AES e’ un nuovo sistema di cifratura alternativoS• Prima dell’AES si cifrava piu’ volte con il DES • Tra le varie, quella piu’ efficace e’ la Triple-DESTra le varie, quella piu efficace e la Triple DES

DES cifratura multipla• Una possibile soluzione consiste nel cifrare ripetutamente un dato

uno stesso algoritmo di cifraturauno stesso algoritmo di cifratura• Sia l’algoritmo di Encryption che quello di Decryption possono

essere pensati come funzioni di cifraturaessere pensati come funzioni di cifratura• Quante volte deve essere ripetuto? (2,3,4, 1000..)• Quante chiavi devono essere utilizzate?Quante chiavi devono essere utilizzate?• Quale combinazione di E e D deve essere scelta? (EEE, ED, etc)

Quante volte ripetere la DES?• Quante più volte il blocco viene cifrato tanto più il sistema risulta

essere sicuroessere sicuro• Da un punto di vista computazionale sarebbe meglio avere un

numero di cifrature minimo indispensabilenumero di cifrature minimo indispensabile• Si cifra due volte con la stessa chiave

plaintext ---K---> ---K---> ciphertextp p– Non è molto più sicuro che nel caso con chiave singola K: una

ricerca esaustiva richiede di cercare tra 256 chiavi • Si cifra due volte con chiavi diverse

plaintext ---K1---> ---K2---> ciphertextC’è tt ( lt ti ) h tt di i l t– C’è un attacco (non molto pratico) che permette di violare questa variante del DES in circa due volte il tempo necessario a violare un singolo DES con un attacco a forza brutag

• Modifica: tripla cifratura con due chiavi (EDE)

Triplo DES (3-DES)

• Lunghezza blocco = 64 bit• Lunghezza blocco = 64 bit• Chiave (k, k´,k´´) lunga 56 + 56 + 56 = 168 bit• Lunghezza blocco = 64 bitLunghezza blocco 64 bit• Chiave (k, k´) lunga 56+56 = 112 bit

– K1 per E, K2 per D, K1 per E1 pe , 2 pe , 1 pe• Spesso chiamato EDE (acronimo per Encrypt Decrypt

Encrypt) or TDEA• Adottato negli standard X9.17 e ISO 8732

Triplo-DES con due chiavi• Usa 2 chiavi K1 e K2 con la sequenza E-D-E

C = E [D [E [P]]]– C = EK1[DK2[EK1[P]]]• Il keyspace è di 2112 possibili chiavi• Cifratura e decifratura possono essere usate in maniera• Cifratura e decifratura possono essere usate in maniera

equivalente per quanto riguarda la sicurezza: non c’è alcuna vantaggio ad usare una piuttosto che l’altra gg p

• Standardizzato in ANSI X9.17 & ISO8732• Compatibile con il DES ponendo K1=K2Compatibile con il DES ponendo K1 K2• Al momento non sono noti attacchi effettuati con successo

Altri cifrari

• IDEA (International Data Encryption Algorithm) [1990]• SAFER (Secure And Fast Encryption Routine)

SAFER K-64 [1994], SAFER K-128 [1995]• RC5 [1995]

cifrario bit chiave bit testoIDEA 128 64IDEA 128 64SAFER K-64 64 64SAFER K-128 128 64RC5 b 32 64 128

• Madryga, NewDES, FEAL, REDOC, LOKI, Khufu, Knafre,

RC5 <256 byte 32,64,128

Madryga, NewDES, FEAL, REDOC, LOKI, Khufu, Knafre, RC2, MMB, GOST, Blowfish, …

• AES• … AES

IDEA• International Data Encryption Algorithm

Usato in PGP (Pretty Good Privacy)– Usato in PGP (Pretty Good Privacy)• Simile a DES

Lavora su blocchi di input di 64 bit– Lavora su blocchi di input di 64 bit• Presi come 4 blocchi da 16 bit

– Usa una chiave a 128 bit– opera in rounds (17 rounds)– La funzione di mangle non deve essere reversibile (è utilizzata nello g (

stesso verso per la cifratura e la decifratura)– La decifratura usa lo stesso algoritmo ma con chiavi diverse

• Le chiavi di cifratura e decifratura sono collegate in maniera complessa

Blowfish• É un cifrario a blocchi simmetrico disegnato da Bruce Schneier

nel 1993/94nel 1993/94

• Caratteristiche• Caratteristiche– È di facile implementazione su CPU a 32 bit– Uso ottimale della memoriaUso ottimale della memoria– La struttura semplice semplifica l’analisi e l’implementazione– La sicurezza variabile varia con la lunghezza della chiave (usa chiavi g (

da 32 a 448 bit)

• É stato implementato in vari prodotti e fino a questo momento non è stato violato

AES• Disegnato per sostituire DES

O i t d l NIST (N ti l I tit t f St d d d– Organizzato dal NIST (National Institute of Standards and Technology) Scelto tra cinque algoritmi candidati– Scelto tra cinque algoritmi candidati

• Rivisitato dal governo US, l’industria e le università• Sono stati necessari quattro anni per mettere a punto• Sono stati necessari quattro anni per mettere a punto

l’algortimo• L’algoritmo vincente è stato scelto il 2 Ottobre 2000• L algoritmo vincente è stato scelto il 2 Ottobre 2000• Il cifrario a blocchi di Rijndael

Joan Daemon Vincent Rijmen (Belgium)– Joan Daemon, Vincent Rijmen (Belgium)• È divenuto uno standard NIST

AES• Dimensioni della chiave

– L’AES specifica tre dimensioni: 128 192 e 256 bit Questo vuolL AES specifica tre dimensioni: 128, 192 e 256 bit. Questo vuol dire che approssimativamente ci sono:

• 3.4 x 1038 possibili per chiavi a 128 bit;• 6.2 x 1057 possibili per chiavi a 192 bit;• 1.1 x 1077 possibili per chiavi a 256 bit.

Le chiavi DES sono lunghe 56 bit questo vuol dire che– Le chiavi DES sono lunghe 56 bit, questo vuol dire che approssimativamente ci sono 7.2 x 1016 possibili chiavi.

– Ci sono circa 1021 volte più chiavi a 128 bit per l’AES che per il DES con chiavi a 56 bit

• L’AES sostituirà il triplo DES e il DES?• L AES sostituirà il triplo DES e il DES?– L’AES è stato sviluppato per sostituire il DES, ma il NIST ha

anticipato che il triplo DES rimarrà un algoritmo approvato (per gli usi del governo U.S.)

Robustezza dell’AES• Nella fine degli anni novanta sono state realizzate delle macchine

capaci di recuperare una chiave DES dopo poche ore In altrecapaci di recuperare una chiave DES dopo poche ore. In altreparole, provando tutti i possibili valori per la chiave, l’hardwarepuòdeterminare quale chiave è stata usata per cifrare unmessaggio

• Se si può trovare una chiave DES in un secondo, sarebberonecessari 149 trilioni di anni per trovare una chiave AES a 128bit utilizzando un attacco a forza bruta con la stessa velocitàSi h l’ i i i di 20 bili i di i• Si suppone che l’universo sia meno antico di 20 bilioni di anni….

• Quanto resisterà l’AES?• DES è stato uno standard del governo U.S. per circa venti anni

i di i l tprima di essere violato

Cifratura di messaggi lunghi

Cifratura di messaggi lunghi• I cifrari a blocchi cifrano blocchi di dimensione fissa

es DES cifra blocchi di 64 bit con una chiave a 56 bit– es. DES cifra blocchi di 64 bit, con una chiave a 56 bit • Necessità di un metodo che consideri una quantità arbitrariadi

informazioni da cifrare (più lunghe di 64 bit)informazioni da cifrare (più lunghe di 64 bit)• Sono stati definiti quattro moalità per il DES nello standard ANSI

X3.106-1983• Questi schemi sono applicabili a DES, 3DES, IDEA, EAS, etc• Modalità:Modalità:

– Electronic Code Book (ECB)– Cipher Block Chaining (CBC)p g ( )– k-bit Cipher Feedback Mode (CFB)– k-bit Output Feedback Mode (OFB)

Electronic Codebook (ECB)• Consiste nel fare la cosa più ovvia e generalmente rappresenta il

metodo peggiore!!metodo peggiore!!• Il mesaggio è diviso in blocchi da 64 bit con padding finale• Ogni blocco è cifrato indipendentemente con la chiave segreta• Ogni blocco è cifrato indipendentemente con la chiave segreta

– Ci = DESK1 (Pi)l di i hiBlocco di testo in chiaro

Blocco di testo cifrato

Testo originaleTesto originale

k k k k

Testo cifratoTesto cifrato

Caratteristiche di ECB• Alla fine del messaggio gestisce un possibile blocco più piccolo

– Inserendo valori che non possono essere dati (es zeros)Inserendo valori che non possono essere dati (es.zeros)– O riempire l’ultimo blocco con un conteggio dei bit di padding da

inserire • eg. [ b1 b2 b3 0 0 0 0 5] data byte, quindi 5 byte= pad+count

• Ci sono una serie di problemi che devono essere gestiti che non compaiono se analizziamo i singoli blocchicompaiono se analizziamo i singoli blocchi– Ripetizioni nel messaggio cifrato possono essere facilemnte rivelate – Se il messaggio contiene 2 blocchi identici di 64 bit iSe il messaggio contiene 2 blocchi identici di 64 bit, i

corrispondenti blocchi cifrati sonoidentici; • in alcuni casi può essere possibile indovinare una porzione del

messaggio• in alcuni casi è possibile alterare il messaggio

ECB è raramente usato tranne quando si inviano piccoli blocchi di– ECB è raramente usato tranne quando si inviano piccoli blocchi di dati

Cipher Block Chaining (CBC)• CBC evita dei problemi dell’ECB• Se lo stesso blocco si ripete nel testo in chiaro non si avranno• Se lo stesso blocco si ripete nel testo in chiaro, non si avranno

ripetizioni nel testo cifrato• Si aggiunge un meccanismo di feedback al cifrario• Si aggiunge un meccanismo di feedback al cifrario• Il testo in chiaro è più difficile da manipolare

Testo originaleTesto originale

rr11⊕

rr22⊕

rr33⊕

rrii⊕

k

⊕

k

⊕

k

⊕

k

⊕

. . .. . .

Testo cifratoTesto cifrato

Cipher Block Chaining (CBC)• Il testo in chiaro viene trattato effettuando un XOR del blocco

corrente M con il blocco precedente Ccorrente M con il blocco precedente C• Necessita di un IV (Initialization vector) di dati casuali per cifrare

il primo bloccoBlocco di testo in chiaroBlocco di testo cifrato

il primo blocco– C0 = IV – Ci = Ek(Mi xor Ci-1)

Testo originaleTesto originale

i k( i i )

V l

XOR XOR XOR

k k kValoreIniziale

Testo cifratoTesto cifrato

Caratteristiche di CBC• La decifratura è semplice perchè la funzione di XOR è reversibile

• CBC ha le stesse prestazioni di ECB, tranne per il costo di generare e trasmettere il IV

• In questo modo ogni blocco del testo cifrato dipende da tutti I blocchi del messaggio – In questo modo un cambio nel testo influenza tutti i blocchi

cifrati dopo un cambio nel blocco originalecifrati dopo un cambio nel blocco originale

Caratteristiche di CBC• Può essere utilizzato come IV uno 0, comunque può portare

alcuni problemialcuni problemi– es. Se un messaggio viene trasmesso ogni settimana è

possibile capire se sono stati effettuati dei cambiamentipossibile capire se sono stati effettuati dei cambiamenti– Inoltre scegliere IV!=0 rende il sistema più robusto

• Se IV è trasmesso in chiaro un attaccante può cambiare i bit del primo blocco e cambiare IV di conseguenza per compensare p g p p– Quindi o il valore IV deve essere un valore fissato o deve

deve essere inviato in modo cifrato in modalità ECB prima del t d l iresto del messaggio

CBC –Modifica di blocchi cifrati• Usando CBC non elimina il problema che qualcuno possa

modificare il messaggio in transitomodificare il messaggio in transito

• Se un attaccante cambia i blocchi del testo cifrato c c questi• Se un attaccante cambia i blocchi del testo cifrato cn, cn questi vengo messi in XOR con i cn+1 cifrati per ottenere mn+1

– Cambiando il bit h di c ha un effetto predicibile sul bit h diCambiando il bit h di cn ha un effetto predicibile sul bit h dimn+1

– L’attaccante può conoscere il nuovo mnp n

• Si può risolvere aggiungendo un CRC al testo in chiaro prima p gg g pdella cifratura

CBC –riordino di blocchi cifrati• Conoscendo il plaintext, i corrispondenti ciphertext e IV, è

possibile ridisporre c1 c2 c3 in modo da ottenere un nuovo m1possibile ridisporre c1, c2, c3, ..in modo da ottenere un nuovo m1, m2, m3 ..

• Un CRC può aiutare ma non risolvere il problema (1 su 232

possibilità che il CRC funzioni; se l’attacco consiste solo nel p ;modificare il messaggio è possibile provare diverse combinazioni)

Output Feedback (OFB)Si t t di i d li• Si comporta come un generatore di numeri pseudo casuali

Il i è if ff d XOR il fl• Il messaggio è cifrato effettuando un XOR con il flusso pseudorandom generato dall’OFB

Il i è t tt t fl di bit– Il messaggio è trattato come un flusso di bit

Output Feedback (OFB)• Come funziona:

– È generato un numero pseudorandom O0 (chiamato IV comeÈ generato un numero pseudorandom O0 (chiamato IV come per CBC)

– O0 viene cifrato (usando la chiave segreta K) per ottenere O10 ( g ) p 1

– Da O1 è ottenuto O2 e così via per tutti i blocchi che sono necessari

Oi = DESK1(Oi-1)O-1 = IV1

– Il feedback è indipendente dal messaggio e può essere calcolato in anticipo

Carateristiche di OFB• Vantaggi dell’OFB:

Se alcuni bit del ciphertext vengono alterati solo questi bit di testo– Se alcuni bit del ciphertext vengono alterati, solo questi bit di testo in chiaro sono alterati (non si ha propagazione di errori)

– Se un messaggio arriva in blocchi di dimensioni arbitrarie, il gg ,messaggio cifrato corrispondente può essere trasmesso immediatamente

• Svantaggi dell’OFB:– Il mittente e il destinatario devono essere sincronizzati

S il l i il i h i i i– Se il plaintext e il ciphertext sono noti a una persona con cattivi intenti, questa può modificare il plaintext in qualsiasi cosa desideri senza che un eventuale ECC (Error Correcting Code) lo riveli( g )

– Non si deve più usare la stessa sequenza (chiave+IV)

Cipher Feedback (CFB)• Molto simile all’OFB• I k bit shiftati nel modulo di cifratura sono i k bit che provengono• I k bit shiftati nel modulo di cifratura sono i k bit che provengono

dal blocco precedente– Ci = Pi XOR DESK1(Ci-1)

Blocco di testo in chiaroBlocco di testo cifrato

Ci Pi XOR DESK1(Ci 1)– C-1 = IV

Testo originaleTesto originale

k k k

ValoreIniziale XOR XOR XOR

Testo cifratoTesto cifrato

• Nel Cipher Feedback (CFB), come per il CBC i blocchi vengono “incatenati” fra loro ma questa volta dopo il normaleincatenati fra loro ma questa volta dopo il normale encriptamento

• In seguito viene fatta la criptazione del blocco cifrato precedenteIn seguito viene fatta la criptazione del blocco cifrato precedente • Infine si esegue l'operazione di XOR con il testo chiaro,

suddiviso in segmenti più piccolig p p• L'idea è quella di elaborare i dati non appena divengono

disponibili invece di aspettare che un blocco sia del tutto completato

• L’approccio è di tipo a flusso

Integrità e MIC• CBC, CFB e OFB, se opportunamente utilizzati, offrono una

buona protezione contro eventuali attaccanti che voglionobuona protezione contro eventuali attaccanti che vogliono decifrare il messaggio

• Nessuno di questi metodi offre una buona protezione controNessuno di questi metodi offre una buona protezione contro attaccanti che possono modificare il messaggio senza essere scoperti

• In molti contesti i messaggi non sono segreti ma l’integrità deve essere assicurata

• Un sistema a chiave segreta può essere utilizzato per generare un checksum cifrato noto come MIC (Message Integrity Code)

Testo originaleTesto originale

XOR XOR XOR

k k k

CBC residue

Privacy e Integrità• Per assicurare la privacy è possibile CBC cifrare il messaggio• Per assicurare l’integrità è opportuno trasmettere dati non cifrati• Per assicurare l’integrità è opportuno trasmettere dati non cifrati

più un residuo CBC• Per assicurare sia la privacy che l’integrità i punti precedenti non• Per assicurare sia la privacy che l integrità, i punti precedenti non

sono sufficienti• Una possibile soluzione è quella di inviare il messaggio cifratoUna possibile soluzione è quella di inviare il messaggio cifrato

CBC con un residuo CBC calcolato con due chiavi diverse– Compleessità doppia!p pp