Obiettivo: Comunicazioni private in ambienti...

33
Luciano Margara [email protected] http://www.cs.unibo.it/~margara Ufficio: Mura Anteo Zamboni 7 Tel: 051 209 4886 Una Panoramica del corso. Obiettivo: Comunicazioni private in ambienti pubblici Strumento: Cifrari

Transcript of Obiettivo: Comunicazioni private in ambienti...

Page 1: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Luciano Margara

[email protected]

http://www.cs.unibo.it/~margara

Ufficio: Mura Anteo Zamboni 7

Tel: 051 209 4886

Una Panoramicadel corso.

Obiettivo:

Comunicazioni private in

ambienti pubblici

Strumento: Cifrari

Page 2: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Esiste un cifrario perfetto ?

• Perfetto ~ inattaccabile.La risposta è né SI né NO !!• Esistono cifrari perfetti ma inefficienti

• Esistono cifrari pratici non perfetti ma efficienti

• Robustezza• Conquistata sul campo

• Relazione con problemi matematici difficili

• Difficoltà di risoluzione– impossibilità: NO

– improponibilità: SI

Alcune Definizioni

• Crittologia:Crittografia + Crittoanalisi

• Crittografia: progetto di cifrari sicuried efficienti.

• Crittoanalisi: metodi, strumenti etecniche per attaccare i cifrari (valutarela loro bontà).

Lo Scenario

Mitt Destc c…

X

Mitt = mittente del messaggio m in chiaro Dest = destinatario del crittogramma c X = impostore che ascolta (crittoanalista) C e D funzioni di cifratura e decifrazione

L’intruso X

• Motivo: curiosità, spionaggio, malvagità,…• Ruolo

– Passivo: si limita ad ascoltare– Attivo: può inserirsi nella comunicazione o

modificarla• Informazioni in suo possesso:

– Cipher-text attack: serie di crittogrammi c1,…., cn

– Known plain-text attack: collezione di coppie(mi, ci)

– Chosen plain-text attack: collezione di coppiescelte

Page 3: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Definizioni e Notazione

• Funzione di cifratura• C(m) = c è il crittogramma

• Funzione di decifrazione• D(c) = m è il messaggio in chiaro originale

• Matematicamente D è l’inversa di C:

• D(C(m)) = m

• Se D(C(m)) = C(D(m)) = m, allora commutativa

Come realizzare C e D ?

• Due grandi famiglie:• Cifrari per uso ristretto:

• La sicurezza si basa sul fatto che C e D sono tenute

nascoste.

• quindi non è previsto l’uso di una chiave segreta.

• Cifrari per uso generale:

• C e D sono note a tutti.

• La sicurezza si basa sull’utilizzo di una chiave

segreta nota solamente al mittente e al destinatario.

Chiave Segreta:

una metafora fisica.

UgualiUguali

è necessario incontrarsiper scambiarsi le chiavi !!!

Utente BUtente A

• Quanto costa scambiare la chiave ?• Incontro face-to-face ma una tantum

• Posso ammortizzare il costo dello scambio• Posso usare canali costosi e disponibili poco frequentemente

• Lo spazio delle chiavi deve essere grande:

• No brute-force attacks (visita esaustiva dello spazio)• Prerequisito cruciale ma non sufficiente

• Passo in avanti sostanziale:• Dal punto di vista teorico

• Dal punto di vista economico

• Esempi: DES, RC5, IDEA, …(hanno superato la prova del fuoco)

Page 4: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Cifrari Simmetrici o a

chiave segreta

• Ruolo di Ck e Dk completamenteinterscambiabile

• Mittente ~ Destinatario:– Conoscono la stessa chiave k– Entrambi possono cifrare e decifrare– Incontro segreto per accordarsi sulla chiave– Segretezza della chiave dipende da entrambi– Cifratura e decifrazione sono molto efficienti in pratica

