Sicurezza nei Sistemi Informativi Crittografia Asimmetrica · Da un lato, però, i problemi di...

Sicurezza nei Sistemi Informativi

Crittografia Asimmetrica

Ing. Orazio [email protected]

Dipartimento di Ingegneria Informatica e delle TelecomunicazioniUniversità di Catania

O.Tomarchio Sicurezza nei Sistemi Informativi 2

Crittografia a chiave pubblica

Costituisce probabilmente la più significativa innovazione nella storia della crittografia

Viene usata una coppia di chiavi: una pubblica e l’altra privata

Si parla di algoritmi asimmetrici in quanto le due parti non sono uguali

Si basa su alcuni concetti legati alla teoria dei numeri Non sostituisce completamente la crittografia a chiave

segreta, piuttosto è complementare ad essa



La crittografia a chiave pubblica (o asimmetrica) coinvolge l’uso di due chiavi: Una chiave pubblica, che può essere resa nota a chiunque,

e che viene usata per cifrare messaggi e verificare signature (firme digitali)

Una chiave privata, conosciuta solo dal legittimo proprietario, che viene usata per decifrare messaggi e per creare signature (firme digitali)

Si parla di algoritmi asimmetrici poiché: chi decifra un messaggio NON può cifrare lo stesso messaggio chi verifica una firma NON può creare la firma



chiavi generate a coppie: chiave privata (Kpri) + chiave pubblica (Kpub)

chiavi con funzionalità reciproca: i dati cifrati con una chiave possono essere decifrati solo con l’altra


Schema ad alto livello

k1 = chiave pubblica di Alice, k2 = chiave privata di Alice m, c = stringhe di bit di lunghezza b Dk2 = Ek1

-1

Proprietà fondamentale (oltre alle proprietà “classiche” già viste per gli algoritmi simmetrici): data k1, deve essere computazionalmente impossibile ricavare k2

Differenze fondamentali rispetto ai meccanismi simmetrici: La chiave k1 usata per Ek può essere distribuita utilizzando canali insicuri Conseguentemente, però, assicurare l’autenticità di k1 diventa più importante, e

più complesso


Applicazioni

Possiamo classificare gli utilizzi della crittografia a chiave pubblica in tre schemi:

encryption/decryption (fornisce confidenzialità)

digital signatures (fornisce autenticazione)

key exchange (di chiavi di sessione)


Confidenzialità senza segreti condivisi

Un generico utente può generare un messaggio segreto per uno specifico destinatario (X) conoscendone solo la chiave pubblica (Kxpub)

Solo il proprietario della chiave privata corrispondente (Kxpri) può decifrare il messaggio


Firma digitale

firma digitale = cifratura asimmetrica dei dati con la chiave privata dell’autore

solitamente non si cifrano direttamente i dati ma un loro riassunto ( digest ) (lo vedremo meglio più avanti)

fornisce autenticazione, integrità dei dati e non ripudio


Caratteristiche fondamentali

Diffie-Helmann, RSA

RSA, ElGamal, DSSRSAAlgoritmi più importanti

- Ottenere la chiave effimera- man-in-the-middle

Falsificazione della firma- Ottenere m partendo da c

- Ottenere k2 partendo da k1

Attacchi di sicurezza più importanti

Instaurazione di una chiave temporanea da usare tra due o più entità per lo scambio confidenziale di dati

1. Autenticazione (di un messaggio)

2. Integrità3. Non ripudio

Classico concetto(così come già visto nello schema generico)

Obiettivi

Scambio di chiaviFirma digitaleConfidenzialità


Alcune note…

Il concetto fondamentale alla base dei meccanismi crittografici asimmetrici è l’esistenza di alcune operazioni elementari che operano sui numeri interi che: Sono semplici da calcolare direttamente

(esempio: n = p·q, con p,q numeri primi) Ammettono solo (ad oggi) algoritmi estremamente inefficienti per il

calcolo dell’operazione inversa (esempio: calcolare, dato n, i suoi fattori primi p e q)

Come vedremo, la sicurezza dei meccanismi crittografici asimmetrici introdotti ad oggi si basa sulla difficoltà tecnica della soluzione di alcuni problemi classici di base della teoria dei numeri La difficoltà nella soluzione di tali problemi è legata strettamente alla

