Crittografia

Moreno Marzolla

Dipartimento di Informatica

Università Ca' Foscari di Venezia

marzolla@dsi.unive.it

http://www.dsi.unive.it/~marzolla

Ringraziamenti

prof. Francesco Dalla Libera

Corso di Commercio Elettronico, Dipartimento di Informatica, Università Ca' Foscari di Venezia.

Scopo della crittografia

Proteggere i dati dall’essere letti da persone non autorizzate

Privatezza

Impedire a persone non autorizzate dall’inserire, cancellare, modificare messaggi

Integrità

Verificare il mittente di ogni messaggio

Autenticazione

Consentire agli utenti di firmare elettronicamente i messaggi

Non ripudiabilità

Privatezza

Garanzia per il mittente

Solo i destinatari autorizzati possono leggere il contenuto dei messaggi

Autenticazione e integrità

Garanzia per il Ricevente

Conosce l’identità del Mittente

I messaggi non sono stati alterati

I messaggi non sono stati ritardati ad arte nella consegna

Crittografia

Disciplina che si occupa di studiare le tecniche per scrivere un messaggio in modo tale che solo il legittimo destinatario sia in grado di leggerlo.

Si occupa dunque del problema della segretezza

I requisiti principali di tale tecnica sono:

Ragionevole efficienza nella creazione del messaggio

Estrema difficoltà nella interpretazione del messaggio da parte di chi non è autorizzato

Possibilità di cambiare con estrema rapidità il metodo usato

Sfatiamo alcuni miti

Un algoritmo crittografico tenuto segreto è automaticamente sicuro perché nessuno sa come funziona

NIENTE DI PIU' FALSO!!!!!

E' impossibile dimostrare che un algoritmo crittografico è sicuro

Un algoritmo crittografico è sicuro finché non viene rotto

Lo esponete allo scrutinio pubblico per verificare se gli esperti individuano delle falle

La sicurezza sta nelle chiavi

La sicurezza di un algoritmo crittografico deve risiedere SOLO ed ESCLUSIVAMENTE sulle chiavi crittografiche che usa, NON nel modo in cui le chiavi vengono usate

Se una persona non conosce la chiave NON deve poter leggere il messaggio cifrato...

...anche se conosce il modo con cui il messaggio è stato cifrato

Esempio

Adobe impiega nei libri elettronici pubblicati nel suo formato proprietario un algoritmo crittografico “segreto”

Un programmatore ha analizzato questo formato, e ha scoperto che la protezione si può violare quasi con carta e penna

Non fidatevi MAI MAI MAI di soluzioni crittografiche “a scatola chiusa”

Sistemi crittografici

A chiave segreta (o crittografia simmetrica)

Mittente e ricevente devono avere la stessa chiave per poter leggere il messaggio

A chiave pubblica (o crittografia asimmetrica)

Mittente e ricevente NON condividono le stesse chiavi

Funzioni hash unidirezionali

Crittografia simmetrica

Alice cifra il messaggio con la chiave K

Bob decifra il messaggio con la stessa chiave

Ovviamente nessun altro deve conoscere la chiave!

Alice

Bob

Algoritmo DES
(Data Encryption Standard)

Progettato dall'IBM e adottato come standard del governo U.S.A. nel 1977

Caratteristiche

Chiave da 56 bit

Il testo in chiaro è codificato in blocchi di 64 bit, che producono ciascuno 64 bit di testo cifrato (cifratura a blocchi)

In teoria, senza sapere la chiave è impossibile decodificare il messaggio...

...a meno di provare tutte le chiavi possibili, che sono 256, cioè circa 1 seguito da 16 zeri

DES all'interno

Trasposizione

Iterazione 1

Iterazione 2

Iterazione 16

32 bit swap

Trasposizione inversa

Chiave 56 bit

64 bit plaintext

64 bit ciphertext

Li-1

Ri-1

Li-1 ⊕ f(Ri-1,Ki)

32 bit

Li

32 bit

Ri

Problemi con DES

Nonostante lo spazio delle chiavi sia molto ampio, l'algoritmo DES non è oggi considerato sufficientemente sicuro

La versione iniziale era basata su un codice IBM chiamato Lucifer, con chiave a 128 bit

La versione standardizzata di DES però aveva una chiave di 56 bit,

Il procedimento con cui la IBM aveva sviluppato DES fu tenuto segreto

E' possibile effettuare una ricerca esaustiva dello spazio delle chiavi con macchine dedicate

Morale: non usatelo!

Triplo DES

