Università degli studi di Camerino
DES e RSA a confronto:
crittografia al servizio della
sicurezza
Marconi Marika
Scopi della crittografia moderna
Disponibilità
Riservatezza
Integrità
Autenticazione
Non ripudiazione
DES e RSA a confronto: crittografia
al ervizio della sicurezza
2
Sigma
INTERFACCIA UTENTE
COMPUTER
HOST BANCARIO
APPLICATIVO
SSD
DISPENSATORE
INTRUSO
CASSAFORTE
DES e RSA a confronto: crittografia
al ervizio della sicurezza
3
Protocollo
Un protocollo è una serie di passi che coinvolge due o più
parti e che serve a portare a termine un compito; deve inoltre
avere le seguenti caratteristiche:
 Chiunque partecipi al protocollo deve conoscerlo.
 Chiunque partecipi al protocollo deve accettare di seguirlo.
 Il protocollo deve essere privo di ambiguità, ogni passo deve
essere descritto con chiarezza e non ci devono essere possibilità di
incomprensioni.
 Il protocollo deve essere completo, quindi deve essere prevista
un’azione per qualunque situazione.
 Non deve fornire più informazioni di quelle per cui è stato
concepito.
DES e RSA a confronto: crittografia
al ervizio della sicurezza
4
Protocollo
1. l’applicativo (challenger) invia una richiesta (challenge)
all’SSD,
2. l’SSD invia una risposta in cui include un numero random
RND all’applicativo,
3. l’applicativo cifra tale numero con l’algoritmo scelto
(simmetrico o asimmetrico) ed invia E(RND) all’SSD,
4. l’SSD decifra il messaggio ricevuto effettuando
D(E(RND)) e, se il numero è esatto, dà all’applicativo il
permesso di procedere.
DES e RSA a confronto: crittografia
al ervizio della sicurezza
5
DES
TESTO IN CHIARO
CHIAVE
IP
64 bit
56 bit
ITERAZIONE 1
64 bit
…
SCHEDULAZIONE
CHIAVI
…
48 bit
ITERAZIONE 16
64 bit
SCAMBIO DX SX
64 bit
IP1
TESTO CIFRATO
DES e RSA a confronto: crittografia
al ervizio della sicurezza
6
DES: IP
Sia x una stringa binaria di
testo in chiaro lunga 64 bit.
L’algoritmo costruisce una
stringa binaria x0 di 64 bit
tramite la permutazione
iniziale fissata IP:
X0=IP(x)=L0 R0.
Dove L0 e R0 sono due stringhe binarie che comprendono
rispettivamente i primi e gli ultimi 32 bit della stringa x0.
DES e RSA a confronto: crittografia
al ervizio della sicurezza
7
DES: i-esima iterazione
Li  R i 1
R i  Li1  f  R i1 , ki 
DES e RSA a confronto: crittografia
al ervizio della sicurezza
8
DES: funzione f
DES e RSA a confronto: crittografia
al ervizio della sicurezza
9
DES: S-box
Dato Bi (l’input a 6 bit dell’S-box Si), il primo e l’ultimo bit di
Bi vengono interpretati come indice di riga, mentre i bit centrali
come indice di colonna.
Si consulta la tabella Si alle coordinate prescritte e il valore in
uscita dall’S-box è l’equivalente binario del decimale trovato.
DES e RSA a confronto: crittografia
al ervizio della sicurezza
10
DES: S-box
DES e RSA a confronto: crittografia
al ervizio della sicurezza
11
DES: schedulazione delle chiavi
DES e RSA a confronto: crittografia
al ervizio della sicurezza
12
TDES
E’ altamente improbabile che, per una coppia di chiavi (k, h)
esista una chiave t tale che, per ogni testo in chiaro x
DESk (DESh (x))=DESt (x).
Da questo risultato nasce l’algoritmo Triplo DES:
y = DESk (DES-1h (DESk (x))).
Lo svantaggio è che risulta meno efficiente del DES singolo di
un fattore 3.
Coppersmith ha osservato però che un attacco di forza bruta
per la ricerca della chiave è dell’ordine di 2112 = 5×1035 .
DES e RSA a confronto: crittografia
al ervizio della sicurezza
13
RSA
Vediamo schematicamente come un utente A può mandare un
messaggio segreto a B usando il metodo RSA.
Innanzitutto B sceglie in modo casuale:
 due primi titanici p, q, calcola N = pq e
  N  = (p - 1)(q - 1);
 due naturali d ed e, l’uno inverso dell’altro modulo   N  .