sicurezza dei sistemi crittografici asimmetrici, in quanto il calcolo di Kpub da Kpriv , per esempio, richiede la soluzione di tali problemi


Alcune note…

Anche le migliori tecniche scoperte ad oggi non riescono a risolvere problemi numerici come la fattorizzazione di grandi numeri in maniera efficiente

Non è ancora stata trovata alcuna prova, in senso scientifico, circa la sicurezza dei meccanismi crittografici asimmetrici. In più, questi meccanismi crittografici sono stati introdotti, e quindi analizzati, solo da qualche decennio

Da un lato, però, i problemi di teoria dei numeri alla base di questi meccanismi sono stati studiati da secoli, e si potrebbe quindi pensare che questo sia una garanzia di sicurezza (“se non hanno trovato tecniche efficienti fino ad ora…”)…

…d’altro canto i matematici che hanno studiato tali problemi fin’ora l’anno fatto senza avere come obiettivo un meccanismo crittografico. Lo studio di tali problemi con l’obiettivo di crittanalizzare algoritmi crittografici ha già portato a un miglioramento sostanziale delle tecniche di base usate per la soluzione dei problemi della teoria dei numeri ai quali abbiamo fatto riferimento


Algoritmi a chiave pubblica

Diffie-Helmann Primo algoritmo a chiave pubblica (1976) Utilizzato per problemi di key-exchange

RSA (Rivest – Shamir – Adleman) Basato su prodotto di grandi numeri primi e relativa difficoltà a

fattorizzare il risultato Utilizzabile sia per segretezza che per firma digitale Brevettato da RSA (negli USA) – (scaduto nel 2000)

DSA (Digital Signature Algorithm) Elevamento a potenza, logaritmo del risultato Applicabile solo per firma digitale Standard NIST per DSS (FIPS-186)

Diffie - Helmann


L’algoritmo di Diffie-Helmann (DH)

Primo algoritmo a chiave pubblica (1976) pubblicato

Obiettivo fondamentale: Scambio sicuro di credenziali crittografiche effimere

(chiavi di sessione temporanee)

Problema fondamentale su cui si basa: È semplice calcolare b = ai mod p Non è ancora stato scoperto un algoritmo efficiente per il

calcolo di i, dati a,b e p (i = logaritmo discreto mod p di b, con base a)


DH: meccanismo di base

Alice e Bob scelgono due interi grandi n e g tali che: n numero primo (grande) g radice primitiva di n (le sue potenze mod n generano tutti gli interi da 1 a n-1)

Alice, scelto un numero a caso x, calcola: A = gx mod n

Bob, scelto un numero a caso y, calcola: B = gy mod n

Alice e Bob si scambiano (pubblicano) A e B Alice calcola kA = Bx mod n

Bob calcola kB = Ay mod n

ma… kA = kB = gxy mod n


DH: meccanismo di base

kA = kB = gxy mod n


Sicurezza di DH

Attacchi passivi È computazionalmente inefficiente, dati a,b e n calcolare i t.c. b=ai mod p

(le tecniche di oggi sono sub-esponenziali, ma super-polinomiali) Attacchi passivi

Leggermente meno complessi da portare se n non è un “primo sicuro”. n è un numero primo sicuro se ((n-1)/2) è primo

Attacchi attivi: DH porta ad uno scambio non autenticato di una chiave effimera Alice e Bob non sono autenticati Attacco man-in-the-middle (se l’attaccante può manipolare i dati)

Soluzione possibile: usare n e g costanti, noti “a tutti” Problema: se tutti usassero gli stessi n e g, il calcolo della tabella (gigante!) dei

logaritmi discreti mod n con base g permetterebbe di compromettere tutti gli scambi DH che usano n e g

Altre soluzioni al problema, e altri usi di DH immuni a questo tipo di attacchi inclusi protocolli di autenticazione basati su DH (lo vedremo più avanti)

In generale, la generazione di n e g è un’operazione computazionalmente complessa


DH: attacco man-in-the-middle


L’algoritmo RSA

Specificato nel 1977, pubblicato nel 1978: primo meccanismo asimmetrico “tuttofare” pubblicato, e ancora in uso

