Andrea Pasquinucci Fileserver... · ©Andrea Pasquinucci Principi di Crittografia P a g . 5 1.1...

Principi di Crittografia

Andrea Pasquinucci

CTS CLUSIT

Giugno 2004

© Andrea Pasquinucci Principi di Crittografia Pag. 2

Indice

1. Generalità sulla crittografia e suoi utilizzi

2. Algoritmi Simmetrici: DES, AES

3. Algoritmi Asimmetrici (RSA), Hash e MAC

4. Firma digitale, protocolli, Certificati digitali, PKI


1.1 Introduzione

● Integrità● Autenticità● Confidenzialità

Non ripudio Privacy

CRITTOGRAFIACRITTOGRAFIA


1.1 Crittografia

DEFINIZIONI DI CRITTOGRAFIA:

● (intuitiva) l'arte di rendere un messaggio inintelligibile a qualunque persona non autorizzata a leggerlo

● (tecnica) lo studio di tecniche matematiche connesse ad aspetti della sicurezza delle informazioni quali integrità, autenticità e confidenzialità

La Crittografia interagisce con due campi più generali:

● La Teoria delle Informazioni

● La Sicurezza (Informatica)


1.1 Sicurezza

SICUREZZA: delle persone, degli oggetti, delle informazioni

● Varie tecniche per garantire un certo grado di sicurezza di quello che si vuole proteggere (la sicurezza assoluta non esiste): crittografia, sicurezza fisica ecc.

● Ogni tecnica va utilizzata nel proprio ambito tenendo ben presente le sue intrinseche limitazioni e le garanzie offerte

● Più tecniche devono essere associate per poter ottenere un certo livello di sicurezza

Esempio: la sicurezza fisica è sempre necessaria in un sistema di sicurezza informatica, chi protegge le chiavi segrete o quelle private?


1.1 Dati Vs. Informazioni

● Dati sono fenomeni fisici scelti per convenzione per rappresentare alcuni aspetti del nostro mondo concettuale e reale

● I significati che diamo ai dati sono le informazioni ● I dati sono usati per trasmettere e immagazzinare

informazioni e derivarne di nuove mediante la manipolazione dei dati secondo regole formali

● Informazioni e dati corrispondono ai due estremi della scala uomomacchina

● Distinzione sottile e causa dei più complessi problemi di computer security


1.1 Scala Uomo Macchina

Meccanismi specifici

complessicentrati sugli utenti

Meccanismigenericisemplici

centrati sui dati

orientatiall’uomo

orientatialla macchina


1.1 Sicurezza delle Informazioni

● La Crittografia è una tecnica per la Sicurezza delle Informazioni ma agisce direttamente sui DATI

● Talvolta è possibile ottenere le informazioni anche senza dover decifrare i dati (ovvero rompere la sicurezza offerta dalla crittografia)


1.1 Teoria delle Informazioni (Shannon)

● L'Entropia o Incertezza di X, indicata con H(X), è una misura della quantità di informazione contenuta in X, più precisamente dell'eccesso di dati usati da X per rappresentare l'informazione

● Alla riduzione dell'entropia H(X) corrisponde un aumento dell'informazione in X, indicata con I(X)

● I(X;Y) = H(X) – H(X|Y)Mutual Information di X e Y = Entropia di X meno la Entropia condizionale di X e Y (ovvero l'incertezza su X una volta che si conosce esattamente Y)


1.1 Esempio di uso dell' Entropia

● Se l' informazione di ogni carattere dell' alfabeto è identica, allora H(X) = log

2n ove n=numero di caratteri dell' alfabeto

● Quante cifre decimali ha un numero di 1024 bit? Log

210=3,3219... quindi ogni cifra decimale porta la

informazione di 3,3219 bit => 1024 bit sono circa 310 ( ≃ 1024 / 3,3219) cifre decimali

● Quante cifre esadecimali ha un numero di 1024 bit? Log

216=4 quindi 1024 bit sono 256 cifre esadecimali (questo

risultato è ovvio, ogni cifra esadecimale sono 4 bit poiché 24=16)


1.1 Esempio di Codifica

I colori BLU, ROSSO, VERDE e NERO possono essere codificati con:

● Una stringa di cinque lettere o spazi (ogni carattere 8 bit, in totale 40 bit)

● Due bit con l'assegnazione: 00=blu, 01=rosso, 10=verde, 11=nero

Nel primo caso abbiamo un eccesso di 38 bit nella codifica, 38 bit sono ridondanti. L'informazione contenuta nelle due codifiche è la stessa, ma l'entropia della prima è molto maggiore dell'entropia della seconda.


1.1 Esempio di Codifica

Nella teoria delle Informazioni si denota con la parola bit l'unità di informazione; coincide spesso anche con il bit informatico, ma attenzione a non fare confusione.

In Inglese, assumendo un vocabolario di 27 caratteri, ogni carattere ha una entropia di circa 1.3 (1.5) bit mentre la ridondanza della lingua è di circa il 75%, ovvero l'informazione contenuta in un libro in linea (solo) teorica potrebbe essere comunicata con ¼ di dati (pagine).


1.1 Ridondanza in Crittografia

Molti degli algoritmi crittografici mantengono la ridondanza del messaggio che viene cifrato, ovvero il messaggio in chiaro e cifrato hanno la stessa lunghezza e vocabolario identico o isomorfo.

Poiché la ridondanza non è distribuita in modo uniforme nel messaggio originale, un algoritmo crittografico deve distribuire la ridondanza in tutto il messaggio cifrato in modo uniforme, altrimenti è (più) facile risalire al messaggio originale.

Entropia, Informazione e Ridondanza sono fondamentali per la Crittoanalisi, ovvero l'arte del decifrare, il cui metodo principale è l' analisi delle sequenze ripetute.


1.2 Elementi di Base

● Crittografia: Sicurezza Attiva a protezione dei dati● Crittografia si basa su Algoritmi matematici● Difficile ideare nuovi algoritmi● Crittoanalisi: arte del decifrare, è l'opposto della Crittografia● Storicamente non vi era una distinzione chiara tra Algoritmo e

Chiave, si attribuisce a Kerckhoffs (1883) aver enunciato chiaramente che la sicurezza della crittografia si basa sulla segretezza della sola Chiave, mentre l'algoritmo prima o poi diviene pubblico.



Per cifrare un messaggio si usa

● Un Algoritmo crittografico (pubblico !)

● Una Chiave segreta (casuale)

La sicurezza risiede nella bontà dell'algoritmo (verifica pubblica)

e nella casualità della chiave



Procedimento più semplice di cifratura:

Algoritmo

Testo + Chiave Cifratura Messaggio Cifrato

Messaggio Cifrato + Chiave D. Testo

Notazioni: EK(M)=C D

K(C)=M



● Per generare le chiavi segrete si usano spesso Numeri Casuali ● Difficile generare numeri casuali, su computer solo numeri

Pseudocasuali (se si è fortunati!)● Alcuni algoritmi Asimmetrici utilizzano anche numeri Primi

(divisibili solo per 1 e per se stessi)

● Protocolli: come combinare diversi algoritmi in procedure che permettono di implementare politiche di sicurezza: un algoritmo da solo non serve a molto


1.3 One Time Pad

(Vernam 1926)

Di norma si applica a messaggi codificati in binario, anche le chiavi sono stringhe binarie, ma si può utilizzare una qualunque altra base scegliendo l'opportuna operazione al posto di XOR (esempio: le 26 lettere dell' alfabeto, somma modulo 26)