Una variante dell'algoritmo DES (Triplo DES) combina fa uso di più passi di codifica in cascata che usano due chiavi

Lo spazio delle chiavi sale a 2112, cioè circa 1 seguito da 33 zeri

Questo è un numero sufficientemente elevato per consi-derare l'algoritmo triplo DES sufficientemente sicuro

...ma per quanto?

Triplo DES

Cifra

Decifra

Cifra

Messaggio

in chiaro

Messaggio

cifrato

K1

K2

K1

Decifra

Cifra

Decifra

Messaggio

cifrato

Messaggio

in chiaro

K1

K2

K1

Oltre DES

DES viene ancora largamente utilizzato

Tuttavia, la sua sicurezza viene costantemente messa in discussione

Successori di DES

IDEA, sviluppato in Svizzera

Chiave di 128 bit

Cifra a sostituzione su blocchi di 64 bit

AES (Advanced Encryption Standard), precedentemente nodo come Rijndael, sviluppato in Belgio

Chiave di 128, 192 o 256 bit

Cifra a sostituzione su blocchi di 128 bit

Scambio di una chiave condivisa:
l'algoritmo Diffie-Hellman

Scegliere due numeri primi n e g con certe proprietà

Alice sceglie un numero segreto x (lungo 512 bit ad esempio)

Alice manda a Bob [ n, g, gx mod n ]

Bob sceglie un numero segreto y (lungo 512 bit)

Bob manda ad Alice [ gy mod n ]

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

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

Diffie-Hellman

Alice

sceglie x

Bob

sceglie y

n, g, gx mod n

gy mod n

(gx mod n)y =

gxy mod n

(gy mod n)x =

gxy mod n

Problema

Alice

sceglie x

Bob

sceglie y

n, g, gx mod n

gz mod n

Trudy

sceglie z

n, g, gz mod n

gy mod n

Crittografia simmetrica: problemi

Un problema si ha quando aumenta il numero di persone che vogliono comunicare fra loro

Ogni coppia di persone deve essere in possesso di una corrispondente chiave

Se N persone desiderano comunicare fra loro ci vogliono N(N-1)/2 chiavi, cioè una per ogni coppia

Questo rende estremamente difficile il problema della distribuzione delle chiavi, che resta il punto debole di tutto il sistema

Crittografia a chiave pubblica
(asimmetrica)

Nella seconda metà degli anni '70 fu introdotto (Diffie e Hellmann, Stanford University) un tipo di crittografia radicalmente nuovo, detto a chiave pubblica (o asimmetrica)

Idea

Ciascun utente ha due chiavi

Se si usa una delle due chiavi per codificare un messaggio, l'altra (e solo quella!) può essere usata per decodificarlo

E' quasi impossibile derivare la prima chiave anche se si conosce la seconda

Esempio

A

B

L'Italia è

una

Repubblica

fondata

sul lavoro

B

L'Italia è

una

Repubblica

fondata

sul lavoro

Fase di

cifratura

Fase di

decifratura

...ma anche

A

B

L'Italia è

una

Repubblica

fondata

sul lavoro

A

L'Italia è

una

Repubblica

fondata

sul lavoro

Fase di

cifratura

Fase di

decifratura

A

Idea di base

Ogni utente possiede due chiavi

Una è pubblica, e viene resa disponibile a chiunque la richieda

La seconda è privata, e l'utente deve custodirla gelosamente e non darla a nessuno

Alice

Bob

A+

B+

A-

B-

Chiavi pubbliche

Chiavi private

Alice e Bob

Alice

Bob

A+

B+

A-

B-

B-

Alice cifra il messaggio con la chiave pubblica di Bob

Bob decifra con la propria chiave privata

1

2

Vantaggi

Alice è sicura che solo Bob riuscirà a decodificare il messaggio

Se N persone devono comunicare, è sufficiente che ciascuno sia in possesso di tutte le chiavi pubbliche (oltre alla propria chiave privata)

Nel caso della comunicazione con chiave simmetrica, N comunicazioni richiedevano N(N-1)/2 chiavi

Non è necessario scambiarsi chiavi segrete; le uniche chiavi che vengono trasferite sono le chiavi pubbliche

Svantaggio

La crittografia asimmetrica è più lenta di quella simmetrica

Proprietà della crittografia asimmetrica

Consideriamo la coppia di chiavi (k+A , k-A)

k+A chiave pubblica

k-A chiave privata

Codifica e decodifica

E( k, m ) = codificare il messaggio m con la chiave k