Obiettivi Confidenzialità dei dati Firme digitali Scambio di chiavi effimere

Problema fondamentale su cui si basa: È semplice calcolare n = p·q, con p e q numeri primi Non è ancora stato scoperto un algoritmo efficiente per il calcolo di p e q,

dato n (fattorizzazione di n, con n “grande”)


Qualche definizione matematica

Numeri primi relativiDue numeri sono primi fra di loro (o “primi relativi”) se non hanno fattori primi in comune(equivale a dire che il loro MCD è pari a 1)

Funzione toziente di Eulero, (n)numero di interi positivi minori di n e primi relativi di n Se p è un numero primo, allora (p) = p-1 Se p e q sono primi ed n = pq, allora

(n)=(pq)=(p) (q) = (p-1)(q-1)


Qualche definizione matematica

Teorema di EuleroPer ogni a ed n primi relativi allora:

a(n) = 1 mod n

CorollarioDati p e q numeri primi, n = pq, ed m con 0<m<n, allora:

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


L'algoritmo RSA: schema

p, q sono due numeri primi (segreti e scelti) n = p * q (pubblico, calcolato) e, relativamente primo

rispetto a (p-1) e (q-1) (pubblico, scelto)cioè mcd((n), e) = 1

d = e-1 mod (n) (privato, calcolato)

Chiave privata → Kpr = { d, n }

Chiave pubblica → Kpub = { e, n }


L'algoritmo RSA: schema funzionamento

Cifratura di un blocco M (con M < n)

CifraturaC = Me mod n

DecifraturaM = Cd mod n

Ruolo di e e d interscambiabile


Perchè RSA funziona

Ricordiamoci che ed = 1 mod (n)

Cd mod n = (Me)d mod n = Me d mod n = M mod n = M

poichè 0≤ Μ<n

Per il corollario delTeorema di Eulero


L'algoritmo RSA: esempio numerico

Generazione chiavi Selezionare due numeri primi p = 11 e q = 5 Calcolare n = pq = 11 * 5 = 55 Calcolare (n) = (p-1)(q-1) = 10 * 4 = 40 Selezionare e primo relativo di (n) = 40, e < (n)

si sceglie e = 3 Calcolare d tale che d*3 = 1 mod 40

Si ottiene d = 27 in quanto: 27 * 3 = 81 = 2 * 40 + 1

Chiavi risultanti: Kpub = { 3, 55 } Kpriv = { 27, 55}


L'algoritmo RSA: esempio numerico

Cifratura di M = 5 Occorre calcolare C = 53 mod 55

C = 53 mod 55 = 125 mod 55 = (2*55+15) mod 55 = 15

Decifratura C =15 Occorre calcolare M = 1527 mod 55

M = 1527 mod 55 = … = 5


L’algoritmo RSA

Base n = p · q nota a tutti p e q sono primi, grandi e segreti chiave pubblica: e scelta a caso purchè relativamente

primo rispetto a p-1 e q-1 chiave privata: d = e-1 mod (p-1)·(q-1)

testo da cifrare: t < N crittografia: c = te mod N decrittografia: t = cd mod N ruolo di e e d interscambiabile

perché (xd)e mod n = (xe)d mod n


L’algoritmo RSA

Sintesi dei parametri principali


RSA: confidenzialità

Bob vuole inviare un messaggio cifrato ad Alice

Alice possiede una coppia di chiavi KApub ={e,n} KApriv = d

Alice invia la propria chiave pubblica KApub ={e,n}

Bob calcola c = me mod ne lo invia ad Alice(m deve essere minore di n)

Alice decifra il messaggio calcolando m = cd mod n

Problema: come fa Bob ad essere sicuro che la chiave pubblica ricevuta sia quella di Alice?

Alice Bob

x

KApub ={e,n}

c = me mod nc

m= cd mod n

Trudy?


RSA: autenticazione ed integrità

Alice vuole inviare un messaggio firmato a Bob



Alice calcola f = md mod ne lo invia a Bob(m deve essere minore di n)

Bob verifica la firma calcolando m’=fe mod n e confrontando m’ con m

