crittografia e sicurezza delle reti - riccardogalletti.com · Collocazione del corso-2° anno della...

CRITTOGRAFIA E SICUREZZA DELLE RETI

Università degli Studi di CassinoLaurea Specialistica in

Ingegneria delle Telecomunicazioni

SLIDE DAL CORSO DI CRITTOGRAFIA E SICUREZZA DELLE RETI ( © prof. Stefano Buzzi) - scaricato da www.riccardogalletti.com/appunti_gratis

Collocazione del corso

- 2° anno della Laurea Specialistica in Ingegneria delle Telecomunicazioni

- 5 CFU

- Obbligatorio per l’orientamento“Telematica”


Contenuti

• Principi introduttivi sulla crittografia e sulla sicurezza

• Tecniche di crittografia simmetrica (a chiave segreta)

• Tecniche di crittografia asimmetrica (a chiave pubblica)

• Applicazioni della crittografia alle reti: autenticazione, segretezza, integrità, etc.

• Una parte del corso dedicata ad esercitazioni in aula informatica


Riferimenti

• W. Stallings. Crittografia e Sicurezza delle Reti. McGraw-Hill, 2004.

• W. Stallings. Cryptography and Network Security, Principles and Practice. PearsonEducation, 2003.

• A. J. Menezes, P. C. van Oorschot, S. A. Vanstone. Handbook of AppliedCryptography. CRC Press, 1996.


Background

• La protezione delle informazioni ha subito negliultimi decenni un radicale cambiamento

• Classicamente, tale protezione era garantitamediante strumenti fisici (serrature, casseforti, etc.)

• L’avvento dei computer ha richiestol’introduzione di strategie alternative per la protezione delle informazioni.

• In più, l’uso delle reti richiede strumenti chepermettano di proteggere le informazionidurante la loro trasmissione


Definizioni

• Computer Security – Nome generico che indical’insieme dei tool utilizzati per proteggere i datiimmagazzinati nei computer

• Network Security – Insieme di misure utilizzateper proteggere i dati durante la lorotrasmissione, ad esempio su una LAN o su unarete telefonica

• Internet Security - Insieme di misure utilizzateper proteggere i dati durante la loro trasmissionesulla rete Internet


Definizioni

• Crittografia: si occupa di garantire la segretezza delle informazioni

• Sicurezza: utilizza tecniche crittograficheper garantire la “sicurezza” dellecomunicazioni in presenza di potenzialiavversari


Focus del corso

• In questo corso si studieranno– Tecniche di crittografia

– L’applicazione di tali tecniche per conseguirela internet security, ovvero per scoraggiare, prevenire, rivelare e porre rimedio a eventualiviolazioni della sicurezza durante la trasmissione delle informazioni


Esempi di violazioni dellasicurezza

• Una comunicazione viene ascoltata in modo fraudolento (attacco passivo)

• A comunica con B spacciandosi per C

• A nega di aver inviato un precedente messaggio

• Nella comunicazione tra A e B, C intercetta i messaggi e li sostituisce con altri da esso creati (attacco attivo)

• Celare delle informazioni all’interno di una comunicazione (steganografia)


Architettura di Sicurezza OSI

• Un documento importante è la raccomandazione X.800 dell’ITU-T

Security Architecture for OSI

• Fornisce una panoramica astratta di molticoncetti trattati nel corso

• Enuncia quali sono i requisiti di sicurezzache devono essere garantiti in una rete di telecomunicazioni


Servizi di Sicurezza in X.800

• Autenticazione – assicurazione dell’autenticitàdei soggetti coinvolti nella comunicazione

• Controllo degli Accessi – Inibizione dell’uso di una risorsa da parte di soggetti non autorizzati

• Confidenzialità – Protezione della riservatezzadei dati

• Integrità – Assicurazione che i dati non sianostati alterati

• Non-Ripudiabilità – Protezione contro la negazione di un soggetto coinvolto nellacomunicazione


Classificazione degli attacchi

• Attacchi passivi – ascolto celato delle comunicazioni (eavesdropping) e monitoraggio del traffico

• Attacchi attivi – modifica dei dati per– Spacciare la propria identità per un’altra

– Rispondere a messaggi inviati ad altre parti

– Modificare i messaggi in transito

– Attacchi di tipo “denial of service”


Un modello per la sicurezzadelle reti


Un modello per la sicurezzadelle reti

• Si evince quindi che nella progettazione di un servizio di sicurezza si deve: – Progettare un algoritmo per la trasformazione di

sicurezza (crittografia)

– Generare le informazioni segrete (chiavi) da utilizzare

– Sviluppare metodi per la condivisione sicura delle chiavi

– Specificare un protocollo (insieme di regole) chepermetta ad Alice e Bob di utilizzare l’algoritmo di crittografia e le chiavi segrete per comunicare in modo sicuro


Modello di sicurezza per gli accessialla rete

Ci occuperemo in maniera limitata di tale modello


Codifica e Crittografia: Parte I

Introduzione alla crittografia simmetrica;

Descriveremo gli algoritmi “classici” e quellipiù moderni;

In particolare, studieremo– DES (Data Encryption System)

– AES (Advanced Encryption Standard)


Crittografia Simmetrica

• Detta anche “a chiave privata,“ “a chiavesingola” o anche “convenzionale”

• Trasmettitore e Ricevitore condividonouna chiave segreta

• Tutti gli algoritmi di crittografia classici sono di questo tipo

• E’ stata l’unico tipo di crittografia fino aglianni ’70, quando fu introdotta la crittografiaa chiave pubblica


Terminologia di base

• Plaintext, testo in chiaro – il messaggio originale• Ciphertext, testo cifrato – il messaggio crittografato• Cipher, cifrario – algoritmo che trasforma il plaintext in

ciphertext• Key, chiave – informazione usata nel cifrario, nota solo a Bob

e Alice • encipher (encrypt), criptare – convertire plaintext in

ciphertext• decipher (decrypt), decriptare – recuperare il plaintext dal

ciphertext• crittografia – studio dei metodi e dei principi alla base degli

algoritmi di cifratura• cryptanalysis (codebreaking) – studio dei principi di base e

dei metodi per ottenere il testo in chiaro senza conoscere la chiave


Schema della CrittografiaSimmetrica


Definizioni

Useremo le notazioni


Requisiti

• Affinchè la crittografia simmetrica sia sicura èrichiesto:– Un algoritmo di cifratura forte

– Una chiave segreta nota solo al trasmettitore e al ricevitore

Y = EK(X)

X = DK(Y)

• Si assume che gli algoritmi E(.) e D(.) siano noti

• C’è bisogno quindi di una metodologia sicuraper distribuire la chiave


Proprietà


L’algoritmo di Crittografia

• È caratterizzato da:– Tipo di operazioni svolte nella cifratura

• Sostituzione / Trasposizione

– Numero di chiavi usate• Singola (privata) / doppia (pubblica)

– Modalità di elaborazione del plaintext• blocco / flusso (una lettera per volta)


Criptoanalisi (Codebreaking)

• Può essere essenzialmente basata su

– Analisi crittografica

– Attacco a forza bruta


Tipi di Attacchi Criptoanalitici

• ciphertext only• known plaintext• chosen plaintext• chosen ciphertext

L’attacco “ciphertext only” è il più complicato daattuare.


Attacco a Forza Bruta• Utilizza ogni possibile chiave

• Costo proporzionale alla cardinalità dello spaziodelle chiavi

• Si assume che il plaintext sia riconoscibile


Esempio: attacco a DES

Il Cifrario a chiave singola DES è stato introdotto nel 1976 ed utilizza chiavi di 56 bit.

Nel 1976, si valutava sufficiente tale lunghezza: Assumendo 1cifratura/μs, ci vorrebbero in media più di 1000 anni per trovare la chiave

Attualmente, hardware dedicati ad architettura parallela dal costo ragionevole, eseguono 1.000.000 di cifrature al μs, ragion per cui il tempo medio di ricerca della chiave si riduce a circa 10 ore

DES quindi non è più considerato sicuro!


Un algoritmo Crittografico è...

• incondizionatamente sicuro– Indipendentemente dalle risorse

computazionali a disposizioni, il cifrario non può essere rotto

In termini probabilistici, schematizzando ilplaintext X ed il ciphertext Y come vettorialeatori, deve essere


Un algoritmo Crittografico è...

• computazionalmente sicuro– Lo sforzo computazionale richiesto per

forzare il cifrario eccede il valoredell’informazione, o richiede un tempo chesupera il tempo in cui l’informazione ha valore

Ovviamente, algoritmi computazionalmente sicuri oggi non è detto che lo siano in futuro!!


Crittografia classica a sostituzione

• Le lettere del testo in chiaro sono sostituiteda altre lettere, o da numeri o da simboli

• Se, in alternativa, il testo è codificato in stringhe di bit, allora sequenze di bit di opportuna lunghezza saranno sostituite daaltre sequenze di bit


Cifratura di Cesare

• E’ il cifrario a sostituzione più antico a noinoto

• Ideato da Giulio Cesare• Utilizzato per le comunicazioni militari• Sostituisce ogni lettera con quella che

viene 3 posizioni dopo• esempio:

Alea iacta estDOHD NDFWD HVZ


Cifratura di Cesare

• Banalmente, la funzione di criptazione è:a b c d e f g h i j k l m n o p q r s t u v w x y zD E F G H I J K L M N O P Q R S T U V W X Y Z A B C

• Matematicamente, si assegni ad ognilettera un numeroa b c d e f g h i j k l m0 1 2 3 4 5 6 7 8 9 10 11 12n o p q r s t u v w x y Z13 14 15 16 17 18 19 20 21 22 23 24 25

• da cui:C = E(p) = (p + k) mod (26)p = D(C) = (C – k) mod (26)


Analisi del cifrario di Cesare

• Soltanto 26 diverse possibilità– A può essere codificata con A,B,..Z

• Ovvero, solo 26 possibili chiavi

• Vulnerabilità all’attacco a forza bruta

• Bisogna tuttavia avere la capacità di riconoscereil plaintext


Cifrari Monoalfabetici

• Generalizzazione del cifrario di Cesare

• Ciascuna lettera del testo in chiaro vieneassociata ad una lettera scelta a caso

• La chiave è lunga in tal caso 26 lettere

Plain: abcdefghijklmnopqrstuvwxyz

Cipher: DKVQFIBJWPESCXHTMYAUOLRGZN

Plaintext: ifwewishtoreplaceletters

Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA


Sicurezza del cifrariomonoalfabetico

• Vi sono ora 26! = 4 x 1026 possibili chiavi

• Si potrebbe quindi pensare che tale cifrario è sicuro

• ERRATO

• Il cifrario si può rompere in virtù dellecaratteristiche del linguaggio


Ridondanza nel Linguaggio e Criptoanalisi

• I linguaggi umani sono ridondanti

• Per l’inglese i digrammi “th” “sh”

• Nell’inglese e è la lettera più comune

• poi T,R,N,I,O,A,S

• Altre lettere sono estremamente rare: Z,J,K,Q,X

• Vi sono tabelle di frequenza di lettere, digrammi, trigrammi, etc...


Frequenza Alfabeto Inglese


Criptanalisi CifrariMonoalfabetici

• Concetto base – la sostituzione monoalfabeticanon modifica la frequenza relativa delle lettere

• Scoperta di matematici arabi del IX secolo

• Occorre calcolare le frequenze relative delle lettere del testo cifrato...

• ...e andare alla ricerca dei massimi e minimi

• Si individuano quindi alcune lettere– Un aiuto è costituito dalle tabelle dei digrammi e

trigrammi più comuni


Esempio di Crittoanalisi

• Si consideri il testo cifrato:UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

• Si determinano le frequenze relative• Si ipotizza che P e Z sono e and t• Si ipotizza che ZW è th e quindi ZWP è the• Andando avanti per tentativi si trova:

it was disclosed yesterday that several informal butdirect contacts have been made with politicalrepresentatives of the viet cong in moscow


Cifratura Playfair

• Il cifrario monoalfabetico non è quindisicuro

• Un’alternativa è cifrare i digrammi inveceche le singole lettere

• Esempio: Cifratura Playfair

• inventata da Charles Wheatstone nel1854, trae il suo nome dal suo amicoBaron Playfair


Chiave Matriciale del CodicePlayfair

• Si consideri una matrice 5X5 di lettere basate suuna parola

• La parola è inserita nella matrice, la quale è poi completata con le rimanenti lettere dell’alfabeto

• I e J occupano la stessa posizione• Esempio: si consideri la parola MONARCHY

M O N A RC H Y B DE F G I KL P Q S TU V W X Z


Criptazione e Decriptazione

• Il plaintext è criptato a digrammi: 1. In presenza di una doppia lettera, si inserisce una

lettera spuria come 'X', ovvero "balloon" diventa "balx lo on"

2. Se entrambe le lettere sono sulla stessa riga, ognilettera è sostituita da quella alla sua destra ciclica, ad esempio “ar" viene criptato in "RM"

3. Se entrambe le lettere sono sulla stessa colonna, ogni lettera è sostituita da quella al di sotto, ad esempio “mu" viene criptato in "CM"

4. Altrimenti, ogni lettera è sostituita da quella nella sua riga nella colonna dell’altra lettera della coppia. Ad esempio, “hs" viene criptato in "BP“.


Sicurezza del Cifrario Playfair

• La sicurezza è molto maggiore del cifrariomonoalfabetico

• Vi sono infatti 26 x 26 = 676 digrammi• L’analisi richiede quindi una tabella con le

frequenze di 676 digrammi (invece che di 26 lettere nel caso monoalfabetico)

• L’analisi richiede una quantità maggiore di testocifrato

• Usato ampiamente, ad esempio nella I GM• Non è tuttavia sicuro, perchè conserva

fortemente la struttura del plaintext


Cifrario di Hill

• Codifica m lettere di plaintext con m lettere di ciphertext


Cifrario di Hill• Posto

la cifratura/decifratura si scrive come

ove tutte le operazioni sono intese mod26


Cifrario di Hill

• La matrice K-1 è l’inversa mod26 della matrice K, ovvero

• Se la lunghezza del blocco m èsufficientemente estesa il cifrario è sicuro ad attacchi ciphertext only


Attacco al Cifrario di Hill

• Vulnerabilità all’attacco known plaintext:

Se

Posto

è C*=KP*mod26, da cui K=C*(P*)-1


Cifrario di Hill: Esempio

17024

61715

15941K

1922

211821

51717

K

100

010

001

26mod

36552494

780495858

4424424431KK


Cifrario di Hill: Esempio di attacco

26mod317

85

516

215

K

151

29

317

851

319

8726mod

107149

60137

151

29

516

215K


Cifrari Polialfabetici

• Per migliorare la sicurezza, si possono usare piùcifrari monoalfabetici contemporaneamente

• Si parla in tal caso di cifrari a sostituzionepolialfabetica

• La distribuzione dei simboli diventamaggiormente uniforme: criptoanalisi più difficile

• Viene utilizzata una chiave per selezionare ilparticolare cifrario monoalfabetico da utilizzareper criptare il generico simbolo

• I vari cifrari monoalfabetici sono usaticiclicamente


Cifrario di Vigenère

• E’ il più semplice cifrario a sostituzionepolialfabetica

• Corrisponde ad un cifrario di Cesare multiplo

• Opera su blocchi di testo lunghi m

• La chiave è costituita da una successione di lettere K = k1 k2 ... km

• L’i-esima lettera definisce il valore dello shift sull’i-esimo carattere di plaintext

• La decriptazione è ovviamente analoga


Cifrario di Vigenère: Esempio

• Anzitutto, si scrive per esteso il plaintext

• Si scrive la chiave ripetutamente sopra ilplaintext

• Si utilizza ogni lettera della chiave come una singola chiave del cifrario Cesare

• Esempio:


Cifrario di Vigenère: ModelloMatematico

• Sia m la lunghezza della chiave, e siano Pi, Ci , e Ki la i-esima lettera dei vettori P, C e K, rispettivamente.

• Le funzioni EK(.) e DK(.) si esprimono come


Sicurezza del cifrario Vigenère

• Ogni lettera del plaintext non è cifrata semprecon lo stesso simbolo

• Le frequenze relative di occorrenza delle letteresono quindi mascherate...

• ...ma non completamente!• Anzitutto, si verificano le frequenze nel

ciphertext– Si verifica quindi se il cifrario è monoalfabetico

• Se non lo è, bisogna individuare m e poi operaresui singoli cifrari monoalfabetici


Sicurezza del cifrario Vigenère

• Per anni il cifrario Vegenère fu ritenuto “le chiffre indéchiffrable”

• Nel 1917 un articolo di Scientific Americanlo ha definito “impossibile da tradurre”

• Di fatto, era stato già violato nel 1854 da Charles Babbage e nel 1863 da Friedrich Kasiski

• Malgrado ciò, cifrari polialfabetici sonostati usati anche agli inizi del XX secolo


Il Telegramma Zimmerman



• Inviato nel 1917 dal Ministro degli Esteri tedesco Arthur Zimmerman all’ambasciatore tedesco in Messico su un cavo transatlantico, ritenuto sicuro perchè riservato per condurre negoziati di pace

• Proponeva al Messico un’alleanza contro gli Stati Uniti promettendo in cambio denaro e delle terre del New Mexico, Arizona e Texas

• L’intento era di creare un fronte della guerra nelle Americhe al fine di distrarre forze dal fronte europeo



• Il telegramma fu intercettato dall’intelligence inglese e reso noto all’opinione pubblica il 24 febbraio 1917

• Il Messico immediatamente negò di aver dato seguito a quella proposta

• Il 6 Aprile 1917 il Congresso Americano approvò (con un solo voto contrario) la decisione del Presidente Wilson di entrare in guerra contro la Germania


Kasiski Method

• Svillupato da Babbage/Kasiski; risale al 1863

• Segmenti identici di plaintext producono lo stesso ciphertext se la loro distanza è multipla di m

• Digrammi e trigrammi ripetuti nel ciphertextoccorrono a distanze che con elevata probabilitàsono multiple di m

• Si può quindi congetturare che m sia un divisoredel massimo comun divisore di tali distanze


Indice di Coincidenza

• Definito da Wolfe Friedman nel 1920

• Sia X una stringa di n caratteri e sia fi il numero di occorrenze della lettera i in X, per 0i 25

• Si definisce indice di coincidenza in X la probabilità che due elementi di X scelti a caso siano uguali

• E’ possibile estrarre due elementi da X in