• Quali sono i difetti di questi cifrari ?– Occorre scambiarsi la chiave– Dati n utenti, abbiamo bisogno di [n (n-1) / 2] chiavi– Troppe per essere memorizzate e scambiate segretamente

Chiave Pubblica:

una metafora fisica.

MittenteDestinatario

Fase 1Fase 2

Cifrari Asimmetrici o a Chiave

Pubblica

• Anno 1976: punto di svolta! (Diffie-Hellman e Merkle)

• Obiettivo: rompere il legame tra Ck e Dk

– Chiunque sappia come cifrare non deve sapere come decifrare

– Chiave k scomposta in due parti < k[priv], k[pub] > :

• La chiave k viene creata da Dest• k[priv] tenuta segreta da Dest e usata per costruire Dk[priv]

• k[pub] resa pubblica da Dest e usata da tutti per definire Ck[pub]

• Difficile andare da k[pub] a k[priv] !!

• Concetto funzione one-way trap-door:

– Ck[pub] facile, ma Dk[priv] difficile senza k[priv] !

Funzioni One-way con

trapdoor

• Funzioni facili da calcolare,

• difficili da invertire,

• a meno che... non si conoscaqualche informazioneaggiuntiva...

Page 5: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Funzioni One-way con

trapdoor

Lucchetto:- è facile da chiudere- è difficile da aprire- se non si possiede la chiave

Funzioni One-way con

trapdoor

Cassetta delle lettere:- è facile imbucare una lettera- è difficile estrarre una lettera- se non si possiede la chiave

Funzioni One-way con

trapdoor

p,q numeri primi:- è facile calcolare n=pq- è difficile dato n trovare p e q- se conosciamo p diventa

facile (q=n/q)

Il Nuovo Scenario

U1

c

cn

1

Numero chiavi per n utenti ---> soltanto nLasciano penetrare qualche informazione...

Esempi: RSA, El Gamal, … (sono considerati oggi robusti)

Dest

Un

Page 6: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Panacea dellecomunicazioni segrete?

• Cifrari asimmetrici sono inefficienti !

• Sistemi Ibridi = asimmetrici + simmetrici !!– Mitt e Dest scelgono “pubblicamente” una chiave “segreta” K*

utilizzando un cifrario asimmetico

– Mitt e Dest comunicano con un cifrario simmetrico basato su K*

– K* viene sostituita più volte nel corso di una comunicazione

– (session-key)

! Lentezza degli asimmetrici incontrata solo nello scambio sporadico dellesession-key.

! Incontro face-to-face per scambio chiavi segrete (nei simmetrici) aggiratoattraverso l’uso dei cifrari asimmetrici per raggiungere l’accordo.

! N2 chiavi segrete (nei simmetrici) nascoste dall’uso delle session-key (usa egetta).

Conclusioni

• Confidenzialità è il solo requisito dei sistemicrittografici moderni ?

• Oggigiorno se ne richiedono altri 4:

•• User IdentificationUser Identification:: Dest può accertare che è proprio Mitt chesta parlando o vuole parlare con lui.

•• IntegritIntegritàà:: Deve essere possibile per Dest stabilire che ilmessaggio ricevuto non ha subito modifiche parziali o totali(sostituzione).

•• AutenticazioneAutenticazione:: Deve essere possibile per Dest accertare che ilmessaggio ricevuto proviene proprio da Mitt.

•• Firma ElettronicaFirma Elettronica:: Mitt non può sottrarsi dall’ammettere che èstato lui a spedire il messaggio, e Dest può convincere unaterza persona (giudice) che questo è il caso.

Parte I:Fondamenti e

Tecniche di Base

Cifrari Storici

Page 7: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Prologo

• Motivazioni:

– Scopi educativi: concetti, tecniche di base,…– Divertimento: settimana enigmistica…

• Crittografia manuale

• Sono note tecniche statistiche per forzarli!

• Nota:– Messaggi e crittogrammi composti di lettere– Chiave segreta: esiste oppure no (degenere)