Nota: Bob (un qualunque verificatore) non ha bisogno della chiave privata di Alice

Alice Bob

x

KApub ={e,n}

m’ = fe mod n m’ = m ?

m, f

f= md mod n

Trudy?


RSA: scambio chiavi di sessione

Alice e Bob vogliono creare un segreto condiviso (da usare come chiave per un cifrario simmetrico)



Bob genera un valore random r e calcola c = re mod n e lo invia ad Alice(r deve essere minore di n)

Alice decifra il messaggio calcolando r = cd mod n

Da questo momento in poi Alice e Bob hanno un segreto condiviso: r

Alice Bob

x

KApub ={e,n}

r = randomc = re mod nc

r= cd mod n

Trudy?


Utilizzo di RSA (in pratica)

Come vedremo nella sezione dedicata ai protocolli, RSA in pratica viene usato solo per crittografare stringhe di bit di lunghezza molto limitata (di solito meno di 160 bit)

Per la firma digitale, come vedremo in seguito, non si cifra l’intero messaggio ma un hash del messaggio

Motivi principali: RSA è molto inefficiente dal punto di vista computazionale Non è possibile usare meccanismi diversi dal CBC (o EBC) per

messaggi lunghi


Generazione/calcolo dei parametri

Perché RSA sia sicuro, è necessario utilizzare valori di n molto grandi (di solito almeno 150 cifre, circa 512 bit)

Questo porta a valori di d ed e molto elevati

Diversi meccanismi per velocizzare le operazioni (un elevamento a potenza mod n si può scomporre in produttorie, quadrati, moltiplicazioni, ecc…)



Ricerca di p e q (grandi a sufficienza da generare n almeno di 512 bit)

Metodo più efficiente Scegliere un numero x a caso grande a sufficienza Verificare che x sia primo, altrimenti ricominciare

La probabilità r che x sia primo è circa (ln x)-1

Per x intorno ai 512 bit r è circa 1/230

Test di primalità ……



Scelta di e Il parametro e può anche essere una costante (!): i valori più usati sono 3, 17 e

65537 (216 + 1) Vantaggi:

Le operazioni legate alla cifratura (encryption, verifica di firme) sono tanto più efficienti e veloci quanto più e è piccolo

è molto facile fare l’elevamento a potenza perché 65537 contiene solo due bit a uno

Non è necessario cercare e tale che mcd(e,φ(n)) = 1 È più semplice, con “trucchi” vari, ricavare p e q tali che (p-1), (q-1) siano

relativamente primi ad e, dato e

Ovviamente non si potrebbe fare lo stesso con d : se d fosse troppo piccolo, la ricerca esaustiva sullo spazio di d sarebbe troppo semplice (d va mantenuto segreto…)


Sicurezza di RSA

Quattro classi di attacchi Ricerca esaustiva nello spazio d

(contrattacco: usare n con il numero maggiore di bit possibile. Problema: più grande è n, più lento sarà l’algoritmo)

Attacchi matematici: per es., fattorizzazione di n I migliori algoritmi per la fattorizzazione dei numeri sono estremamente

inefficienti (sub-esponenziali, ma super-polinomiali) Migliaia di anni-MIPS per la fattorizzazione di un numero di 512 bit (150+

di cifre) Attacchi attivi di tipo man-in-the-middle legati alla mancata autenticazione

delle chiavi pubbliche Attacchi di altro tipo: per esempio, smooth numbers attacks: attacchi poco

probabili


Sicurezza di RSA

1.1. Fattorizza n2.2. Computa (p-1)(q-1)3.3. Computa d ← e-1 mod (p-1)(q-1)

1.1. Fattorizza n2.2. Computa (p-1)(q-1)3.3. Computa d ← e-1 mod (p-1)(q-1)

Se potesse fattorizzare…


Sicurezza di RSA

Se potesse computare ϕ (n)=(p-1)(q-1)

…

… potrebbe calcolare d ← e-1 mod (p-1)(q-1)


Se potesse computare ϕ (n)=(p-1)(q-1),

potrebbe calcolare d ← e-1 mod (p-1)(q-1)

n = pq ϕ (n) = (p-1)(q-1)

Due soluzioni: p,q

Sicurezza di RSA

