Cifratura

Scenario

Crittografia: Servizi richiesti• SEGRETEZZA: evitare che i dati inviati da un soggetto A a un

soggetto B vengano intercettati da un terzo soggetto C.

• AUTENTICAZIONE: verificare l’identità di chi manda o riceve i dati (evitare che un intruso si spacci per chi non è).

• INTEGRITA’: essere sicuri che i dati ricevuti siano uguali a quelli inviati (evitare cioè che un intruso o un evento accidentale alteri i dati durante la trasmissione).

• NON RIPUDIO: evitare che chi manda dei dati possa in futuro negare di averli mandati (firma digitale).

Componenti della crittografia

Terminologia

• Testo in chiaro: messaggio originale • Testo cifrato: messaggio codificato • Algoritmo di cifratura: algoritmo usato per convertire il testo in

chiaro in testo cifrato • Chiave: informazione usata dall’ algoritmo di cifratura nota solo

al trasmettitore e al ricevitore • Cifrare: convertire testo in chiaro in testo cifrato• Decifrare: ricavare il testo in chiaro dal testo cifrato

Cifratura Decifratura

Testoin chiaro

Testocifrato

Testooriginale

Principio di Kerckhoffs

La sicurezza di un crittosistema, o cifrario,deve dipendere solo dalla segretezza della chiave

e non dalla segretezza dell’algoritmo usato

Jean Guillaume Hubert Victor Francois Alexandre Auguste Kerckhoffs von Nieuwenhof(1835-1903), filologo olandese, “La Criptographie Militaire” [1883

Crittografia simmetrica

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

cifrario sarà sicuro

Esempio:

Ciphertext= ankyodkyurepfjbyojdsplreyiunofdoiuerfpluytdKey= pxlmvmsydofyrvzwc tnlebnecvgdupahfzzlmnyihPlaintext= Mr mustard with the candlestick in the hall

Ciphertext= ankyodkyurepfjbyojdsplreyiunofdoiuerfpluytdKey= mfugmiydgaxgoufhklllmhsqdqogtewbqfgyovuhwtPlaintext= Miss scarlet with the knife in the library

One-Time Pad• Vantaggi:

– Non è violabile dato che il ciphertext non ha relazioni statistichecon il plaintext

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

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

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 utilizzate

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

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

numero di righe

• Il messaggio cifrato viene letto riga per riga

• 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 po s t p o n ed u n t i l tw 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 linguaggio

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

molto più robusto

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

Cifrari a blocchi e a flusso

Cifrari a blocco e a flussoCifrari a blocco

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

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

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

più)Cifrari a stream

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

• Molti cifrari utilizzati sono a blocchi

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

cifrato

• 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 tavoladi decifratura a partire da una coppia <plaintext,ciphertext>

– Se il blocco è troppo lungo si hanno degli svantaggi legatiall’aumento di complessità

– Spesso si scelgono blocchi da 64 bit

Esempio di cifrario a blocco

Testo originaleTesto originale

Testo cifratoTesto cifrato

k k k k

Blocco di testo in chiaroBlocco di testo cifrato

Cifrari a blocco• Le principali trasformazioni usate sono:

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

lunghezza k-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 bit– permutazione

• Specifica per ognuno dei k bit di input la corrispondenteposizione dell’input

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

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

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

– 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 un

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

S1 S2 S3 S4

Permutation

Substitutions

Lo

op

wit

hn

ro

un

ds

Cifrari a sostituzione e permutazione

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

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

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

• 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 originale

• Il one-time pad fa esattamente questo

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

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

• Rende la relazione tra ciphertext e chiave il più complessopossibile

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

concetto di cifrari a prodotto invertibile

• 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 diarrotondamendo sulla parte destra dei dati e una successivaoperazione di XOR con la parte sinistra dei dati. Si ha quindi unapermutazione che inverte parte destra e sinistra

– L’arrotondamento è effettuato a partire da una chiave che cambia ad ogni round

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

Cifrario di Feistel

⊕

⊕

⊕

Principi di progettazione• Dimensione del blocco

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

• 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 rallenta

l’algoritmo

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

l’algoritmo

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

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

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