Cifrario di Cesare

C D

È un cifrario degenereIntrodurre chiave k = shift ciclico

C(mi) = lettera in posizione (pos(mi) + k) mod 21

D(ci) = lettera in posizione (pos(ci) – k) mod 21

f g h i l m n o p q r s t u v za b c d e

f g h i l m n o p q r s t u v z a b cd e

è u n a b e l l a g i oo g g i

h a q d e h o o d l n rr l l n

Cifrario Completo

• Ammettiamo tutte le possibili permutazioni dell’alfabeto

– sono (21! – 1), un numero spropositatamente grande !

• Chiave k = <BFRULMZQWEA....> = una permutazione

• Questo cifrario è sicuro ? No, attacco statistico.

– Istogrammi di frequenza delle lettere nelle frasi in italiano

– Istogrammi di frequenza delle lettere nel crittogramma

– Molti crittogrammi a disposizione !

A B C D A B C D

Cifrario a Trasposizione

1 2 3 4 5 6 7 8 9 10 11 12 13 14

m = c i v e d i a m o t a r d i

c = c i d v a i e m o r t i d a

!

! = <1,2,5,3,7,6,4>

• Permutazione delle lettere• Periodo = 7• No attacco statistico !• Attacco sulla lunghezza del periodo

Page 8: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Cifrario Polialfabetico

Ogni occorrenza di una lettera nel messaggio in chiaro può esseresostituita con diverse lettere nel crittogramma, a seconda dellasua posizione o del suo contesto.

A ABCDEFGHIJKLMNO..B BCDEFGHIJKLMNO..C CDEFGHIJKLMNO...D DEFGHIJKLMNO...... ...Y YZABCDEFGHIJK...Z ZABCDEFGHIJ....

ABCDEFGHIJKLMNO..

- Monoalfabetico ogni |k| caratteri- Attacco statistico possibile, ma difficile

m F E D E L E ...

k B A C C A B ...

c G E F G L F ...

Cifrari Perfetti:

one-time pad

One-time pad: esempio

Messaggio: 1 1 0 1 0 0 0 1

Chiave: 1 0 0 0 1 1 1 0

Crittogramma: 0 1 0 1 1 1 1 1

Chiave: 1 0 0 0 1 1 1 0

Messaggio: 1 1 0 1 0 0 0 1

Pregi e Difetti

• Se ogni bit della chiave è generatocasualmente allora conoscere un bit delcrittogramma non fornisce nessunainformazione aggiuntiva sul corrispondente bitdel messaggio: cifrario perfetto.

• La chiave (pad):– è lunga (quanto il messaggio)

– si consuma (one-time)

– occorre scambiarsela

Page 9: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

DES

Data Encryption Standard

Un po’ di storia…

• Nel 1972, l’NBS (National Bureau of Standards. Oggi NIST: NationalInstitute of Standards and Technology) iniziò un programma perproteggere le comunicazioni non classificate.

• Lo scenario era interessante:– NSA (National Security Agency) disponeva di molte conoscenze in

materia di cifrari e metodi di decrittazione.– Esistevano molti prodotti pressocchè oscuri, non certificati e non

compatibili.

• Nel 1973, l’NBS pubblicò un call for proposals:– Sistema a chiave segreta (certificazione e chiarezza)– Realizzabile in hardware (compatibilità)

• Bando andò pressocchè deserto.

…. ancora un po’.

• In un bando successivo IBM propose un sistema simile al suoprodotto Lucifer (operazioni logiche su gruppi di bit)

• Poco dopo NSA certificò Lucifer con il nome di DES: fececommenti e propose variazioni.– Chiave ridotta da 128 bit a 64 bit.– Modifiche significative alla funzione S-box.

• Diverse agenzie replicarono in modo allarmato !!

• Dopo alcune indagini il DES fu certificato e reso pubblico nel1977.

• Primo esempio di cifrario robusto (con certificazione NSA) che iricercatori potevano studiare.