sostituendo p = n/q

p2- (n-ϕ (n)+1)p + n = 0

sostituendo p = n/q

p2- (n-ϕ (n)+1)p + n = 0


Sicurezza di RSA

Se potesse computare d …

… ma questo è computazionalmente

equivalente a fattorizzare!


Sicurezza di RSA

Scoprire d conoscendo e, n e c Non è stato dimostrato (matematicamente) che sia necessario fattorizzare n per ricavare d. È

anche vero che se si trovasse un meccanismo tale, questo meccanismo potrebbe essere usato per fattorizzare n…

Calcolare φ(n) È stato dimostrato che ciò sarebbe altrettanto complesso (computazionalmente) della

fattorizzazione di n Ricerca esaustiva sullo spazio di d

Ancora meno efficiente delle tecniche di fattorizzazione Naturalmente la sicurezza di RSA dipende in misura proporzionale dalla

dimensione di n (in bit) Oggi si ritiene che sia necessario utilizzare n di almeno 1024 bit per ottenere una coppia di

chiavi “sicure” contro la fattorizzazione Se m può assumere solo un numero piccolo di valori diversi mi, può essere possibile per

un intruso crittografare con Kpub tutti i possibili valori di mi, e confrontare poi i vari ci con quanto transita sul canale

Soluzione: concatenare m con un numero casuale prima di crittografarlo


Sicurezza di RSA (attacchi teorici)

Smooth numbers attack (numeri che sono il prodotto di un insieme (piccolo) di (piccoli) numeri primi) Attacco estremamente improbabile, specialmente perché, nelle

implementazioni di RSA (i protocolli), i messaggi vengono firmati solo dopo adeguato padding con numeri casuali, rendendo la probabilità che Alice firmi uno smooth number estremamente bassa

Timing attack Attacco che si basa sulla possibilità, per Trudy, di osservare il tempo

necessario per un calcolatore ad effettuare le operazioni di moltiplicazione ed elevamento a potenza


Lunghezza delle chiavi RSA

256 bit sono attaccabili in alcune settimane

512 bit sono attaccabili in alcuni mesi

1024 bit offrono una sicurezza ragionevole per vari secoli


Lunghezza delle chiavi RSA

1 MIPS-year: un processore da 1 MIPS in esecuzione per un intero anno

Un Pentium da 1GHz è un PC da circa 250 MIPS


RSA PKCS (Public Key Cryptography Standard)

Standard sviluppato da RSADSI per normalizzare i meccanismi (protocolli) con cui usare RSA

Definisce Come codificare una chiave pubblica (e privata) Come codificare una firma RSA (il risultato dell’operazione di firma) Come codificare (aggiungere padding) prima di crittografare un

messaggio “corto” con RSA Come codificare (aggiungere padding) prima di firmare un messaggio

“corto” con RSA I meccanismi definiti da PKCS sono pensati per ridurre al minimo le

possibilità di attacchi conosciuti non sulla matematica di RSA, ma sulle sue implementazioni Per esempio, il fatto di aggiungere padding casuale in un certo modo (come

specificato da PKCS), riduce la minimo la possibilità di portare attacchi come quelli che abbiamo visto quando e=3


RSA: sommario

Primo algoritmo di crittografia asimmetrica pubblicato (con molteplici usi) ancora in uso

La crittanalisi effettuata in 30 anni non ne ha provato l’insicurezza, ma nemmeno la sicurezza

Operazione di generazione delle chiavi estremamente complessa (e quindi lenta da eseguire)

Estremamente inefficiente (lento) rispetto agli algoritmi moderni simmetrici

Il protocollo con il quale l’algoritmo di base viene usato (per esempio, il padding) ne influenza in maniera estrema la sicurezza effettiva

Usatelo preferibilmente con chiavi di almeno 1024 bit

Altri algoritmi asimmetrici


DSS

Standard proposto dal (solito) NIST nel 1991, basato su una variante di ElGamal DSS: Digital Signature System DSA: Digital Signature Algorithm

Grosso “problema” politico e tecnico, simile a quanto avvenne con il DES È stata proposta dal NIST, con la “benedizione” dell’NSA. Hmmmm… Perché una variante di ElGamal, e non RSA? Diverse componenti delle chiavi, una di 160 bit, l’altra di 512 bit (o più, fino a 1024 bit): ma con 512 bit si

