"PROTEZIONE DELL'INFORMAZIONE :

DALLA CIFRATURA DI CESARE ALLA CRITTOGRAFIA

MODERNA"

CrittografiaLa protezione di informazioni riservate, quali i messaggi di interesse militarediplomatico o industriale, può essere realizzata codificando con opportuna chiave (cifratura, crittografia). L'uso della crittografia, antico di due millenni, ha avuto una notevole evoluzione nel Cinque e Seicento con le tecniche polialfabetiche e nel Novecento con l'uso di macchine cifranti (Enigma…) e di calcolatrici per la decrittazione (Colossus). La crittografia per usi civili e militari assume oggi importanza ancor maggiore con l’espansione delle retI problemi fondamentali della crittografia e dalla distribuzione sicura delle chiavi ha trovato largo spazio nei programmi di ricerca delle grandi aziende di Information Technology e degli organismi governativi dei paesi più industrializzati.Rif.: Prof. G. GALATI, Seminario presso l’Università Tor Vergata, Roma. G Brassard Introduzione alla criptologia moderna, Masson, 1990.A. Tanenbaum :reti di computer, UTET, 1997.C. Kaufman,R Perlman, R.Speciner: Network Security, Prentice Hall1, 1995.

PROTEZIONE DELL’INFORMAZIONE (definizioni)

Crittografia: arte di fornire comunicazione sicuraCifratura: sostituzione, permutazione manuale edautomatica dei simboliLo scopo di un criptosistema è di cifrare un testo intellegibile(in chiaro) producendo un testo cifrato(criptogramma)

1- criptosistemi a chiave segreta (simmetrici)2- criptosistemi a chiave pubblica (asimmetrici)

Decifrare: operazione messa in atto dal destinatario per riottenere il testo in chiaroProblemi:

1- gli algoritmi2- la distribuzione sicura delle chiavi, 3- l’autenticazione del mittente, del destinatario

e del messaggio.

PROTEZIONE DELL’INFORMAZIONE (definizioni)

Crittoanalisi: arte di penetrare i canali di comunicazione ritenuti sicuri

Attacco: azione di un crittoanalista mirata a violare (rompere, sfondare) il crittosistema

Crittoanalisti più diffusi: Scopo:studente curiosare nella posta altruihacker violare e danneggiareuomo d’affari strategie di mercatoprogettista progetti altruiex dipendente danneggiarebancario furtoagente di cambio negare azioni fallimentaritruffatore numeri di carte di creditoterrorista rubare segreti strategicispia rubare segreti militari e civili, spionaggio/controspionaggio intercettare messaggi e

inviare messaggi falsi

PROTEZIONE DELL’INFORMAZIONE (definizioni)

Intrusopassivo Intruso

attivo

Il modello crittografico

messaggio in chiaro m

Metodo di cifratura Metodo di decifratura

Chiave di cifratura

Chiave di decifratura Testo cifrato

C = Ek(m)

messaggioin chiaro m

Storia della crittografia

Cifratura a sostituzione:monoalfabetica (Giulio Cesare),polialfaberica (Vigenère).

Cifratura a trasposizione.Macchina Enigma/Ultra.Metodo Lorentz/Colossus.Cifratura moderna:

cifratura a chiave segreta(o a chiave privata),cifratura a chiave pubblica( a doppia chiave una pubblica e una privata).

Storia della crittografia

La cifratura monoalfabetica (Giulio Cesare) con K variabile(invece di 3 fisso a rotazione) potrebbe sembrare inviolabile, su 26 lettere dell’alfabeto ci sono 26!= ≈ 4×10 26 chiavi (combinazioni) da provare. Un computer che generi una soluzione ogni µsec potrebbe impiegare fino a 10 13 anni per provare tutte le chiavi.