• È stato certificato pressocchè ogni 5 anni, dal 1998 non è piùconsiderato sicuro. Ad esso si preferisce il Triplo-DES.

• AES: il cifrario simmetrico del prossimo millennio !

Caratteristiche principali

di DES

• Codifica Simmetrica• Codifica a blocchi• Blocco = 64 bit• Chiave = 64 Bit (solo 56 usati)

Page 10: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Operazioni di Base

• Permutazione

• Sostituzione

• Espansione

• Contrazione

• Shift Circolare (destro e sinistro)

Permutazione

1

2

3

4

5

6

5

1

6

3

2

4

P=(5,1,6,3,2,4)

Un bit in ingresso determina un bit in uscita

Sostituzione

Ogni ingresso può determinare ogni uscita

Ingresso: A B CUscita: A+B+C

000 010001 011010 100011 111100 110101 000110 001111 101

Una permutazione è anche una sostituzione

Ci sono sostituzioni che non sono permutazioni

Page 11: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Espansione

3

3

3

3

Numero delle uscite maggiore del numero degli ingressi

Esempio:

Contrazione

1

2

3

4

5

6

1

6

3

2

Alcuni ingressi non influenzano le uscite, vengono scartati

Numero delle uscite minore del numero degli ingressi

Esempio (scelta):

Scelta Permutata

1

2

3

4

5

6

1

2

4

6

6

4

2

1

Scelta (contrazione)

Permutazione

Permutazione Iniziale : PI

Fase 1

Fase 2

Fase 16

Scambio a 32 bit

Permutazione Iniziale

Inversa: PF

Scelta Permutata 2

Scelta Permutata 2

Scelta Permutata 2

Shift circolare a Sinistra

Shift circolare a Sinistra

Shift circolare a Sinistra

Scelta Permutata: T

64 bit testo in chiaro 64 bit chiave

k1

k2

k16

64 bit testo cifrato

Permutazione Iniziale : PI

Permutazione Iniziale

Inversa: PF

Scelta Permutata: T

Page 12: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

PI, PF, e T

Mancano ingressi: 8,16,24,32,40,48,56,64.Servono come controllo di parità.

L i-1

L i R i

R i-1 R i-1 D i-1

C i D i

Shift a sinistra Shift a sinistra

Permutazione/ContrazioneXOR

Espansione/Permutazione

Sostituzione/Scelta

Permutazione

XOR

32 32

48

48

32

32

3232

48 Ki

28 28

2828

s1 s2 s3 s4 s5 s6 s7 s8

P

32 bit

+48 bit K (48 bit)

EE

32

48

Page 13: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

S-Box

RSA

Rivest, Shamir, Adelman

E’ necessaria

la chiave segreta ?

• A manda a B lo scrigno chiuso con ilsuo lucchetto.

• B chiude lo scrigno con un secondolucchetto e lo rimanda ad A

• A toglie il suo lucchetto e rimanda loscrigno a B

• B apre lo scrigno !!!

Un secondo protocollo

• B manda ad A il suo lucchetto aperto

• A chiude lo scrigno con il lucchettoricevuto da B e glielo spedisce

• B riceve lo scrigno e lo apre !!!

Page 14: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Funzioni One-way

con Trapdoor

• Un lucchetto è una funzioneone-way con trapdoor !

• Infatti tutti possono chiudere un lucchetto pursenza possedere la chiave.

• Nessuno può aprire un lucchetto senza averela chiave.

• La cassetta delle lettere èun’altra funzione one-waycon trapdoor. Perchè ?

Chiave Pubblica

• Per ottenere un protocollo a chiavepubblica occorre trovare una funzionematematica one-way con trapdoor !

• Cioè una funzione facile da calcolare edifficile da invertire a meno dipossedere qualche informazioneaggiuntiva (chiave).

• La Teoria dei numeri ci viene in aiuto…

Page 15: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