D( k, m ) = decodificare il messaggio m con la chiave k

Vale la proprietà

D( k+A , E( k-A , m ) ) = m

D( k-A , E( k+A , m ) ) = m

Un po' più formalmente...

Alice genera una coppia di chiavi (k+A , k-A) rende pubblica k+A e tiene segreta la chiave k-A

Chi vuole mandare un messaggio m in modo sicuro con Alice

si procura k+A

calcola c = E ( k+A , m )

invia c ad Alice

solo Alice può calcolare m = D ( k-A , c ) perché la chiave è segreta

Algoritmo RSA

All'inizio:

Scegliere due numeri primi p e q (> 10100)

Calcolare n=p×q, z=(p-1)×(q-1)

Scegliere un numero d relativamente primo a z

Scegliere e tale che e×d ≡ 1 mod z

Le chiavi sono:

pubblica: (e,n)

privata: (d,n)

Codifica e decodifica

Codifica: Calcolare C = Pe (mod n)

Decodifica: Calcolare P = Cd (mod n)

Però...

...come fa Bob ad essere sicuro che un messaggio proviene proprio da Alice e non da qualcun altro?

Infatti chiunque può codificare il messaggio con la chiave pubblica di Bob, dato che tale chiave è disponibile a chiunque

La crittografia asimmetrica può essere usata per risolvere anche questo problema!

Autenticazione del mittente

Prendiamo il messaggio m

Alice lo codifica con la propria chiave privata

Si ottiene E( k-A , m )

Alice lo codifica ulteriormente con la chiave pubblica di Bob

Si ottiene E( k+B , E( k-A , m ) )

Bob decodifica prima con la sua chiave privata

Si ottiene D( k-B, E( k+B , E( k-A , m ) ) ) = E( k-A , m )

Bob decodifica poi con la chiave pubblica di A

Si ottiene D( k+a, E( k-A , m ) ) = m

Integrità e firma

La crittografia a chiave pubblica può essere usata per autenticare l'origine di un messaggio e per garantirne l'integrità, ossia di fatto per firmare un messaggio.

Si fa uso delle funzioni one-way hash (dette anche funzioni digest, cioè funzioni riassunto) che vengono applicate al messaggio e ne producono un riassunto (MD = message digest).

Cos'è una funzione hash?

Consideriamo un messaggio m

Una funzione hash produce un “riassunto” del messaggio m, che indichiamo con MD(m), con la seguente proprietà

Il riassunto MD(m) deve apparire come “scelto a caso” rispetto a m

Se due messaggi m ed m' differiscono di un solo bit, i riassunti MD(m) e MD(m') dovrebbero apparire completamente diversi

Deve essere difficile costruire un messaggio m che abbia un certo riassunto

MD5 funzione standard

Funzioni hash usate

MD5

Sviluppato da Ronald Rivest

Genera una signature di 128 bit

SHA-1

Sviluppato dalla NSA

Genera una signature di 160 bit

E' stato recentemente forzato e non è ritenuto sicuro. Meglio usare alternative più robuste come SHA-256 o SHA-512

Esempio / 1

Spettabile ditta,

con la presente vi richiediamo l'invio di 10 confezioni da 5 pezzi

dell'articolo di codice CX409W, che pagheremo alla consegna.

Cordiali saluti.

MD5

b67ceef802e72ad8c14de17de0e58e9e

Esempio / 2

Spettabile ditta,

con la presente vi richiediamo l'invio di 11 confezioni da 5 pezzi

dell'articolo di codice CX409W, che pagheremo alla consegna.

Cordiali saluti.

MD5

04eb92e6d8e2a932ebe14e85d887a3dd

Uso delle funzioni hash

Vengono utilizzate per garantire l'integrità di un messaggio, cioè che un messaggio non è stato alterato

Problemi?

Alice invia il messaggio corredato del riassunto; quando Bob riceve il tutto, ricalcola il riassunto e lo confronta con quello ricevuto

Modalità esposta all'attacco di un intruso

Potrebbe intercettare il messaggio, sostituirlo con uno diverso correlato del relativo digest, e inviarlo a Bob come se fosse quello proveniente da Alice.

Soluzione: firma elettronica

Firma elettronica: obiettivi

Il ricevente può verificare l’identità del mittente

Il mittente non può ripudiare in seguito il contenuto del messaggio

Cioè negare di aver inviato proprio lui quel messaggio, con quel contenuto

Il ricevente non può aver “costruito” in proprio il messaggio

