DES e RSA a confronto:
crittografia al servizio
della sicurezza
Scopi della crittografia moderna
Disponibilità
Riservatezza
Integrità
Autenticazione
Non ripudiazione
Sigma
INTERFACCIA UTENTE
COMPUTER
HOST BANCARIO
APPLICATIVO
SSD
DISPENSATORE
CASSAFORTE
INTRUSO
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.
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.
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 .
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.
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  .
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).
Confronto
Produzione
Personalizzazione
Fornitura
Prima istallazione
Manutenzione
Utilizzo
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.
Confronto: fornitura
TDES
RSA
 Viene fornita la carta, il
Pin ed il tool per
interagire con la carta.
 A questo punto il client
deve scegliere se usare
una chiave unica o una
diversa per ogni ATM.
 Accorgimenti:
memorizzare la chiave in
un DB in modo sicuro e
scegliere la chiave
escludendo le weak key.
 Viene fornita la carta, il
Pin, la PB di CA ed il tool
per interagire con la carta.
 Due possibili soluzioni: CA
autentica ogni ATM o CA
autentica Client che
autentica gli ATM.
 Non ci sono attacchi
significativi se non di tipo
Impersonation.
Confronto: prima istallazione
TDES
RSA
 Nel caso di chiave
 In entrambi i casi non
uguale si potrebbe
avvengono scambi di
cablarla già nella
chiave e dunque non ci
smartcard ed escludere
sono attacchi significativi.
ogni attacco.
 Porre attenzione alla
 Nel caso di chiave
generazione delle chiavi:
diversa l’unico attacco è
n diverso per ogni ATM,
di tipo “cipher-text only”
PRa non troppo piccola,
per scoprire la chiave: è
PBa non troppo piccola .
allora importante che la
chiave non abbia un
significato ma sia casuale.
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.
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).
Attacchi ai protocolli
Esaustione
Know-Key attack
Replay
Man in the middle
Impersonation
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
Confronto: utilizzo con TDES - forza bruta
Dimensione Algoritmo
della
che
chiave
utilizza
espressa
tale
in bit
chiave
Numero di
possibili
chiavi
256=7,2 x 1016
Tempo
Tempo necessario
necessario
1crittografia/ms
106crittografi
e/ms
255ms = 1142 anni
56
DES
112
TDES con 2 112
2111ms = 7,9 x 1019
33
2 =5,5 x 10
5,4 x 1013 anni
chiavi
anni
2128=3,4
x
1038
10,01 ore
2127ms = 5,4 x 1024
5,4 x 1018 anni
anni
128
AES, IDEA
168
TDES con 3 168
2167ms = 5,9 x 1036
50
2 =3,7 x 10
5,9 x 1030 anni
chiavi
anni
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.
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.
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.
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.
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.
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.
La Sigma ha scelto di
implementare l’SSD
con l’algoritmo TDES.
Fine