RSA

• Generazione delle chiavi

• Codifica. Encryption. C(m)

• Decodifica. Decryption. D(c)

RSA: Generazione delle chiavi.

Scelgo due numeri primi grandi p e qCalcolo n=pqScelgo e tale per cui GCD(e,"(n)) = 1

Calcolo d tale per cui de mod "(n) = 1

Chiave Pubblica = (e,n)

Chiave Privata = (d,n)

RSA: Encryption

c = me mod n

RSA: Decryption

m = cd mod n

Page 16: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

RSA: esempio.

• Scegliamo p=5 e q=11.• Dunque n=55 e "(n)= (5-1)(11-1)=40.• Prendiamo e=7. Calcoliamo d=23.

d * e = 161 = 4 * 40 + 1 = 1 mod 40.• Quindi il nostro sistema ha le seguenti chiavi:

K[priv]=(23,55) e K[pub]=(7,55)

• Sia m=5.

Codifica: c=57 mod 55 = 25

Decodifica: m=c23 mod 55 = 5

Domande

• Chi ci assicura che D(C(m)) = m ?

• Chi dice che RSA sia sicuro ?

• RSA è efficiente ?

• Come eseguo le varie operazioni ?

Correttezza di RSA

Page 17: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita
Page 18: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Sicurezza di RSA

• Nessun Teorema !!!

• Nessuno è ancora riuscito a violare RSA

• Un modo per risalire alla chiave privataconoscendo quella pubblica è il seguente:Fattorizzo n e ottengo p e q.Calcolo "(n) e quindi d.

• Si congettura sia vero anche il viceversa.

Massimo Comun Divisore

Definizione: produttoria dei fattori comuni con il minimo esponente

Esempio: GCD(233472,2271132) = 2271

Algoritmo ottenuto dalla definizione: FATTORIZZAZIONE !!! Tempo esponenziale

Serve un’idea !!!

Page 19: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Algoritmo di Euclide

GCD(x,y) = GCD(x-y,y)

GCD(x,y) = GCD(x-ky,y)

GCD(x,0) = x

-2435024

11-161753

-233422

1-118711

0140800

10595-1

01408-2

vnunrnqnn

GCD(408,595)qn = rn-2 div int rn-1

un = un-2 - qnun-1

vn = vn-2 - qnvn-1

rn = unx + vn yx y

408 = 2#187 + 34

3 = 1 - 2#-1

Se x e y sono primi tra loro alla fine abbiamo

Quindi u è l’inverso moltiplicativo di x modulo yovvero

Vogliamo d: ed $ 1 mod "(n)

sapendo già che GCD(e, "(n)) = 1

Usiamo l’algoritmo di Euclide.

Calcoliamo GCD(e,"(n)) ottenendo u e v tali per cui

ue + v"(n) = 1

u è ciò che cerchiamo !!!

Page 20: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Algoritmo di Euclide.

Function E(a,b)

if b=0

then Return a

else Return E(b, a mod b)

Algoritmo di Euclide Esteso.

Function EE(a,b)

if b=0

then Return <a,1,0>

else <d’,x’,y’> = EE(b,a mod b)

<d,x,y> = <d’,x’,y’-%a/b&y’>

Return <d,x,y>

ALGORITMO STUPIDO:Moltiplico 158 per 158 per 158....58 volte e poi divido per 678 e prendo il resto.

Tempo di esecuzione dell’ALGORITMO STUPIDO

per calcolare qualche decimo di secondo...

per calcolare con a e b di 150 cifre = usando tutti i calcolatori del mondo, la vita dell’universo !!!!

Trucchi computazionali per

calcolare

Eseguire l’operazione di modulo dopo gni operazione (non basta!)

Page 21: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

...ma...

Cosa succede se devo calcolare ???

Operazioni Base:

Usiamo le operazioni base per calcolare efficientemente ilrisultato finale.

Concludendo...

• Le operazioni di modulo le distribuiscoad ogni passo ( per ridurre ledimensioni dei numeri ottenuti via via..)

• EFFICIENZA ? OK!Il numero di moltiplicazioni è linearenell’esponente.

Page 22: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Generazione di

primi “grandi”

Ci sono tavole di numeri primi ma non così grandi...

Quanti numeri primi ci sono ? Ovvero, come sono distribuiti ?Qual è la probabilità di prendere un numero a caso equesto sia primo ?

n di 10 cifre

n di 100 cifre

IDEA:Genero n a caso poi verifico se è primo.Se è primo ho finito.Altrimenti Inizio da capo.

Test di Primalità

Fino a qualche tempo fa non si conosceva nessun algoritmo per testare se un numero è primo oppure no. Adesso esiste un algoritmo che svolge questo compito in n4 passi.

Polinomiale ma poco efficiente. Come si procede in pratica ???

Teorema di Fermat (caso particolare del teorema di Eulero)

Page 23: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Pomerance 1981

a numero casuale tra 1 e n-1

n numero casuale di circa 100 cifre

1- Genero n a caso

2- Genero a tra 1 e n a caso

3- Calcolo

4- If x = 1

then Stop: n primo

else Stop: n composto

Test probabilistico di primalità

S n è primo: risposta esatta sempre.

Se n è composto: risposta errata con probabilità =

Può non essere sufficiente per alcune applicazioni !!

Come procediamo ???

Analisi dell’algoritmo:

1- Genero n a caso2- Genero a tra 1 e n a caso3- Calcolo4- If x = 1

then Stop: n primo

else Stop: n composto

Test probabilistico di

primalità ESTESO.

k volte

Page 24: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Come generare d, e ?

• e deve essere primo con

• d deve soddisfare

1- Scelgo e a caso.2- Verifico se e è primo con "(n).

2.a- Se si Fine

2.b- Se no goto 1.

Con l’algoritmo di Euclide Esteso trovol’inverso moltiplicativo di e mod "(n)

Identificazione, Autenticazionee Firma Digitale

• In origine crittografia = confidenzialità

• Diffusione delle reti: nuove funzionalità.

• Identificazione

• Autenticazione

• Firma digitale

Page 25: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

• Identificazione: un sistema dielaborazione deve essere in grado diaccertare l’identità di un utente che vuoleaccedere ai suoi servizi

• Autenticazione: il destinatario di unmessaggio deve essere in grado diaccertare l’identità del mittente el’integrità del messaggio

• Firma digitale: funzionalità complessarichiesta quando mittente e destinatario diun messaggio non si fidano l’uno dell’altro(reciprocamente). Proprietà simili allafirma cartacea.

Firma digitale...

• il mittente non può negare di averinviato il messaggio

• il destinatario può accertare l’identitàdel mittente e l’integrità del messaggio(autenticazione)

• il desinatario non può sostenere di averricevuto un messaggio diverso daquello che realmente ha ricevuto

• il tutto verificabile da una terza parte(giudice)

Identificazione

Autenticazione

Firma digitale

Contrastanopossibiliattacchiattivi

Funzioni Hash

Page 26: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Proprietà di funzioni Hash

Elementi molto simili in X appartengano a

sottoinsiemi distinti

Funzioni Hash in crittografia:

Hash one-way

Hash one-way

• Prima proprietà dovrebbe valereanche per funzioni Hash classiche

• Seconda proprietà: one-way

• Terza proprietà: claw-free(opzionale)

• Esempi: MD5, SHA

Identificazione:

Un caso pratico ed un protocollo

Caso pratico: accesso di un utente alla propria casella di posta elettronica o ai file personali memorizzati su un calcolatore ad accesso riservato.

L’utente usa una login e password.

Supponiamo: password ben scelta e canale sicuro

Page 27: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Attacco sferrato

dall’amministratore del sistema.

L’amministratore accede al file delle chiavi.

Contromisura: memorizziamo la password in forma cifrata utilizzando le funzioni hash one-way.

COME ???

Cifratura della pwd con funzioni

hash one-way:UNIX

Quando l’utente U fornisce per la prima volta la password Pil sistema associa a P due sequenze S e Q.

S e Q vengono memorizzate al posto di P

S è detto seme. E’ un numero generato a caso dal sistema.

Q = h(PS).

Cifratura della pwd con funzioni

hash one-way:UNIX

Quando l’utente si collega il sistema:- recupera S dal file delle chiavi, - concatena S con P e applica f ottenendo Q’. - confronta Q’ con Q.- se Q’=Q allora OK altrimenti FAIL

Se qualcuno accede al file delle chiavi ottiene S e Q. Dai quali non riesce a inferire nulla su P.

Alcune osservazioni:

• E’ difficile risalire da S,Q a P.

• La presenza del seme casuale diversoper ogni utente impedisce di scoprire sedue utenti hanno la stessa password erende impossibile un attacco simultaneoa tutte le chiavi.

Page 28: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Abbiamo assunto che il canale attraverso il quale la chiaveviene comunicata al sistema sia sicuro. In realtà di solito non lo è !!!

Protocollo di trasmissione della chiave cifrata usando RSA .

- U richiede accesso al sistema S- S genera un numero casuale r < n e lo invia a U- U calcola f=rd mod n (decifra r con la sua chiave privata) e - spedisce f a S (U firma r).- S cifra f calcolando r*=fe mod n

- Se r*=r allora OK altrimenti FAIL

Alcune osservazioni:

• Il sistema non deve memorizzare leinformazioni circa la chiave P. Semmaideve solo memorizzare la chiavepubblica di U

• E’ possibile invertire cifratura edecifratura perché RSA e’ commutativo

• SSL è un meccanismo di identificazionepiù sofisticato.

Autenticazione

• Identificazione: stabilire l’identità di un utente.• Autenticazione: qualcosa in più di

identificazione.• Mittente spedisce un messaggio a

Destinatario.Destinatario autentica il messaggio se:

- identifica Mittente +- verifica l’integrità del messaggio

MAC

Message Authentication Code

• Immagine breve del messaggio che puòessere generata solo da un mittenteconosciuto dal destinatario.

• Aspetti in comune con le funzioni Hashcrittografiche

• A volte generato usando funzioni Hashcrittografiche

• Entra in gioco una chiave segreta k

Page 29: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

MAC

Mess

aggio

m d

i lu

ng

he

zza

n q

uals

iasi

MA

C

MAC(m,k)

Il MAC ha una lunghezza fissataindipendente da n

Esempio di MAC

Otteniamo un MAC applicando una funzione hash alla concatenazione di m e della chiave k

NOTA: il MAC non è invertibile. Può solo essere calcolato di nuovo ma non invertito !!!

Esempio di Autenticazione

usando MAC

- Mitt spedisce (m,h(mk)) a Dest.

- Dest riceve (m*,h(mk)*).

- Dest conosce k quindi può calcolare h(m*k).

- Dest confronta h(m*k) con h(mk)*.

- Se h(m*k)=h(mk)* Dest conclude che m*=m (integro) e che il mittente di m èeffettivamente Mitt.

Perché ?

• L’intruso X non può spedire un messaggio aDest fingendosi Mitt. Perché ? Perché nonconosce k. IDENTIFICAZIONE

• L’intruso X intercettando (m,h(mk)) non puòmodificare m. Perché ? Perché non conoscek. INTEGRITA’

• Cosa succederebbe spedendo (m,h(m)) ???

Page 30: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Autenticazione +

confidenzialità

- Mitt spedisce (Ck(m),h(mk)) a Dest.

- Dest riceve (Ck(m)*,h(mk)*).

- Dest conosce k quindi decodificaCk(m)* e risale a m*

- Dest conosce k quindi può calcolare h(m*k).

- Dest confronta h(m*k) con h(mk)*.

- Se h(m*k)=h(mk)* Dest conclude che m*=m (integro) e che il mittente di m èeffettivamente Mitt.

Firma Manuale e

Firma Digitale

• La firma digitale deve soddisfare leproprietà di quella manuale.

• La firma digitale è una stringa di bit equindi è facilmente duplicabile/copiabile.La firma manuale no !!

• Firma manuale e firma digitale sonofisicamente oggetti di naturacompletamente diversa !

Firma Manuale:

Proprietà

• La può generare solo una persona enon è falsificabile.

• Non è riutilizzabile (legata al documentosu cui è apposta).

• Il documento su cui è apposta non èmodificabile.

• Non può essere ripudiata da chi l’hagenerata.

Firma Digitale:

Implementazione Ingenua

Firma digitale: digitalizzazione della firma manuale,ad esempio usando uno scanner.

Attacco: Copia e Incolla !!!

Page 31: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Diffie e Hellman:

Cifrari Asimmetrici

U: Firma. f=D(m,kU[priv])

send <U,m,f>

V: Verifica. m*=C(f,kU[pub])

if m*=m then si else no

Protocollo 1

Osservazioni

• Occorre un cifrario commutativo, cioèD(C(m)) = C(D(m)) = m. RSA ècommutativo.

• Il documento firmato non è indirizzatoad uno specifico destinatario. Tuttipossono fare la verifica.

Proprietà del protocollo

• La può generare solo una persona: colui checonosce kU[priv] cioè U.

• Non è riutilizzabile/copiabile/falsificabile: in quanto èfunzione del documento su cui è apposta.

• Il documento su cui è apposta non è modificabile: inquanto anche la firma andrebbe nuovamentegenerata.

• Non può essere ripudiata da chi l’ha generata: inquanto solo conoscendo kU[priv] è possibilegenerarla.

Difetti del protocollo

• La lunghezza del messaggio scambiatoè il doppio della lunghezza delmessaggio originario.

• Il messaggio non può esseremascherato in quanto dall’operazione diverifica è possibile risalire al messaggiospedito

Page 32: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Soluzione

U: Firma e cifraf=D(m,kU[priv])

c=C(f,kV[pub])

send <U,c>

V: Verifica. f*=D(c*,kV[priv])

m*=C(f*,kU[pub])

if m* ”ha senso”

then si else no

Protocollo 2

In Pratica...

U: Firma. f=D(h(m),kU[priv])

c=C(m,kV[pub])

send <U,c,f>

V: Verifica. m*=D(c*,kV[priv])

if h(m*)=C(f*,kU[pub])

then si else no

Protocollo 3

Men in-the-middle Attack

• Attacco attivo

• X si mette nel mezzo tra U e V

• X si comporta come U per V

• X si comporta come V per U

• X devia la comunicazione tra U e Vfacendola passare per se stesso...

V: Destinatariodi un messaggio cifrato.

U: Mittentedi un messaggio cifrato.

kV[pub]

Intruso X

kV[pub] kX[pub]

kV[pub] kX[pub]

Page 33: Obiettivo: Comunicazioni private in ambienti pubblicibabaoglu/courses/security06-07/lucidi/critto-1.pdf · ¥Lo spazio delle chiavi deve essere grande: ¥No brute-force attacks (visita

Men in-the-middle Attack

• U richiede a V la sua chiave pubblicakV[pub] (per e-mail ad esempio)

• X intercetta kV[pub] e la sostituisce conkX[pub]

• X intercetta i crittogrammi da U a V lidecodifica con kX[priv] li ri-codifica conkV[pub] e li ri-spedisce a V

CA: Certification Authority

• Enti preposti alla certificazione divalidità delle chiavi pubbliche.

• Certificato:– Chiave pubblica di U– Lista di Informazioni su U– Date di inizio e fine validità del certificato– Lista di Algoritmi di codifica usati– Firma di CA