Cioè tali che d  e  1(mod (N)).
Poi rende noti N ed e: questo forma la sua chiave pubblica.
Tiene invece gelosamente segreto d: la sua chiave privata.
DES e RSA a confronto: crittografia
al ervizio della sicurezza
14
RSA
L’utente A per mandare un messaggio a B compie allora le
seguenti operazioni:
1. eleva ogni unità del messaggio, a, ad e modulo N
a  a e (modN) = b;
2. invia a B ogni unità b così ottenuta.
Per decodificare il messaggio B calcola
b  a
d

e d
 a  mod N  .
DES e RSA a confronto: crittografia
al ervizio della sicurezza
15
RSA
Ciò che ottiene B è proprio M grazie ad un classico teorema di
Fermat-Eulero, che in questo caso, afferma che:
(a e )d  a (modN).
Infatti da
d  e  1(mod (N))
si ha che
d  e = t (N) + 1
da cui
(a e )d  a ed  a (N)t+1  (a (N) ) t  a  a (modN).
DES e RSA a confronto: crittografia
al ervizio della sicurezza
16
Confronto
Produzione
Personalizzazione
Fornitura
Prima istallazione
Manutenzione
Utilizzo
DES e RSA a confronto: crittografia
al ervizio della sicurezza
17
Confronto: produzione e personalizzazione
TDES
RSA
 Dopo la fase di produzione
nella carta è presente
soltanto il Pin
Administrator di default.
 In fase di
personalizzazione viene
inserito il Pin
Administrator specifico del
cliente.
 Gli unici attacchi
apportabili sono furto o
modifica del Pin stesso.
 Nella prima fase sono
presenti il Pin di default e
la PB di CA di default.
 Nella seconda fase
vengono inseriti il Pin e la
PB di CA propri del
cliente.
 Gli unici attacchi sono
furto o modifica Pin.
DES e RSA a confronto: crittografia
al ervizio della sicurezza
18
Confronto: fornitura
TDES
RSA
 Viene fornita la carta, il Pin  Viene fornita la carta, il
Pin, la PB di CA ed il tool
ed il tool per interagire con
per interagire con la carta.
la carta.
 A questo punto il client deve  Due possibili soluzioni: CA
autentica ogni ATM o CA
scegliere se usare una
autentica Client che
chiave unica o una diversa
autentica gli ATM.
per ogni ATM.
 Accorgimenti: memorizzare  Non ci sono attacchi
significativi se non di tipo
la chiave in un DB in modo
sicuro e scegliere la chiave
Impersonation.
escludendo le weak key.
DES e RSA a confronto: crittografia
al ervizio della sicurezza
19
Confronto: prima istallazione
TDES
RSA
 Nel caso di chiave uguale
si potrebbe cablarla già
nella smartcard ed
escludere ogni attacco.
 Nel caso di chiave diversa
l’unico attacco è di tipo
“cipher-text only” per
scoprire la chiave: è allora
importante che la chiave
non abbia un significato
ma sia casuale.
 In entrambi i casi non
avvengono scambi di
chiave e dunque non ci
sono attacchi significativi.
 Porre attenzione alla
generazione delle chiavi:
n diverso per ogni ATM,
PRa non troppo piccola,
PBa non troppo piccola .
DES e RSA a confronto: crittografia
al ervizio della sicurezza
20
Confronto: manutenzione TDES
Chiave unica
Chiave diversa
 Guasto smartcard:
sostituzione con una
smartcard nuova con
inserita la chiave.
 Guasto ATM:
ricaricamento chiave (può
essere automatico).
 Furto chiave:
Ricaricamento chiave su
tutte le smartcard e tutti
gli ATM.
 Guasto smartcard:
sostituzione con una
smartcard nuova con
inserita la stessa chiave o
una chiave nuova.
 Guasto ATM:
ricaricamento chiave
(deve viaggiare sicura).
 Furto chiave: modifica
chiave solo su smartcard e
ATM interessati.
DES e RSA a confronto: crittografia
al ervizio della sicurezza
21
Confronto: manutenzione RSA
CA/Client/ATM
CA/ATM
 Guasto smartcard:
sostituzione con una
smartcard nuova.
 Guasto ATM: si ripetono
le procedure effettuate in
fase di prima istallazione.
 Furto chiave: si ripetono
le procedure effettuate in
fase di prima istallazione.
 Guasto smartcard:
sostituzione con una
smartcard nuova.
 Guasto ATM: si ripetono
le procedure effettuate in
fase di prima istallazione
(interviene la CA).
 Furto chiave: si ripetono
le procedure effettuate in
fase di prima istallazione
(interviene la CA).
DES e RSA a confronto: crittografia
al ervizio della sicurezza
22
Attacchi ai protocolli
Esaustione
Know-Key attack
Replay
Man in the middle
Impersonation
DES e RSA a confronto: crittografia
al ervizio della sicurezza
23
Attacchi alla cifratura
Brute Force
Cipher-text only
Known-plaintext attack
Chosen-plaintext attack
Adaptive Chosen-plaintext attack
Chosen Cipher-text
Adaptive Chosen Cipher-text
Timing
DES e RSA a confronto: crittografia
al ervizio della sicurezza
24
Confronto: utilizzo con TDES - forza bruta
Dimensione
della
Algoritmo che Numero di
utilizza
possibili
chiave
tale chiave
chiavi
espressa in
bit
256=7,2
x
1016
Tempo
necessario
1crittografia/
ms
Tempo
necessario
106crittografi
e/ms
255ms=1142
anni
10,01 ore
56
DES
112
TDES con 2 112
2111ms=7,9 x
33
2 =5,5 x 10
5,4 x 1013 anni
19
chiavi
10 anni
2128=3,4
x
1038
2127ms=5,4 x
5,4 x 1018 anni
24
10 anni
128
AES, IDEA
168
TDES con 3 168
2167ms=5,9 x
50
2 =3,7 x 10
5,9 x 1030 anni
36
chiavi
10 anni
DES e RSA a confronto: crittografia
al ervizio della sicurezza
25
Confronto: utilizzo con TDES - forza bruta
Il costo di un processore che computa 106 crittografie al
microsecondo è però molto elevato: si stima intorno ai 5000
dollari il costo della forzatura della chiave a 56 bit (DES)
mentre si stima intorno a 2 x 1025 dollari il costo della
forzatura della chiave a 112 bit. Si presuppone però che tali
costi possano scendere molto velocemente con il passare degli
anni e lo sviluppo tecnologico che aumenta; ad esempio nel
giro di 6 o 7 anni il costo della forzatura del DES potrebbe
scendere a 50 dollari.
Infine considerando che il TDES utilizza chiavi di 112 bit si
può considerare questo attacco potenzialmente inefficace al
momento.
DES e RSA a confronto: crittografia
al ervizio della sicurezza
26
Confronto: utilizzo con TDES - crittoanalisi
Nel 1981 Merkle ed Hellman presentarono un attacco chosenplaintex che forza il TDES avendo a disposizione 256 coppie di
testo scelto (testo in chiaro e cifrato).
L’idea fu migliorata per diventare un attacco known-plaintext:
Se assumiamo che l’analista ha a disposizione 232 coppie RND
e f(RND) e 25 macchine da usare in parallelo per un costo
totale di 1 milione di dollari (dovuto alle risorse di memoria
necessarie) si ha che il tempo necessario alla forzatura della
chiave è 4 x 108 anni.
A parità di risorse con un attacco a forza bruta si avrebbe una
stima temporale di 2,5 x 1012 anni.
DES e RSA a confronto: crittografia
al ervizio della sicurezza
27
Confronto: utilizzo con RSA - forza bruta
Forza bruta: corrisponde a fattorizzare n, al momento non ci
sono metodi rapidi se si sceglie n sufficientemente grande.
Per dare un’idea della complessità, per un crittosistema RSA, un
numero di 256 bits è facilmente fattorizzato da chiunque
disponga di un semplice home computer; chiavi da 384 bits
possono essere violate da gruppi di ricerca universitari o da
alcune compagnie; crittosistemi a 512 bits possono esser rotti
dai maggiori governi; chiavi da 768 bits saranno probabilmente
violate tra pochissimo; chiavi a 1024 sono per il momento
considerate sicure a meno di vistosi progressi fatti nel campo
della fattorizzazione, mentre le chiavi di 2048 bits possono esser
ritenute sicure almeno per una decina di anni.
DES e RSA a confronto: crittografia
al ervizio della sicurezza
28
Confronto: utilizzo con RSA - crittoanalisi
Per facilitare le operazioni di cifratura (calcolo di f(RND)) da
parte dell’applicativo si potrebbe scegliere una chiave privata
piccola, il tempo di calcolo potrebbe diminuire anche di 10
volte ma esiste un attacco formulato da Wiener che rompe
crittosistemi RSA con chiavi private piccole.
Questo attacco si basa sul seguente risultato:
Sia n=pq con q<p<2q. Dati n, e, siano d ed e primi fra loro
modulo   n  . Allora si può calcolare rapidamente d se
1 14
d N .
3
Se N è di 1024 bit d deve dunque essere almeno di 256 bit.
DES e RSA a confronto: crittografia
al ervizio della sicurezza
29
Confronto: utilizzo con RSA - Timing
L’unico attacco interessante formulato al momento è di tipo
Timing, Kocher ha infatti scoperto che misurando il tempo
impiegato dalla macchina per effettuare f(RND) è possibile
risalire alla chiave privata d.
Lo stesso Kocher ha ultimamente formulato un attacco simile
misurando stavolta il consumo di energia della macchina
durante il calcolo della funzione cifrante; tale attacco è però
ancora lontano dall’essere applicabile, specialmente in un
sistema come l’SSD.
DES e RSA a confronto: crittografia
al ervizio della sicurezza
30
Conclusione
Un’implementazione
Con il
c’è con
Anche
seTDES
la sicurezza
è
Perché
non
ci
sono
Ma
a
noi
interessa
il
RSA comporta
deiche
costi
minore
rispetto
all’RSA
sempre
qualcuno
attacchi
al sia
rapporto
molto
elevati
è conosce
comunque
sufficiente
la chiave
crittosistema?
costi/sicurezza
economici
che
come
al
sistema...
SSD.
segreta
Know-How.
NonDal
si hapunto
bisogno
data base
didivista
In
conclusione
E’
piùdic’è
sicuro
in
giusto:
l’SSD
se di
Il E’
tempo
computazione
protetti
e
poi
uno
scarico
matematico
la
scelta è
RSA
è
più
implementato
delle
cifrature
e
decifrature
ogni
fase,
nonlivello
responsabilità ad ogni
elementare!
sicuro!
può
didecisamente
produzione
enon
gestione.
ècorrettamente
più
elevato
avvengono
mai
subire di
attacchi
rispetto
alchiave!!
TDES.
scambi
significativi.
DES e RSA a confronto: crittografia
al ervizio della sicurezza
31
La Sigma ha scelto di
implementare l’SSD
con l’algoritmo TDES.
Fine
DES e RSA a confronto: crittografia
al ervizio della sicurezza
32