• Cifra blocchi di 64-bit usando chiavi lunghe 56-bit• Ha un ampio impiego

Data Encryption Standard (DES)• Il DES consiste di

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

il round precedente– Una permutazione finale

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

– Non era questa l’intenzione!

DES• Consiste in

– Una permutazione iniziale(P)

– Una trasformazione dellachiave

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

sono spostati nei 32 bit più a sinistra dell’output

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

• La chiave è shiftata ad ogniround

– Una permutazione finale (P-1)

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

– Un cambiamento di un solo bit nell’input o nella chiavecomporta una modifica di almeno metà dei bit di uscita!!

– Tentare di indovinare la chiave diventa impossibile

• DES presenta un forte effetto valanga3-DES, AES

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

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

chiavi• AES e’ un nuovo sistema di cifratura alternativo• Prima dell’AES si cifrava piu’ volte con il DES • Tra 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 cifratura• Sia l’algoritmo di Encryption che quello di Decryption possono

essere pensati come funzioni di cifratura• Quante volte deve essere ripetuto? (2,3,4, 1000..)• 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 sicuro• Da un punto di vista computazionale sarebbe meglio avere un

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

plaintext ---K---> ---K---> ciphertext– 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---> ciphertext– 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 bruta

• Modifica: tripla cifratura con due chiavi (EDE)

Triplo DES (3-DES)

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

– K1 per E, K2 per D, K1 per E• Spesso chiamato EDE (acronimo per Encrypt Decrypt

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

AES• Disegnato per sostituire DES

– Organizzato dal NIST (National Institute of Standards and Technology)

– Scelto tra cinque algoritmi candidati• Rivisitato dal governo US, l’industria e le università• Sono stati necessari quattro anni per mettere a punto

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

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

AES• Dimensioni della chiave

– L’AES specifica tre dimensioni: 128, 192 e 256 bit. Questo vuoldire 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 cheapprossimativamente ci sono 7.2 x 1016 possibili chiavi.

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

• 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 gliusi del governo U.S.)

Crittografia asimmetrica/a chiave pubblica

Crittografia a chiave pubblica• A volte indicata con crittografia asimmetrica (or two-key

cryptography)• Probabilmente è il passo in avanti più grande nei 3000 anni di storia

della cifratura• L’invenzione pubblica risale a Whitfield Diffie & Martin Hellman

in 1975– È il primo algoritmo noto– Era noto ancora prima nelle comunità… (e.g. National Security

Agency)• Applica in modo intelligente alcuni principi di teoria dei numeri alle

funzioni crittografiche• Complementa piuttosto che sostituire la crittografia simmetrica

Crittografia a chiave pubblica• Con la crittografia simmetrica/chiave segreta

– Si ha bisogno di un metodo sicuro per comunicare all’altro utente la chiave

– Si ha bisogno di una chiave separata per ogni persona con cui sidesidera comunicare

• Al contrario, con la crittografia pubblica, le chiavi non sonocondivise

• Usa due chiavi:– Una chiave pubblica, che può essere conosciuta da chiunque ed

essere usata per cifrare il messaggio e verificare le firme– Una chiave privata, nota solo al ricevente e usata per decifrare il

messaggio, e firmare/creare la firma• É asimmetrica perchè

– Coloro che cifrano i messaggi o verificano le firme non possonodecifrare i messaggi o creare le firme

Possibili scenari

Impiego della chiave pubblica del destinatario per cifrare un messaggio che solo il destinatario potrà decifrare con la propria chiave segreta: RISERVATEZZA

Impiego della propria chiave privata per autenticare e cifrare un messaggio che verràdecifrato dal destinatario con la nostra chiave pubblica: AUTENTICITÀ

Impiego della chiave pubblica del destinatario per cifrare un messaggio che solo lui potrà decifrare con la propria chiave segreta, ma aggiungendo un certificato che autentica la nostra identità: RISERVATEZZA, AUTENTICITÀ, INTEGRITÀ

Crittografia a chiave pubblica: primo caso Schema generaleSupponendo che A voglia spedire un messaggio in maniera sicura M a B. Allora:

1. A ottiene la chiave pubblica di B, PB;2. A calcola il testo cifrato C = PB (M) corrispondente al messaggio

M e lo spedisce a B; 3. B riceve il testo cifrato C e adopera la sua chiave privata SB per

ottenere il messaggio M, SB (C) = SB (PB (M)) = M.

Nel caso in cui un nemico intercetti una trasmissione da A, certamente non può essere decifrata perché SB è privata, per questo motivo la sicurezza è garantita anche se come per gli schemi a chiave privatal’attacco di ricerca esaustiva a forza bruta è sempre possibile in linea teorica

Confronto con il crittosistema a chiave privata

• Nell'ambito della crittografia a chiave segreta si ha che: – La chiave di cifratura è essenzialmente uguale a quella di

decifratura, e comunque ciascuna può essere facilmente calcolatadall'altra.

– La chiavi risultano note ad entrambi i partner. – La chiave è tenuta segreta da entrambi i partner.

• Con la crittografia a chiave pubblica questi concetti subiscono una radicale modifica:– La chiave di cifratura è completamente diversa dalla chiave di

decifrazione. – La chiave di cifratura è nota a tutti, e dunque è resa pubblica dal

destinatario. – La chiave di decifrazione è mantenuta segreta dal destinatario ed è

nota soltanto a lui. – Le funzioni di cifratura e decifrazione sono note a tutti.

Confronto con il crittosistema a chiave privata

• La crittografia a chiave pubblica non può fare quello che fa la crittografia a chiave segreta, ma...

• Gli algoritmi crittografici a chiave pubblica noti sono di ordini digrandezza più lenti rispetto ai più noti algoritmi crittografici a chiave segreta– Sono di solito usati solo quando la crittografia a chiave segreta non

è appropriata

• Spesso è unita a tecnologia a chiave segreta– e.g. la crittografia a chiave pubblica potrebbe essere usata all’inizio

di una comunicazione per l’autenticazione e per stabilire una chiavesegreta temporanea e condivisa usata per cifrare la comunicazione

Applicazioni• Può essere usata per:

– Distribuzione di chiavi – sicurezza delle comunicazioni (coinvolgeuna o più chiavi private delle due parti)

– Firme digitali – verificare se un messaggio è pervenuto intattodalla sorgente (autenticazione: la sorgente firma un messaggio con la propria chiave privata tramite un algoritmo che viene applicato al messaggio o a una piccola parte del messaggio)

– Cifrare/decifrare – segretezza delle comunicazioni(confidenzialità: la sorgente cifra il messaggio con la chiavepubblica del ricevente)

• Alcuni algoritmi sono utilizzabili da chiunque altri no

Autenticazione: secondo caso

RSA

RSA

• Ideato nel 1977 da Rivest, Shamir & Adleman del MIT• È l’algoritmo a chiave pubblica più conosciuto e usato• RSA garantisce l’impossibilità di ricavare la chiave privata da

quella pubblica• RSA sfrutta le proprietà dei numeri primi e la considerazione

(consolidata da secoli di studi) che è molto difficile fattorizzare(cioè trovare i divisori) numeri molto grandi

• Le chiavi sono lunghe 512, 1024, 2048 bit per offrire buonasicurezza

• RSA è molto più lento degli algoritmi a chiave segreta (DES, IDEA) ma in genere è applicato a piccole quantità di dati, ad esempio per la trasmissione delle chiave di una sessione DES

Algoritmo RSARSA è basato sul problema complesso della fattorizzazione in numeri primi. Il suo funzionamento base è il seguente:

1. si scelgono a caso due numeri primi, p e q, l'uno indipendentemente dall'altro, abbastanza grandi da garantire la sicurezza dell'algoritmo

2. si calcola il loro prodotto n = p · q, chiamato modulo, dove φ(N)=(p-1)(q-1)

3. si sceglie poi un numero e (chiamato esponente pubblico), più piccolo e coprimo con (p-1)(q-1) dove 1<e< N, gcd(e, φ(N))=1

4. si calcola il numero d (chiamato esponente privato) tale che e·d mod (p-1)(q-1) =1