Il messaggio è arrivato integro

Firma elettronica: in pratica

Si calcola il riassunto del messaggio con una funzione hash

Il riassunto, prima di essere spedito, viene cifrato dal mittente con la propria chiave privata e decifrato dal destinatario con la chiave pubblica del mittente.

Un riassunto cifrato in questo modo si dice firma elettronica del mittente

Si dice firma digitale (digital signature) del mittente, perché assicura sia l'integrità del messaggio che l'autenticità del mittente, proprio come una firma apposta (in originale) in calce a un documento cartaceo

Schema

Fonte: Schneider e Perry, Commercio elettronico, Apogeo

Problemi di sicurezza risolti dalla crittografia

Privatezza di dati, messaggi, conversazioni

Commercio Elettronico sicuro

Non-ripudiabilità delle transazioni

Autenticazione degli utenti

Sicurezza della posta elettronica

Mail privata

Obiettivi

Confidenzialità

Solo il destinatario può interpretare il contenuto del messaggio

Autenticazione

Il destinatario sa che il messaggio proviene proprio dal mittente, e non da qualcun altro che ne ha preso il posto

Non-repudiabilità

Il destinatario sa che il mittente non potrà in seguito negare di aver spedito quel messaggio con quel contenuto

Mail privata:
Integrità e autenticazione

Testo

del

messaggio

MD5

Riassunto MD5

+

Testo

del

messaggio

Riassunto cifrato

con la chiave privata

del mittente

RSA

Per verificare

Testo

del

messaggio

MD5

Riassunto MD5

calcolato dal testo

Testo

del

messaggio

Riassunto decifrato

con la chiave pubblica

del mittente

RSA

=

Sistemi ibridi di cifratura

La cifratura a chiave simmetrica (chiave condivisa tra mittente e ricevente) è molto veloce, ma è difficile distribuire le chiavi in modo sicuro

La cifratura a chiave pubblica rende facile distribuire le chiavi, ma è meno veloce

Soluzione: usare la cifratura a chiave pubblica per distribuire una chiave privata condivisa, e successivamente effettuare la cifratura mediante la chiave simmetrica

Esempio / 1

Messaggio

Cifrato

DES

Chiave simmetrica casuale

Now is the

time for

all good

men...

s5%lk)@

slm#]l0|

;k^nb[we

pqs...

Testo del

messaggio

Esempio / 2

Chiave simmetrica

casuale

Chiave simmetrica cifrata

RSA

Chiave pubblica del destinatario

Firma digitale

Esempio / 3

MD5

RSA

Now is the

time for

all good

men...

Chiave privata del mittente

Testo del messaggio

Esempio / 4

Testo del

Messaggio

Cifrato

Contenuto del

messaggio

inviato

Chiave simmetrica cifrata

s5%lk)@

slm#]l0|

;k^nb[we

pqs...

Firma digitale

Tecniche di autenticazione forte

Smart cards or tokens

Software (server) and smartcard based

PIN-protected smartcard private key

System issues challenge based on user

User uses password to unlock smartcard, which reads challenge, calculates cryptographic response

Response is used as response to challenge

Meccanismo challenge-response

Idea

Mittente e destinatario si scambiano una serie di messaggi che servono a dimostrare alla controparte che loro sono in quel momento chi dicono di essere

Si sfrutta il meccanismo di codifica asimmetrica (chiavi pubbliche e private

Come si fa

Alice manda a Bob un messaggio contenente un numero casuale XA da lei generato. Il messaggio è codificato con la chiave pubblica di Bob

Bob riceve il messaggio, ed è in grado di decodificarlo. Invia una risposta contenente XA, un numero casuale generato da Bob XB e una chiave privata K (simmetrica) da usare successivamente

Alice riceve il messaggio e lo legge. Vede che Bob è riuscito a decodificare il suo messaggio precedente (perché ha letto XA), e invia un nuovo messaggio contenente il numero casuale di Bob codificato con la chiave di sessione K

Esempio

E( KB+, XA )

E( KA+, [ XA, XB, K ] )

K( XB )

Alice

Bob

Challenge-Response
con chiave condivisa K

Alice

A

Bob

RB

K(RB )

RA

K(RA )

Una versione semplificata
(che non funziona!)

Alice

A, RA

Bob

RB, K(RA )

K(RB )

Perché non funziona?

Trudy

A, RT

Bob

RB, K(RT )

A, RB

RB2, K(RB )

K(RB )

Prima sessione

Seconda

Sessione

2004-02-20T09:34:47