● Algoritmo crittografico : XOR di ogni bit del messaggio con il corrispondente bit della chiave

● Chiave segreta : stringa casuale lunga quanto il messaggio● Unico algoritmo assolutamente sicuro (dimostrato matema

ticamente) se la chiave è casuale ed usata una volta sola


1.3 One Time Pad

XOR: 0X0=0 0X1=1 1X0=1 1X1=0 (aXa)=0

● Testo XOR Chiave = Messaggio Cifrato

● Messaggio Cifrato XOR Chiave = Testo


1.3 One Time Pad

● EsempioTesto: 1011010001Chiave: 0110100011XORMessaggio Cifrato: 1101110010

● Se la Chiave è veramente Casuale, anche il Messaggio Cifrato è veramente Casuale, solo chi possiede la Chiave può ottenere il Testo originale


1.3 One Time Pad

● Problema: Generare le Chiavi casuali lunghe a sufficienza● Problema: Distribuire le Chiavi (una per ogni messaggio!) a

chi deve ricevere il messaggio● (Il problema della distribuzione delle Chiavi è comune a tutti

gli algoritmi simmetrici, algoritmi che usano una sola chiave per cifrare e decifrare, o due chiavi semplicemente derivabili una dall' altra)


1.3 Cifrario di Cesare

● Algoritmo crittografico: sostituisci una lettera con la Nesima lettera successiva nell'alfabeto modulo 26

● Chiave Segreta C: N Chiave Segreta D: N

● Esempio: N=3 A => D, B => E, ..., Z => C

● Crittoanalisi: dato un messaggio cifrato non breve, conta la frequenza di apparizione di ogni lettera (2, 3 ... lettere consecutive, parole di 2, 3 ... lettere) e paragona con la frequenza nota (ad esempio in Inglese la frequenza della E è circa 13%, mentre Z e Q compaiono circa lo 0,1%, TH circa il 3,5% tra le combinazioni di 2 lettere consecutive)



Alcuni problemi del cifrario di Cesare (di Vigenère, Playfair ecc.):● Non distribuisce la ridondanza/entropia/informazione in modo

uniforme su tutto il testo cifrato, anzi rimangono identiche a quelle del messaggio originale sia preso globalmente che in ogni sua parte

● La chiave viene riutilizzata per ogni lettera del messaggio, è il riutilizzo della stessa chiave l'origine del punto precedente

● La chiave, anche se casuale, è troppo semplice, più precisamente lo spazio delle chiavi (25 in tutto) è troppo piccolo e si possono provare tutte in un tempo ragionevole



Se il Cifrario di Cesare garantisse che ogni lettera che compare nel testo cifrato ha la stessa frequenza, ovvero la stessa probabilità di apparire, sarebbe (a prima vista) impossibile decifrare senza conoscere la chiave segreta.

Se si provassero tutte le chiavi, si otterrebbero tutti i messaggi di quella lunghezza. Ma lo spazio delle chiavi è molto piccolo, per cui è facile scegliere tra i 25 messaggi ottenuti quello vero.

(Lo spazio delle chiavi di One Time Pad è 2^[numero di bit del messaggio], solitamente è un numero enorme)


1.4 Crittoanalisi

Breve classificazione degli Attacchi:● ATTIVI o PASSIVI● Ciphertext only (ottenere la chiave dai soli testi cifrati)● Known plaintext (noti alcuni testi non cifrati e i corrispondenti

testi cifrati)● Chosen plaintext (l'attaccante sceglie i testi non cifrati)● Adaptive chosen plaintext (la scelta del testo non cifrato

dipende dai testi cifrati ottenuti precedentemente)

Un buon algoritmo crittografico deve far fallire tutti questi tipi di attacchi.


1.4 Crittoanalisi

Altri tipi di attacchi:● Differential Cryptoanalysis sottoclasse dei chosenplaintext, si

analizza la differenza tra testi cifrati ottenuti da testi originali con particolari differenze

● RelatedKey Cryptoanalysis l'attaccante è a conoscenza della differenza fra alcune chiavi usate, ma non le chiavi stesse

● Linear Cryptoanalysis si cerca una approssimazione lineare all' algoritmo (idea da OneTimePad: se faccio XOR del testo originale con il testo cifrato ottengo la chiave)

● ....


1.5 Proprietà degli Algoritmi

● La chiave è molto più breve del testo da cifrare● La chiave viene riutilizzata molte volte● La chiave non è esattamente casuale

Questo implica che l'algoritmo deve cercare di rendere il più casuale possibile il testo cifrato distribuendone l'entropia. Shannon mostrò che vi sono due tecniche di base per ottenere ciò:● Confusion rende confusa la relazione tra il testo originale e quello

cifrato, esempio la sostituzione di un carattere con un altro secondo una tabella

● Diffusion distribuisce l'informazione su tutto il testo cifrato, ad esempio permutando (trasponendo) i caratteri


1.5 Classi di Algoritmi

● Algoritmi Simmetrici: stessa o (semplicemente deducibile una dall'altra) chiave C e D

● Algoritmi Asimmetrici o a Chiave Pubblica: è in pratica impossibile ottenere la chiave C dalla chiave D in un tempo ragionevole

● Algoritmi di Hash o Digest: data una stringa di lunghezza arbitraria generano una stringa praticamente unica di lunghezza fissa


2.1 Algoritmi Simmetrici

● Il testo cifrato deve dipendere da tutti i bit della chiave e del testo originale

● Cambiando 1 bit nel testo o nella chiave, ogni bit del testo cifrato può cambiare con la stessa probabilità

● Cambiando 1 bit nel testo cifrato, ogni bit del testo decifrato può cambiare con la stessa probabilità

● Tipi: Blocchi, Caratteri (Stream)● Modi: ECB, CBC, CFB, OFB, A/Synchronous Stream


2.1 Algoritmi Simmetrici Blocchi

Blocchi il testo è diviso in blocchi di lunghezza fissa (spesso pari alla lunghezza della chiave) e produce blocchi della stessa lunghezza● ECB (Electronic Code Book): ogni blocco è cifrato in modo

indipendente● CBC (Cipher Block Chaining): ogni blocco ha un riporto dal blocco

precedente, il primo blocco ha un IV (Initial Value) noto (selfsynchronizing)

ECB: Errori Ripetizioni CBC: Errori Ripetizioni


2.1 Algoritmi Simmetrici Stream

Stream: cifrano un bit (o carattere) alla volta usando una trasformazione che cambia per ogni bit, tipicamente l'operazione è bit XOR chiave ove la chiave (anche essa 1 bit) è generata dinamicamente dall'algoritmo (keystream) e dipende dallo stato precedente

● Sincrono il bit della chiave è generato indipendentemente dal testo cifrato e non cifrato (One Time Pad può essere visto come il più semplice esempio)

● Asincrono il bit della chiave dipende da un numero fissato di bit cifrati precedenti (self synchronizing)


2.1 Algoritmi Simmetrici Stream

Gli algoritmi a blocchi possono essere usati anche per creare algoritmi di tipo Stream, di norma generando la chiave di stream da XOR con il prossimo bit● CFB (Cipher Feed Back): la chiave di stream (1bit) è ottenuta

cifrando una combinazione del bit cifrato precedente e del blocco di riporto, il blocco di riporto iniziale è un IV (selfsynchronizing)

● OFB (Output Feed Back): la chiave di stream (1bit) è ottenuta cifrando il blocco di riporto cifrato precedente, il blocco di riporto iniziale è un IV (not selfsynchronizing)



BLOCCHI vs. STREAM

Non è ovvia quale sia la differenza, visto che gli uni possono essere usati per creare un algoritmo degli altri. In pratica si denotano

● come Stream algoritmi veloci e che agiscono su di un singolo bit (carattere) di testo, adatti quindi a cifrare comunicazioni in tempo reale facendo un XOR del bit con la streamkey

● come Blocchi gli algoritmi ove vengono fatte delle operazioni contemporaneamente su tutti gli elementi di un blocco di n (ad esempio n=64) bit, come permutazioni e non un semplice XOR



● DES (Data Encryption System): blocco di 64bit, chiave di 56bit (non sicuro) meglio in hardware

● 3DES: DES (DES)1DES – blocco 64bit, chiave 168 o 112 bit – sicuro (non tutte le chiavi sono buone)

● AES (Advanced Encryption Standard): blocco 128 bit, chiave di 128, 192 o 256 bit

● IDEA (International Data Encryption Algorithm): blocco 64bit, chiave 128bit – molto sicuro ma Proprietario

● RC4: Stream, 10 volte più veloce di DES, chiave di almeno 40bit (in pratica molto di più) Proprietario



● USO: Poiché sono veloci si usano per cifrare i dati e le comunicazioni, possono anche essere usati come Hash o per autenticazione

● PROBLEMI: La distribuzione delle Chiavi, che va ripetuta spesso poiché ogni chiave può essere usata solo per cifrare una quantità massima di dati


2.2 Metodi per Algoritmi Simmetrici

● Trasposizione/Permutazione: a periodo fisso o variabile a seconda della chiave [elementi del blocco (1,2,3,4,5) => (5,3,1,2,4)]

● Sostituzione: ● monoalfabetica (Cifrario di Cesare), affine (c=at+b mod26)● poligrammatica (2 o più caratteri sostituti in corrispondenti gruppi

Playfair) ● omofonica (1 carattere => k caratteri di cui 1 scelto a caso, k

dipende dalla frequenza del carattere, allargamento dell'alfabeto)● polialfabetica (esempio: monoalfabetica ma con k alfabeti che si

ripetono – Vigenère, macchine a rotori, Enigma)


2.3 Data Encryption Standard (DES)

● 1973 NBS (ora NIST, National Institute of Standards and Technology) bandisce concorso per algoritmo crittografico per scopi commerciali

● 1974 IBM fornisce un algoritmo basato su Lucifer● NSA (National Security Agency) modifica l'algoritmo, chiave solo

56bit, nuove Sbox, 16 round● NSA ha inserito backdoor? 1990 NO, ha protetto algoritmo contro

Differential Cryptoanalysis● 1975 NBS pubblica l'algoritmo, malinteso con NSA che pensava che

l'algoritmo fosse segreto e solo in hardware, ma i principi di progettazione e le caratteristiche dell'algoritmo furono mantenuti segreti sino al 1992


2.3 DES

● DES è un OTTIMO algoritmo● Problema: non scala a chiavi più lunghe● Problema: chiave a 56 bit troppo corta● Problema non grave: DES ha 64 weak keys (0000...)● DES non è un gruppo (1992) perciò applicandolo più volte aumenta

la sicurezza● Oggi DES è rotto poiché la potenza di elaborazione è tale da rendere

insicuro qualsiasi algoritmo con chiavi di meno di circa 100 bit● 3DES ha una chiave di lunghezza effettiva di 112 bit, ad oggi non è

rotto, ma domani...


2.3 DES

DES è un SubstitutionPermutation Network che agisce su blocchi di 64 bit ripetendo 16 volte le stesse operazioni con sottochiavi diverse

source HAC


2.3 DES

● La chiave iniziale è di 64 bit, ma 8 bit sono di parità; dalla chiave di 56 bit vengono estratte 16 sottochiavi di 48 bit

● DES è un Cifrario di Feistel poiché agisce solo su 32 dei 64 bit in ogni round, per convenzione Blocco=(L,R) con L=32 bit di sinistra e R=32 bit di destra, e

Li = R

i1 R

i = L

i1 x f(R

i1,K

i)

Sour

ce A

MM


2.3 DES

Il cuore di DES è nella funzione f, essa è basata su semplici operazioni su bit facilmente implementabili in hardware quali shift, permutazioni e lookup in tavole fisse e consiste di:● Espansione dei 32 bit a 48 bit: 32

bit divisi in 8 blocchi di 4 bit, il primo e l'ultimo bit di ogni blocco è raddoppiato (e permutato) ottenendo 8 blocchi di 6 bit = 48 bit so

urce

HAC


2.3 DES

● XOR dei 48 bit con la iesima sottochiave a 48 bit

● Ogni blocco passa attraverso la corrispondente SBOX (S = Sostituzione), in pratica una SBOX è una lookup table fissa con indici i 6 bit del blocco, che individua un blocco di 4 bit che diventa l'output, quindi i blocchi tornano ad essere di 4 bit => totale 32 bit

● Una Permutazione finale

sour

ce H

AC


2.3 DES

● Le SBox sono il cuore di DES poiché sono l'unico elemento nonlineare; la scelta delle lookuptable è fondamentale per la sicurezza dell'algoritmo (dalla NSA)

● 16 round sono il minimo necessario a rendere tutti gli attacchi noti difficili quanto il bruteforce, ovvero ogni bit dei 64 di output dipende in modo sufficientemente identico da ognuno dei 64 bit di input e da ognuno dei 56 bit della chiave

● Per decifrare basta usare DES nello stesso modo ma invertendo l'ordine delle sottochiavi, cioè se per cifrare si usa K

1 ... K

16 nei round

1 ... 16, per decifrare si usa K16

... K1


2.4 Advanced Encryption Standard (AES)

● Dal 1987 NIST ha cercato un sostituto a DES● Nel 1997 NIST annunciò una competizione internazionale per un

algoritmo simmetrico a blocchi di 128 bit e chiavi di 128, 192, e 256 bit; doveva essere implementabile sia in HW che SW ed anche in sistemi embedded (veloce, poca RAM e ROM); l'algoritmo vincitore sarebbe divenuto di pubblico dominio

● 15 concorrenti, 5 finalisti, 1 vincitore (10/2000): Rijndael (J.Daemen, V. Rijmen), Twofish, SERPENT, RC6, MARS, DEAL, SAFER+, FROG, LOKI97, CAST256, Magenta, DFC, CRYPTON, E2, HPC

● Standard Pubblico 26/11/2001 FIPSPUB197● 6/2003 NSA approva AES a 128 bit per SECRET e a 192/256 bit per

TOPSECRET !!!


2.4 AES

● AES non è un Feistel cipher ma solo un SubstitutionPermutation network; agisce su sottoblocchi di 8bit organizzati in una matrice 4x4 (8x4x4=128), 4 righe di 4 colonne

● Tutte le operazioni sono effettuate sui sottoblocchi di 8 bit

● 10 round con key 128 bit, 12 round con key 192 bit e 14 round con key a 256 bit

● 4 operazioni: SubBytes, ShiftRows, MixColumns, AddRoundKey

● Solo SubBytes (SBOX) è nonlineare sour

ce h

ttp://

hom

e.ec

n.ab

.ca/


2.4 AES

● C'è un extra AddRoundKey all'inizio e l'ultimo round non ha il MixColumns

● Dalla chiave originale vengono estratte 11/13/15 sottochiavi a 128bit

● Le operazioni effettuate sono algebriche vedendo i sottoblocchi come polinomi nel campo GF(28)

● Per AES inverso sono definite 4 operazioni inverse delle precedenti: InvSubBytes ecc.

sour

ce h

ttp://

hom

e.ec

n.ab

.ca/


2.4 AES

● Problema: il numero di round è troppo basso per ottenere una sufficiente distribuzione dell'entropia ???

● Proposta: aumentare i round (da 13 in su)

● Proposta: usare blocchi sino a 256bit e chiavi sino a 352bit● Struttura algebrica molto semplice: nuovi attacchi Algebrici (AES

rappresentato come un problema algebrico, la chiave si ottiene come la soluzione di un sistema di eq. quadratiche detto XSL)

sour

ce h

ttp://

hom

e.ec

n.ab

.ca/


2.4 AES

● XSL per ora non implementabile, molti ritengono che non sia un attacco realizzabile in pratica (molti sistemi algebrici nonlineari sono di classe NP)

● Nessun attacco realizzabile in pratica è noto al giorno d'oggi, alcuni hanno dubbi sulla solidità dell'algoritmo, ma per ora solo prove positive

● NSA crede in AES (o è in grado di romperlo ?)


2.5 DES vs. AES

● Rijndael: prestazioni equivalenti in velocità e memoria in tutte le implementazioni (SW, HW, embedded, CPU da 8 a 64 bit, RAM a partire da 128Byte, ecc.) sempre tra i migliori

● Da 2 a 10 volte più veloce di 3DES● CON: Gestione chiavi più lenta, funzioni diverse per decifrare● PLUS: Struttura algebrica più semplice, facile da implementare● Esempi di test in software (difficili da paragonare a seconda del

linguaggio, compilatore, OS, CPU ecc.):Cipher KeySize Speed1 Speed2 (MB/s)

AES 128 27.6 62.046

AES 192 24.4 56.067

AES 256 22.0 49.155

3DES 168(112) 10.4 18.790


2.5 DES vs. AES in HW (FPGA)

sour

ce P

awel

Cho

divi

ec


2.5 DES vs. AES

sour

ce M

edia

cryp

t AG


3.1 Algoritmi Asimmetrici

● 1976: DiffieHellmann (+ Merkle) propongono una nuova idea per superare il problema della distribuzione delle chiavi degli algoritmi simmetrici e per le firme digitali

● Idea: una chiave Pubblica ed una Privata, dalla chiave Pubblica non è possibile in pratica risalire a quella Privata

● Per fare ciò si usano oneway trapdoor functions basate su difficili problemi matematici, i.e. problemi nella classe NP ( = Polynomial on a Nondeterministic Turing machine =? al crescere della lunghezza n dell' input al problema, il numero di operazioni necessarie per risolvere il problema cresce più velocemente di qualunque potenza na)


3.1 Algoritmi Asimmetrici

● Onewaytrapdoorfunction: una funzione difficile da invertire, ma facile da invertire se si conosce una informazione ulteriore

● Definizione: Un numero primo è un numero divisibile solo per 1 e per se stesso (il numero di primi minori od uguali ad x è circa x/lnx)

● Tipico esempio: prodotto di due numeri primi grandi (di più di 100 decimali l' uno)

n = p x qdato n trovare p e q è un problema NP, ma dato n e p trovare q è facile!

● Problemi NP più utilizzati: Fattorizzazione in numeri Primi, Logaritmi Discreti


3.1 Sicurezza degli Algoritmi Asimmetrici● Non vi è dimostrazione matematica che NP ≠ P ! ● Se si provasse che NP = P, si troverebbero anche algoritmi per

risolvere in tempo polinomiale i problemi NP => la crittografia basata su questi problemi matematici sarebbe ROTTA

● Non è stato dimostrato che il problema RSA (basato sulla fattorizzazione in numeri primi) sia un problema NP

● Assumendo che si dimostri matematicamente che NP ≠ P e che RSA è NP, la sicurezza di questi algoritmi si basa sull' utilizzo di chiavi pubbliche lunghe a sufficienza rispetto alla potenza di calcolo degli elaboratori del momento

● I problemi NP saranno risolvibili in tempo polinomiale dai futuri elaboratori quantistici


3.1 Sicurezza degli Algoritmi Asimmetrici

Algoritmi per la fattorizzazione in numeri primi:

● Trial division: prova tutti i primi sino a n● Metodo di Fermat (1643)● Pollard' s rho o Monte Carlo● Continued Fraction ● Elliptic Curve method● Quadratic Sieve (per numeri con meno di 110 cifre decimali)● Number Field Sieve (Pollard 1988, per numeri con più di 110 cifre

decimali, va come exp[(1.185 + o(1))(lnx1/3 lnlnx2/3)] Bernstein 2000)


3.2 RSA

● Rivest, Shamir, Adleman 1977● Scegli due numeri Primi molto grandi p e q (oggi circa 200 cifre

decimali, 600 bit)● Scegli un numero (casuale) 1< e < =(p-1)(q-1) e Relativamente

Primo a , ovvero e e hanno solo 1 come divisore comune● Calcola n=pq● Calcola d come l' unico intero 1< d < tale che ed≡1 mod()

(ovvero esiste un k intero tale che ed=1+k, l'operazione mod() può essere vista come il resto della divisione per , oppure sottraendo/sommando , ridurre il numero dato all' intervallo [0,1] )


3.2 RSA

● La Chiave Pubblica D è la coppia (e,n)

● La Chiave Privata C è la coppia (d,n)

● Si noti che per calcolare d è necessario conoscere e,p-1,q-1 quindi chi conosce la chiave pubblica deve, in linea di principio, fattorizzare n per calcolare p,q e con questi calcolare poi d

● In pratica, al giorno d'oggi l'unico modo noto pubblicamente di ottenere la chiave privata da quella pubblica è quello di fattorizzare n, se questo è un numero di almeno 1024bit (più di 300 cifre decimali) non è noto pubblicamente alcun elaboratore che sia in grado di farlo in un tempo ragionevole


3.2 RSA

● Data la Chiave Pubblica ed il messaggio m posso de/cifrare con la formula c = me mod(n)

● Data la Chiave Privata ed il messaggio c posso de/cifrare con la formula m = cd mod(n)

● cd = (me)d mod(n) = med mod(n)Per il teorema di Fermat, se ed≡1 mod() allora med = m mod(n), e quindi cd mod(n) = m, cvd

● ATTENZIONE: un messaggio cifrato con una delle due chiavi viene decifrato con l'altra chiave! L'uso delle chiavi è simmetrico, ma una chiave è Privata, l'altra è Pubblica


3.2 RSA

● Di solito nelle applicazioni viene scelto e=3 oppure e=216+1=65537 (3, ed in generale e piccolo, non dovrebbe essere usato se si cifra lo stesso messaggio ripetutamente con la stessa chiave; 65537 contiene solo due 1 nella rappresentazione binaria)

● RSA è circa 1000 volte più lento di DES in HW e circa 100 volte in SW

● Chiavi sicure oggi sono di 1024, 2048 o 4096 bit!

● Altri principali Algoritmi Asimmetrici: ElGamal, DSA (solo per Firme Digitali) usano i Logaritmi Discreti


3.3 Uso degli Algoritmi Asimmetrici

● USO: Poiché sono lenti si usano per lo più per autenticazione, firme digitali e lo scambio di Chiavi Simmetriche

● Se A cifra con la propria chiave Privata, tutti possono decifrare con la chiave pubblica di A ottenendo di essere sicuri che è stato proprio A ad inviare il messaggio (Firma Digitale, autenticazione)

● Se B cifra con la chiave Pubblica di A, solo A può decifrare il messaggio (confidenzialità)

● Problema risolto: Scambio delle chiavi segrete per gli algoritmi simmetrici

● PROBLEMA: come faccio ad essere sicuro che una certa chiave Pubblica appartiene proprio ad A ?


3.4 Hash

● Trasforma una stringa di lunghezza arbitraria in una di lunghezza fissa detta Impronta (Hash o Digest)

● Hash Crittografico:● Data un'Impronta non è possibile ricostruire la stringa o documento

originario (resistenza alle preimmagini)● E' statisticamente impossibile che due documenti (di lunghezza

sufficiente) generino la stessa Impronta (resistenza alle collisioni)● Una piccola modifica di un documento genera una grande modifica

dell'Impronta (resistenza alle correlazioni)


3.4 Hash

● Attenzione: un algoritmo di HASH perfetto non esiste, prima di utilizzare un particolare algoritmo, verificare che non abbia debolezze critiche per la applicazione specifica

● Supponiamo di considerare tutte le stringhe di lunghezza sino a t e di farne un Hash (perfetto) di lunghezza n => vi sono 2t-n stringhe che producono la stessa impronta ! Scegliendo a caso due stringhe, la probabilità che abbiano la stessa impronta è 2-n (indipendente da t)

● La lunghezza dell'impronta è connessa al problema delle collisioni


3.4 Hash

● Proviamo a costruire un algoritmo di Hash (questa è in realtà una checksum non crittografica, da NON usare per sicurezza):● Data la stringa originale lunga b bit, si estenda con padding ad un

multiplo di 128 bit● Si divida la stringa in m sottoblocchi di 128 bit (m x 128 = b + pad)● Si faccia lo XOR di ogni sottoblocco con il successivo, il risultato è

una stringa di 128 bit● Di solito nel padding si aggiunge b (od una sua rappresentazione)

per ridurre le collisioni● Ma il vero problema per la sicurezza è ovviamente l'ultimo passo,

cioè lo XOR


3.4 Hash

● La struttura di un algoritmo di Hash è:● Si estenda la stringa di lunghezza b ad un multiplo intero m della

lunghezza n del sottoblocco (di solito n = 512 bit = 64 Byte) includendo nel padding una rappresentazione di b

● Si divida la stringa in m sottoblocchi di lunghezza n● Per ogni sottoblocco x

i si calcoli H

i = f(x

i,H

i-1) ove H

i è il valore

dello Hash sino al sottoblocco i, ed è di lunghezza h (ad esempio h = 128 o 160 bit); la funzione f è il cuore dell' algoritmo di Hash


3.4 Hash

● Hash basati su Algoritmi Simmetrici: la funzione f è basata sul calcolo di E

K(X) xor X ove E rappresenta la cifratura utilizzando ad esempio

DES, e la chiave K ed il testo X sono derivati da xi e H

i-1

● Algoritmi di Hash Custom: la funzione f è costruita appositamente per soddisfare il più possibile le richieste di un Hash utilizzando (come per gli algoritmi simmetrici) multipli round di sostituzioni e permutazioni:● MD4 (rotto, ma è la base di tutti i successivi)● MD5● SHA1● RIPEMD160


3.4 Hash

Nome H(in bit) n(in bit) Preimage Collision Round x step Velocità rel.

MD4 128 512 2128 220 3 x 16 1.00MD5 128 512 2128 264 4 x 16 0.68SHA1 160 512 2160 280 4 x 20 0.28RIPEMD160 160 512 2160 280 5 x 16 0.24

source HAC


3.4 Yuval' s Birthday Attack ad un Hash

● Basato sul Teorema del Paradosso dei Compleanni (se vi sono 23 persone in una stanza, la probabilità che due abbiano il compleanno lo stesso giorno è del 50%)

● Siano dati due messaggi X1 (vero) e X

2 (truffaldino) ed un algoritmo di Hash di

lunghezza m bit (esempio 128 o 160 bit)● Si generino 2m/2 modifiche di X

1 e di X

2, X'

1 e X'

2, ad esempio cambiando la

formattazione, sostituendo spazi bianchi con tab ecc.ecc. (sono necessarie 2m/2 operazioni per ottenere una collisione)

● Si calcolino gli Hash di tutti gli X'1 e X'

2

● Si trovino i due messaggi X'1 e X'

2 con IDENTICO hash (garantito dal Teorema)

● Il truffatore fa firmare digitalmente il contratto X'1 ma poi va dal giudice dicendo

che il contratto firmato è X'2 visto che hanno lo stesso Hash


3.4 MAC● Message Authentication Code (MAC): in generale è un codice che

permette di stabilire l'autenticità di un documento (ma da solo non il NonRipudio)

● HMAC: MAC basati sull'uso di un HASH insieme ad una chiave segreta (RFC2104)

● Caso più semplice: concatenare una chiave segreta al documento e poi calcolarne la Impronta, solo chi conosce la chiave segreta può verificarla e solo chi ha la chiave segreta può averla fatta (attenzione alle collisioni o la possibilità di creare HMAC falsi dato uno vero)

● Oppure creare un algoritmo MAC basato su di un Algoritmo simmetrico, ad esempio DES, chiave 56 bit, sottoblocco e hash 64 bit

Hi = f = E

K(H

i-1 xor x

i)


3.5 Paragone Algoritmi

Symmetric and Public-key Key Lenghts with similar resistances to brute force attacks (in bits, * broken)

Symmetric Public-key 56* 384 64* 512 80 768 112 1792 128 2304

Recommended Public-key Key Lengths (in bits)

Year Length Min Length Max 1995 768 1536 2000 1024 1536 2005 1280 2048 2010 1280 2048 2015 1536 2048

Source: B.Schneier, Applied Cryptography



+-------------+-----------+--------------+--------------+ | System | | | | | requirement | Symmetric | RSA or DH | DSA subgroup | | for attack | key size | modulus size | size (bits) | | resistance | (bits) | (bits) | | | (bits) | | | | +-------------+-----------+--------------+--------------+ | 70 | 70 | 947 | 129 | | 80 | 80 | 1228 | 148 | | 90 | 90 | 1553 | 167 | | 100 | 100 | 1926 | 186 | | 150 | 150 | 4575 | 284 | | 200 | 200 | 8719 | 383 | | 250 | 250 | 14596 | 482 | +-------------+-----------+--------------+--------------+

Source: RFC3677



Sour

ce N

IST


4.1 Cifrare Messaggi con Algoritmi Simmetrici

1. Scegliere 1 Chiave Simmetrica per ogni messaggio da cifrare di lunghezza opportuna

2. Ricordarsi a Memoria, o tenere in luogo sicuro, tutte le chiavi (NON su di un computer)

3. PROBLEMA: creazione e gestione di tutte le chiavi

Garantisce: Confidenzialità


4.1 Scambiare Messaggi con Algoritmi Simmetrici

1. Scegliere 1 Chiave Simmetrica per ogni messaggio da cifrare e per ogni corrispondente di lunghezza opportuna

2. Inviare la Chiave in modo sicuro al proprio corrispondente!3. Ricordarsi a Memoria, o tenere in luogo sicuro, tutte le chiavi (NON

su di un computer)4. PROBLEMA: creazione e distribuzione di tutte le chiavi

Garantisce: Confidenzialità ed Autenticità (Debole)

(se la chiave segreta è nota solo ai due corrispondenti, un messaggio decifrato con quella chiave [molto probabilmente] è stato cifrato dall'altro corrispondente ed è sicuro poiché è cifrato)


4.1 Scambiare Messaggi con Algoritmi Simmetrici

5. Se al messaggio concateniamo anche il suo Hash prima della cifratura, otteniamo anche l'integrità

Garantisce: Confidenzialità, Autenticità (Debole) ed Integrità

(se sono in grado di provare che quella chiave apparteneva al mio corrispondente, allora posso ottenere anche il Non Ripudio)


4.2 Cifrare Documenti con Algoritmi Asimmetrici

1. A cifra il documento con la propria chiave Pubblica

2. A mantiene la propria chiave Privata in un posto molto sicuro (Smart Card ???)

3. Per decifrare il documento è necessaria la chiave Privata di A, che A deve quindi proteggere bene!

Garantisce: Confidenzialità


4.2 Scambiare Messaggi con Algoritmi Asimmetrici

1. A(lice) vuole inviare un messaggio cifrato a B(ob)

2. A si procura la chiave Pubblica di B

3. A cifra il messaggio con la chiave Pubblica di B (solo B ha la corrispondente chiave Privata perciò solo B può decifrare il messaggio)

4. A invia il messaggio cifrato a B

5. B decifra il messaggio con la sua chiave Privata


4.2 Scambiare Messaggi con Algoritmi Asimmetrici

Cifrare con la Chiave Pubblica del destinatario

Garantisce: solo Confidenzialità (autenticità mittente manca del tutto, chiunque può inviare il messaggio usando la chiave Pubblica di B)


4.2 Confronto

● Chiave Simmetrica: molto veloce, immediato ottenere Autenticità (Debole) oltre Confidenzialità, facile Integrità (non Ripudio ?)

Problema: Distribuzione Chiavi

● Chiave Asimmetrica: facile distribuire chiavi, nella modalità di base solo Confidenzialità (vedremo come ottenere il resto)

Problema: Lentissimo !!!


4.3 Firma Digitale

Autenticità con Algoritmi Asimmetrici

1. A genera un'Impronta del documento che vuole inviare a B2. A cifra l' Impronta con la propria chiave Privata (solo A può fare

questo)3. A invia il messaggio e l'Impronta cifrata a B4. B si procura la chiave Pubblica di A 5. B decifra l'Impronta inviata da A con la chiave Pubblica di A6. B calcola indipendentemente l'Impronta del messaggio ricevuto

da A e la confronta con quella ricevuta da A

Se le due Impronte coincidono si ha Autenticità ed Integrità


4.3 Firma Digitale

Per la Firma Digitale bisogna cifrare (l'Impronta) con la Chiave Privata del Mittente


4.3 Solo Autenticazione

A: Ciao Bob B: Chi sei? A: Sono Alice B: Non ci credo!

1. A si connette a B

2. B ha la chiave Pubblica di A, B vuole essere sicuro di parlare con A

3. B invia ad A un numero casuale in chiaro (nonce)

4. A cifra il numero casuale con la propria chiave Privata

5. A invia il numero casuale cifrato a B

6. B decifra il numero con la chiave Pubblica di A, se il numero è uguale a quello inviato, B è sicuro di parlare con A


4.3 Solo Autenticazione

In alternativa:

1. B cifra il numero casuale con la Chiave Pubblica di A

2. A lo decifra con la sua Chiave Privata

3. A invia a B un'impronta del numero

4. B verifica che le impronte corrispondano


4.4 Utilizzo congiunto dei protocolli

Prendiamo come esempio l'invio di un messaggio di posta elettronica utilizzando PGP. Vogliamo ottenere Confidenzialità, Autenticità ed Integrità.

1. A vuole inviare un lungo messaggio a B2. A si procura la chiave Pubblica di B ed ha pronta la propria chiave

Privata3. A appone una Firma Digitale al documento da inviare, con la propria

chiave Privata4. A sceglie un Algoritmo Simmetrico e genera una Chiave Simmetrica

detta Di Sessione (casuale)


4.4 Utilizzo congiunto dei protocolli5. A cifra il messaggio + firma digitale per B con l'Algoritmo

Simmetrico e la Chiave simmetrica scelta6. A cifra la Chiave Simmetrica con la Chiave Pubblica di B (solo B

può decifrarla!)7. A concatena al messaggio cifrato con la chiave Simmetrica, la

chiave Simmetrica stessa cifrata con la chiave Pubblica di B8. A invia il tutto a B


4.4 Utilizzo congiunto dei protocolli

9. B riceve il messaggio10. B con la propria Chiave Privata decifra la chiave Simmetrica (di

sessione)11. B con la Chiave Simmetrica decifra il messaggio e la Firma Digitale12. B calcola l'impronta del messaggio13. B usa la chiave Pubblica di A per decifrare la Firma Digitale14. B confronta le due impronte, se sono uguali ha ottenuto

Confidenzialità, Autenticità e Integrità

La stessa struttura è utilizzata da molti altri protocolli quali: IPSEC, SSL/TSL, SSH, SMIME ecc.


4.5 PKI

● Autenticazione iniziale● Verifica delle credenziali● Non ripudiabilità

ProblemiProblemi

● Voglio inviare un documento ad Alice, trovo su di un sito Web la sua Chiave Pubblica, sarà veramente di Alice o di un impostore?

● Faccio firmare un contratto Digitalmente, ma il contraente nega di aver mai posseduto quella chiave Asimmetrica, e di non aver mai firmato un contratto in quella data.


4.5 PKI

SoluzioniSoluzioni

● WebofTrust (PGP)

● Ente Certificatore ● Certification Authority (CA)● più una infrastruttura per la verifica dei certificati rilasciati dall' ente

certificatore (Public Key Infrastructure, PKI)


4.5 PKI

● Registration Authority (RA): identifica (autentica) chi sta richiedendo la emissione di un certificato digitale

● Certification Authority (CA): Emette il Certificato Digitale Distribuisce il proprio Certificato Digitale (autofirmato) per

permettere la verifica dei certificati Revoca i certificati digitali se scaduti o se la chiave Privata è stata

compromessa (Certificates Revocation List, CRL, OCSP)


4.5 PKI

● Non Ripudio: Per i contratti necessario vero non ripudio possibile solo con Timestamp Authority (TA), garantisce con un'altra Firma Digitale il momento in cui la Firma Digitale è apposta

● RA/CA Privata: genera e gestisce Certificati Digitali per dipendenti, clienti, elaboratori e applicazioni solo 1 password, quella per la Chiave Privata del Certificato Digitale


4.6 Certificato Digitale

● La chiave Pubblica dell' utente (Alice)● Firmata Digitalmente con la chiave Privata dell' ente certificatore (CA)● Con l'aggiunta di una serie di dati che caratterizzano sia l' utente

(nome indirizzo ecc.) che la CA

● Firmando il certificato digitale la CA garantisce l' identità della chiave Pubblica in esso contenuto

● I certificati sono strutturati come un Directory Service (ITU X.500) in modo gerarchico (ad albero):

Root => Country (c) => Organization (o) => OrganizationalUnit (ou) => CommonName (cn)



● Esempio: cn=Mario Rossi, ou=Ufficio Acquisti, o=Società XXX, c=IT

● Il percorso che individua un elemento in una Directory si chiama DistinguishedName (dn)

● Una Directory può contenere i Certificati Digitali, che si ottengono specificando il dn (X509 v3)

● Si può accedere ad una Directory X.500 via TCP/IP usando LDAP (Lightweight Directory Access Protocol) (LDAP v3)



X509:numero serie algoritmo firmanome CA validità (da/a)nome soggetto chiave pubblicafirma digitale

X509v3 (1996) Estensioni:ind. Criticità id. Estensioneval. Estensione

● uso chiave (CA, firma, email ..)● CRL distribution point



X509 CRL:data emissione algoritmo firmanome CA next updatelista certificati revocati

X509v3 (1996) CRL Estensioni:CRL number Authority KeyCRL Reason Code (per ogni certificato revocato)


Bibliografia Essenziale

● A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography, CRC Press, New York, 1997 (HAC)

● B. Schneier, Applied Cryptography, John Wiley & Sons, New York 1997

● D. Welsh, Codes and Cryptography, Oxford Science Pub., New York, 1988

● T.M. Cover, J.A. Thomas, Elements of Information Theory, John Wiley & Sons, New York, 1991

● D. Kahn, The Codebreakers, McMillan Pub., New York, 1967● C. Meltzer, D. Baker, Cryptography Decrypted, AddisonWesley, 2001


Bibliografia Essenziale

● 3DES FIPS: http://csrc.nist.gov/publications/fips/fips463/fips463.pdf● AES home page: http://www.esat.kuleuven.ac.be/~rijmen/rijndael/● AES NIST: http://csrc.nist.gov/CryptoToolkit/aes/● AES FIPS: http://csrc.nist.gov/publications/fips/fips197/fips197.pdf● AES WiKi:http://en.wikipedia.org/wiki/Advanced_Encryption_Standard● Attacchi a AES: http://www.cryptosystem.net/aes/● Breve introduzione a AES online

http://home.ecn.ab.ca/~jsavard/crypto/co040401.htm● R. River, A. Shamir, L. Adleman, A method for obtaining digital signa

tures and publickey cryptosystems, Comm. ACM 21 (1978) 120● R. Rivest, The MD5 MessageDigest Algorithm, RFC1321


Bibliografia Essenziale in Italiano

● Simon Singh, Codici e segreti, Rizzoli, Milano, 1999

● L. Berardi, A. Beutelspacher, Crittologia, FrancoAngeli, Milano, 1996

● A. Sgarro, Crittografia, Franco Muzzio Editore, Padova, 1993

● M. Zanotti, Crittografia, Hoepli Editore, Milano, 1976

● P. Ferragina, F. Luccio, Crittografia, Bollati Boringhieri, Torino, 2001


Copyright

Queste slide sono Copyright Andrea Pasquinucci/CLUSITEDUCATION, possono essere distribuite in formato PDFnonmodificabile o cartaceo solo ai soci CLUSIT ed ai partecipanti ai seminari CLUSITEDUCATION secondo la licenza Creative Commons ncnd 2.0 qui sotto sommariamente riportata.

This work is licensed under the Creative Commons AttributionNonCommercialNoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/byncnd/2.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA. You are free:● to copy, distribute, display, and perform the work under the following conditions:

● Attribution. You must give the original author credit.● Noncommercial. You may not use this work for commercial purposes.● No Derivative Works. You may not alter, transform, or build upon this work.

● For any reuse or distribution, you must make clear to others the license terms of this work.● Any of these conditions can be waived if you get permission from the copyright holder.

Andrea Pasquinucci Fileserver... · ©Andrea Pasquinucci Principi di Crittografia P a g . 5 1.1...

Documents

Transcript of Andrea Pasquinucci Fileserver... · ©Andrea Pasquinucci Principi di Crittografia P a g . 5 1.1...