può costruire un calcolatore (con soli 25M$) che sia in grado di creare firme DSS false in meno di un anno…

Richiede l’uso di parametri che sono calcolabili solo in maniera inefficiente. Come per RSA, questi possono anche essere sostituiti da particolari costanti. Le costanti proposte dal NIST non sembrano essere state scelte “a caso”…

Non crittanalizzato a sufficienza …

Molto più veloce di RSA nelle operazioni necessarie a generare chiavi e a calcolare firme, ma molto più lento di RSA (centinaia di volte, se scegliamo e=3) nelle operazioni di verifica delle firme

Progettato per essere implementato su smart-card per applicazioni di autenticazione Firme DSS sempre di 320 bit

Non brevettato Nel ‘91 questo era importante (RSA è rimasto coperto da brevetto fino al Settembre 2000)


Chiavi DSA

utente chiave pubblicautente chiave pubblicaA A (p,q,α ,β ) … …


chiave privatachiave privata(p,q,α ,s)


file pubblico

nnarella

Sicurezza basata sulla difficoltà del

logaritmo discreto


Chiavi DSA





β =α s mod p

q primo di 160 bit, q|(p-1)

p primo di 512, …, 1024 bit

s numero casuale, s<q

α in Zp* di ordine q

file pubblico

nnarella


Algoritmi basati su curve ellittiche

Evoluzione negli algoritmi asimmetrici Se RSA, DH, DSS, ecc. si basano su problemi le cui tecniche di soluzione

migliori ad oggi sono sub-esponenziali (e stanno migliorando velocemente), ECC si basa su una classe di problemi che non ammette (ancora?) algoritmi di soluzione sub-esponenziali

Risultato: Per essere ragionevolmente sicuri, oggi, con RSA, dobbiamo usare chiavi

di 1024 bit o più, rendendo le operazioni RSA molto lente (e, parallelamente, resource intensive). Pensate ad un server web che esegue centinaia di transazioni basate su RSA al secondo…

Usando ECC, possiamo ottenere lo stesso grado di sicurezza con chiavi molto più piccole (ordine di 1/10) di quelle usate con RSA


Alcune note finali…

RSA, così come altri algoritmi crittografici asimmetrici, sono algoritmi a blocchi

Per poterli usare con messaggi più grandi della dimensione del blocco, è possibile applicare gli stessi principi che abbiamo visto per gli algoritmi simmetrici, ma attenzione, non si possono usare quei modi che usano Ek sia in encryption che in decryption, ossia OFB e CFB

Si possono usare ECB e, molto meglio, CBC


Crittografia simmetrica e asimmetrica

Crittografia a chiave segreta Requisiti di funzionamento

Per la crittografia e decrittografia viene utilizzato lo stesso algoritmo con la stessa chiave

Il mittente e il destinatario devono condividere l’algoritmo e la chiave

Requisiti per la sicurezza La chiave deve essere mantenuta segreta Deve essere impossibile o quanto meno

impraticabile decifrare un messaggio senza avere a disposizione altre informazioni

La conoscenza dell’algoritmo e di campioni di testo cifrato non deve consentire di determinare la chiave

Crittografia a chiave pubblica Requisiti di funzionamento

Viene utilizzato un unico algoritmo per la crittografia e la decrittografia con una coppia di chiavi: una per la crittografia e una per la decrittografia

Il mittente ed il destinatario devono utilizzare una coppia di chiave correlate ma distinte

Requisiti per la sicurezza Una delle due chiavi deve essere mantenuta

segreta Deve essere impossibile o quanto meno

impraticabile decifrare un messaggio senza avere a disposizione altre informazioni

La conoscenza dell’algoritmo, di una delle due chiavi e di campioni di testo cifrato non deve consentire di determinare l’altra chiave

Sicurezza nei Sistemi Informativi Crittografia Asimmetrica · Da un lato, però, i problemi di...

Documents

Transcript of Sicurezza nei Sistemi Informativi Crittografia Asimmetrica · Da un lato, però, i problemi di...