modi 2/)1(2

nn

n



• Ma allora, per ogni i, ci sono fi (fi –1)/2 modi diversi di estrarre due caratteri entrambi uguali ad i. Quindi, si ha

Prob. di estrarre due lettere uguali dal testo x



• Se X è un testo inglese, le lettere A,B,... Si presenteranno con probabilità p0, p1, ..., p25. Se X è abbastanza lungo, si ha

da cui



• In una stringa con distribuzione uniforme, ogni lettera ha probabilità 1/26, e l’indice di coincidenza sarà

• Tali considerazioni portano ad una metodologia per determinare m



• Sia Y una stringa di testo cifrato lunga n.• Si assuma n multiplo di m• Si formino i vettori Y0, Y1, ..., Ym-1 decimando con passo

m il vettore Y• Se m è effettivamente la lunghezza della chiave ciascun

vettore Yi rappresenta il ciphertext di un cifrario monoalfabetico. Di conseguenza, gli indici di coincidenza di ciascun vettore devono essere prossimi a 0,065

• In caso contrario, gli indici di coincidenza si avvicineranno a 0,038

• Mediante tentativi successivi si risale dunque al valore di m


Cifrario con autochiave• Idealmente, si vorrebbe avere una chiave lunga

quanto il messaggio• Vigenère propose il cifrario con autochiave• La chiave viene anteposta al messaggio che,

ritardato opportunamente, viene usato come chiave

• Anche in questo caso si ha vulnerabilitàall’analisi statistica

• Esempio con chiave deceptivekey: deceptivewearediscoveredsavplaintext: wearediscoveredsaveyourselfciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLA


Cifrari incondizionatamente sicuri



• Siano M, K e C tre variabili aleatorie che rappresentano il messaggio in chiaro, la chiave ed il testo cifrato

• Il cifrario è perfetto se



TEOREMA: In ogni cifrario perfetto, |K||M|PROVA: Poichè E(.) è iniettiva, deve essere |M| |C|, ovvero il numero di testi cifrati deve essere non inferiore al numero di testi in chiaro.Se fosse |K|<|M||C|, fissato un messaggio mM, esisterebbe almeno un c*C che non può essere generato da m, ovvero

P(m | c*)= 0 P(m) Tale relazione contraddice il fatto che il cifrario sia perfetto c.v.d.


One-Time Pad

• Usando una chiave “aleatoria” lunga quanto ilmessaggio si ottiene un cifrario perfetto

• Il cifrario è detto One-Time pad

• E’ un’evoluzione del cifrario di Vernham (1918)

• Non si può rompere perchè il testo cifrato non ha alcuna dipendenza statistica dal testo in chiaro poichè per ogni coppia (testo in chiaro, testo cifrato) esiste una chiave che realizza tale corrispondenza


One-Time Pad

• La chiave può essere usata solo una volta

• Infatti, se la chiave è lunga N bit e la usodue volte in tempi diversi, di fatto ho inviato 2N bit con una chiave lunga N; in tal caso ho che |K|<|M| e il cifrario perde le caratteristiche di sicurezza!

• Il problema è la distribuzione della chiave!!


Cifrari a trasposizione

• Consideriamo ora i cifrari classici a trasposizione o permutazione

• Il messaggio è cifrato cambiandoposizione alle lettere

• La frequenza relativa delle lettere non cambia


Cifrario Rail Fence (staccionata)

• Il messaggio è scritto in diagonale per un certo numero di righe

• E poi viene letto per righe

• esempio:m e m a t r h t g p r y

e t e f e t e o a a t

• Il ciphertext èMEMATRHTGPRYETEFETEOAAT


Cifrario a trasposizione di righe

• E’ uno schema più complesso• Il messaggio è scritto per righe in una

matrice• Poi le colonne sono lette in un ordine

dettato da una certa chiaveKey: 3 4 2 1 5 6 7Plaintext: a t t a c k p

o s t p o n ed u n t i l tw o a m x y z

Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ


Cifrari composti

• I cifrari a trasposizione non sono sicuri• Si possono considerare più cifrari in

successione per ottenere un algoritmomaggiormente robusto. – Due sostituzioni portano ad una sostituzione più

complicata– Due permutazioni portano ad una permutazione più

complicata– Tuttavia una sostituzione seguita da una

trasposizione porta alla creazione di un cifrariomolto più resistente

• I moderni sistemi crittografici sfruttano questorisultato


Macchine a rotazione

• Le macchine a rotazione sono i progenitori deimoderni cifrari

• Ampiamente usate nella II GM– German Enigma, Allied Hagelin, Japanese Purple

• Realizzano un cifrario composto a sostituzionealquanto complesso

• Si utilizzava una serie di cilindri, ciascuno deiquai da luogo a una sostituzione, e che eranoruotati dopo la cifratura di ciascuna lettera

• Con 3 cilindri si hanno 263=17576 chiavi


Macchine a rotazione


Steganografia

• E’ un’alternativa alla crittografia

• Cela un messaggio segreto in uno pubblico– Ad esempio usando un sottoinsieme di lettere di un

messaggio

– Utilizzando il LSB in immagini grafiche e file audio e video

• Il principale svantaggio è che c’è bisogno di unagrossa mole di dati da inviare per celare dati di dimensione molto più ridotta


Crittografia simmetricaAlgoritmi moderni


Cifrari SimmetriciContemporanei

• I cifrari simmetrici sono tuttora uno dei tipi di algoritmi crittografici più utilizzati

• Sono utilizzati per implementare i servizi di confidenzialità (segretezza) e autenticazione

• Tra tali cifrari, ci occuperemo nel seguitodi DES (Data Encryption Standard)


Cifrari a blocco e a flusso

• I cifrari a blocchi elaborano il messaggio dacriptare dividendolo in blocchi di lunghezzafissa; il messaggio cifrato si ottiene elaborandosingolarmente ogni blocco

• Possono essere riguardati come cifrari a sostituzione operanti su un alfabeto a cardinalitàmolto grande

• I cifrari a flusso elaborano il messaggio un bit o un byte per volta

• La maggior parte dei cifrari moderni sono a blocco.


I cifrari a blocco

• In linea di principio, un cifrario a blocco può essererealizzato tramite un look-up table

• Infatti, un cifrario a blocco non è altro che un cifrario a sostituzione

• Utilizzando blocchi di n bit, tale tabella richiede una memoria pari a n2n. Questa è di fatto la chiave del codice

• Per n=64 è 64 x 264 =1021 bit.• Per ridurre l’ingombro di memoria, si utilizzano cifrari

“strutturati”• In pratica, cifrari complicati sono ottenuti componendo

cifrari più semplici


Cifrari basati su Sostituzioni e Permutazioni (by Claude Shannon)• Il lavoro “Communication Theory of Secrecy

Systems,” apparso nel 1949, contiene i concettifondamentali utilizzati nei cifrari a bloccomoderni

• In realtà, tali contenuti erano gia presenti nelreport “A mathematical theory of criptography,”datato 01/09/1946, e che fu tenuto segreto

• Shannon introdusse l’idea di utilizzare reticostituite da cifrari più semplici, operanto le operazioni di sostituzione e permutazione


Cifrari basati su Sostituzioni e Permutazioni (by Claude Shannon)• Le reti S-P sono alla base dei moderni

cifrari a blocco• Tali reti sono basate su due semplici

operazioni crittografiche che abbiamo giàesaminato: – sostituzione (S-box)– permutazione (P-box)

• Tali reti introducono sul messaggio glieffetti di confusione e diffusione


Confusione e Diffusione

• Un buon cifrario dovrebbe mascherarecompletamente le proprietà statistiche del plaintext (esempio: one-time pad)

• Per ottenere in pratica un cifrario “quasi-ideale”Shannon suggerì di utilizzare strutture cheportassero alla

• diffusione – spalma la struttura statistica del plaintext su blocchi di testo cifrato

• confusione – rende la relazione tra il testocifrato e la chiave utilizzata il più complicatapossibile



• La confusione si realizza mediante operazioni di

- Permutazione: nasconde le frequenze dei q-grammi, con q>1

- Combinazione:ogni bit del ciphertext viene fatto dipendere da molti bit del plaintext, in modo da nascondere le frequenze delle singole lettere (Idealmente, ogni lettera del testo cifrato dovrebbe dipendere da tutti i caratteri del testo in chiaro)



Esempio:


La “Struttura Feistel”

• Primi anni 70: Horst Feistel, ricercatorepresso il Thomas J. Watson Research Lab dell’IBM inventò una struttura ad-hoc facilmente invertibile e molto semplice darealizzare– Era basata sull’uso di cifrari composti

• Il blocco da cifrare è diviso in due parti• Utilizza le funzioni di permutazione e

sostituzione indicate da Shannon


La “StrutturaFeistel”

•Forma particolare della struttura proposta daShannon

•Implementa n volte la stessa funzione•Elabora separatamente parte dx e parte sx•In ogni round solo metà dei dati è alterata


Parametri di Progetto dellaStruttura Feistel

• Dimensione del blocco– Ha impatto sulla sicurezza, ma anche sulla velocità di esecuzione della

criptazione e decriptazione• Dimensione della chiave

– Idem, come sopra• Numero di round (iterazioni)

– Idem, come sopra• Generazione delle sottochiavi

– Funzioni complesse rendono l’analisi crittografica più complicata, ma rallentano il codice

• Funzione round– Idem, come sopra

• Velocità del software e facilità di analisi– È bene che l’algoritmo sia implementabile con software veloci e, anche,

che sia semplice, in modo che l’analisi crittografica possa porne in evidenza eventuali punti deboli.


Criptazio-ne e De-criptazio-

ne del Cifrario di

Feistel

Non è richiesto chela F sia invertibile!!


Data Encryption Standard (DES)

• E’ uno dei cifrari a blocco più ampiamenteutilizzati nel mondo

• Adottato nel 1977 dal NBS (now NIST, National Institute of Standards and Technology)– come FIPS PUB 46 (Federal Information Processing

Standard)

• Cripta parole di 64-bit usando una chiave di 56 bit

• Vi sono state moltissime discussioni circa la suasicurezza


La storia di DES

• L’ IBM sviluppò nel 1971 il cifrario LUCIFER– Il team di sviluppo era guidato da Feistel

– Criptava parole di 64 bit con una chiave di 128 bit

– Fu venduto ai Lloyd di Londra per l’utilizzo nei cash dispenser

• A partire da LUCIFER, l’IBM decise di svilupparne unaversione più evoluta che potesse essere realizzata e commercializzata su un chip

• Nel 1973 NBS emanò un call for proposal per unostandard di cifratura nazionale

• IBM sottopose la versione evoluta di LUCIFER che fu poi accettata e divenne DES


Le polemiche su DES

• DES è un algoritmo pubblico

• Vi sono state polemiche in quanto– La chiave è di 56 bit (vs Lucifer 128-bit)

– I criteri di progetto dei round non sono noti

• Le analisi che susseguirono hanno tuttaviamostrato che DES è un buon algoritmo

• DES è stato ampiamente utilizzato, specialmente per transazioni finanziarie


Criptazione DES


La Permutazione Iniziale

• E’ il primo stadio dell’algoritmo

• Riordina i dati in ingresso

• I bit pari sono posti nella metà sinistra, quelli dispari nella metà destra

• La struttura è alquanto regolare, cosicchèpossa essere implementata in modo semplice in hardware


La Permutazione Iniziale

Esempio: L’output di IP sarà b(58) b(50) b(42) b(34) ....... b(15) b(7)


Struttura dei round in DES

• Divide i dati nella parte sinistra (L) e destra (R)• Come nella classica struttura Feistel, si ha:

Li = Ri–1

Ri = Li–1 xor F(Ri–1, Ki)

• La funzione F elabora i 32 bit della parte R e la sottochiave di 48 bit come segue:– espande R a 48 bit mediante una

permutazione/espansione (vedi lucido seguente)– Somma il risultato alla sottochiave– Invia il tutto a 8 S-boxes per avere un output di 32 bit – I 32 bit sono assoggetati a una permutazione finale


Struttura dei round in DES


L’Espansione/Permutazione (da 32 a 48 bit)


La Permutazione Finale


Le S-Box

• Vi sono 8 S-Box che sono funzioni cheaccettano in ingresso 6 bit e ne producono 4

• Ciascuna S-box è una matrice 4 x 16 contenenteinteri in {0, 1, ..., 15}– I bit 1 & 6 selezionano la riga

– I bit 2-5 selezionano la colonna

– Il risultato è l’espansione binaria dell’elementoselezionato della matrice

• L’output delle S-box dipende sia dai dati chedalla chiave


Le S-Box in DES


Generazione delle sottochiavi

• In ogni round sono utilizzate delle sottochiavi

• La chiave originaria è lunga 64 bit, ma un bit ogni 8 non conta, quindi si tratta solo di 56 bit– Vi è una permutazione iniziale della chiave, che viene

poi suddivisa in due metà di 28 bit ciascuna

– Vi sono poi 16 stadi in cui: • Si selezionano 24 bit da ciascuna metà

• Si effettua una permutazione (PC2),

• Si ruota verso sinistra ciascuna metà di un numero di posizioni pari a 1 o a 2


La chiave in ingresso


La prima permutazione


La seconda permutazione e gli shift ciclici


Un singolo round in DES


La decriptazione in DES

• La decriptazione è analoga alla criptazione

• In virtù della struttura Feistel, la decriptazione è analoga alla criptazionecon le sottochiavi utilizzate in ordineinverso

• Nota che la permutazione finale è l’inversodella permutazione iniziale


L’effetto valanga

• E’ una caratteristica desiderata per ognialgoritmo di criptazione

• Un cambiamento di pochi bit nel plaintext deve provocare un cambiamento di quanti più bit nel ciphertext

• DES possiede un forte effetto valanga


L’effetto valanga in DES


La forza di DES: la chiave

• Vi sono 256 = 7.2 x 1016 possibili chiavi

• Nel 1977 l’attacco a forza bruta non era fattibile

• Le cose sono cambiate negli ultimi anni– nel 1998 fu rotto in 3 giorni dalla EFF (Electronic

Frontier Foundation) con una macchina dedicata del costo di $ 250.000

– nel 1999 tale tempo fu ridotto a 22 ore!

• Al giorno d’oggi, vi sono alternative a DES, chevedremo più avanti nel corso (es. AES, 3DES)


Criteri di progetto di DES

• I criteri di progetto si rifanno al progettoLUCIFER di Feistel

• Numero di round– La loro numerosità rafforza il codice

• La funzione F:– È quella che introduce la “confusione”, deve essere

non lineare (robustezza all’attacco known plaintext), e possedere l’effetto valanga

• Gestione della chiave– La creazione della sottochiave deve essere

complicata; deve essere garantito l’effetto valanga


Modalità di utilizzo dei cifrari a blocco

• I Cifrari a blocchi criptano parole di lunghezzafissa (esempio: DES elabora blocchi di 64 bit)

• Nella realtà, con grosse moli di dati, vi sonomolteplici blocchi da criptare

• L’ ANSI standard ANSI X3.106-1983 Modes of Use ha stabilito 4 possibili modi di utilizzo deicifrari a blocco

• I modi di utilizzo usualmente considerati sono 5


Electronic Codebook (ECB)

• Il messaggio è suddiviso in blocchiindipendenti che sono poi criptatisingolarmente

• Si tratta a tutti gli effetti di un cifrario a sostituzione

• E’ la modalità ideale per la trasmissione di brevi quantità di dati


Electronic Codebook (ECB)


Svantaggi della modalità ECB

• La ridondanza del plaintext viene riportatanel ciphertext– Blocchi uguali di plaintext in tempi diversi

produrranno blocchi analoghi di ciphertext

– Se il messaggio è strutturato (header comune) si possono ottenere copie di testo in chiaro/testo cifrato su cui lavorare

• La modalità ECB vine utilizzata per l’inviodi piccole quantità di dati


Cipher Block Chaining (CBC)

• Il plaintext è diviso in parole di 64 bit• Tali parole sono però collegate tra loro durante

la criptazione• Ciascun blocco cifrato è concatenato (tramite

uno XOR) col successivo blocco di plaintext• Il primo blocco di plaintext fa uso di un vettore di

inizializzazione (IV): Ci = DESK1(Pi XOR Ci-1)C-1 = IV

• La modalità CBC viene usata per la criptazionedi grosse quantità di dati


Modalità CBC: vantaggi e svantaggi

• Ciascun blocco di ciphertext dipende da tutti i precedenti blocchi di plaintext

• Un cambiamento in un singolo blocco ha effettodu tutti i blocchi cifrati seguenti

• C’è bisogno di un vettore di inizializzazione (IV) noto al trasmettitore e al ricevitore– IV tuttavia non può essere inviato in chiaro

– IV deve essere invato in forma criptata (ad esempiocon modalità ECB) o deve assumere un valore fisso e noto


Cipher FeedBack (CFB)

• Il messaggio è considerato come un flussodi bit

• Viene aggiunto all’uscita del testo cifrato• Il risultato è poi utilizzato allo stadio

successivo• Lo standard stabilisce che possano essere

criptati un numero arbitrario di bit per volta(ovviamente non superiore a 64)

• usi: criptazione di dati in tempo reale


CFB: Vantaggi e Svantaggi

• È appropriata quando i dati arrivano in bytes o gruppi di bit

• È il cifrario di flusso più comune

• Lo svantaggio principale è la sensibilità ad errori sul canale di trasmissione: Un erroresi propagherà anche nei blocchi successivi


Output FeedBack (OFB)

• Il messaggio è considerato come un flusso di bit• Viene aggiunto all’uscita del testo cifrato• Il risultato è poi utilizzato allo stadio successivo• L’informazione di feedback non dipende dal

plaintext, ma solo dalla chiave• Può quindi essere calcolata preventivamente

Ci = Pi XOR OiOi = DESK1(Oi-1)O-1 = IV

• Usi: criptazione di flussi per trasmissione sucanali rumorosi


OFB: Vantaggi e Svantaggi

• Utilizzato quando possono esservi errori nellatrasmissione

• A prima vista è simile al CFB

• In realtà il feedback è indipendente dal messaggio

• Il feedback fa si che si utilizzi una chiave tempo-variante

• Trasmettitore e ricevitore devono quindi operare in sincronia

• E’ vulnerabile a un attacco a modifica del flusso: cambiando un bit del ciphertex si ottiene il cambiamentodello stesso bit nel plaintext


Counter (CTR)

• E’ una modalità proposta nel 1979, ma che ha acquisito importanza solo in epoca recente

• È simile a OFB, con la differenza che vienecriptato un contatore invece che un’informazioneinviata in feedback

• Il contatore deve essere diverso per ogni bloccodi plaintextCi = Pi XOR OiOi = DESK1(i)

• Uso: criptazione nelle reti ad alta velocità (es. ATM)


Counter (CTR)


CTR: Vantaggi e Svantaggi

• efficienza– Si presta all’implementazione parallela di più

criptazioni– Se si dispone di memoria, si possono calcolare le

uscite Oi prima che il plaintext sia disponibile– È indicato per reti veloci e traffico a burst

• I blocchi di dati possono essere criptati/decriptatiin modo casuale (random access)

• É una modalità sicura almeno quanto le altre• Si deve garantire però che non venga usata lo

stesso counter con la stessa chiave più di unavolta


Estensioni di DES


Limiti di DES

• DES è vulnerabile ad attacchi a forza bruta(lunghezza della chiave: 56 bit):– nel 1977 si riteneva che già esistesse la tecnologia

per violare DES in 10 ore (costo 20 milioni USD)– nel 1998 la Electronic Frontier Foundation costruisce

una macchina ‘DES cracker’ in grado di violare DES in tre giorni (costo 250 000 USD)

NOTA: l’attacco a forza bruta richiede chel’analista sia in grado di riconoscere il testo in chiaro decifrato!


Soluzioni

• Progettare un algoritmo di crittografia completamente nuovo e più resistente agli attacchi a forza bruta (i.e., AES).

• Utilizzare una crittografia DES multipla con più chiavi:– Double DES

– Triple DES a due chiavi

– Triple DES a tre chiavi


Double DES

• Due fasi di crittogra-fia in cascata che utilizzano due chiavi distinte K1 e K2:

]][[

]][[

21

12

CEEP

PEEC

KK

KK


Double DES

• Apparentemente Double DES usa una chiave di 56x2=112 bit.

• Domanda: date due chiavi K1 e K2, è possibile trovare una chiave K3 tale che

• Risposta: in generale, applicando DES due volte si ottiene un mappaggio che non può essere ottenuto da una sola applicazione di DES.

?][E]][E[E312 KKK PP


Attacco Meet-in-the-Middle

• Data una coppia nota (P,C), l’attacco procede come segue:– Si esegue la crittografia di P per tutti i 256 valori di K1

– Si esegue la decrittografia di C per tutti i 256 valori di K2

– Quando si trova una corrispondenza, si esegue il test delle due chiavi risultanti contro una nuova coppia (Pa,Ca). Se le due chiavi producono il testo cifrato corretto, si tratta delle chiavi corrette.

][][]][[2112

CDPEXPEEC KKKK



• Per ogni testo in chiaro P, Double DES produce uno fra 264 possibili valori cifrati.

• Poiché Double DES usa chiavi di 112 bit, ci sono in media 2112/264= 248 chiavi che producono lo stesso testo cifrato C.

• L’attaco meet-in-the-middle produce in media 248

falsi allarmi sulla coppia (P,C).• Utilizzando una seconda coppia (Pa,Ca), i falsi

allarmi si riducono a 248-64= 2-16, ovvero la proba-bilità di individuare le chiavi corrette è 1- 2-16.



• L’attacco meet-in-the-middle ha una complessitàcomputazionale pari 256.

• Di conseguenza, pur utilizzando chiavi di 112 bit, Double DES può essere violato in maniera relativamente semplice con un attacco a testo in chiaro noto.

NOTA: Si ricordi che DES può essere violato con un attacco a testo in chiaro noto con un impegno pari a 255 .


Triple DES con due chiavi

• Una contromisura contro l’attacco meet-in-the-middle è l’uso di tre fasi di crittografia:


Triple DES con due chiavi

• Vengono ancora utilizzate due chiavi crittografiche da 56 bit ciascuna.

• La presenza di una decrittografia nella seconda fase consente agli utenti Triple DES di decrittografare i dati crittografati dagli utenti DES (basta porre K1=K2).

• L’attacco meet-in-the-middle a testo in chiaro noto avrebbe una complessità 2112.


Attacchi a Triple DES con due chiavi

• Se è nota la coppia (A,C), il problema si riduce ad un attacco a Double DES.

• In pratica, se le due chiavi K1 e K2 sono sconosciute, A non è noto all’analista. In tal caso si procede fissando una valore potenziale di A e si tenta di trovare una coppia nota (P,C) che produce A.


Schema di attacco (1/3)• Ottenere n coppie (P,C) e

inserirle nella tabella (b) ordinate per valori di P.

• Scegliere un valore A=a. Per tutte le 256 chiavi Ki=i calco-lare Pi=Di[a]. Per ciascun Pi presente anche nella tabella (b) creare una voce nella tabella (c) contenente Ki e Bi=Di[C]. Ordinare la tabella (c) sulla base dei valori di B.


Schema di attacco (2/3)• Per tutte le 256 chiavi Kj=j

calcolare Bj=Dj[a]. Se si trova una corrispondenza nella tabella (c) si è trovata una coppia di chiavi candidate che produce una coppia nota (P,C).

• Verificare le coppie di chiavi candidate su altre coppie testo in chiaro/testo cifrato. Se necessario, ripetere la procedura con un nuovo valore di a.


Schema di attacco (3/3)

• Date n coppie (P,C), la probabilità di successo per un singolo valore selezionato di A=a è n/264.

• Dalla teoria della probabilità è noto che il numero medio di tentativi per estrarre una pallina rossa da un’urna contenete n palline rosse e (N-n) verdi è (N+1)/(n+1).

• Pertanto il tempo si esecuzione dell’algoritmo èdell’ordine di

nnn

26464 log120256

11256 222


Triple DES con tre chiavi

• La sicurezza di Triple DES può essere ulteriormente incrementata usando chiavi crittografiche distinte per ciascuna fase:

• La compatibilità con DES si ha ponendo K3=K2 o K2=K1.

• Molte applicazioni per internet e per la gestione della posta elettronica hanno adottato Triple DES a tre chiavi (PGP, S/MIME, etc.).

]]][[[123

PEDEC KKK


I CAMPI FINITI


Campi finiti: Introduzione

• Ci occupiamo ora di “campi finiti”

• Rivestono un ruolo importante nellamoderna crittografia– AES, curva ellittica, IDEA, chiave pubblica

• Avremo a che fare con operazioni su“numeri”

• Inizieremo con alcuni concetti di algebra astratta


Gruppo

• Un insieme di oggetti, elementi o “numeri”

• Un’operazione il cui risultato appartieneall’insieme (chiusura)

• proprietà:– associativa: (a.b).c = a.(b.c)– Esistenza dell’elemento identico e: e.a = a.e = a– Esistenza dell’inverso a-1: a.a-1 = e

• Se vale la proprietà commutativa a.b = b.a– Si parla allora di gruppo abeliano


Gruppo Ciclico

• Si definisca esponenziazione l’applicazioneripetuta dell’operazione– esempio: a+3 = a.a.a, a-3 = a-1.a-1.a-1

• E si ponga: e=a0

• Un gruppo è detto ciclico se ogni elemento sipuò ottenere come potenza di un elementofisso, ovvero:– b = ak per qualche a and per ogni b nel gruppo

• a è detto generatore del gruppo


Anello

• Un insieme di “numeri” con due operazioni (addizione e moltiplicazione) che sono:

• Un gruppo abeliano per quanto riguarda l’addizione• La moltiplicazione gode delle proprietà:

– di chiusura– è associativa– è distributiva rispetto all’addizione: a(b+c) = ab + ac

• Se la moltiplicazione è commutativa si parla di anellocommutativo

• Se esiste l’identità per l’operazione di moltiplicazione e non vi sono divisori dello zero, si parla allora di dominiointegrale


Campo

• È un insieme di elementi su cui sonodefinite due operazioni (addizione e moltiplicazione)

• Gode di tutte le proprietà del dominiointegrale, con in aggiunta la proprietà cheogni elemento, ad eccezione dello 0, ha un inverso moltiplicativo


Aritmetica Modulare

• L’operazione a mod n da il resto intero delladivisione di a per n

• Si dice che a è congruente a b modulo n e si indica come: a ≡ b mod n se– a e b, divisi per n danno lo stesso resto

– esempio 100 = 34 mod 11

• Tale resto è detto residuo di a mod n

• Tale resto è compreso tra 0 e n-1 -12 mod 7 ≡ -5 mod 7 ≡ 2 mod 7 ≡ 9 mod 7


Esempio: Aritmetica Modulo 7

... -21 -20 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 67 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 ...


Divisori

• Un numero b diverso da 0 divide a se ilrapporto a/b è intero

• Si usa in tal caso la notazione b|a• E si dice che b è un divisore di a

• Esempio: 1,2,3,4,6,8,12,24 dividono 24: 2|24, 3|24, 4|24, ....


Operazioni in aritmeticamodulare

• L’aritmetica modulare usa un numero finitodi valori: le operazioni sono definite tuttemodulo un certo intero

• Nota che vale la proprietàa+b mod n=[a mod n + b mod n] mod n


Aritmetica Modulare

• Può essere realizzata con qualsiasi gruppo di interi: Zn = {0, 1, … , n-1}

• L’insieme Zn è un anello commutativo per l’addizione

• Esiste anche l’identità nella moltiplicazione• Nota che

– se (a+b)≡(a+c) mod n allora b≡c mod n– ma (ab)≡(ac) mod n allora b≡c mod n solo sea è relativamente primo con nES: 6x3=18 ≡ 2 mod n, 6x7=42 ≡ 2 mod n


Esempio: Aritmetica Modulo 8


Massimo Comun Divisore(Greatest Common Divisor)

• Il GCD (a,b) è il più grande intero chedivide contemporaneamente a e b– esempio GCD(60,24) = 12

• Se due numeri non hanno fattori comuni, illoro GCD è 1 e i numeri sono dettirelativamente primi– Esempio: GCD(8,15) = 1

– Quindi, 8 e 15 sono relativamente primi


GCD: Algoritmo di Euclide

• È un modo efficiente per calcolare il GCD(a,b)

• Utilizza il risultato:– GCD(a,b) = GCD(b, a mod b)

• Algoritmo di Euclide– A=a, B=b– while B>0

• R = A mod B• A = B, B = R

– return A


Esempio: GCD(1970,1066)

1970 = 1 x 1066 + 904 gcd(1066, 904)1066 = 1 x 904 + 162 gcd(904, 162)904 = 5 x 162 + 94 gcd(162, 94)162 = 1 x 94 + 68 gcd(94, 68)94 = 1 x 68 + 26 gcd(68, 26)68 = 2 x 26 + 16 gcd(26, 16)26 = 1 x 16 + 10 gcd(16, 10)16 = 1 x 10 + 6 gcd(10, 6)10 = 1 x 6 + 4 gcd(6, 4)6 = 1 x 4 + 2 gcd(4, 2)4 = 2 x 2 + 0 gcd(2, 0)


Campi di Galois

Born: 25 Oct 1811 in Bourg La Reine (near Paris), FranceDied: 31 May 1832 in Paris, France


Evariste Galois: Breve biografiaNato a Bourg-la-Reine nel 1811 da Nicholas Gabriel e Adelaide Marie Demante, due genitori interiggenti e con buone conoscenze nel campo della filosofia, della letteratura classica e della religione. La madre sarà la prima persona a curarsi della formazione del piccolo Evariste, fino all'età di 12 anni quando si iscrive al liceo Louis-le-Grand. I primi anni della sua carriera scolastica registrano buoni risultati in tutte le materie. Nel febbraio del 1827 Galois entra a far parte della sua prima classe di matematica di M. Vernier. Questi dirà di lui: "E' la passione per la matematica a dominarlo, penso che sarebbe meglio per lui se i suoi genitori lo obbligassero a studiare qualsiasi altra cosa, sta sprecando il suo tempo qui e non fa altro che tormentare i suoi insegnanti e ricoprirsi di punizioni."Le note scolastiche descriveranno spesso Galois come un ragazzo singolare, bizzarro, originale e chiuso. Nel 1928 Galois sostiene l'esame d'ammisione per l'Ecole Polytechnique, così torna al Louis-le-Grand però questa volta nella classe di Louis Richard. Lavora molto sulle proprie ricerche personali e molto poco sui propri compiti scolastici, tanto che Richard dice di lui: "Questo studente lavora soltanto nei più alti regni della matematica".L'Aprile del 1829 vede la prima pubblicazione di un articolo di Galois sulle frazioni continue sui prestigiosi Annales de mathématique. Seguiranno a questa altre pubblicazioni sulla risoluzione dell equazioni algebriche.Ma continueranno ancora le difficoltà con le istituzioni scolastiche, infatti fallirà anche il suo secondo tentativo di entrare all'Ecole Politechnique e dovrà 'rassegnarsi' ad entrare all'Ecole Normale di Parigi. Per entravi sostiene un esame al termine del quale il suo esaminatore di matematica riporterà la seguente nota:"Questo ragazzo è talvolta oscuro nell'esprimere le sue idee, ma è intelligente e mostra un notevole spirito di ricerca"Mentre il suo esaminatore di letteratura dirà:"Questo è l'unico studente che mi ha risposto scarsamente, non conosce assolutamente nulla. Ho sentito dire che questo studente ha straordinarie capacità per la matematica. Ciò mi stupisce enormemente, poiché, dopo il suo esame, ritengo che possegga una scarsa intelligenza"Galois spedisce a Cauchy i suoi lavori sulla teoria delle equazioni, ma viene a sapere di un articolo postumo di Abel che ricalca alcuni suoi risultati, così ritira i suoi lavori. Nel febbraio del 1930 invia a Cauchy un altro articolo Sulle condizioni per cui un equazione e risolvibile per radicali, il suo lavoro viene girato a Fourier per considerarlo in vista del Gran Premio della Matematica, ma Fourier muore pochi mesi dopo e i lavori di Galois vanno misteriosamente perduti. Ma le disavventure di Galois non finiscono qua. Il giovane matematico verra prima espulso dall'Ecole Normale e poi due volte arrestato per le sua focosa e attivissima militanza politica repubblicana. Galois si scontrò a duello con Perscheux d'Herbinville il 30 maggio 1832, le ragioni del duello non sono chiare, ma sembrano collegate in qualche modo ad una donna, Stephanie-Felice du Motel, di cui Galois si era invaghito qualche mese prima. Una sorte di legenda racconta che Galois passò la notte prima del duello a scrivere tutto ciò che sapevasulla teoria dei gruppi, è ragionevole pensare che ciò sia un po' esagerato. Comunque Galois fu gravemente ferito e lasciato sulla strada da d'Herbinville e dal suo secondo. Morirà in ospedale il giorno dopo, il 31 maggio 1832 quando non ha ancora compiuto i 21 anni.Il materiale di Galois fu ricopiato e spedito dal fratello e da un amico a Gauss, Jacobi e altri. I matematici del tempo si accorgeranno del patrimonio rappresentato da quegli appunti solo una decina di anni dopo. Il contenuto di quei fogli passa oggi sotto il nome di Teoria di Galois: in meno di 21 anni di vita Evariste Galois portò alla luce concetti ancora fondamentali per l'algebra moderna.


Campi di Galois

• Si è visto che affinchè Zn possa essere un campo, una condizione sufficiente è che n sia un numero primo

• Galois introdusse campi finiti con un numero di elementi pari a pn, ove p è un numero primo e n un intero positivo

• Tali campi sono detto campi di Galois e siindicano con GF(pn)

• Useremo i campi:– GF(p)– GF(2n)


Campo di Galois GF(p)

• GF(p) è l’insieme degli interi {0,1, … , p-1} con le usuali operazioni definite modulo p

• Tale insieme è un campo perchè ognielemento ha il suo inverso moltiplicativo

• Quindi le operazioni matematiche sono“well-behaved” e si possono fare le 4 usuali operazioni +, -, x, / senza lasciare ilcampo


Esempio: GF(7)


Calcolo dell’inversomoltiplicativo

• Si usa l’algoritmo di Euclide estesoEXTENDED EUCLID(m, b)1. (A1, A2, A3)=(1, 0, m);

(B1, B2, B3)=(0, 1, b)2. if B3 = 0

return A3 = gcd(m, b); no inverse3. if B3 = 1

return B3 = gcd(m, b); B2 = b–1 mod m4. Q = A3 div B35. (T1, T2, T3)=(A1 – Q B1, A2 – Q B2, A3 – Q B3)6. (A1, A2, A3)=(B1, B2, B3)7. (B1, B2, B3)=(T1, T2, T3)8. goto 2


Esempio: calcolo inverso di 550 in GF(1759)

355


Riepilogo


Riepilogo

• Campo: è un insieme su cui si possono eseguire le operazioni di +,-,x,/ senza uscire fuori dall’insieme.– Campi di ordine infinito sono i numeri reali, i numeri

razionali e i numeri complessi.– ZP={0,1,…,P-1}, con P numero primo, è un

campo se le operazioni vengono eseguite modulo P.

• In crittografia siamo interessati a lavorare su campi di ordine finito con un numero di elementi che sia una potenza di due.


Riepilogo

• E’ possibile costruire campi finiti di ordine Pn, con P numero primo e n intero (Galois Field).– Z2^n non è un campo per n>1.

• I campi GF(Pn) con n>1 hanno una struttura differente da Zp.

– Le operazioni su questi campi seguono le regole dell’aritmetica polinomiale modulare su GF(P)

• Per studiare questi campi è necessario introdurre alcuni concetti sull’aritmetica dei polinomi.


Aritmetica Polinomiale

• Fa uso di polinomi

f(x)=anxn+an-1xn-1+…+a1x+a0

• Vi sono varie alternative– Aritmetica ordinaria

– Aritmetica polinomiale con coefficienti mod p

– Aritmetica polinomiale con coefficienti mod p e polinomi mod M(x)


Aritmetica Polinomiale Ordinaria

• Si utilizzano le regole convenzionali

• Ad esempio– sia f(x) = x3 + x2 + 2 e g(x) = x2 – x + 1

f(x) + g(x) = x3 + 2x2 – x + 3

f(x) – g(x) = x3 + x + 1

f(x) x g(x) = x5 + 3x2 – 2x + 2


Aritmetica polinomiale con coefficienti modulo p

• I coefficienti sono scalati modulo p• L’insieme dei polinomi è in tal caso un anello

(anello polinomiale)• p può essere qualsiasi numero primo• Ci interessa tuttavia il caso p=2

– Ovvero, tutti i coefficienti sono o 0 o 1– La somma equivale allo XOR, la moltiplicazione

all’AND– Es.: sia f(x) = x3 + x2 e g(x) = x2 + x + 1f(x) + g(x) = x3 + x + 1f(x) x g(x) = x5 + x2



• Anche se l’insieme dei coefficienti è un campo, la divisione fra polinomi non sempre è esatta. In generale, la divisione produce un quoziente ed un resto:

)()()()()(

)()(

)(

)( xrxgxqxfxgxrxq

xgxf

+=↔+=

• Se il grado di f(x) è n ed il grado di g(x) è m (m<=n),allora il grado del quoziente q(x) è n-m ed il grado del resto è al più m-1.



• L’insieme di tutti polinomi i cui coefficienti sono elementidi un campo forma un dominio integrale (nota analogiacon l’insieme dei numeri interi).

• In analogia con l’aritmetica degli interi, si definiscer(x)=f(x) mod g(x).

• Se r(x)=0, allora g(x) divide f(x).

• se g(x) ha come soli divisori se stesso e 1, allora si dice essere un polinomio irriducibile (o primo).


Esempio

• Il polinomio f(x)=x4+1 su GF(2) è riducibile:– x4+1=(x+1)(x3+x2+x+1)

• Il polinomio f(x)=x3+x+1 su GF(2) è irriducibile:– Non è divisibile per x.– Non è divisibile per x+1.– f(x) non ha fattori di grado 1. Se fosse riducibile do-

vrebbe avere un fattore di grado 1 ed uno di grado 2.


Massimo Comune Divisore di polinomi

– c(x) = GCD(a(x), b(x)) se c(x) è il polinomiodi grado massimo che divide sia a(x) cheb(x)

– Si utilizza l’algoritmo di Euclide per il calcolo

– EUCLID[a(x), b(x)]

1. A(x) = a(x); B(x) = b(x)

2. if B(x) = 0 return A(x) = gcd[a(x), b(x)]

3. R(x) = A(x) mod B(x)

4. A(x) ← B(x)

5. B(x) ← R(x)

6 goto 2


Aritmetica polinomiale modulare

• Si consideri l’insieme S di tutti i polinomi di grado n-1 con coefficienti in Zp

f(x)=an-1xn-1+an-2xn-2+…+a1x+a0

• Si considerino le seguenti regole dell’aritmeticamodulare: 1. Si seguono le regole dell’aritmetica ordinaria fra

polinomi con due raffinamenti successivi.2. L’aritmetica sui coefficienti viene eseguita modulo P.3. Se la moltiplicazione produce un polinomio di grado

maggiore di n-1, viene ridotto modulo un polinomioirriducibile m(x) di grado n. In pratica, si divide per m(x) e si tiene il resto.


Aritmetica polinomiale modulare

L’insieme S con le regole dell’aritmetica modulare forma

un campo, GF(Pn)


IL Campo GF(2n)

– Sono polinomi con coefficienti modulo 2

– Il loro grado è minore di n

– Quindi devono essere ridotti in modulo tramite un polinomio irriducibile di grado n

• Formano un campo finito

• Quindi esiste sempre l’elemento inverso– L’algoritmo esteso di Euclide permette il calcolo

dell’inverso

• Ogni polinomio è in corrispondenza con unastringa di n bit!!! (ecco perchè li studiamo)


Esempio GF(23)

Polinomio irriducibile x3

+ x + 1


Esempio

AES usa l’aritmetica di GF(28), con polinomio irriducibile

m(x)=x8 + x4 + x3 + x8 +1

NOTA: Per costruire GF(28), infatti, c’è bisogno di scegliere un polinomio irriducibile di grado 8


Segretezza ecrittografia simmetrica


Sommario

• Potenziali punti di attacco

• Posizionamento della logica crittografica– Crittografia del collegamento

– Crittografia punto-a-punto

• Mascheramento del traffico

• Distribuzione della chiave

• Cenni sulla generazione di numeri casuali


Scenario tipico

• Workstation e Server connessi fra loro medianti reti LAN;

• Reti LAN di uno stesso edificio connesse fra loro mediante switch e router;

• Reti LAN geograficamente separate interconnesse mediante reti pubbliche a commutazione di pacchetto.


Possibili attacchi alla segretezza

• Analisi del traffico all’interno della rete locale (dall’interno o dall’esterno).

• Attacco all’armadio di cablaggio e/o ad uno qualsiasi dei collegamento fisici della rete.

• Analisi e/o alterazione dei pacchetti in transito nei nodi di commutazione delle reti di interconnessione pubbliche.


Tipi di attacco

• Attacco attivo– L’intruso deve assumere il controllo fisico di una

porzione di collegamento (in genere è necessario far uso di apparecchiature invasive).

– L’intruso è in grado sia di ascoltare che di modificare le trasmissioni.

• Attacco passivo– L’intruso non ha il controllo fisico del canale, ma è in

grado di ascoltare le trasmissioni (utilizzando mezzi non invasisi).


Crittografia del collegamento

• Ciascun collegamento fisico vulnerabile viene dotato di un dispositivo di crittografia.

• Vantaggi:– Tutto il traffico su tutti i collegamenti è sicuro– Ogni coppia di nodi ha una chiave univoca usata per tutti i

messaggi in transito– Facilità nella distribuzione delle chiavi

• Svantaggi:– Il messaggio è decrittografato (e dunque vulnerabile) negli switch– L’utente non controlla la sicurezza dei nodi della rete pubblica– Tutti i collegamenti devono essere crittografati– Assenza di autenticazione


Crittografia punto-a-punto

• Il processo di crittografia viene eseguito solo dai due sistemi terminali, ed è completamente trasparente ai nodi interni della rete di interconnessione.

• Vantaggi:– Dati protetti contro gli attacchi ai collegamenti o agli switch– Garantisce l’autenticazione

• Svantaggi:– La distribuzione delle chiavi è più complessa– L’indirizzo del destinatario non può essere crittografato


Crittografia del collegamento e punto-a-punto


Posizionamento logico della crittografia

• Crittografia del collegamento: livello fisico (1) o di collegamento (2) del modello OSI (Open System Interconnection).

• Crittografia punto-a-punto: livelli 3-7 del modello OSI.

• Spostandoci verso l’alto nella gerarchia dei livelli di comunicazione vengono crittografate meno informazioni, ma si ottiene una maggiore sicurezza sui dati. Inoltre, aumenta il numero di chiavi crittografiche da utilizzare.


Posizionamento logico della crittografia


Utilizzo delle chiavi

• Crittografia del collegamento: una singola chiave èutilizzata per crittografare tutti i dati in transito nel collegamento.

• Crittografia punto-a-punto a livello di rete: tutti i processi utenti e le applicazioni di un dato terminale T1 condividono la stessa chiave per comunicare con un altro terminale T2.

• Crittografia punto-a-punto a livello dell’applicazione:ogni processo utente o applicazione di un dato terminale T1 usa una propria chiave per comunicare con il corrispondente processo utente o applicazione del terminale T2


Analisi del traffico

• L’analisi del traffico può fornire informazioni su:– Identità dei partner– Frequenza di comunicazione dei partner– Lunghezza e/o quantità dei messaggi scambiati– Schema di trasmissione dei messaggi

• Schemi di traffico segreti possono essere impiegati per creare canali nascosti (ad esempio, pacchetto lungo = 0, pacchetto corto = 1).

• L’analisi del traffico è usata in ambito militare e commerciale.


Segretezza del traffico

• La crittografia punto-a-punto è estremamente vulnerabile all’analisi del traffico (essendo le intestazione dei pacchetti in chiaro). Contromisure:– inserimento di pacchetti nulli – pacchetti in uscita di uguale dimensione (maschera il volume di

dati scambiato)– crittografia del collegamento (maschera gli indirizzi finali)

• La crittografia del collegamento può essere resa piùsicura utilizzando la tecnica Traffic Padding: in assenza di testo in chiaro viene comunque prodotto un output cifrato in maniera casuale.


Traffic Padding


Distribuzione della chiave

• Dati due terminali A e B, si possono avere varie alternative per la distribuzione delle chiavi.

1. A sceglie una chiave e la consegna fisicamente a B;

2. Una parte terza C sceglie una chiave e la consegna fisicamente ad A e B;

3. Se A e B hanno usato recentemente una chiave, una delle parti trasmette all’altra parte la nuova chiave usando la vecchia chiave;

4. Se A e B hanno una connessione crittografata sicura con C, quest’ultima può consegnare una chiave sui collegamenti crittografati ad A e B;


Distribuzione della chiave

• Le opzioni 1 e 2 richiedono la consegna manuale della chiave: sono ragionevoli solo per la crittografia di un collegamento.

• L’opzione 3 è poco sicura: se una chiave viene violata, anche le chiavi successive saranno automaticamente violate.

• Per la crittografia punto-a-punto sono general-mente adottate delle varianti dell’opzione 4.


Centro di Distribuzione delle Chiavi (KDC)

• Per la crittografia punto-a-punto si assume che ci sia un centro responsabile della distribuzione delle chiavi alle coppie di utenti in base alle richieste.

• Sono utilizzati due livelli gerarchici di chiavi– Chiavi master: condivise fra ciascun utente e il KDC– Chiavi di sessione: utilizzate per la comunicazione fra due utenti

• Le chiave di sessione vengono trasmesse alle coppie di utenti in forma crittografata usando le chiavi master.

• Il problema della distribuzione delle chiavi è semplificato: se ci sono N terminali andranno consegnate fisicamente solamente N chiavi master.


Esempio di distribuzione della chiave di sessione

• KA chiave master di A (nota solo ad A ed al KDC)• KB chiave master di B (nota solo ad B ed al KDC)


Controllo gerarchico della chiave

• In reti di grandi dimensioni si possono definire centri gerarchici di distribuzione delle chiavi.– Ogni centro è responsabile di un piccolo dominio

– Per comunicazioni fra terminali dello stesso dominio, le richieste vengono gestite dal KDC locale

– Per comunicazione fra terminali in domini differenti, i KDC locali comunicano con un KDC globale per coordinare la scelta della chiave

• Vantaggi: maggiore robustezza ai guasti e semplicità nella distribuzione delle chiavi master.


Durata di una chiave di sessione

• Due esigenze contrastanti:– Maggiore è la frequenza con cui si cambiano le chiavi

di sessione, maggiore sarà la sicurezza delle chiavi.

– La distribuzione delle chiavi introduce un overheadiniziale ad ogni comunicazione, introducendo ritardi di trasmissioni. Inoltre, genera traffico nella rete.

• Regola pratica: vanno stabiliti tempi massimi di durata e/o numero massimo di transazionieffettuabili con una singola chiave di sessione.


Schema a controllo trasparente della chiave

• Per crittografie punto-a-punto a livello di rete orientate alla connessione, le operazioni di richiesta della chiave di sessione e di crittografia del messaggio possono essere delegate ad un processore esterno denominato FEP (Front-End-Processor).

• Con quest’approccio l’operazione di crittografia diviene trasparente ai singoli terminali:– Per il terminale e la rete esterna, il processore FEP

appare come un nodo di commutazione


Schema a controllo trasparente della chiave


Controllo della chiave decentralizzato

• In uno schema centralizzato, il KDC deve essere fidato e protetto contro ogni tipo di attacco.– I rischi derivanti da eventuali attacchi al KDC

potrebbero essere eliminati se il processo di distribuzione delle chiavi di sessione fosse decentralizzato.

• Una decentralizzazione completa in reti di grandi dimensioni non è pensabile. Tuttavia, è una valida alternativa in contesti locali.


Controllo della chiave decentralizzato

• Si assume che ci siano n terminali in grado di comunicare in modo univoco fra loro.– Sono richieste n(n-1)/2 chiavi master (la distribuzione può avvenire

di persona dato che queste chiavi non verranno più cambiate).

• Le chiavi di sessione vengono ottenute come segue:


Controllo dell’utilizzo delle chiavi

• Il concetto di gerarchia delle chiavi e l’uso di tecniche automatiche di distribuzione delle chiavi riduce notevolmente il numero di chiavi da distribuire manualmente.

• Per un corretto uso delle chiavi sessione distribuite dai KDC, può essere utile specificare la loro funzione:– Chiavi di sessione / Chiavi master– Chiavi di crittografia per dati– Chiavi di crittografia per codici PIN– Chiavi per crittografia di file – …


Esempio di controllo dell’utilizzo delle chiavi

• DES accetta in ingresso una chiave a 64 bit. Tuttavia, solo 56 bit vengono utilizzati per produrre le sottochiavi. I restanti 8 bit hanno il seguente significato:– Un bit indica se la chiave è di sessione o master

– Un bit indica se la chiave può essere utilizzata per la crittografia

– Un bit indica se la chiave può essere utilizzata per la decrittografia

– I bit rimanenti sono riservati per utilizzi futuri


Generazione di numeri casuali

• I numeri casuali vengono utilizzati in numerosi algoritmi crittografici:– Schemi di autenticazione

– Generazione chiave di sessione

– Generazione chiavi per l’algoritmo di crittografia RSA a chiave pubblica (che verrà studiato in seguito)

• Idealmente gli elementi di una sequenza casuale sono statisticamente indipendenti fra loro (ovvero, imprevedibili) ed uniformemente distribuiti.


Generazione di numeri casuali

• Trovare sorgenti di numeri effettivamente casuali è difficile.– I generatori fisici di rumore sono buone sorgenti, ma

sono poco pratici da usare.

• Un’alternativa è usare algoritmi numerici deterministici per la produzione di sequenze di numeri pseudo-casuali.– Se l’algoritmo è di buona qualità, le sequenza prodotte

passeranno numerosi test ragionevoli di casualità


Metodo della congruenza lineare

mXX

mcc

maa

mm

mcaXX nn

00

1

0 seme oiniziale valoreil

0 incrementol'

0 toremoltiplicail

0 moduloil

mod)(



• La scelta dei valori di a, c, e m è fondamentale per ottenere buone sequenza di numeri pseudo-casuali.

• Si vorrebbe che m fosse molto esteso in modo da produrre una lunga sequenza di numeri casuali distinti– m è scelto pari al massimo intero non-negativo

rappresentabile

• Si dimostra che una buona scelta è a=16807, c=0 e m=231-1 – La sequenza che si ottiene ha un periodo pari ad m



• Una volta fissati il seme ed i parametri a e c, la sequenza risultante di numeri segue in maniera deterministica.

• Nell’algoritmo non vi è nulla di casuale, se non la scelta dei parametri iniziali.

• La sequenza di numeri così generata può essere ricostruita da un estraneo che è a conoscenza dell’algoritmo e dei parametri usati.– Per evitare tale problema la sequenza viene

periodicamente riavviata usando come seme il valore dell’orologio interno del calcolatore.


Algoritmo AES (AdvancedEncryption Standard)


Origini di AES

• 3DES non rappresenta un buon candidato nel lungo periodo:– Esecuzione software lenta (DES era stato progettato agli inizi

degli anni ’70 per un’implementazione hardware)– Usa blocchi di 64 bit di dati (per motivi di efficienza e sicurezza

sarebbe preferibile utilizzare blocchi di lunghezza maggiore)

• Nel 1997 il NIST emette una richiesta di proposte per un nuovo standard chiamato (AES).

• Il nuovo standard dovrà progressivamente sostituire 3DES.


Origini di AES

• Requisiti minimi richiesti:– Doti di sicurezza uguali o maggiori a 3DES– Elevata efficienza computazionale– Blocchi dati di 128 bit / Lunghezza chiavi: 128, 192, 256 bit– Specifiche di progetto di pubblico dominio– Vita media 20-30 anni

• Inizialmente vengono accettate 15 delle 21 proposte.

• Successivamente i candidati sono ristretti a 5.

• Standard finale (FIPS PUB 197) pubblicato nel 2001. L’algoritmo selezionato è ‘RIJNDAEL’, sviluppato dai crittografi belgi Dr. Joan Daemen e Dr. Vincent Rijmen.


Criteri iniziali di valutazione di AES

• Sicurezza: Scartati gli attacchi a forza bruta, viene valutato l’impegno necessario per un analisi crittografica dell’algoritmo.

• Costo: algoritmo disponibile a tutti, ed utilizzabile in un ampia gamma di applicazioni; criteri di valutazione sono anche l’efficienza computazionale e i requisiti di memoria.

• Caratteristiche dell’algoritmo e dell’implementazione:flessibilità, possibilità di usare chiavi e blocchi di dati di varie dimensioni, possibilità di impiego in varie imple-mentazioni hardware e software, semplicità di analisi


AES: caratteristiche

• Sicurezza Generale: basato su un’analisi pubblica della sicurezza condotta dalla comunità dei crittografi (durata 3 anni).

• Implementazioni software: velocità di esecuzione, prestazioni su piattaforme differenti, velocità in funzione della lunghezza della chiave.

• Ambienti con spazio limitato: occupazione di memoria• Implementazione hardware: costi, velocità di

esecuzione e dimensioni dei chip.• Attacchi alle implementazioni: resistenza ad attacchi

che misurano il tempo di esecuzione e/o la potenza consumata.


AES: Caratteristiche

• Crittografia e Decrittografia: differenze fra gli algoritmi di crittografia e decrittografia.

• Agilità della chiave: tempo richiesto per impostare una nuova chiave, calcolo delle sottochiavi

• Flessibilità: possibilità di variare e/o ottimizzare i parametri dell’algoritmo in base al tipo di applicazione richiesta.

• Parallelismo: capacità di sfruttare le funzionalità di architetture multi-processore.


Cifratura AES

• Criteri progettuali dell’algoritmo RIJNDAEL:– Resistenza contro attacchi noti– Velocità e compattezza del codice – Semplicità

• Blocco dati: 128 bit / Lunghezza della chiave: qualunque multiplo di 32 bit.– In pratica si usano chiavi di 128, 192 e 256 bit

• I parametri dell’algoritmo dipendono dalla lunghezza della chiave (vedi lucido seguente).

• Nel seguito si considera una chiave a 128 bit.


Parametri Algoritmo


Dati Input Algoritmo AES


Schema Algoritmo

AES


Commenti su AES

• Non si tratta di una struttura di Feistel.

• La chiave viene espansa in 44 word da 32 bit. Ciascuna fase usa 4 word distinte.

• Operazioni effettuate– Substitute Bytes: blocchi di 8 bit sono sostituiti

mediante una S-box.

– Shift Rows: semplice permutazione.

– Mix Columns: sostituzione che usa l’aritmetica su GF(28), con il polinomio irriducibile m(x)=x8+x4+x3+x+1.

– Add Round Key: XOR bit-a-bit con la sottochiave.


Commenti su AES

• Tutte le trasformazioni sono invertibili.

• L’algoritmo di decrittografia usa le sottochiavi in ordine inverso.

• L’algoritmo di decrittografia non è identico a quello di crittografia.

• L’ultima fase della crittografia e della decrittogra-fia contiene solo tre trasformazioni.


Trasformazione Substitute Bytes(diretta)

• Viene definita una matrice 16x16 di byte detta S-box

• Ogni byte in ingresso viene mappato in un nuovo byte nel seguente modo:– I primi quattro bit indicano la riga e i rimanenti

4 bit la colonna– I valori di riga e colonna fungono da indici per

la S-box


Trasformazione Substitute Bytes(diretta)


Esempio

C5AD2DF0

B098335C

965D4583

856504EA

A695D88C

E746C34A

904C6EEC

974DF287

)01111001(7958)01011000(

)11010100(4D56)01010110(

)00101111(F204)01000000(

)01111000(87EA)10101110(

//

//

//

//

binesaSubBytesesabin




SubBytes


Progetto della S-box

• Inizializzare la S-box con il valore dei byte in sequenza ascendente. La prima riga contiene {00},{01},…,{0F}.

• Associate a ciascun byte della S-box il suo inverso moltiplicativo su GF(28), con il polinomio irriducibile m(x)=x8+x4+x3+x+1; {00} è mappato su se stesso.

• Considerare che ciascun byte della S-box è costituito da 8 bit (b7, b6,…, b0). Applicare la trasformazione:

)1,1,0,0,0,1,1,0()c,c,c,c,c,c,c,(ccon 01234567

8mod)7(8mod)6(8mod)5(8mod)4(

c

iiiiiii cbbbbbb


Progetto della S-box

• Progettata per resistere a tutti gli attacchi noti ad analisi crittografica.

• Bassa correlazione fra i bit in ingresso e in uscita (l’output non è una semplice funzione matematica dell’input).

• La costante additiva c è stata scelta in modo da non avere punti fissi (S-box(a)=a) e punti fissi opposti (S-box(a)=neg(a)).


Trasformazione Substitute Bytes(inversa)


Trasformazione Shift Rows

• Diretta: Riga 1 non viene modificata; Riga 2 scorrimento circolare a sx di un byte; Riga 3 scorrimento circolare a sx di 2 byte; Riga 4 scorrimento circolare a sx di 3 byte.

• Inversa: gli scorrimenti sono effettuati verso destra.


Esempio

A695D88C

E746C34A

904C6EEC

974DF287

95D88CA6

C34AE746

EC904C6E

974DF287

Shift Rows


Trasformazione Mix Columns(Diretta)

• Opera su una singola colonna: ciascun byte di una colonna viene mappato in un nuovo valore funzione dei 4 byte presenti nella colonna.

• Somme e moltiplicazioni sono eseguite secondo l’aritmetica di GF(28), con m(x)=x8+x4+x3+x+1.


Aritmetica su GF(28)

• La somma di due polinomi in GF(28) corrisponde all’operazione di XOR bit-a-bit.

{D4}}83{{57}

:eesadecimalnotazione

(11010100)(10000011)(01010111)

:binarianotazione

)1()1(

:epolinomialnotazione

ESEMPIO

24677246

xxxxxxxxxx


Aritmetica su GF(28)

• La moltiplicazione su GF(28) può essere difficile da implementare. Tuttavia, utilizzando come polinomio irriducibile m(x)=x8+x4+x3+x+1, si ha

1se

0se

)1,1,0,1,1,0,0,0()0,,,,,,,(

)0,,,,,,,()(

:

1se

0se

)1()(

)(mod)()(

)1(])([)(mod

7

7

0123456

0123456

7

7

340

21

32

43

54

65

76

02

13

24

35

46

57

6

02

13

24

35

46

57

68

7

012

23

34

45

56

67

7

3488

b

b

bbbbbbb

bbbbbbbxfx

b

b

xxxxbxbxbxbxbxbxb

xbxbxbxbxbxbxb

xmxbxbxbxbxbxbxbxbxfx

bxbxbxbxbxbxbxbf(x)

xxxxxmxmx

bitIn

cuida


Esempio

95D88CA6

C34AE746

EC904C6E

974DF287

BCA6A5ED

423AE494

9F70D437

4CA34047

MixColumns


Esempio (cont.)

}47{)01110100(

)01101010()01100100()00101011()01010001(

)00101011(

)11001101()11100110(})E6{}02({}E6{}E6{}03{

)01010001()10110001()11100000(}87{}02{

)01110100(}47{

),01101010(}A6{),01100100(}46{

),11100110(}6E{),01111000(}87{

}47{}6A{}46{})E6{}03({})87{}02({

/

/

/

/

//

//

esabin

binesa

binesa

binesa

binesabinesa

binesabinesa

:Infatti


Trasformazione Mix Columns(Inversa)

• Si usa una matrice di trasformazione che è l’inversa moltiplicativa della matrice di trasformazione diretta:

1000

0100

0010

0001

02010103

03020101

01030201

01010302

0E090D0B

0B0E090D

0D0B0E09

090D0B0E

con

0E090D0B

0B0E090D

0D0B0E09

090D0B0E

3,32,31,30,3

3,22,21,20,2

3,12,11,10,1

3,02,01,00,0

3,32,31,30,3

3,22,21,20,2

3,12,11,10,1

3,02,01,00,0

ssss

ssss

ssss

ssss

ssss

ssss

ssss

ssss


Trasformazione Mix Columns –Commenti generali

• Mix Columns combinata con Shift Rows garantisce che dopo alcune fasi tutti i bit di output dipendano da tutti i bit di input.

• La scelta dei coefficienti della trasformazione diretta {01}, {02} e {03} semplifica l’implementazione:– La moltiplicazione richiede al più uno scorrimento e uno XOR.

• La trasformazione inversa è invece più complessa da implementare.– Per le modalità Cipher Feedback e Output Feedback si usa solo

la crittografia.


Trasformazione Add Round Key(Diretta e Inversa)

• XOR della matrice di dati con i 128 bit della chiave di fase.

• Trasformazione molto semplice: sicurezza garantita dalla complessità dell’espansione della chiave e dalla comples-sità delle altre trasformazioni.


Esempio

BCA6A5ED

423AE494

9F70D437

4CA34047

6A4121F3

0029DC66

5CD1FA77

572819AC

D2E7841E

421338F2

C3A12E40

1B8B59EB

=

95)10010101()10010001()00000100(

)10010001(91),00000100(40

EB)10111110()11001010()01110100(

)11001010(AC),01110100(47

/

//

/

//

esabin

binesabinesa

esabin

binesabinesa


Schema di una fase di AES


Espansione della chiave

• A partire da una chiave di 4 word (16 byte) viene prodotto un array di 44 word (156 byte).

• L’espansione è descritta dal seguente pseudocodice:

}

}

temp;4]-w[i w[i]

Rcon[i/4];))tWord(tempSubWord(Ro temp0)4mod(i

1];-w[i temp

{

)i44;i4;(i

3]);key[4i2],key[4i1],key[4i(key[4i], w[i]),i4;i0;(i

temp;

{

w[44])key[16],(

if

for

for

word

wordbyteonKeyEspansi



• La chiave viene copiata nelle prime 4 word della chiave espansa.

• Ciascuna word aggiuntiva w[i] dipende da w[i-1] e w[i-4]:– Se i non è multiplo di 4, viene usata una

semplice funzione di XOR;

– Altrimenti viene usata una funzione piùcomplessa



• RotWord svolge uno scorrimento circolare a sinistra su una word

• SubWord svolge una sostituzione su ciascun byte della word utilizzando la medesima S-box della trasformazione Substitute Bytes diretta.

• Rcon[j] costante di fase. E’ una word in cui i tre byte più a destra sono zero. In esadecimale si ha: Rcon[j] = (RC[j],0,0,0), con

361B8040201008040201RC[j]

10987654321j


Schema di generazione delle prime 8 word della chiave espansa


Criteri usati per la generazione della chiave espansa

• Resistenza ad attacchi crittografici

• Trasformazione invertibile

• Alta velocità di esecuzione

• Uso di costanti di fasi per eliminare le simmetrie nelle varie fasi

• Ogni bit della chiave crittografica influenza piùbit della chiave espansa

• Algoritmo di generazione non lineare.

• Facilità di descrizione


Cifratura inversa equivalente

• Per la crittografia e la decrittografia di AES, la programmazione della chiave è la stessa, ma la sequenza di operazioni da effettuare è diversa.– Sono richiesti due moduli software o firmware per le

applicazioni che effettuano entrambe le operazioni

• Vi è una versione equivalente dell’algoritmo di decrittografia che usa la stessa sequenza di operazioni di quello di crittografia (invertendole), ma una diversa programmazione della chiave.


Cifratura inversa equivalente

• Scambio InvShiftRows e InvSubBytes: InvShiftRowsaltera la sequenza dei byte, ma non il loro contenuto; InvSubBytes agisce sul contenuto del byte, indipenden-temente dalla sua posizione Possono essere invertite.

• Scambio InvMixColumns e AddRoundKey: si ha

3

2

1

0

3

2

1

0

33

22

11

00

j

0E090D0B

0B0E090D

0D0B0E09

090D0B0E

0E090D0B

0B0E090D

0D0B0E09

090D0B0E

0E090D0B

0B0E090D

0D0B0E09

090D0B0E

)mns(InvMixColu)mns(InvMixColu)mns(SInvMixColu

w

w

w

w

s

s

s

s

ws

ws

ws

ws

wSw jjj

infatti


Aspetti implementativi

• Implementazione efficiente su CPU a 8 bit (presenti nelle smart card):– Add Round Key: semplice operazione di XOR

– Shift Rows: operazione di scorrimento dei byte

– Substitute Bytes: opera a livello del byte e richiede una tabella di soli (16x16) 256 byte

– Mix Columns: richiede solo scorrimenti e XOR

• Implementazione efficiente su CPU a 32 bit: tutte le operazioni possono essere espresse sulle word invece che sui singoli byte.


Algoritmo di crittografia Blowfish


Caratteristiche di Blowfish

• Sviluppato da Bruce Schneier (1993)

• Velocità: su CPU a 32bit può crittografare dati ad una frequenza di 18 cicli di clock per byte (DES, invece, richiede 50 cicli di clock per byte).

• Compatezza: può operare con 5KB di memoria.

• Semplicità: la struttura è facile da implementare (facilità di analisi).

• Sicurezza regolabile: lunghezza della chiave regolabile da 32 a 448 bit.

• Blocco dati: 64 bit


Generazione della sottochiave e della S-box

• Una chiave da 32 a 448 bit (ovvero, da 1 a 14 word da 32 bit) viene usata per:– generare 18 sottochiavi a 32 bit

– generare 4 S-box 256x32

• La chiave è conservata in una matrice K: K=[K1,K2,….,Kj] con 1≤j≤14.

• Le sottochiavi sono memorizzate in un array P: P=[P1,P2,….,P18]



• Ciascuna delle 4 S-Box è memorizzata in 256 voci da 32 bit:

255,41,40,4

255,31,30,3

255,21,20,2

255,11,10,1

,,,

,,,

,,,

,,,

SSS

SSS

SSS

SSS


1. Inizializzare prima l’array P e poi le 4 S-Box utilizzando i bit della parte frazionaria della costante π.

2. Svolgere uno XOR bit-a-bit dell’array P e dell’array K, riutiliz-zando ciclicamente le word dell’array K. Per esempio, per la chiave di lunghezza massima (14 word da 32 bit): P1=P1K1, P2=P2K2,…., P14=P14K14, P15=P15K1,…, P18=P18K4.

3. Crittografare un blocco di 64 bit nulli utilizzando P e le 4 S-Box correnti. Sostituire P1 e P2 con l’output della crittografia.

4. Crittografare l’output del passo 3 utilizzando P e le 4 S-Box correnti e sostituire P3 e P4 con l’output della crittografia.

5. Continuare questa operazione per aggiornare tutte le word di P e tutte le word delle 4 S-Box.



Commenti

• Per produrre l’array finale P e le 4 S-Box finali sono necessarie 521 esecuzioni consecutive dell’algoritmo di crittografia.– Blowfish non è adatto per applicazioni in cui la chiave

segreta cambia spesso

– Per memorizzare la matrice P e le 4 S-Box sono necessari più di 4 KB di memoria

– Resistente contro attacchi a forza bruta (fino ad ora la sicurezza di Blowfish è ritenuta inattaccabile!)


Crittografia e Decrittografia


Funzione F (S-Box)

Somma modulo 232

XOR


Funzione F (S-Box)

• Sono usate due operazioni primitive:– Somma di word, rappresentata con +,

eseguita modulo 232

– XOR bit-a-bit, rappresentato con

• L’input di 32 bit di F viene diviso in 4 byte. Se questi byte vengono indicati con a, b, c, d, si ha

F[a,b,c,d]=((S1,a+ S2,b) S3,c)+ S4,d)


Blowfish: descrizione

• La generazione di una chiave richiede 521 applicazioni dell’algoritmo: difficoltàdell’attacco a forza bruta

• La funzione F introduce un forte effetto valanga

• Le S-box dipendono dalla chiave

• La funzione F non dipende dalla fase


Crittografia a chiave pubblica

Cenni alla teoria dei numeri


Numeri Primi

• I numeri primi hanno come divisori solo se stessie l’unità– Non possono essere ottenuti dal prodotto di altri

numeri

• eg. 2,3,5,7 sono primi, 4,6,8,9,10 non lo sono• I numeri primi svolgono un ruolo fondamentale

nella teoria dei numeri• Ecco l’elenco dei numeri primi inferiori a 200:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199


Fattorizzazione in numeri primi

• Ogni intero può essere diviso in fattori in modo univoco

• N.B.: Fattorizzare un numero è alquantopiù complicato che ottenere il numero stesso mediante moltiplicazione dei fattori

• Esempi di fattorizzazione: 91=7×13 ; 3600=24×32×52



• In generale, dato un intero a, vale la relazione

a=p1a1p2

a2p3a3......

ossia

ove P è l’insieme dei numeri primi

0,

pPp

a apa p



• Il valore di un intero positivo lo si può specificare semplicemente indicando i valori degli esponenti non nulli, ossia:

12={a2=2, a3=1}, 18={a2=1,a3=2}

• La moltiplicazione di due numeri equivale alla somma degli esponenti:

• K=mn kp=mp+np, per ogni pP


Numeri Relativamente primi & GCD

• I numeri a,b sono relativamente primise, a parte l’unità, non hanno divisoricomuni, ovvero GCD(a,b)=1– e.g. 8 & 15 sono relativamente primi

• Il GCD può essere calcolato dallascomposizione in fattori primi– eg. 300=21×31×52 18=21×32, da cui:GCD(18,300)=21×31×50=6


Il Piccolo Teorema di FermatDato un numero primo p e un intero a tale che gcd(a,p)=1, è:

ap-1 mod p = 1

Pierre de FermatBorn: 17.09.1601 in Beaumont-de-LomagneDied: 12.01.1665 in Castres


Il Piccolo Teorema di Fermat: Prova (1/2)

• Poichè p è primo, Zp={0, ..., p-1} ètale che moltiplicando modulo p gli elementi di Zp per a, si riottengono gli stessi elementi di Zp in ordine diverso;

• Moltiplicando gli elementi di entrambi gli insiemi (ad eccezione dello 0) si ottiene

1 x 2 x ... x (p-1) mod p=(p-1)! mod p

a x 2a x ... x (p-1)a mod p=ap-1(p-1)! mod p


Il Piccolo Teorema di Fermat: Prova (2/2)

• Pertanto si ha– (p-1)!ap-1 mod p=(p-1)! mod p

• Semplificando (p-1)! (lo si può fare, perchè??) si ha la tesi.

Una formulazione equivalente del teorema è ovviamente

ap mod p = a


La Funzione Toziente di Eulero(n)

• Dato un intero positivo n, la funzionetoziente di Eulero (n) è pari al numero di interi positivi minori di n e primi relativi con n, ovvero

(n)=card({x Zn : gcd(x,n)=1})

• Esempi:

(3)=2, (5)=4, (6)=2.

• Nota: (p)=p-1, per ogni p numero primo



• Il calcolo di (n) richiede in genere la verifica e la conta esaustiva degli elementi di Zn

relativamente primi con n

• Valgono le seguenti eccezioni– Se p è primo (p) = p-1– Se p e q sono primi (pq) = (p-1)(q-1)

• eg.– (37) = 36– (21) = (3–1)×(7–1) = 2×6 = 12


Teorema di Eulero

• È una generalizzazione del teorema di Fermat

Se a e n sono primi relativi, allora

a (n) mod n = 1

• Esempi– a=3;n=10; (10)=4; – quindi 34 = 81 = 1 mod 10

– a=2;n=11; (11)=10;– hence 210 = 1024 = 1 mod 11


Teorema di Eulero: Prova (1/3)

• Se n è primo, (n)=n-1 e la prova èbanale (th. di Fermat)

• Se n non è primo, si considerino i (n) interi positivi minori di n e relativamenteprimi con n: R={x1, ... , x (n)}

• Si consideri ora l’insieme S dato da

S={ax1 mod n , ... , ax (n) mod n}



• L’insieme S coincide con R in quanto– a e xi sono entrambi primi relativi con n, e

quindi lo è anche axi. Pertanto gli elementi di S sono tutti interi minori di n e primi relativi di n

– in S non vi sono duplicati in quanto se axi

mod n = axj mod n, allora xi=xj.



Ma allora, se R=S, si ha

da cui segue banalmente la tesi.

Una forma alternativa del teorema èa (n)+1 mod n = a

)(

1

)(

1

modmodn

ii

n

ii nxnax


Perchè studiamo questa roba??

• Siano p e q due primi, sia n=pq e sia 0<m<n• Vale la relazione

m(n)+1 = m(p-1)(q-1)+1 mod n = m mod n

Se m ed n sono primi relativi, la relazione è vera per il teorema di Eulero. In realtà, tale relazione si dimostra essere valida anhe se m ed n non sono primi relativi

• Tale relazione è alla base del funzionamento dell’algoritmo RSA di crittografia a chiave pubblica


Test di primalità

• Nella crittografia, c’è bisogno di procedure per generare numeri primi grandi

• Dato un numero generato in manierapseudocasuale, bisogna stabilire se è un numero primo

• Una procedura sistematica consiste nel provarea dividere per tutti i numeri primi minori dellaradice quadrata del numero sotto test

• Chiaramente, al crescere di n tale approccio èinutilizzabile


Test di primalità

• Si ricorre quindi ad un approccio statistico, ovvero si usano test che garantiscono cheun numero sia primo “con una certaaffidabilità,” ovvero in senso probabilistico

• Tali test si basano sulla verifica di una proprietà– Soddisfatta da tutti i numeri primi– ... Ma usualmente soddisfatta anche da

qualche numero composto


Test di Fermat

• Il teorema di Fermat afferma che se n è primo, per ogni a<n tale che gcd(a,n)=1 si ha:

an-1=1 mod nEsempio: consideriamo 341=11 x 312340=1 mod 3413340=56 mod 341 341 è composto

• N.B.: Il test di Fermat permette di stabilire con certezza che un numero è composto, ma non può provare che esso sia primo

• Inoltre, il test di Fermat prova che un numero ècomposto, ma non fornisce la sua scomposizione in fattori primi


I numeri di Carmichael

• Consideriamo il numero 561=3 x 11 x 17

• E’ possibile verificare che, comunque si scelga a < 561 e primo con 561, il test di Fermat non riesce a dimostrare la non primalità di 561

• Sfortunatamente, esistono infiniti numeri di tal tipo

• Essi sono detti numeri di Carmichael


I numeri di Carmichael

• 561 è il più piccolo numero di Carmichael

• E’ stato dimostrato che esistono infiniti numeri di Carmichael

• 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, ... sono tutti numeri di Carmichael

• Di conseguenza, il test di primalità di Fermat non è affidabile!


Test di Miller Rabin

• E’ basato sul teorema di Fermat• Diamo l’algoritmo senza dimostrazione

TEST (n) is:1. Find integers k, q, k > 0, q odd, so that (n–1)=2kq2. Select a random integer a, 1<a<n–13. if aq mod n = 1 then return (“maybe prime"), STOP;4. for j = 0 to k – 1 do

5. if (a2jq mod n = n-1)

then return(" maybe prime "), STOP

6. return ("composite"), STOP



Esempio: n=29; n-1=28=22 x 7; si prenda a=10;

107 mod 29=17 che è diverso da 1 e –1

107 x 2 mod 29=28 MAYBE PRIME

Si riprovi con a=2



Di fatto, il risultato “maybe prime” si ottiene con tutti gli interi a compresi tra 1 e 28.



Esempio: n=221=13 x 17; n-1=220=22 x 55; si prenda a=5;


555 x 2 mod 221=168 COMPOSITE

Se avessimo scelto a=21 si sarebbe avuto



Di fatto, il risultato “maybe prime” si ottiene con 6 dei 220 interi compresi tra 1 e 220.


Considerazioni Probabilistiche

• Se l’esito del test di Miller-Rabin è “composite” il numeroè sicuramente non primo

• In caso contrario, potrebbe essere primo• È stato mostrato che, se n è composto, scegliendo a

caso la base a, la probabilità che il test dia come output “maybe prime” è < ¼

• Ripetendo il test t volte con basi a scelte a caso ho chela probabilità che il test dia un output “maybe prime” in presenza di un numero composto è 4-t

• Un numero composto viene identificato quindi con probabilità 1-4-t

– E.g., per t=10 tale probabilità è > 0.99999


Distribuzione dei numeri primi

• DOMANDA: Generato un numero dispari n grande, con che probabilità questo è un numeroprimo???

• Il “teorema dei numeri primi” stabilisce che, per n grande, i numeri primi sono spaziatimediamente ogni ln(n) interi

• Poichè non si considerano i numeri pari e quelliche terminano per 5, in pratica c’è bisogno in media di 0.4 ln(n) tentativi per poteridentificare un numero primo


Distribuzione dei numeri primi

• Nota però che questi sono risultati validi in media....

ESEMPI:– Gli interi consecutivi 1012+61 e 1012+63 sono

entrambi primi

– I numeri 1001!+2, 1001!+3, ... 1001!+1001 èuna sequenza di mille interi consecutivi e non primi


Il Teorema Cinese del Resto

• È utilizzato per velocizzare i calcolidell’aritmetica modulare

• Si supponga di dover lavorare modulo un certonumero M che è a sua volta prodotto di numeri a coppia relativamente primi– eg. mod M = m1m2..mk

• Il Teorema Cinese del Resto ci permette di lavorare con singolarmente modulo ciascuno deifattori mi

• Questo permette di risparmiare notevolmente in termini di risorse computazionali



• Il teorema afferma che è possibile ricostruire gli interi di un determinato intervallo a partire dai loro resti modulo una coppia di numeri relativamente primi

• ESEMPIO: Gli elementi in Z10 possono essere rappresentati dai loro resti modulo 2 e 5



• Sia M=m1m2 ...mk, con gcd(mi,mj)=1 per ogni i j

• Per ogni intero A ZM, posto ai=A mod mi,

la corrispondenza A (a1, a2, ..., ak) èbiunivoca

Si tratta in realtà di un mappaggio da ZM a Zm1 x Zm2 x .... x Zmk



• Si supponga di voler calcolare (A mod M)• Dapprima si calcolano separatamente gli ai =(A

mod mi) e poi si combinano insieme secondo le formule:

ove Mi=M/mi

kimMMc iiii 1per modx 1

McaAk

iii mod

1



ESEMPIO:M=1813=37 x 49, A=973a1=973 mod 37=11, a2=973 mod 49=42M1=49, M2= 37(49)-1 mod 37=34, (37)-1 mod 49=4 c1 =49 x 34=1666, c2 =4 x 37=148A=(1666 x 11 + 148 x 42) mod M=973


Radici Primitive

• Sappiamo dal teorema di Eulero che per a ed n primi relativi si ha a(n)mod n=1

• Si consideri l’equazione in m: ammod n=1, congcd(a,n)=1– Una soluzione è certamente m= (n), ma può esserci

una soluzione minore di (n)– Le potenze si ripetono poi ciclicamente

• Se la più piccola soluzione è m= (n) allora a èdetto una radice primitiva di n

• Se n è primo, allora le potenze successive di a generano Zp (=Zn)


Radici Primitive

ESEMPIO: Potenze di 7 modulo 19

71 mod 19 = 7

72 mod 19 = 11

73 mod 19 = 1

74 mod 19 = 7

75 mod 19 = 11

.......................


Radici Primitive

• Non tutti gli interi hanno radici primitive

• Gli unici interi con radici primitive sono nella forma 2, 4, p e 2p .

ESEMPIO:

Le radici primitive di 19 sono 2, 3, 10, 13, 14 e 15


Logaritmi Discreti

• Abbiamo trattato dell’esponenziazionemodulare

• La funzione inversa dell’esponenziazionemodulare è il cosiddetto logaritmodiscreto di un numero modulo p

• Il logaritmo di b in base a e modulo p èquell’intero x tale che ax = b mod p

• Si usa la notazione x=loga b mod p ox=inda,p(b)


Logaritmi Discreti

• In generale, non è garantita l’esistenza del logaritmo discreto

• Se a è una radice primitiva di m, allora illogaritmo in base a e modulo m esiste sempre– x = log3 4 mod 13 (ovvero trova x tale che 3x = 4 mod

13) non ha soluzione– x = log2 3 mod 13 = 4 per ricerca esaustiva

• N.B.: Mentre l’elevazione a potenza è alquantosemplice, il calcolo del logaritmo discreto èunanimemente riconosciuto non fattibile quando m diventa grande


Sommario

• Ieri abbiamo parlato di:– Numeri primi

– I Teoremi di Fermat e di Eulero

– Test di primalità (statistici)

– Il Teorema Cinese del Resto

– Logaritmi Discreti


Richiami Lezione Precedente

• Il Piccolo Teorema di Fermat

Dato un numero primo p e un intero a tale che gcd(a,p)=1, è:

ap-1 mod p = 1



• Il teorema di Eulero

Se a e n sono primi relativi, allora

a (n) mod n = 1



• I Test di primalità– Test di Fermat

– Numeri di Carmichael

– Test di Miller-Rabin

• Il Teorema cinese del resto



• Radici primitive:

a è detta radice primitiva di n se l’equazione am mod n=1, ammette come soluzione m più piccola m=(n).

Se n è primo, am mod n genera, al variare di m, tutti gli elementi di Zn ad eccezione dello 0



• Logaritmi discreti– Il logaritmo di b in base a e modulo p è

quell’intero x tale che ax = b mod p

– In generale, non è garantita l’esistenza del logaritmo discreto

– Se a è una radice primitiva di m, allora illogaritmo in base a e modulo m esiste sempre

– Il calcolo del logaritmo discreto di numerigrandi è complicato!!


Oggi parleremo di....

• Crittografia a chiave pubblica– L’algoritmo RSA

• Procedure per lo scambio delle chiavi


Crittografia a singola chiave

• Come detto più volte, la crittografia a chiavesegreta usa un’unica chiave

• La chiave è condivisa da trasmettitore e ricevitore

• Se la chiave è violata, la comunicazione non èpiù sicura

• La crittografia è simmetrica, ovvero i due attoridella comunicazione sono paritetici

• Quindi il ricevitore potrebbe coniare un messaggio, crittografarlo e sostenere che tale messaggio sia stato inviato dal trasmettitore!!



• Probabilmente, trattasi della scoperta piùimportante nella storia millenaria dellacrittografia

• utilizza due chiavi: una è pubblica e una èprivata

• È asimmetrica poiché i soggetti dellacomunicazione non sono uguali

• Si basa su concetti avanzati della teoria deinumeri

• Tuttavia, essa complementa e non rimpiazzal’uso della crittografia simmetrica



• La crittografia a chiave pubblica/a due chiavi/asimmetrica si basa sull’uso di due chiavi: – una chiave pubblica, che è pubblicamente

nota, ed è usata per criptare messaggi e verificare le firme

– una chiave privata, nota solo a soggettodella comunicazione, usata per decriptare i messaggi e firmare i messaggi



• è asimmetrica perchè– Coloro che criptano i messaggi o verificano le

firme non possono decriptare i messaggi o creare le firme


Crittografia a chiave pubblicaCrittografia



Autenticazione


Perchè è stata inventata la crittografia a due chiavi??

• Per risolvere due problemi fondamentali:– La distribuzione della chiave – come

possono aversi comunicazioni sicure senzadover porre fiducia in un KDC?

– Firme digitali – come è possibile verificareche un messaggio proviene in forma intattadal presunto mittente?



• Fu introdotta nel 1976 da Whitfield Diffie e Martin Hellman, all’epoca ricercatoripresso la Stanford University (California)



• Di fatto, il concetto di crittografia a chiave pubblica era già noto alla NSA dalla metàdegli anni 60.

• Il lavoro di Diffie&Hellman indusse gli studiosi di crittografia a progettare schemi a chiave pubblica.

• Nel 1977, Ron Rivest, Adi Shamir e LenAdleman del MIT concepirono l’algoritmo RSA


Caratteristiche

• Gli algoritmi a chiave pubblica si basano su due chiavi con le seguenti caratteristiche– È computazionalmente irrealizzabile trovare la chiave

di decriptazione sulla base della conoscenzadell’algoritmo e della chiave di criptazione

– È computazionalmente facile criptare e decriptare i messaggi se si conoscono le rispettive chiavi

– Una delle due chiavi può essere usata per la cifratura, e l’altra deve essere usata per la decifratura (solo però in alcuni schemi)


Combinazione di segretezza e autenticazione


Applicazioni della Crittografia a chiave pubblica

• Gli usi rientrano in tre categorie:– Criptazione/decriptazione (per ottenere la

segretezza)

– Firma digitale (per ottenere l’autenticazione)

– Scambio di chiavi (ovvero, di chiavi di sessione)

• Alcuni algoritmi possono essere usati per tutti e tre gli usi, altri no.


Sicurezza degli schemi a chiavepubblica

• Come nella crittografia simmetrica, l’attacco a forza bruta è sempre teoricamente possibile

• Si usano chiavi molto lunghe (>512bits) • La sicurezza si basa sulla difficoltà della

criptoanalisi• In generale, si sa come rompere il codice, solo

che ciò è talmente complicato da essereirrealizzabile

• Bisogna utilizzare numeri molto grandi• Gli schemi a chiave pubblica sono più lenti degli

schemi a chiave segreta


RSA

• by Rivest, Shamir & Adleman del MIT in 1977 • È lo schema a chiave pubblica maggiormente

noto ed usato• È basato sull’elevazione a potenza in aritmetica

modulo un intero molto grande– N.B. l’esponenziazione richiede O((log n)3) operazioni

(è facile)

• Utilizza interi dell’ordine di 1024 bit• La sicurezza è basata sulla difficoltà nel

fattorizzare grandi numeri interi– N.B. la fattorizzazione richiede O(e log n log log n)

operazioni (è complicata)


RSA

• Il testo in chiaro è cifrato a blocchi; ogni blocco è un intero minore di un dato n

• Ovvero il blocco è lungo k bit con 2k<n

• Detto M il plaintext e C il ciphertext, le operazioni di crittografia e decrittografia si esprimono:

C=Me mod n

M=Cd mod n=Med mod n


RSA

• n è noto sia al mittente che al destinatario

• Il mittente conosce e (che è pubblica)

• Solo il destinatario conosce d

• Quindi KR={d, n}, KU={e, n}


RSA

• Requisiti:– È possibile trovare i valori di n, d, e tali che Med mod n =M,

– È relativamente facile calcolare Me e Cd per tutti i valori di M<n

– È computazionalmente impossibile determinare d sulla base di e ed n


Scelta delle chiavi in RSA (1/2)

• Le due chiavi di ciascun utente sonoscelte come segue:

• Si generano due numeri primi molto grandi: p,q

• Si pone poi n=pq– Nota che (n)=(p-1)(q-1)

• Si seleziona in maniera aleatoria la chiavee

• ove 1<e<(n), gcd(e,(n))=1


Scelta delle chiavi in RSA (2/2)

• La chiave di decriptazione d è l’inversa di e modulo (n)– d=e-1 mod (n) con 0≤d≤n

• La chiave pubblica di criptazione è: KU={e,n}

• La chiave segreta di decriptazione è: KR={d,p,q}


Uso di RSA

• Per criptare un messaggio M il mittente:– Si procura la chiave pubblica del destinatarioKU={e,n}

– calcola: C=Me mod n, ove 0≤M<n

• Per decriptare il testo cifrato C ildestinatario:– utilizza la sua chiave privata KR={d,p,q}

calcolando la quantità M=Cd mod n

• N.B. Deve essere M<n


RSA: Perchè funziona? (1/2)

• Per il teorema di Eulero è: a(n)mod n = 1 – ove è gcd(a,n)=1

• Un corollario del teorema di Eulero, che non dimostriamo, stabilisce che

– Dati due numeri primi p e q e gli interi n=pq, m<n, e k>0, vale la relazione

mk(n)+1=m mod n


RSA: Perchè funziona? (2/2)

• in RSA si ha:– n=pq– (n)=(p-1)(q-1)– e e d sono selezionati in modo che siano inversi in

aritmetica modulo (n)– Quindi è ed=1+k (n) per qualche k

• Da cui:Cd = (Me)d = M1+k(n) = M (M(n))k = M (1)k = M1 = M mod n


RSA

• In sintesi, i valori di n ed e sono noti

• d si potrebbe ottenere calcolando l’inverso di e modulo (n)

• Tuttavia (n) è incalcolabile, a meno che non si sappia che n = pq e che quindi

(n)=(p-1)(q-1)• Ecco perchè la forza di RSA si basa sul fatto che

è difficile fattorizzare grandi numeri interi.


RSA: Un esempio

1. Seleziona i numeri primi: p=17 & q=11

2. Calcola n = pq =17×11=187

3. Calcola (n)=(p–1)(q-1)=16×10=160

4. Seleziona e : gcd(e,160)=1; scegli e=7

5. Determina d: de=1 mod 160 e d < 160 tale valore è d=23 poichè 23×7=161= 10×160+1

6. La chiave pubblica è KU={7,187}

7. La chiave privata è KR={23,17,11}


RSA: Un Esempio

• Esempio di criptazione e decriptazione• Si consideri il messaggio M = 88 (n.b. 88<187)

• criptazione:C = 887 mod 187 = 11

• decriptazione:M = 1123 mod 187 = 88


Esponenziazione modulare

• Algoritmo “Square and Multiply”

• Permette di effettuare l’esponenziazione in modo veloce ed efficiente

• La base della potenza viene ripetutamente elevata al quadrato

• Vengono poi moltiplicati insieme solo i valori necessarialla formazione del risultato finale

• Si utilizza la rappresentazione binaria dell’esponente

• La complessità è O(log2 n) – eg. 75 = 74.71 = 3.7 = 10 mod 11

– eg. 3129 = 3128.31 = 5.3 = 4 mod 11


RSA: Generazione delle chiavi

• Per usare RSA si deve:– Determinare in modo aleatorio 2 numeri primi p e q

– selezionare e o d e calcolare l’altro

• I primi p,q non devono essere facilmentederivabili dal prodotto n=p.q– Devono quindi essere sufficientemente elevati

– Si usa il test di primalità di Miller-Rabin

• Tipicamente e si sceglie piccolo, in modo che dsia grande


Sicurezza di RSA

• Vi sono 3 strategie di attacco a RSA:– Ricerca a forza bruta (non è fattibile perchè la

chiave è lunga)– Attacchi matematici (cercano di fattorizzare n,

o di calcolare (n))

– Attacchi a tempo (carpiscono informazioni daitempi impiegati per la decriptazione)


Attacco matematico

• L’attacco matematico si svolge in 3 modi:– Si fattorizza n=pq, e quindi si trova (n) e

poi d

– Si trova (n) direttamente e quindi d

– Si cerca direttamente d

• Si ritiene che la difficoltà di tali attacchi siala stessa

• RSA è sicuro se n è lungo circa 1000 bit


Attacchi a tempo

• Si sono sviluppati dalla metà degli anni ‘90

• Misura i tempi di esecuzione delle esponenziazioni

• Possibili contromisure:– Utilizzo di un tempo di esponenziazione

costante

– Introduzione di ritardi aleatori

– Inserimento di valori spuri nei calcoli


Gestione della chiave

• La crittografia a chiave pubblica aiuta a risolvere il problema della distribuzionedelle chiavi

• Dobbiamo occuparci...– Della distribuzione delle chiavi pubbliche

– Dell’uso della crittografia a chiave pubblicaper distribuire chiavi di sessione


Distribuzione delle chiavipubbliche

• Vi sono 4 possibili strategie– Annuncio pubblico

– Elenco pubblico

– Autorità di distribuzione delle chiavi pubbliche

– Certificati con chiave pubblica


Annuncio pubblico

• Gli utenti distribuiscono le chiavi pubblichetramite messaggi di broadcast o in allegato ai loro messaggi– e.g., aggiungendo le chiavi alla fine delle loro

e-mail o sui newsgroup

• Vi è però un grande punto debole....– Chiunque può spacciarsi per un altro e

pubblicare una chiave falsa– Un utente malizioso può quindi spacciarsi per

un altro


Elenco Pubblico

• Maggiore sicurezza si ha registrando le chiavipresso un elenco pubblico

• Tale elenco è tale che:– Contiene voci del tipo {nome,chiave pubblica}– Gli utenti registrano la loro chiave in forma sicura– Gli utenti possono sostituire la chiave quando

vogliono– L’elenco viene pubblicato periodicamente– L’elenco può essere consultato elettronicamente (in

modo protetto)

• L’elenco pubblico può comunque essere violato


Autorità di distribuzione delle chiavi pubbliche

• Migliora la sicurezza mediante un controllo piùrigido sulla distribuzione delle chiavi

• Si tratta ancora di un database di chiavi• Gli utenti devono conoscere la chiave pubblica

dell’autorità di distribuzione• Gli utenti interagiscono con l’autorità per

ottenere in modo sicuro la chiave pubblica di altri utenti– È richiesto quindi l’accesso in tempo reale al

database ogno volta che sono richieste delle chiavi


Autorità di distribuzione delle chiavi pubbliche


Certificati a chiave pubblica

• Permettono lo scambio delle chiavi senzabisogno di dover accedere in tempo reale al database pubblico appena considerato

• I certificati possono essere usati direttamentedagli utenti per scambiarsi le chiavi

• Ciascun certificato contiene una chiavepubblica, informazioni supplementari (periodo di validità, condizioni di uso, etc.), e la firma dell’autorità di certificazione (CA)

• Un utente invia agli altri la propria chiavetrasmettendo il proprio certificato


Certificati a chiave pubblica


Distribuzione delle chiavi segretetramite chiavi pubbliche

• I metodi presentati permettono di ottenere la chiave pubblica

• Possono essere utilizzati per la segretezza e l’autenticazione

• ...ma gli algoritmi a chiave pubblica sono lenti• Quindi si preferisce commutare sulla crittografia

a chiave segreta• Bisogna quindi scambiarsi una chiave di

sessione• Vi sono varie strategie...


Semplice distribuzione (Merkle, 1979)

• proposta da Merkle nel 1979– A genera una coppia di chiavi– A invia a B la chiave pubblica e la sua identità (in

forma non protetta!!!)– B genera una chiave di sessione K e la invia ad A

criptata con la chiave pubblica di A– A decripta la chiave di sessione e comincia la

comunicazione

• Il problema è che un intruso può intercettare ilprimo messaggio e impersonare entrambi i soggetti della comunicazione


Distibuzione della chiave con segretezza e autenticazione

• Si utilizza in tal caso la crittografia a chiave pubblica


Scambio delle chiavi Diffie-Hellman

• È il primo tipo di schema a chiave pubblica• by Diffie & Hellman in 1976 insieme

all’esposizione del concetto di crittografiaa chiave pubblica– N.B.: dal 1987 si sa che James Ellis (UK

CESG) aveva proposto tale tecnica nel 1970

• È un metodo pratico per lo scambiopubblico di una chiave segreta

• Usato in molti prodotti commerciali


Scambio delle chiavi Diffie-Hellman

• Lo schema di Diffie-Hellman– Non può essere usato per scambiarsi un

messaggio arbitrario– Ma solo per stabilire una chiave nota solo ai

due soggetti della comunicazione

• È basato sul concetto di esponenziazionein un campo finito di Galois

• La sua sicurezza si basa sulla difficoltà nelcalcolare i logaritmi discreti


Diffie-Hellman: Inizializzazione

• Gli utenti concordano dei parametricomuni e noti:– Un grande numero primo o polinomio q

– α, una radice primitiva di q

• Ogni utente (eg. A) genera la sua chiave– sceglie un numero: xA < q

– Calcola la chiave pubblica: yA =αxA mod q

• A rende poi nota la chiave yA


Diffie-Hellman: Scambio delle chiavi

• La chiave di sessione per A e B è KAB: KAB = α

xA.xB mod q= yA

xB mod q (che B può calcolare) = yB

xA mod q (che A può calcolare)

• KAB è poi usata come chiave di sessione in uno schema di crittografia a chiave segreta tra Alice e Bob

• L’attacco a tale schema richiede che vengacalcolato XA, ovvero il logaritmo discreto di yA in base α e modulo q


Diffie-Hellman: Esempio

• Alice & Bob vogliono scambiarsi le chiavi;• Concordano su q=353 e α=3• Selezionano in modo random le chiavi segrete:

– A sceglie xA=97, B sceglie xB=233

• Calcolano le chiavi pubbliche:– yA=3

97mod 353 = 40 (Alice)

– yB=3233

mod 353 = 248 (Bob)

• Calcolano la chiave di sessione segreta:KAB= yB

xA mod 353 = 24897

= 160 (Alice)KAB= yA

xB mod 353 = 40233

= 160 (Bob)


Autenticazione dei messaggi e funzioni hash


Autenticazione

• L’autenticazione serve a: – Proteggere l’integrità del messaggio– Validare l’identità del mittente– Garantire la non ripudiabilità

• In generale, tre possibili approcci sonopossibili:– Criptazione dei messaggi– message authentication code (MAC)– Funzioni hash


Requisiti di Sicurezza

• In generale, sono possibili i seguenti attacchi– Violazione della segretezza– Analisi del traffico– Mascheramento (inserzione di messaggi fasulli)– Modifica dei contenuti– Modifica della sequenza dei messaggi– Modifica temporale– Ripudiazione dell’origine (l’origine nega di aver

trasmesso il messaggio)– Ripudiazione della destinazione (la destinazione nega

di aver trasmesso il messaggio)


Criptazione dei messaggi

• Abbiamo già visto che la criptazione ècapace di fornire in una certa misuraanche l’autenticazione

• Se è utilizzata la crittografia simmetrica:– Il destinatario sa che l’informazione arriva dal

mittente

– Se il messaggio è strutturato (ad esempiomediante bit di ridondanza) è possibilerivelarne eventuali alterazioni


Controllo degli errori interno

In questo caso si garantisce l’autenticazione


Controllo degli errori esterno



• Se è utilizzata la crittografia a due chiavi:– La criptazione con la chiave privata del

mittente non assicura la segretezza

– Tuttavia se:• Il mittente firma il messaggio con la proprie chiave

privata

• Poi lo cripta con la chiave pubblica del destinatario

• Si consegue sia la segretezza sia l’autenticazione



• Se il ricevente conserva una copia del messaggio criptato, può dimostrare che èstato inviato dal mittente!!

• C’è ancora bisogno di riconoscereeventuali messaggi alterati

• Tale schema richiede un totale di 2 crittografie e decrittografie per messaggioinviato


Message Authentication Code (MAC)

• E’ una tecnica alternativa: viene generato un piccolo blocco di dati che– Dipende sia dal messaggio che da una chiave

segreta– Differisce dalla criptazione perchè tale trasformazione

non deve essere reversibile

• Il MAC viene aggiunto al messaggio come se fosse una firma

• Il destinatario può calcolare il MAC e verificareche il messaggio è giunto integro e proviene dalmittente


Message Authentication Code (MAC)

• La funzione MAC è del tipo many-to-one• Ad esempio, se

– n è la lunghezza del MAC– N è il numero di possibili messaggi– k è la lunghezza della chiave

• Allora:– Vi saranno solo 2n<<N diversi codici MAC– Ciascun codice MAC sarà generato mediamente da N / 2n diversi messaggi

– Vi saranno 2k diversi mappaggi dal set dei messaggi al set dei codici MAC


Modi di Uso del MAC

Autenticazione senza segretezza


Modi di Uso del MAC

Autenticazione e segretezza;Codice MAC concatenato al plaintext


Modi di Uso del MAC

Autenticazione e segretezza;Codice MAC concatenato al ciphertext


Codici MAC

• Il MAC può essere quindi abbinato alla crittografia per fornire segretezza– In genere si usano chiavi diverse per autenticazione e

segretezza

– In genere si preferisce concatenare il MAC al testo in chiaro

• Perchè usare il MAC per garantire l’autenticazionequando basta anche la crittografia?– A volte è richiesta solo l’autenticazione

– Il MAC richiede minori risorse computazionali

– A volte l’autenticazione deve essere conservata per verificareogni volta l’integrità dei dati memorizzati


MAC=firma digitale?

• Si noti che il MAC non fornisce il serviziodi firma digitale!

• Infatti, mittente e destinatario condividonola stessa chiave


Proprietà dei MAC

• Il MAC è sostanzialmente un checksum crittograficoMAC = CK(M)

– Condensa un messaggio di lunghezzavariabile

– Utilizzando una data chiave segreta K– Il MAC ha lunghezza fissa

• È una funzione many-to-one– Molti messaggi possono avere lo stesso MAC


MAC: Esempio di attacco

• Si supponga k>n (la chiave è più lunga del codice MAC)

• Dati M1 e MAC1 l’estraneo calcola il MAC su M1per tutte le possibili 2k chiavi

• Il numero di corrispondenze è 2k-n

• Dati M2 e MAC2 l’estraneo calcola il MAC su M2per tutte le 2k-n chiavi candidate

• E così via.....• N.B. C’è bisogno di diverse coppie di messaggi

e dei relativi codici MAC


Requisiti di sicurezza dei MAC

1. Noto un messaggio ed il MAC è impossibiletrovare un altro messaggio cui corrisponde lo stesso MAC (assumendo ovviamente che la chiave non sia nota)

2. I MAC devono essere uniformemente distribuiti(ovvero, scelti a caso 2 messaggi, i loro MAC coincidono con probabilità 2-n )

3. Il MAC deve dipendere in “egual maniera” datutti i bit del messaggio


Codici MAC basati su DES


Codici MAC basati su DES

• Si può in realtà utilizzare qualsiasi schema crittografico a blocchi

• Data Authentication Algorithm (DAA) è un codice MAC ampiamente usato basato su DES-CBC– usa IV=0 e uno zero-padding del blocco finale– Cripta i messaggi usando DES in modalità CBC– Il MAC è il blocco finale, o i primi M bit (16≤M≤64) del

blocco finale

• Nota che la lunghezza del MAC finale è peròtroppo corta per garantire la sicurezza


Funzione Hash

• Associa a messaggi di lunghezzaarbitraria una stringa di lunghezza fissa

• A differenza del MAC, la funzione hash ènota e non dipende da alcuna chiave

• Viene usata per rivelare cambi in un messaggio

• Può essere usata in vari modi• Può servire anche a creare una firma

digitale


Uso delle funzioni hash – chiave segreta

Garantisce segretezza e autenticazione;B può però coniare un messaggio e dire che è statoInviato da A


Uso delle funzioni hash – chiave segreta

Viene crittografato solo il codice hash;Nota che hash + crittografia = codice MAC


Uso delle funzioni hash – chiave pubblica

Viene crittografata solo la funzione hash con la chiave privata del mittente.

Si tratta della tecnica a firma digitale!!


Uso delle funzioni hash – chiave pubblica + chiave segreta

Firma digitale + segretezza con crittografia a chiave segreta(tale tecnica è ampiamente utilizzata)


Uso delle funzioni hash

Viene utilizzata la funzione hash ma senza la crittografia;si assume che trasmettitore e ricevitore condividano unvalore segreto comune S


Uso delle funzioni hash

Tale schema differisce dal precedente per l’aggiunta della segretezza


Requisiti delle funzioni Hash

1. Può essere calcolate per messaggi M di qualsiasi dimensione

2. Produce un output h di lunghezza fissa3. h=H(M) è facile da calcolare qualunque sia M4. dato h è impossibile trovare x : H(x)=h

• Proprietà “one-way”

5. dato x è impossibile trovare y : H(y)=H(x)• Resistenza debole alle collisioni

6. È impossibile trovare una coppia x,y : H(y)= H(x)

• Resistenza forte alle collisioni


Semplici funzioni hash

• Una funzione hash molto comune èbasata sull’uso della XOR

• Non è una scelta sicura in quanto ilmessaggio può essere manipolato senzache l’hash cambi

• Tale funzione deve essere quindiaccoppiata con una funzione crittografica


Esempio


Attacchi a compleanno

• Le funzioni hash sono vulnerabili all’attacco a compleanno

• L’attacco a compleanno opera nel modo seguente:– L’origine A firma un messaggio con un codice hash di m bit e

crittografandolo con la sua chiave privata– L’attaccante genera 2

m/2 varianti del messaggio valido tutte con lo stesso significato

– L’attaccante genera inoltre 2m/2 varianti di un messaggio

fraudolento che si vuole inviare– I due set di messaggi sono confrontati per trovare una coppia

con lo stesso hash (la probabilità che ciò accada è > 0.5 per ilparadosso del compleanno)

– L’attaccante può quindi sostituire i messaggi

• La lunghezza del codice hash deve quindi esserenotevole


Una lettera in 237

varianti


Il Paradosso del compleanno

• Sia n=2m il numero di possibili funzioni hash

• Dato un Y, scelto un messaggio X a caso, la probabilità che H(X)=H(Y) è 1/n; la probabilità che H(X)H(Y) è (1-1/n)

• Scelti k valori casuali di X, la probabilitàche nessuno di tali messaggi verifichi l’uguaglianza è (1-1/n)k


Il Paradosso del compleanno

• Ne consegue che la probabilità che vi sia almeno una corrispondenza su k è:

1-(1-1/n)k k/n

• Ne consegue quindi che, al crescere di k la probabilità di trovare una coincidenza non è trascurabile


Funzioni Hash basate su Cifrari a Blocchi

• I cifrari a blocchi possono essere usati per creare funzioni hash– Ad esempio, posto H0=0

– calcola: Hi = EMi [Hi-1], con Mi blocco i-esimo del messaggio

– Si usa l’ultimo blocco come codice hash

– Nota che non c’è una chiave!

• Il codice hash risultante può essere troppopiccolo (64-bit)– Vulnerabile ad attacchi crittografici tra cui l’attacco a

compleanno


Algoritmi di generazione di funzioni hash


Algoritmi hash

• Vi sono analogie tra l’evoluzione delle funzionihash e quella dei cifrari simmetrici– Aumento dell’efficacia degli attacchi a forza bruta

– Ne consegue un’evoluzione degli algoritmi

– e.g., da DES ad AES nei cifrari a blocchi

– da MD4 & MD5 a SHA-1 & RIPEMD-160 neglialgoritmi hash

• Anche gli algoritmi hash usano strutture iterative, analoghe alla struttura di Feistel nei cifrari a blocco


MD5

• Progettato da Ronald Rivest (la R di RSA)• È succesivo ai precursori MD2 e MD4• Produce un codice hash di 128 bit; l’input

è elaborato in blocchi di 512 bit• È stato uno dei più usati algoritmi hash

fino a qualche anno fa– Recentemente sono sorti dubbi sulla sua

vulnerabilità agli attacchi a forza bruta

• È anche un Internet standard (RFC1321)


MD5 Overview

• La lunghezza del messaggio è resa pari a 448 mod 512

• Viene poi aggiunta una stringa di 64 bit, contenente la lunghezza mod 264 del messaggio originale (si parte dal LSB; si ottiene così una stringa multipla di 512)

• Vengono inizializzati i 4 buffer da 32 bit l’unoche conterranno poi l’uscita. I valori di inizializzazione sono– A=67452301, B=EFCDAB89, C=98BADCFE

D=10325476


MD5 Overview

• Elabora il messaggio in blocchi da 512 bit

– utilizza 4 fasi, in cui sono svolte operazionisul generico blocco di messaggio e sulbuffer

• Il codice hash è il contenuto dei buffer alla fine dell’algoritmo


MD5 Overview


La funzione HMD5

• Ciascuna fase ha 16 passi del tipo: a = b+((a+g(b,c,d)+X[k]+T[i])<<<s) k=1, ..., 16

• a,b,c,d sono i 4 buffer, ma utilizzati in variecombinazioni– In ogni passo, solo un buffer è aggiornato– Dopo 16 passi ogni buffer è aggiornato 4 volte

• g(b,c,d) è una funzione non lineare diversa in ogni fase (F,G,H,I)

• T[i] è un valore costante derivato dalla funzioneseno


La Funzione

HMD5

p2(i)=(1+5i) mod 16p3(i)=(5+3i) mod 16p4(i)=7i mod 16


Il generico passo


MD5: Le funzioni F G H I


MD4

• È il precursore di MD5• Produce anch’esso un codice hash di 128 bit• ha 3 fasi di 16 passi (invece che 4 come in MD5)• Obiettivi di progetto (simili a quelli di MD5):

– Resistenza alle collisioni (ovvero difficoltà nel trovaremessaggi collidenti)

– Sicurezza implicita, non dipendente da problemicomputazionalmente complicati

– Velocità, semplicità e compattezza– Utilizzo dell’architettura little endian (byte meno

significativo nel byte con l’indirizzo più basso, èutilizzata nei PC)


MD4 versus MD5

• MD4 usa 3 fasi invece che 4 fasi

• In MD5 viene utilizzata una costante additiva T[i] diversa per ciascuno dei 64 passi; MD4 usa invece una costante fissa


La forza di MD5

• Ogni bit dell’hash MD5 dipende da tutti i bit del messaggio

• Rivest sostiene nel documento RFC che MD5 èil codice hash a 128 bit più resistente possibile

• Sono stati pubblicati tuttavia vari tipi di attacchi:– Berson 92 ha dimostrato che è possibile trovare con

l’analisi differenziale messaggi che producono lo stesso output per ciascuna fase (non è stato tuttaviain grado di estendere il risultato all’insieme delle 4 fasi)


La forza di MD5

– Boer & Bosselaers 93 si sono accorti che, per un messaggio lungo 512 bit, due diverse inizializzazioni dei buffer ABCD davano luogoallo stesso codice hash (pseudocollisione)

– Dobbertin 96 ha creato una collisione sumessaggi lunghi 512 bit nel caso in cui i buffer ABCD sono azzerati

• In conclusione, MD5 è apparso in fin deiconti vulnerabile!


Secure Hash Algorithm (SHA-1)

• SHA fu sviluppato dal NIST e dall’ NSA nel 1993; fu poi rivisto nel 1995 e chiamato SHA-1

• US standard, usato con la tecnica di firma digitale DSA– Lo standard è FIPS 180-1 1995; compare anche come RFC3174

– N.B. l’algoritmo è detto SHA, lo standard è detto SHS (Secure hash standard)

• Produce codici hash di 160 bit

• È attualmente l’algoritmo hash maggiormente preferito

• È basato sulla struttura di MD5


SHA-1 Overview• Il messaggio viene allungato in modo

tale che la sua lunghezza sia pari a 448 mod 512

• Sono poi aggiunti 64 bit cherappresentano la lunghezza, modulo 264, del messaggio originale

• I 5 buffer (A,B,C,D,E) – totale 160 bit –sono inizializzati a

(67452301,efcdab89,98badcfe,10325476,c3d2e1f0)


SHA-1 Overview

• Il messaggio è elaborato in blocchi di 512 bit (16 word da 32 bit)

• Vi sono 4 fasi da 20 passi– le 16 word sono espanse a 80 word tramite

operazioni di miscelazione e duplicazione

– L’output è sommato all’input per ottenere ilnuovo valore dei buffer

• Il codice hash è il valore finale del buffer


Elaborazione SHA-1 di un singolo bloccoda 512 bit


SHA-1


Funzionamento di SHA-1

• Nel grafico precedente....– a,b,c,d,e sono le 5 word del buffer– t è il numero di passo– f(t,B,C,D) è la funzione non lineare della

fase in esame– Wt è una parola di 32 bit derivata dal

messaggio– Kt è un valore costante ottenuto prendendo

alcune cifre decimali di opportuni numeriirrazionali


Le funzioni logiche di SHA-1


MD5 – SHA-1: Confronto

• L’attacco a forza bruta è più complicato (160 bit invece che 128)

• Al momento, non sono noti attacchicriptoanalitici verso SHA-1

• SHA-1 è leggermente più lento (80 passi inveceche 64)

• Entrambi gli algoritmi sono semplici dadescrivere e da implementare

• SHA-1 è ottimizzato per l’architettura big endian(al contrario di MD5)


Revisione di SHS

• Nel 2002, il NIST ha emesso una revisionedi SHS tramite il documento FIPS 180-2

• Sono aggiunti 3 nuovi algoritmi hash:– SHA-256, SHA-384, SHA-512

• La struttura di tali algoritmi è simile a quella di SHA-1

• Di conseguenza, anche l’analisi di talialgoritmi si basa sulle stesse tecnicheutilizzate per SHA-1


RIPEMD-160• RIPEMD-160 fu sviluppato in Europa nell’ambito

di un progetto di ricerca europeo• Gli ideatori sono i ricercatori che concepirono gli

attacchi a MD4/MD5• È l’evoluzione di un precedente algoritmo a 128

bit, rivelatosi vulnerabile• È simile a MD5/SHA• usa 2 cascate parallele di 5 fasi da 16 passi• Il codice hash prodotto è di 160 bit• È più lento, ma forse più sicuro, di SHA-1• Architettura little-endian


Struttura di una fase diRIPEMD-160


Codici MAC derivati daalgoritmi hash

• Abbiamo visto come DES possa essereutilizzato per creare un codice MAC

• Recentemente, ci si è interessati allacreazione di codici MAC a partire daalgoritmi hash– Gli algoritmi hash sono infatti generalmente

più veloci

– Non limitati da divieti di esportazione come glialgoritmi crittografici


Codici MAC derivati daalgoritmi hash

• Una possibilità è di includere la chiave nelmessaggio e poi calcolare il codice hash

• Ovvero:KeyedHash = Hash(Key|Message)

– Tale schema presenta delle vulnerabilità

• Tale approccio ha poi portato allo sviluppodi HMAC


HMAC

• È un internet standard RFC2104 • È obbligatorio per la sicurezza IP e viene usato

in protocolli internet come SSL• Obiettivi progettuali di HMAC:

– Utilizzo delle funzioni hash liberamente disponibili e presenti nelle librerie software

– Possibilità di facile sostituzione delle funzioni hash utilizzate

– Preservare la robustezza degli algoritmi hash utilizzati– Utilizzare e gestire le chiavi in modo semplice– Avere buona resistenza all’analisi crittografica


HMAC

• Utilizza un algoritmo hash:HMACK = Hash[(K+ XOR opad) ||

Hash[(K+ XOR ipad)||M)]]

• where K+ è la chiave zero-padded a sinistra in modo che sia lunga b bit (b è la lunghezza del blocco elaborato dalla funzione hash)

• opad=5C (ripetuto b/8 volte), ipad=36 (ripetutob/8 volte)

• MD5, SHA-1, RIPEMD-160 possono essereutilizzati


Funzionamento di HMAC


Firme digitali e protocolli di autenticazione


Firme Digitali

• Come detto più volte, la firma digitale ha la capacità di– Verificare l’autenticità del mittente e

individuare la data e l’ora della firma

– Verificare l’integrità del messaggio

– Permettere l’esibizione della firma ad un’autorità estranea per risolvere dispute e contenziosi


Requisiti di una firma digitale

• Deve dipendere dal messaggio che si sta firmando

• Deve utilizzare informazioni specifiche del mittente– Per evitare modifiche e ripudiabilità dell’origine

• Deve essere alquanto facile da produrre

• Deve essere facile da riconoscere e verificare

• Deve essere computazionalmente impossibile– Creare un nuovo messaggio con una firma a disposizione

– Creare una nuova firma per un dato messaggio fraudolento

• Deve essere facile memorizzare le firme per verifichefuture


Firma digitale diretta

• Coinvolge solo mittente e destinatario

• Ne abbiamo già parlato, richiede l’usodella crittografia a chiave pubblica

• Il mittente firma l’intero messaggio o un codice hash con la sua chiave privata

• La sicurezza dipende sull’inviolabilità dellachiave privata del mittente


Firma digitale arbitrata



• Fa affidamento su un arbitro A che verifica i messaggi prima che giungano al destinatario– L’arbitro verifica la firma su ogni messaggio– Dopodichè lo data e lo invia al destinatario

• Al solito, richiede un grande livello di fiducianell’arbitro

• Può essere implementata sia con crittografiasimmetrica che asimmetrica

• L’arbitro può avere o non avere accesso aimessaggi


Protocolli di Autenticazione

• Utilizzati per convincere i soggetti dellacomunicazione dell’identità reciproca e per scambiarsi le chiavi di sessione

• Possono essere monodirezionali o reciproci

• Questioni cruciali sono– confidenzialità – per proteggere le chiavi di

sessione– puntualità – per prevenire gli attacchi a replay


Uso della crittografia simmetrica: Needham-Schroeder Protocol

• Si fa affidamento su un KDC

• La sessione tra A e B è mediata dal KDC

• Il protocollo è il seguente:1. A→KDC: IDA || IDB || N1

2. KDC→A: EKa[Ks || IDB || N1 || EKb[Ks||IDA] ]

3. A→B: EKb[Ks||IDA]

4. B→A: EKs[N2]

5. A→B: EKs[f(N2)]


Protocollo Needham-Schroeder

• Utilizzato per distribuire in modo sicurouna nuova chiave di sessione tra A e B

• È vulnerabile a un attacco a replay se unavecchia chiave di sessione è stata violata– Il messaggio 3 può essere reinviato

convincendo B che sta comunicando con A

• Per porre rimedio c’è bisogno di– timestamps – Utilizzo di un nonce extra


Uso della crittografia asimmetri-ca con Authentication Server

• Denning 81 ha proposto il seguente schema:1. A→AS: IDA || IDB

2. AS→A: EKRas[IDA||KUa||T] || EKRas[IDB||KUb||T]

3. A→B: EKRas[IDA||KUa||T] || EKRas[IDB||KUb||T] || EKUb[EKRas[Ks||T]]

• Si noti che la chiave di sessione è scelta da A, quindi il livello di fiducia da riporre sull’AS èminore

• I timestamps prevengono gli attacchi a replay ma richiedono una sincronizzazione dei clock


Digital Signature Standard (DSS)

• E’ lo schema ufficiale di firma digitale approvatodagli USA (FIPS 186)

• Utilizza l’algoritmo SHA

• Progettato da NIST & NSA nei primi anni ‘90

• DSS è lo standard, DSA è l’algoritmo

• La firma è lunga 320 bit, ma con una sicurezzadell’ordine di 512-1024

• La forza dell’algoritmo si basa sulla difficoltà di calcolo del logaritmo discreto


RSA vs. DSS


Generazione della chiave in DSA

• Vi sono anzitutto dei valori pubblicamentecondivisi (p,q,g): – p 2L

• ove L è multiplo di 64 e varia tra 512 e 1024

– q, è un numero primo di 160 bit e fattore di p-1 – g = h(p-1)/q

• ove h<p-1, h(p-1)/q (mod p) > 1

• Ogni utente sceglie la sua chiave privata x e calcola quella pubblica y: – si sceglie quindi x<q– e si calcola y = gx (mod p)


DSA: Creazione della firma

• per firmare un messaggio M, il mittente:– Genera una chiave aleatoria k, k<q

(N.B. k deve essere aleatoria, usata una sola volta e poi distrutta)

– Calcola poi i parametri di firma: r = (gk(mod p))(mod q)

s = k-1(SHA(M)+ x.r)(mod q)

– Invia la firma (r,s) insieme al messaggio M


DSA: Verifica della Firma

• ... avendo ricevuto M & la firma (r,s)• per verificare una firma, il destinatario

calcolaw = s-1(mod q) u1= (SHA(M).w)(mod q) u2= (r.w)(mod q) v = (gu1.yu2(mod p)) (mod q)

• se v=r allora la firma è verificata• Vediamo perchè funziona...


DSA: Proof

• Se la firma è autentica, deve essereSHA(M)=-xr + ks (mod q)

• Premoltiplicando per w...

wSHA(M)+wxr = wks (mod q)

wSHA(M)+wxr = k (mod q)

u1 + xu2 (mod q)= k (mod q)=k(nell’ultimo passaggio si è tenuto conto del fatto che k<q)


DSA: Proof

• Ora, da tale relazione si hag(u1 + xu2) (mod q)= gk

• D’altra parte, gq=hp-1mod p=1 per il th. di Fermat, quindig(u1 + xu2) = gk

gu1 (gx)u2 = gk

• E, prendendo tale relazione mod p mod q si ha:gu1 (gx)u2 mod p mod q= gk mod p mod qgu1.yu2(mod p)(mod q)=gk mod p mod q


DSA: Proof

• In definitiva, abbiamo trovato che

gu1yu2 mod p mod q=gk mod p mod q

v = r

• Altrimenti detto, lo schema funziona!


DSA: La firma


DSA: La verifica


La sicurezza della posta elettronica

PGP (Pretty Good Privacy), S/MIME


L’e-mail...

• Il servizio di e-mail è una delle applicazionipiù largamente usata dagli utenti di internet

• Al momento, le e-mail comunementeutilizzate non sono crittografate– Possono quindi essere captate durante la loro

trasmissione sulla rete

– O, anche, da utenti privilegiati del mailserverdi destinazione


Requisiti di sicurezza desiderati

• riservatezza– Protezione della privacy

• autenticazione– Del mittente del messaggio

• integrità– Protezioni da modifiche

• Non-ripudiabilità dell’origine– Il mittente non deve poter negare l’invio del

messaggio


Pretty Good Privacy (PGP)

Philip R. Zimmermann

(ideatore e creatore di PGP)

www.philzimmermann.com


Pretty Good Privacy (PGP)

• Rappresenta uno standard “de facto” per l’e-mail sicura

• Sviluppato da Phil Zimmermann• Egli impliegò i migliori algoritmi crittografici• ... e li integrò in un unico programma semplice e

disponibile per una varietà di sistemi operativi: Unix, PC, Macintosh e Amiga

• Originariamente era gratuito, oggi lo è ancora, ma sono disponibili anche delle versionicommerciali


PGP

• Phil Zimmermann ha reso la documentazione ed il codice sorgente dell’applicazione liberamente disponibile in rete

• ... ha stretto accordi con la Viacrypt (ora Network Associates) per fornire una versione commerciale pienamente compatibile e a basso costo di PGP

• PGP è ora uno standard per internet (RFC 3156)


I servizi di PGP

• PGP comprende 5 servizi– Autenticazione

– Segretezza

– Compressione

– Compatibilità con la posta elettronica

– Segmentazione


PGP: Autenticazione

1. Il mittente crea il messaggio

2. L’algoritmo SHA-1 viene utilizzato per generareun hash di 160 bit

3. Viene poi usato DSS o RSA per criptare ilcodice hash

4. Al solito, il messaggio è accettato come autentico solo se l’hash generato in ricezionecoincide con quello inviato


PGP: Autenticazione

• Le firme non sono sempre allegate al messaggio. A volte vengono inviate separatamente.

• Ciò è utile– Per rivelare eventuali virus che si sono auto-

allegati all’e-mail– Quando un messaggio deve essere firmato

da più parti– Per conservare una registrazione separata

delle firme dei messaggi ricevuti


PGP: Confidenzialità

1. Il mittente genera un messaggio e una chiaverandom di 128 bit utilizzata solo per questomessaggio

2. Si utilizza l’algoritmo CAST-128, IDEA o 3DES3. La chiave di sessione è criptata con RSA (con

chiave pubblica del destinatario e posta in attachment)(in alternativa a RSA, PGP prevede anchel’utilizzo di una variante di Diffie-Hallmann –crittografia di ElGamal – che permette di realizzare la crittografia del messaggio)


PGP: Confidenzialità e Autenticazione

• Vengono implementati entrambi i serviziprecedenti su un unico messaggio– Si crea la firma e la si allega al messaggio

– Il messaggio e la firma sono entrambi criptati

– Viene poi allegata la chiave di sessione, criptata con RSA

(questa sequenza è preferibile a quella cheprevede prima crittografia e poi firma)


PGP: Compressione

• PGP comprime in maniera automatica i messaggi dopo che sono stati firmati ma prima della criptazione– Si può quindi conservare il messaggio non

compresso e la sua firma per eventuali verifiche– Inoltre l’algoritmo di compressione non è

deterministico, quindi è meglio prima firmare e poi comprimere

• Si utilizza l’algoritmo ZIP (Lempel-Ziv)• L’applicazione della crittografia dopo la

compressione migliora la sicurezza del sistema


PGP: Compatibilità con l’e-mail

• L’output delle operazioni di firma e criptazione èun file binario

• Tuttavia l’e-mail è stata originariamenteconcepita per l’invio di testi

• Quindi PGP deve convertire i file binari in caratteri di testo ASCII stampabili

• Si utilizza l’algoritmo radix-64– Associa a 3 bytes 4 caratteri stampabili– Aggiunge poi un bit di parità– La dimensione del messaggio aumenta del 33%


PGP: Compatibilità con l’e-mail

• Tale espansione viene poi compensata tramite la funzione zip

• PGP fornisce anche un servizio di segmentazione e riassemblaggio– La segmentazione avviene dopo la

compressione e la criptazione

– La chiave di sessione e la firma compariranno quindi solo all’inizio del primo sottomessaggio


PGPlato

mittente


PGPlato

ricevente


PGP: Generazione delle chiavimonouso

• Ogni messaggio è criptato con una chiavedi sessione– Di dimensione variabile: 56-bit DES, 128-bit

CAST o IDEA, 168-bit Triple-DES

• Si utilizza un algoritmo di generazionepseudocasuale ANSI X12.17

• Utilizza input aleatori quali i tasti premutisulla tastiera e le pause tra una pressionee l’altra


PGP: Le chiavi pubbliche

• Ciascun utente può utilizzare simultaneamentepiù coppie (chiave pubblica, chiave privata)

• Bisogna poter identificare quale chiave vieneutilizzata per criptare una data chiave di sessione

• Si utilizza quindi un identificatore di chiavi– Sono gli ultimi 64 bit della chiave– La probabilità di una collisione è molto bassa

• Tale ID viene allegato anche alla firma digitale, ovvero al codice hash criptato


PGP: Formato

generale di un

messaggio


PGP: I portachiavi (Key Ring)

• Ciascun utente PGP ha due portachiavi:– Il portachiavi delle chiavi pubbliche contiene

tutte le chiavi pubbliche di utenti PGP conosciuti, ordinati a seconda del Key ID

– Il portachiavi delle chiavi private contiene le coppie (chiave pubblica, chiave privata) di chiavi dell’utente, ordinate a seconda del Key ID e conservate in forma criptata con chiavegenerata, mediante un hash, da una frasesegreta (passphrase)


Il portachiavi privato


Il portachiavi delle chiavi pubbliche

Spiegheremo dopo i campi “Owner Trust,” “Key legitimacy”e “Signature Trust”


PGP: Gestione delle chiavi

• Siamo arrivati al punto nodale....... come si gestiscono le chiavi pubbliche??

• Non si ricorre ad autorità di certificazione• in PGP ogni utente è una sorta di “autorità di

certificazione”…– …può quindi “firmare” chiavi pubbliche di altri utenti a

lui noti

• Altrimenti detto, i vari utenti si legittimanoreciprocamente; ogni utente ha nei confrontidegli altri utenti un dato livello di fiducia (trust)



• Ogni voce del portachiavi pubblico è un certificato

• A ogni chiave è associato un campo di legittimitàdella chiave

• A ogni chiave sono associate anche zero o piùfirme

• A ciascuna firma è associato un campo di fiduciadella firma

• Il campo di legittimità della chiave deriva dalcampo di fiducia della firma



• Vi è poi il campo di fiducia del proprietario, che indical’affidabilità del proprietario nel firmare certificati

• Quindi I campi di fiducia della firma sono copie dei campidi fiducia del proprietario

• Quando un utente inserisce una nuova voce nelportachiavi pubblico, deve anche indicare la fiducia nelproprietario della chiave

• È possibile poi allegare una o più firme, con i relativicampi di fiducia

• Il valore del campo di legittimità della chiave vienecalcolato sulla base dei valori presenti tra I campi di fiducia delle firme



• Si forma quindi un “web of trust”– Si ripone fiducia nelle chiavi che sono formate da

persone di cui ci fidiamo

• Nota che gli utenti possono anche revocare le loro chiavi pubbliche: Viene emesso un certificato di revoca, firmato con la chiave privatacorrispondente alla chiave pubblica che si vuolerevocare

• Periodicamente, PGP elabora il portachiavipubblico per verificarne la coerenza


S/MIME (Secure/Multipurpose Internet Mail Extensions)

• Contiene l’introduzione di principi di sicurezzaallo standard di e-mail MIME– Il servizio di mail definito originariamente nella

RFC822 era concepito per il trasporto esclusivo di testi, mediante il protocollo SMTP

– MIME è un’estensione di RFC822 per porre rimedioad alcuni problemi di SMTP:

• Incapacità di trasmettere file binari• Incapacità di trasmettere caratteri internazionali (solo

caratteri a 7 bit)• Limite sulla dimensione dei messaggi• Problemi sulla formattazione dei testi


MIME & S/MIME

• Specifiche di MIME– Nuovi campi di intestazione del messaggio

che forniscono informazioni sul body– Nuovi formati di contenuti (multimedia e-mail)– Codifiche di trasferimento tra i vari formati

• S/MIME– Aggiunge specifiche di sicurezza a MIME– Supportato in diversi e-mail clients: MS

Outlook, Netscape, etc...


Tipi di contenuti di MIME

– Text

– Multipart (il messaggio contiene più parti indipendenti- esempio:multipar/alternative)

– Message

– Image

– Video

– Audio

– Application


Servizi di S/MIME

• enveloped data– Contenuto criptato con in allegato la chiave

• signed data– Messaggio + hash criptato con chiave privata, il tutto

codificato base64

• clear-signed data– Messaggio + (hash criptato e codificato base64)

• signed & enveloped data– Combinazione di firma e crittografia


Algoritmi crittografici in S/MIME

• Funzioni hash: SHA-1 & MD5• Firme digitali: DSS & RSA• Scambio chiave sessione: ElGamal & RSA• Criptazione dei messaggi: Triple-DES, RC2/40 e

altri• Vi è una procedura per decidere quali algoritmi

usare; ogni agente di decisione allega a ognimessaggio una lista, in ordine di preferenzadecrescente, degli algoritmi di crittografia cheutilizza


Scelta degli algoritmi in S/MIME

1. Scegliere, se possibile, la forma di decrittografiapreferita dal destinatario

2. Utilizzare lo stesso algoritmo presentenell’ultimo messaggio ricevuto da parte del destinatario

3. Usare 3DES (si rischia che il destinatario non riesca a fare la decriptazione)

4. Usare RC2/40 (algoritmo meno sicuro)

Se un messaggio va inviato a più destinatari potrebbe esserenecessario crittografarlo con più algoritmi!!!


Enveloped Data

1. Generare una chiave di sessionepseudocasuale per un algoritmo di crittografiasimmetrico

2. Crittografare la chiave di sessione con la chiave pubblica del destinatario (va fatto per ogni destinatario)

3. Creare, per ogni destinatario, un campo “recipient info” contenente un identificatore del certificato di chiave pubblica utilizzato

4. Crittografare il contenuto del messaggio con la chiave di sessione


Signed Data

1. Selezionare un algoritmo hash2. Calcolare l’hash del messaggio da

firmare3. Crittografare l’hash con la chiave privata

del mittente4. Preparare il blocco “signer info”

contenente il certificato della chiavepubblica del mittente, l’identificatoredell’algoritmo hash utilizzato


Clear-Signed Data

- Il messaggio viene inviato in chiaro

- E’ quindi visualizzabile da entità non aventi funzionalità S/MIME

- Solo l’hash è criptato e codificato base64


Gestione dei certificati in S/MIME

• S/MIME utilizza certificati X.509 v3

• La gestione è un ibrido tra un meccanismo che fa un usorigoroso di CA e uno basato sul “web of trust” del PGP

• Ciascun utente S/MIME...– Deve generare coppie di chiavi con Diffie-Hellman e DSS;

dovrebbe poter generare coppie di chiavi RSA

– Deve registrare la propria chiave pubblica presso una CA, per poter ricevere un certificato di chiave pubblica X.509

– Deve poter accedere a un elenco locale di certificati per verificare le firme in ingresso e crittografare i messaggi in uscita


Gestione dei certificati in S/MIME

• Ciascun utente ha quindi una lista di CA di cui si fida

• E un proprio database di coppie di chiaviprovate/chiavi pubbliche e certificati

• I certificati devono essere firmati dalle CA di cui l’utente si fida


Autorità di certificazione

• Esistono varie aziende che forniscono servizi di certificazione

• Verisign è una delle più note• Verisign emette diversi tipi di certificati (Digital ID)• Ciascun Digital ID contiene almeno le seguenti

informazioni– Chiave pubblica del proprietario– Nome e alias del proprietario– Data di scadenza– Numero di serie del digital ID– Nome della CA che ha emesso il certificato– Firma digitale della CA che ha emesso il certificato


Verisign: quotazioni Nasdaq


Autorità di certificazione

• Ciascun Digital ID può poi contenere altreinformazioni

– Indirizzo del Certificate Owner

– Indirizzo di e-mail del Certificate Owner

• Verisign emette tre tipi di certificati con livello crescente di sicurezza...– Vi sono quindi certificati di Classe 1, Classe 2

e Classe 3


Applicazioni per l’Autenticazione


Applicazioni per l’autenticazione

• ... ci soffermeremo sulle funzioni che permettono di implementare l’autenticazione, a livello di applicazione, sulle reti internet

• Parleremo di– Kerberos

– Servizio di autenticazione a directory X.509 (servizio utilizzato da S/MIME)


Kerberos

• Servizio di autenticazione sviluppato dal MIT

• Si tratta di un server “fidato” di chiavi

• Kerberos fornisce un server di autenticazionecentralizzato la cui funzione è quella di autenticare gli utenti per i server e i server per gli utenti

• Kerberos fa uso soltanto della crittografiasimmetrica (DES)

• Ve ne sono due versioni in uso: la 4 e la 5


Kerberos

• Lo scenario di riferimento è quello in cui ci sono delle postazioni accessibili da vari utenti e dei server che forniscono delle risorse

• Un utente si siede presso una postazione e accede tramite la propria password alle risorse del server

• L’obiettivo è quello di rendere questo sistema “sicuro”. Ovvero, solo gli utenti autorizzati devono poter usare le risorse


Requisiti di Kerberos

• Il primo documento pubblicato su Kerberos elencava i seguenti requisiti:– Sicurezza: non deve accadere che un utente

sostituisca un altro utente– Affidabilità: si utilizza un’architettura a server

distribuiti– Trasparenza: teoricamente l’utente non dovrebbe

accorgersi che sta avvenendo l’autenticazione, se non fosse per l’immissione di una password

– Scalabilità: Il sistema deve poter supportare un grannumero di client e server

• Kerberos si basa su un protocollo di autenticazione del tipo Needham-Schroeder


Needham-Schroeder Protocol

1. A→KDC: IDA || IDB || N1

2. KDC→A: EKa[Ks || IDB || N1 || EKb[Ks||IDA] ]

3. A→B: EKb[Ks||IDA]

4. B→A: EKs[N2]

5. A→B: EKs[f(N2)]


Kerberos 4: Overview

• È uno schema di autenticazione basato su 2 autorità superiori

• Vi è un Authentication Server (AS) – Gli utenti inizialmente comunicano con l’AS per

identificarsi

– L’AS fornisce all’utente delle credenziali autenticatenon modificabili (ticket granting ticket TGT)

• Vi è un Ticket Granting server (TGS)– Gli utenti poi chiedono accesso ai vari servizi al TGS

sulla base del TGT


Il Protocollo Kerberos (1/2)

Kc,tgs

indirizzo di rete di C


Il Protocollo Kerberos (2/2)


I “reami” Kerberos

• Un ambiente kerberos è fatto di– Un server Kerberos (AS + TGS)– Un certo numero di clients, tutti registrati presso il

server– Server di calcolo, ciascuno dei quali condivide una

chiave col server Kerberos

• Tale insieme viene detto “reame” (realm)– Si tratta tipicamente di un singolo dominio

amministrativo

• Se vi sono più reami, allora i server kerberosdevono condividere delle chiavi e avere fiducial’uno negli altri


Kerberos Versione 5

• Sviluppata a metà degli anni ‘90

• Rispetto alla versione 4 vi sono i seguenticambiamenti– Si possono utilizzare più algoritmi di crittografia (non

solo DES)

– Il protocollo è esteso a reti che non hanno indirizzi in formato IP

– I ticket possono avere durata arbitraria e non più unadurata massima di 5 x 256 = 1280 minuti

– Possibilità di inoltro automatico dell’autenticazione


Kerberos Versione 5

– Autenticazione tra N realm diversi non richiede N2 relazioni tra i server Kerberos

– Viene eliminata la doppia crittografia presentenei messaggi 2 e 4

• Kerberos versione 5 è pubblicato come Internet standard nella RFC 1510


Servizio di Autenticazione X.509• La raccomandazione ITU-T X.509 fa parte delle

raccomandazioni X.500 che definiscono un servizio a directory

• La directory è un server (o un insieme di server) che gestisce un database di informazioni sugliutenti

• X.509 definisce una struttura per fornire servizidi autenticazione degli utenti: La directory puòcontenere i certificati di autenticazione degli utenti

• I certificati e i protocolli X.509 sono ampiamenteutilizzati (S/MIME, IPSec, SSL/TLS, SET)


Servizio di Autenticazione X.509

• X.509 è stato emesso inizialmente nel 1988; èstato poi rivisto nel 1993 e nel 1995 (versione 3)

• X.509 si basa sull’uso della crittogafia a chiavepubblica e delle firme digitali– Lo standard non è agganciato a qualche particolare

algoritmo, anche se viene raccomandato RSA

• Il cuore di X.509 è il certificato utente, che ècreato da una CA e inserito nella directory. Il server che ospita i certificati non coincide quindiin generale con la CA


Certificati X.509

• Un certificato X.509 contiene... – versione (1, 2, or 3) – serial number (unique within CA) identifying certificate – signature algorithm identifier – issuer X.500 name (CA) – period of validity (from - to dates) – subject X.500 name (name of owner) – subject public-key info (algorithm, parameters, key) – issuer unique identifier (v2+) – subject unique identifier (v2+) – extension fields (v3) – signature (of hash of all fields in certificate)

• CA<<A>> indica il certificato di A firmato da CA


Certificati X.509


Come si ottiene un Certificato?

• Ogni utente che conosce la chiavepubblica della CA può leggere i certificatiemessi da questa CA

• Solo la CA può modificare i certificati

• Poichè i certificati non possono essere nèalterati nè falsificati, possono essere postiin una directory pubblica


Gerarchia delle CA

• Come possono autenticarsi due utenti che fannoriferimento a due diverse CA?Esempio: A ha un certif. firmato dalla CA X1, e B da X2A ottiene il certificato di X2 firmato da X1; puòquindi essere certo della chiave pubblica di X2 e quindi leggere il certificato di B:

X1<<X2>>X2<<B>>Analogamente, B ottiene la chiave pubblica di A con la catena inversa

X2<<X1>>X1<<A>>


Gerarchia delle CA

• In generale, le varie CA sono disposte in modo gerarchico

• Ciascuna CA ha i certificati delle CA antecedenti e susseguenti nella gerarchia

• Un utente può quindi verificare i certificatiemessi da qualsiasi CA che fa parte dellagerarchia


Esempio di gerarchia di CA


Revoca dei certificati

• I certificati hanno un periodo di validità

• Possono essere revocati in anticipo se:1. La chiave privata è violata

2. L’utente non è più certificato da una data CA

3. Il certificato è stato violato

• Ciascuna CA ha una lista dei certificatirevocati, la Certificate Revocation List (CRL)

• Gli utenti devono controllare che i certificatinon siano inseriti in tale elenco


Procedure di Autenticazione

• X.509 prevede tre diverse procedure di autenticazione

• One-Way Authentication (es. e-mail)

• Two-Way Authentication (sessioniinterattive con timestamp)

• Three-Way Authentication (sessioniinterattive senza timestamp)

• Tutte usano firme a chiave pubblica


One-Way Authentication

• 1 messaggio ( A->B) utilizzato per– Provare l’identità di A e che il messaggio è

stato trasmesso da A– Provare che il messaggio era indirizzato a B– Stabilire l’integrità e l’originalità del messaggio

• Il messaggio include un timestamp, un nonce, l’identità di B, e una chiave di sessione (criptata con la chiave pubblicadi B) ed è firmato da A


Two-Way Authentication

• 2 messaggi (A->B, B->A) che in aggiunta aiprecedenti– Stabiliscono l’identità di B ed il fatto che la risposta

proviene da B

– Provano che la risposta è destinata a A

– Provano l’integrità e l’originalità della risposta

• La risposta contiene il nonce originale da A, un timestamp, la chiave di sessione criptata con la chiave pubblica di A, e un nonce di B


Three-Way Authentication

• 3 messaggi (A->B, B->A, A->B) che permettonodi effettuare l’autenticazione bidirezionale senza far uso dei timestamp, ovvero senza doversincronizzare gli orologi

• In aggiunta ai messaggi precedenti, vi è la ritrasmissione, da A a B, del nonce generato daB e firmato da A

• Questo permette di non far affidamento sui timestamp e prevenire gli attacchi a replay


IP Security

Cenni


IP Security

• Sinora abbiamo considerato alcuneapplicazioni specifiche che implementanola sicurezza– eg. S/MIME, PGP, Kerberos

• Sarebbe preferibile tuttavia avere un meccanismo che permetta connessionisicure su una rete non sicura per tutte le applicazioni


IPSec

• IPSec fornisce la sicurezza a livello IP

• IPSec fornisce– autenticazione

– segretezza

– Un meccanismo di gestione delle chiavi

• Si può utilizzare su reti LAN, reti WAN e, ovviamente, sulla rete Internet


Esempio di uso di IPSec


Vantaggi e Caratteristiche di IPSec

• Se implementato in un firewall o router, IPSec fornisce un livello di sicurezza che riguarda tuttoil traffico che attraversa il perimetro. Il firewall sioccupa del sovraccarico computazionale legato alla sicurezza

• IPSec è sotto il livello di trasporto, quindi ètrasparente alle applicazioni superiori

• IPSec può essere trasparente agli utenti finali• IPSec può garantire sicurezza anche a singoli

utenti (vedi creazione di una VPN di un utente in trasferta con la propria LAN aziendale)


Architettura IPSec

• Le specifiche di IPSec sono alquantocomplesse

• Sono definite in diverse RFC...– Ad es. RFC 2401/2402/2406/2408

• L’uso di IPSec è obbligatorio in IPv6

• Algoritmi crittografici utilizzati:– 3DES a tre chiavi, RC5, IDEA, 3IDEA a tre

chiavi, CAST, Blowfish


Web Security


Web Security

• Il World Wide Web è ormai un elementofondamentale della vita comune

• Internet & Web sono in realtà vulnerabili• Vi sono una serie di minacce

– integrità– confidenzialità– denial of service– autenticazione

• Vi è bisogno quindi di meccanismisupplementari di sicurezza


Web Security


SSL (Secure Socket Layer)

• È un servizio di sicurezza a livello del protocollodi trasporto

• Sviluppato originariamente da Netscape• La versione 3 è stata sviluppata con revisione

pubblica• Tale versione è diventata uno standard Internet

col nome di TLS (Transport Layer Security)• SSL si poggia su TCP per ottenere un servizio di

trasmissione punto-punto affidabile• SSL ha due livelli protocollari


Architettura SSL


SSL (Secure Socket Layer)

• Il protocollo SSL Record Protocol forniscei servizi di sicurezza di base per i variprotocolli di livello superiore, come ad esempio http, che può operare su SSL

• Nell’ambito di SSL sono definiti treprotocolli di alto livello necessari allagestine degli scambi SSL


Architettura SSL

• Sessione SSL– È un’associazione tra client e server– È creata dal protocollo di handshake– Definisce un insieme di parametri di sicurezza

crittografica che possono essere usati da piùconnessioni

– Viene quindi evitata la negoziazione per ogniconnessione

• Connessione SSL– Un link di comunicazione punto-punto e temporaneo– Ciascuna connessione può essere associata ad

un’unica sessione SSL


SSL Record Protocol

È un protocollo di trasporto che fornisce i servizi di

• confidenzialità– Tramite crittografia simmetrica con chiave scambiata

tramite il protocollo di handshake

– IDEA, RC2-40, DES-40, DES, 3DES, Fortezza, RC4-40, RC4-128

– Il messaggio è compresso prima della crittografia

• integrità– Usa un MAC con chiave segreta condivisa

– Si tratta di una variante di HMAC


SSL Record Protocol

blocchi di non più di214 byte


SSL Change Cipher Spec Protocol

• È uno dei 3 protocolli specifici SSL cheusano lo SSL Record protocol

• Si tratta di un singolo messaggio

• Lo scopo di tale messaggio è fare in modoche lo stato provvisorio venga copiatonello stato corrente, aggiornando la cifratura che verrà usata nella sessionecorrente


SSL Alert Protocol

• Trasporta messaggi di allarme relativi allaconnessione SSL

• I messaggi sono caratterizzati da due diversigradi di importanza:

• warning or fatal

• Allarmi specifici sono i seguenti:• unexpected message, bad record mac, decompression

failure, handshake failure, illegal parameter• close notify, no certificate, bad certificate, unsupported

certificate, certificate revoked, certificate expired, certificate unknown

• I messaggi sono compressi e criptati come tutti i dati SSL


SSL Handshake Protocol

• Permette al client e al server di:– Autenticarsi a vicenda– Negoziare gli algoritmi MAC e crittografici da

utilizzare– Negoziare le chiavi da usare

• Prevede lo scambio di una serie di messaggi in varie fasi– Stabilisce le capacità crittografiche del client e del

server– Provvede all’autenticazione reciproca del client e del

server e allo scambio delle chiavi


SET

Secure Electronic Transactions


Secure Electronic Transactions (SET)

• È una specifica di sicurezza espressamenteprogettata per proteggere l’uso della carta di credito su Internet

• Fu sviluppato nel 1996 su richiesta di Visa e Mastercard

• Non è un sistema di pagamento...• ... ma una suite di protocolli che forniscono

– Comunicazioni sicure tra i soggetti coinvolti– Autenticazione tramite l’uso di certificati X.509v3– Privacy confinando l’informazione solo a chi ne ha

bisogno effettivamente


Componenti di SET

Banca delcompratore

Banca del venditore


Una Transazione SET

1. Il cliente apre un conto2. Il cliente riceve un proprio certificato3. I commercianti hanno anch’essi i loro certificati4. Il cliente emette un ordine5. Il commerciante è “verificato”6. L’ordine e il pagamento vengono inviati7. Il commerciante richiede l’autorizzazione al pagamento8. Il commerciante conferma l’ordine9. Il Commerciante fornisce il prodotto richiesto10. Il Commerciante richiede il pagamento


Firma Doppia

• Il cliente crea due messaggi– order information (OI) per il commerciante– payment information (PI) per la banca

• Le due informazioni devono essere distinte (la banca non ha bisogno di sapere la OI)

• Tuttavia devono poter essere collegate per risolvere le dispute

• Si usa quindi una doppia firma – Viene firmata la concatenazione degli hash dell’OI e

della PI


Richiesta di acquisto - Cliente


Richiesta di Acquisto -Commerciante


Richiesta di Acquisto -Commerciante

1. Verifica il certificato dell’acquirente

2. Verifica la doppia firma usando la chiavepubblica dell’acquirente per essere sicuriche non sia stato alterato e che sia statoeffettivamente inviato dall’acquirente

3. Elabora l’ordine e invia la PI al payment gateway per l’autorizzazione

4. Invia una risposta all’acquirente


Autorizzazione del payment gateway

1. Verifica tutti i certificati

2. Decripta la busta digitale per ottenere la chiave segretae decripta il messaggio inviato dal commerciante

3. Verifica la firma del commerciante

4. Verifica la doppia firma

5. Verifica che l’identificativo di transizione ricevuto dalvenditore coincide con quello inviato dall’acquirente

6. Richiede e riceve un’autorizzazione dall’issuer (banca)

7. Invia l’autorizzazione al commerciante


Cattura del Pagamento

• Il commerciante invia al payment gateway una richiesta di cattura del pagamento

• Il gateway controlla la richiesta

• Poi dispone il trasferimento dei fondi sulconto del venditore

• Informa poi il commerciante dell’avvenutopagamento


Crittografia e Reti Wi-fi


Reti Wi-Fi

• Ci focalizziamo sulle reti IEEE802.11• Modalità operative

– Ad Hoc mode (Independent Basic Service Set - IBSS)

– Infrastructure mode (Basic Service Set - BSS)


802.11 Infrastracture Mode


Ad-Hoc mode

Laptop users wishing to share files could set up an ad-hoc network and share files without need for external media.

Client A Client B

Client C


Sicurezza nelle WLAN

• La trasmissione sul canale wireless èovviamente meno sicura di quella su un canale wired

• Meccanismi di sicurezza:– SSID broadcast– MAC filtering– WEP protocol

• I meccanismi di sicurezza sono disabilitati di default!!!


Service Set Identifier (SSID)• Dovrebbe limitare gli accessi identificando l’area coperta

dall’access point• L’AP periodicamente invia il proprio SSID• I terminali hanno la possibilità di associarsi ad un AP

sulla base del suo SSID• In questo modo sono facilmente note le reti presenti in

una certa zona…• Esistono tool di analisi (es. AirMagnet, Netstumbler,

AiroPeek) per l’identificazione dell’ SSID.• Alcuni produttori usano dei nomi di default ben noti (es.

CISCO usa tsunami)• … in realtà l’SSID non è un dispositivo di sicurezza!!


MAC address filtering

Esempio di MAC address: 00-12-F0-62-3D-1AVantaggi:• consente maggiore sicurezzaSvantaggi:• aumenta la complessità• riduce la scalabilità• hackers esperti possono comunque aggirare

tale sistema


Wired Equivalent Privacy• Designed to provide confidentiality to a wireless network similar to that of

standard LANs. • WEP is essentially the RC4 symmetric key cryptographic algorithm (same

key for encrypting and decrypting).• Transmitting station concatenates 40 bit key with a 24 bit Initialization

Vector (IV) to produce pseudorandom key stream.• Plaintext is XORed with the pseudorandom key stream to produce

ciphertext.• Ciphertext is concatenated with IV and transmitted over the Wireless

Medium.• Receiving station reads the IV, concatenates it with the secret key to

produce local copy of the pseudorandom key stream.• Received ciphertext is XORed with the key stream generated to get back

the plaintext.


WEP: Integrità e Confidenzialità

24 bits 40 bits

IV | shared key used as RC4 seed• Must never be repeated (why?)• There is no key update protocol in 802.11b,

so security relies on never repeating IV

IV sent in the clearWorse: 802.11b says that changing IV with each packet is optional!CRC-32 checksum is linear in ⊕: if attacker flips some bit

in plaintext, there is a known, plaintext-independent set of CRC bits that, if flipped, will produce the same checksum

no integrity!


RC4

• Progettato nel 1987 da Ron Rivest• Fu conservato come segreto industriale e

reso noto nel 1994 da un hacker• Chiave a lunghezza variabile tra 1 e 256

bytes• Si utilizza un vettore di stato S fatto di 256

byte


RC4for i=0:255,

S(i)=iT(i) = K (i mod keylength)

end;

j=0;for j=0:255,

j=(j+ S(i) + T(i)) mod 256swap(S(i),S(j))

end% S contiene ora tutti i numeri tra 0 e 255


RC4i=j=0while (testo da cifrare presente)

i=(i+1) mod 256j=(j+S(i)) mod 256Swap(S(i),S(j))t= (S(i) +S(j)) mod 256k=S(t)

end

k va poi sommato al byte di testo in chiaro


WEP Overview• WEP relies on a shared key K between communicating parties• Checksum: For a message M, we calculate c(M). The plaintext is P={M,c(M)}• Encryption: The plaintext is encrypted using RC4. RC4 requires an initialization vector

(IV) v, and the key K. Output is a stream of bits called the keystream. Encryption is XOR with P.

• Transmission: The IV and the ciphertext C are transmitted.

Message CRC

RC4(v,K)

Ciphertextv Transmit

)K,v(4RCPC ⊕=


Obiettivi di sicurezza di WEP• WEP had three main security goals:

– Confidentiality: Prevent eavesdropping– Access Control: Prevent inappropriate use of 802.11 network,

such as facilitate dropping of not-authorized packets– Data Integrity: Ensure that messages are not altered or

tampered with in transit• The basic WEP standard uses a 40-bit key (with 24bit

IV)• Additionally, many implementations allow for 104-bit key

(with 24bit IV)• None of the three goals are provided in WEP due to

serious security design flaws and the fact that it is easy to eavesdrop on WLAN


Riuso della chiave in WEP• Vernam-style stream ciphers are susceptible to attacks when same IV

and key are reused:

• Particularly weak to known plaintext attack: If P1 is known, then P2 is easy to find (as is RC4).– This might occur when contextual information gives P1 (e.g. application-

level or network-level information reveals information)• Even so, there are techniques to recover P1 and P2 when just (P1 XOR

P2) is known – Example, look for two texts that XOR to same value

21

2121

22

11

PP)K,v(4RCP)K,v(4RCPCC

)K,v(4RCPC)K,v(4RCPC

⊕=⊕⊕⊕=⊕

⊕=⊕=


(In)Sicurezza del WEP• WEP’s engineers were aware (it seems??) of this weakness and

required a per-packet IV strategy to vary key stream generation• Problems:

– Keys, K, typically stay fixed and so eventual reuse of IV means eventual repetition of keystream!!

– IVs are transmitted in the clear, so its trivial to detect IV reuse– Many cards set IV to 0 at startup and increment IV sequentially from

there– Even so, the IV is only 24 bits!

• Calculation: Suppose you send 1500 byte packets at 5Mbps, then 224 possible IVs will be used up in 11.2 hours! (5 hours at 11Mbps)

• Even worse: we should expect to see at least one collision after5000 packets are sent! (due to birthday paradox)

• Thus, we will see the same IV again… and again…


Recupero delle chiavi

• Get access point to encrypt a known plaintext– Get victim to send an email with known content

• If attacker knows plaintext, it is easy to recover keystream from ciphertext– C ⊕ M = (M⊕RC4(IV,key)) ⊕ M = RC4(IV,key)– Not a problem if this keystream is not re-used

• Even if attacker doesn’t know plaintext, he can exploit regularities (plaintexts are not random)– For example, IP packet structure is very regular


Recupero delle chiavi

• Misuse of RC4 in WEP is a design flawwith no fix– Longer keys do not help!

• The problem is re-use of IVs, their size is fixed (24 bits)

– Attacks are passive and very difficult to detect


Da non fare!!!!Ingredients: Laptop (with 802.11b card, GPS, Netstumbler, Airsnort,

Ethereal) and the car of your choice• Drive around, use Netstumbler to map out active wireless networks

and (using GPS) their access points• If network is encrypted, park the car, start Airsnort, leave it be for a

few hours– Airsnort will passively listen to encrypted network traffic and, after 5-10

million packets, extract the encryption key• Once the encryption key is compromised, connect to the network as

if there is no encryption at all• Alternative: use Ethereal (or packet sniffer of your choice) to listen to

decrypted traffic and analyze• Many networks are even less secure


Netstumbler


Un’antenna gusto barbecue…


Integrità dei messaggi• The checksum used by WEP is CRC-32, which is not a

cryptographic checksum (MAC)– Purpose of checksum is to see if noise modified the message,

not to prevent “malicious” and intelligent modifications• Property of CRC: The checksum is a linear function of

the message

• This property allows one to make controlled modifications to a ciphertext without disrupting the checksum:– Suppose ciphertext C is:

– We can make a new ciphertext C’ that corresponds to an M’ of our choosing

)y(c)x(c)yx(c ⊕=⊕

)}M(c,M{)K,v(4RCC ⊕=


Alterazione dei messaggi

)}'M(c,'M{)K,v(4RC)}M(c,'M{)K,v(4RC

)}(c)M(c,M{)K,v(4RC)}(c,{)}M(c,M{)K,v(4RC

)}(c,{C'C

⊕=δ⊕⊕=

δ⊕δ⊕⊕=δδ⊕⊕=

δδ⊕=


Warchalking…


Contromisure• Run VPN on top of wireless

– Treat wireless as you would an insecure wired network– VPNs have their own security and performance issues

• Compromise of one client may compromise entire network

• Hide SSID of your access point– Still, raw packets will reveal SSID (it is not encrypted!)

• Have each access point maintain a list of network cards addresses that are allowed to connect to it– Infeasible for large networks– Attacker can sniff a packet from a legitimate card, then re-code

(spoof) his card to use a legitimate address


Fixing the Problem• Extensible Authentication Protocol (EAP)

– Developers can choose their own authentication method• Cisco EAP-LEAP (passwords), Microsoft EAP-TLS (public-key

certificates), PEAP (passwords OR certificates), etc.

• 802.11i standard fixes 802.11b problems– Still RC4, but encrypts IVs and establishes new shared keys for

every 10 KBytes transmitted• No keystream re-use, prevents exploitation of RC4 weaknesses• Use same network card, only upgrade firmware

– Long-term: AES, 128-bit keys, 48-bit IVs• Block cipher (in special mode) instead of stream cipher• Requires new network card hardware


Crittografia al livello fisico


The wire-tap channel(A.D. Wyner, Oct. 1975)

Sorgente Encoder MainChannel Decoder

Wire-tapChannel

SK XN YN

ZN

KS


The BSC wire-tap channel

Sorgente Encoder Decoder

BSC(p)

SK XN YN

ZN

KS


The Gaussian wire-tap channel(Leung-Yan-Cheong & Hellman, July ‘78)

Sorgente Encoder DecoderSK XN YN

ZN

KS+

+

n1N

n2N


crittografia e sicurezza delle reti - riccardogalletti.com · Collocazione del corso-2° anno della...

Documents

Transcript of crittografia e sicurezza delle reti - riccardogalletti.com · Collocazione del corso-2° anno della...