Algoritmo RSA4. La chiave pubblica è (n,e), mentre la chiave privata è (n,d). I fattori p

e q possono essere distrutti, anche se spesso vengono mantenuti all'interno della chiave privata.

5. La forza dell'algoritmo è che per calcolare d ed e (così come il contrario) non basta la conoscenza di n , ma serve il numero (p-1)(q-1) visto che fattorizzare (cioè scomporre un numero nei suoi divisori) è un'operazione molto lenta, soprattutto se n è un numero grande, poiché non si conoscono algoritmi efficienti.

6. Un messaggio m viene cifrato attraverso l'operazione me , mentre il messaggio viene decifrato con cd = med = m1 mod n . Il procedimento funziona solo se la chiave e utilizzata per cifrare e la chiave d utilizzata per decifrare sono legate tra loro dalla relazione e·d mod (p-1)(q-1) = 1, e quindi quando un messaggio viene cifrato con una delle due chiavi può essere decifrato solo utilizzando l'altra. Tuttavia proprio qui si vede la debolezza dell'algoritmo: si basa sull'assunzione mai dimostrata (nota come assunzione RSA) che il problema di calcolare con n numero composto di cui non si conoscono i fattori sia computazionalmente non trattabile.

mode c n

Schema generale RSA

EncryptionPlaintext: M<nCiphertext: C = Memodn

DecryptionCiphertext: CPlaintext: M = Cdmodn

Key GenerationSelect p, q p and q both primeCalculate n = p x qCalculate φ(n) = (p-1)(q-1)Select integer e gcd(φ(n),e)=1; 1<e< φ(n)Calculate d de modφ(n) = 1Public key KU = [e, n]Private key KR = [d, n]

RSA

M Blocco di testo in chiaroC Blocco di testo cifrato

Chiave cifraturaKe

Kd Chiave decifratura

M

M

C

C

Kc

Kd

C=E(Ke,M)C=E(C=E(KeKe,M),M)

M=D(Kd,C)M=D(Kd,C)M=D(Kd,C)

Esempio RSA• Si scelgono : p=17 & q=11• Calcola n = pq =17×11=187• Calcola φ(n)=(p–1)(q-1)=16×10=160• Trova e tale che gcd(e,160)=1; scegli e=7• Trova d tale che de=1 mod 160 e d < 160 Il valore è

d=23 visto che 23×7=161= 10×160+1• Pubblica la chiave pubblica KU={7,187}• Mantieni segreta la chiave privata

KR={23,187}={23,17,11}

Sicurezza in RSA• La sicurezza di RSA risiede nel fatto che è difficile fattorizzare

un numero molto grande. I metodi di fattorizzazione piùconosciuti sono altresì molto lenti.

• Fattorizzare un numero di 512 bit con le tecniche più conosciuterichiederebbe circa mezzo milione di MIPS-years (million instructions per second) ossia 1,000,000 • (365 days/year) •(86400 seconds/day), ossia 31.5 trilioni di istruzioni.

• Alcuni autori suggeriscono che la tecnica migliore è aspettare 300 anni e poi usare la tecnica più conosciuta

• Se dunque A e B impiegano pochi secondi a cifrare e decifrare, chiunque intercetti le loro comunicazioni impiegherebbe milioni di anni per scoprire i due fattori primi con cui si può decifrare il messaggio.

RSA Security• Tre approcci per attaccare RSA:

– Attacco a forza bruta: si provano tutte le posbili chiavi private

– Attacchi matematici: ci sono diversi approcci che in generaletentano di fattorizzare il prodotto di due primi.

– Attacchi basati sul tempo: dipendono dalla quantità di tempo necessaria per l’algoritmo di decifratura

Algoritmi ibridi…• Le chiavi pubbliche sono ottime per le comunicazioni ma

l’esponenziale è lento!!!

• DES e altri algoritmi a chiave segreta sono generalmentecomposti da moltiplicazioni, addizioni, traslazioni e operazionisimili. Spesso implementate a livello hardware

• Le chiavi simmetriche sono difficili da gestire

• Spesso, una chiave di una sessione simmetrica è generata da un partecipante e cifrata con la chiave pubblica dell’altro