Invece un buon crittografo sa che per ogni linguaggio esistono lettere più usate di altre, bigrammi e trigrammi comuni (Ital.: are, ere, ire, ini, oni…Engl.: the, ing, and, ion……ed allora è facile violarla.Successivamente fu usata la tavola di Vigenere

Cifrari a trasposizioneLa chiave è una parola che non contiene ripetizioniad es.: MEGABUCKM E G A B U C K7 4 5 1 2 8 3 6P L E A S E T R A N S F E R O N E M I L L I O N D O L L A R S TO M Y S W I S SB A N K A C C OU N T S I X T WO T W O A B C D

IN CHIARO:PLEASETRANSFERON EMILLIONDOLLARSTOMYSWISSBANKACCOUNTSIXTWOTWOCIFRATO:AFLLSKSOSELWAIATOOSSCTCLNMOMANTESILYNTWRNNTSOWDPAEDOBUOERIRICXB

STORIA, WW2

Oltre ad Ultra (bombe di Turing), usata per tradurre i messaggi Enigma, i britannici inventarono un altro dispositivo di decrittazione,il Colossus, progettato per debellare un sistema crittografico ancora più resistente: la cifratura Lorenz.La cifratura di Lorenz era usata per crittare le comunicazioni traHitler e i suoi capi di stato maggiore.La codifica era effettuata dalla macchina Lorenz SZ40, simile aEnigma nei princìpi di funzionamento ma molto più complicata;infatti, essa si dimostro ben presto un osso duro. Partendo dal concetto di macchina universale elaborato da Alan Turing,Newman progettò una calcolatrice capace di adattarsi aproblemi differenti - quello che oggi chiamiamo computer.Flowers, un ingegnere coinvolto nella valutazione del progetto,decise di proseguire lungo la via indicata da Newman.

STORIA, WW2Lavorando al centro di ricerche dell'Ufficio delle Poste, a Dollis Hill, Flowers spese dieci mesi per trasformare lo schema del matematico nella macchina Colossus, che portò a Bletchley Park l'8 dicembre 1943.L'apparecchio conteneva 1.500 valvole elettroniche, molto più veloci degliimprecisi interruttori elettromeccanici delle bombe.Tuttavia la caratteristica più interessante di Colossus non consisteva nellavelocità, ma nella programmabilità.Era questa a farne un precursore dei moderni elaboratori digitali.Come tutto ciò che si trovava a Bletchley Park, Colossus fu distrutto dopola guerra, e a coloro che l'avevano usato fu proibito parlarne.Così, lo schema di funzionamento del primo calcolatore andòdefinitivamente perduto.Nel 1945 J. Presper Eckert e John W. Mauchly dell'Università dellaPennsylvania realizzarono ENIAC (Electronic Numerical Integrator AndCalculator: un'apparecchiatura contenente 18.000 valvole elettroniche. Per decenni, non Colossus ma ENIAC fu considerato il capostipite dei moderni elaboratori.

CIFRATURA DI MESSAGGI NUMERICILa conversione può essere eseguita in base a vari codici, tra i quali unodei più diffusi e 1'American Standard Code for Information Interchange[Codice americano standard per lo scambio di informazioni], o, informa di acronimo, ASCII.I1 codice ASCII assegna un particolare numero binario a ognilettera dell'alfabeto.Ci sono 128 (2 7 ) modi di disporre 7 cifre binarie, perciò il codice ASCIIpuò esprimere fino a 128 caratteri distinti.Vi è quindi posto per le lettere minuscole (per esempio, a = 1100001),per i segni di interpunzione (per esempio, ! = 0100001) e peraltri simboli di uso comune (per esempio, & = 0100110).Una volta convertito il messaggio in numeri binari, la cifratura puòcominciare.Supponiamo di voler cifrare il messaggio SALVEtrasformiamolo con ASCII: 1010011 1000001 1001100 1010110 1000101

CIFRATURA DI MESSAGGI NUMERICILa cifratura per sostituzione la facciamo con la chiave DAVIDtrasformata con ASCII e poi ne facciamo lo XOR con SALVE:

messaggio: SALVEASCII. 10100111000001100110010101101000101chiave DAVID: 10001001000001101011010010011000100testo cifrato: 00101110000000001101000111110000001

per decrittarlo basta rifare XOR del testo cifrato con DAVID in ASCII.

L’operazione di XOR è alla base del metodo Lucifer che fu all’origine del DES (Data Encryption Standard) metodo IBMadottato dagli USA nel 1976.

CIFRATURA DI DESDES critta i messaggi tramite le seguenti operazioni:

Il testo è convertito in una stringa di bit .La stringa è divisa in blocchi di 64 bit da cifrare separatamente.Ogni blocco è sottoposto a 16 passi:in ogni passo:il blocco è diviso in due sottoblocchi di 32 bit chiamati L0 e R0, poi R0 è introdotto in una funzione deformante F(R0, K1) e poi sommato (xor) a L0. La somma diviene R1 mentre l’originario R0 diventa L1.

La chiave per cifrare è di 56 bit e serve per la funzione F.Ad ogni passo la chiave cambia: viene divisa in due blocchi da 28 ognuno ruotata a sinistra di un numero di bit uguale al numero di iterazionK1deriva da questa chiave ruotata estraendo un sottoinsieme di 48 bit.L’algoritmo è perfettamente reversibile.

Crittografia: DESTesto in chiaro su 64 bit

L i-1 R i-1Trasposizione iniziale

Chi

ave

di 5

6 bi

t

Interazione 1

Interazione 2

Scambio a 32 bit

Trasposizione inversa

L i-1 f(R i-1, Ki)Interazione 16

R i 32 bitL i 32 bit Testo cifrato su 64 bit

(b)(a)

DECIFRATURA DI DESDES può essere violato? SI! dalla “Lotteria Cinese”.Le possibili chiavi di DES sono 7× 1016, se 1.200.000.000 cinesi avessero ciascuno un pc di vecchia tecnologia con un processore DES potrebbero, ricevendo dalla rete un messaggio cifrato ed uno spazio di chiavi da generareconvertire in chiaro il messaggio in meno di un minuto…….. raddoppiando la chiave DES a 116 bit ci metterebbero invece 100.000.000 an

Però utilizzando in rete (semplicemente noleggiandoli) i computer di casa moderni si potrebbe con 140.000 pc violare DES in un mese.

Sono stati inoltre progettati (e forse costruiti) processori anti-DES con previsiodi spesa inferiori a 1.000.000$. Da qui l’idea di destinare il DES di 56 bit ad operazioni di minor valore cercaremetodi più sicuri.

DOPPIO DESIl metodo progettato in IBM è uno standard e usa due chiavi K1 e K2 di 56 bit ed una TRIPLA codifica:

E D D E DE

P

C C

P

K1 K2 K1K1 K2 K1

(a) (b)

Si critta P con K1 poi si decritta come se fosse stato crittato con K2 poi si critta nuovamente con K1 (a). L’algoritmo è reversibile (b).Non si conosce (ufficialmente ) un metodo per attaccare DES in modalità EDEanche se c’è chi suggerisce il DES a tre chiavi in modalità EEE.

IDEAIl metodo progettato in Svizzera (ETH) con chiave a 128 bit si basa su concetti simili al DES , in quanto i blocchi di 64 bit del messaggio vengono “macinati” in 8 iterazioni usando le operazioni di xor e di somma e moltiplicazione modulo 216(cioè si prende sempre la parte del risultato contenuta nei 16 bit meno significativi).I 64 bit del messaggio vengono divisi un 4 gruppi di 16 e mescolati con 6chiavi di 16 estratte dalla chiave di 128 bit.Dalla chiave di 128 vengono estratte 56 sottochiavi di 16 da usare a gruppi di 6 in ognuna delle 8 iterazioni , mentre 4 vengono usate per la trasformazione finale. La decifratura utilizza lo stesso algoritmo della cifratura con sottochiavi diverse.La chiave a 128 bit lo rende immune (per qualche decennio) ad attacchi “brutali” del tipo della Lotteria cinese. Attualmente non si conoscono tecniche in grado di forzare IDEA.

Crittografia:IDEATesto in chiaro su 64 bit

4 blocchi di input a 16 bitTrasposizione iniziale

+

+

++

×

×

×

##

####

× k4k2 k3

k6

k1Interazione 1

Interazione 2

Interazione 8

Trasformazione

Interazione 7

Testo cifrato su 64 bit

k5

4 blocchi di output a 16 bit

× Moltiplicazione a 16 bit modulo 2 16

+ Addizione a 16 bit modulo 2 16

(b)#(a) OR esclusivo a 16 bit

Problemi di distribuzione delle chiaviApproccio:

corrieri fidatisuddivisione della chiave in segmenti

Gravi problemi logistici: al crescere degli utenti (es. clienti banche)alla modifica della chiave (mezzi militari in missione)

Insicurezza delle reti:riservatezzaintegrità del messaggioautenticazione dell’origine misure anti ripudio

Crittografia a chiave publicaNel 1976 Diffie ed Hellman (Stanford) proposero di

studiare sistemi crittografici a due chiavi: una pubblicaE ed una privata D tali per cui l’algoritmo di cifraturaAE debba usare E per cifrare mentre l’algoritmo per decifrare AD non possa usare E ma debba usare la chiave D:deve valere per un messaggio P la relazione:AD(AE(P)) = P, inoltreAE non deve essere invertibile e sia estremamente difficile ricavare D da E.

Bob pubblica (sul suo sito o altro) il suo E ed AE.Se Alice vuole inviare messaggi a Bob può crittarli con E e AE ed è

sicura che solo Bob può decrittarli con AD . Quindi Bob “pubblica “ la sua chiave E mentre tiene segreta la chiave D ed è l’unico a conoscerla.

Crittografia a chiave publicaLe funzioni A si chiamano “a senso unico” (“trap door”) .La funzione più nota è l’elevamento a potenza modulare:c=F(a,m,n)=am mod n con 1<a<n , dati a,m,ncon numeri di centinaia di cifre c non è facile da calcolare

ma esistono algoritmi per farlo:function expo(a,m,n)

if m=0 allora return 1if m è pari allora return[(expo(a,m/2,n)]2 mod naltrimenti return [(a × expo(a,m-1,n)] mod n

Per il problema inverso (“problema del logaritmo discreto”), dati c,a,n, non esistono algoritmi in grado di calcolare m.

Criptosistema RSA (Rivest,Shamir,Adleman,MIT)

Siano p e q due numeri primi sufficientemente grandi (≈10100) , sia n=p×q , sia d un numero primo rispetto a z=(p-1)×(q-1), sia e un numero tale per cui e×d=1 (mod z)

allora d è una chiave privata, mentre la coppia <e,n> è la chiave pubblica

La funzione di cifratura è c = Ek(m) = me mod n.La funzione di decifratura è m = Dk(c) = cd mod n (per il teorema di Eulero, m e×d = m mod n, quindi m e×d mod n = m )Esempio: p=19, q=23 , n= p×q =437, z= (p-1)×(q-1)=396 , sia e=13 così

che d=61, dato che 13 × 61 =793 =2 × z+1.Un messaggio m=123 viene cifrato come c = 12313 mod 437=386 e decifrato con 38661 mod 437=123 .

Criptosistema RSA (Rivest,Shamir,Adleman,MIT)

La sicurezza del metodo si basa sulla difficoltà di fattorizzare numeri grandi. Se il crittoanalista riuscisse a fattorizzare n (noto) potrebbe trovare p e q e z. Ma per fattorizzare un numero composto da n cifre con 200<n<500 ci vogliono con gli attuali computer da 109 a 10 24 anni!

Es. cifriamo SUZANNE, scegliamo p=3 q=11 , n=33, z=20per d scegliamo 7 dato che 7 e 20 non hanno fattori comuni,e può essere trovato con 7 × e =1 (mod 20) = 3. Il messaggio m in questo caso è piccolo (<33).Se p e q fossero di 100 cifre n sarebbe di 200, ogni m potrebbe essere

fino 644 bit (2644 ≈ 10 200) contro i 64 di IDEA.La crittografia a chiave pubblica è però da 100 a 1000 volte più lenta

di quella a chiave segreta.

Crittografia: RSA

Testo cifrato Testo decrittatoTesto chiaro

simbolico numerico m3 m3 (mod 33) c7 c7(mod 33) simbolico

S 19 6859 28 13492928512 19 SU 21 9261 21 1801088541 21 UZ 26 17576 26 1280000000 26 ZA 01 1 1 1 1 AN 14 2744 5 78125 14 NN 14 2744 5 78125 14 NE 05 1255 26 8031810176 5 E

Calcoli del mittente Calcoli del ricevente

Il problema della distribuzione delle chiaviOK: la crittografia è sostanzialmente sicura! Ma,• essendo la chiave pubblica disponibile chiunque ci

voglia inviare messaggi lo può fare con la certezza che solo noi possiamo decifrarli, ma

• come facciamo ad avere la certezza su chi è l’interlocutore?

• Ci vogliono metodi sicuri per l’AUTENTICAZIONE dell’interlocutore sia in chiave pubblica che segreta

• E’ un grosso problema!

AutenticazioneAutenticazione con chiave segreta condivisa, protocollo di sfida risposta.A e B sono gli id di Alice e Bob, KAB è la chiave condivisa RB, RA sono“messaggi di sfida”.

Alic

e

Bob

A, RA

RB, KAB(RA)

KAB(RB)

A e B dimostrano di saper cifrare le sfide e la comunicazione può iniziare….però … la spia T (Trudy) si può inserire!

T conosce l’id di A e stabilisce un collegamento con B e sospende la sessione. B risponde. T apre una seconda sessione con A sfidando B con RB . B risponde. T chiude la seconda sessione riprendendo la prima .B crede di comunicare con A.

Autenticazione

Trud

y

Bob

A, RT

RB, KAB(RT)

A, RB

RB2, KAB(RB)

KAB(RB)

Ia

IIa

Ia

Metodo dell’attacco riflesso

AutenticazioneSfida più lenta e più sicura.

Alic

e

Bob

A

RB

KAB(RB)

RA

KAB(RA)

Regole fondamentali:• chi inizia deve provare chi è prima di chi risponde• chi inizia e chi risponde dovrebbero usare due chiavi differenti

per la prova • chi inizia ec hi risponde devono scegliere le sfide da insiemi

differenti (es. numeri pari e dispari)

AutenticazioneStabilire una chiave condivisa, protocollo di scambio Diffie-Hellman:A e B hanno a disposizione due numeri pubblici n e g e decidono due numeri x ed y segreti

Alicesceglie

Alic

e

Bob

n,g, gx mod n

gy mod n

Bobsceglie

Bob calcola(gx mod n) y= gyx mod n

Alice calcola(gy mod n) x= gyx mod n

La chiave segreta condivisa sarà gyx mod n.es.: n=47, g= 3 x==8 y=10. gx mod n= 28, gy mod n= 17(gy mod n) x = (gx mod n) y = gyx mod n= 4

Protocollo elegante ma violabile

AutenticazioneT intercetta A e si intromette.alla fine degli scambi T può intercettare decifrare e ritrasmettere senza farsi scoprire

Alicesceglie x

Trudysceglie z

Bobsceglie z

Alic

e

Trud

y

n,g, gx mod n

gz mod n Bobn,g, gz mod n

gy mod n

AutenticazioneStabilire chiavi di comunicazione è fattibile, ma è caotico gestirle e cambiarle.Autenticazione tramite centro di distribuzione delle chiavi (KDC):KDC è un centro che gestisce le chiavi di un gruppo di clienti (bisogna fidarsi),A chiede a KDC di comunicare con B , cifra il suo messaggio con la sua chiave KA che solo KDC conosce e trasmette una chiave casuale di sessione KS(solo per quella sessione) per B (A non conosce la chiave KB di B) , KDC conosce la chiave di B e la usa per trasmettere la chiave di sessione KS e l’identità di A. Adesso A e B comunicano con KS

Alic

e

KD

CA,KA(B , KS )

Bob

KB (A,KS )

Autenticazione con RSA• A conosce la chiave pubblica di B , invia un messaggio cifrato con KB

con l’identificazione e una chiave casuale KA

• B risponde con un messaggio crittato con la chiave pubblica di A:– riinviando Ra (segnala ad A che lui è proprio B)– Rb chiave casuale per sapere se A è veramente A– KS una chiave di sessione con la quale A, se ha decrittato il messaggio,– può crittare RB, KS sarà la chiave di sessione

• A si fa riconoscere crittando Rb con Ks e accettando KS

Alic

e

Bob

EB (A, RA)

EA(RA , RB , KS)

KS(RB)

Se non si conoscono le chiavi pubbliche si ricorre al KDC

Firme a chiave segreta

Firma autentica di un messaggio (problemi bancari , commerciali, amministrativi, militari) . Si usa un Garante accettato da tutti che conosce le chiavi di tutti.

A: invia a GA l’id. B, il testo T e la marca temporale tGA: invia a B lo stesso messaggio di A più la prova KGA(A,t,T) indecifrabile garantita da GA del contenuto del messaggio (che potrà essere decifrata solo da GA in caso di contestazione: misura antiripudio)

Alic

e

GAA, KA(B , t , T)

Bob

KB (A,t,T, KGA(A,t,T) )

Firme a chiave pubblica

Si scambiano le funzioni di chiave pubblica e privata assumendo che :E(D(T))=T (funzioni E: Encrypt, D: Decrypt) oltre al fatto noto dell’ RSA che : D(E(T))=T.

Chiave privatadi Alice DA

Chiave pubblicadi Bob EB

Chiave privatadi Bob DB

Chiave pubblicadi Alice EA

TT

EB(DA(T)) DA(T)DA(T)

Computer di Alice Computer di BobLinea di trasmissione

Sintesi dei messaggi

Crittare tutto un messaggio può essere troppo dispendioso e lento, spesso basta l’autenticazione e non serve la segretezza, serve però che il messaggio non venga modificato.Si usano algoritmi HASH che generano una sintesi SM (digest) del testo di lunghezza in bit prefissata con le seguenti proprietà:

- dato T è facile calcolare SM(T)- dato SM(T) è impossibile trovare T- se si cambia solo un bit del messaggio (che diventa T’)

allora SM(T’)≠SM(T)

Le sintesi devono essere > di 128 bit.Le funzioni Hash più note sono MD5 e SHA.MD5 è più insicuro ma veloce. SHA è molto più sicuro ma lento.MD5 è uno standard per Internet , SHA è uno standard governativo USA

Email sicura: PGP (pretty good privacy)

Chiave RSA privata di Alice DA

Chiave RSA pubblicadi Bob EB

T

MD5 RSA

Zip IDEA

RSABase64

KM

T1.ZT1 CZ TA

TA: Testo ASCIIverso la rete

T : messaggio in chiaro di Alice

T1:concatenazione di T e della firma hash di TT1.Z: T1 compressoKM :chiave monouso del messaggio per IDEAcompresso

CZ: concatenazione di T1.Z crittato con IDEA e KM crittato con EB

Crittografia:sicurezzaRSA viene usato per per cifrare la sintesi di MD5 di 128 bit e la chiave di IDEA a 128 bitPGP supporta 3 lunghezze di di chiave RSA:384 bit : sicurezza bassa, transazioni normali.512 bit: commerciale sicura, violabile da organizzazioni il cui

nome è a tre lettere (CIA, KGB….)1024 bit: militare, praticamente inviolabile da chiunque( si dovrebbe indovinare un numero di oltre 300 cifre decimali)2048 bit: violabile da potenze aliene La chiave inviolabile dovrebbe essere: casuale, monouso edi lunghezza uguale al messaggio.Tempo zero per calcolatore quantistico

Crittografia quantistica