1
•L’algoritmo DES semplificato
•Cifratura di flussi e cifratura a blocchi
•La cifratura di Feistel
• L’algoritmo DES (Data Encryption Standard)
•La cifratura DES
•Decrittografia DES
•Effetto valanga
• La potenza di DES
•L’uso di chiavi a 56 bit
•La natura dell’algoritmo DES
•Attacchi temporizzati
•Analisi crittografica differenziale e lineare
•Principi di progettazione della cifratura a blocchi
•Criteri progettuali di DES
2
•Des semplificato(S-DES)Des semplificato(S-DES)•Sviluppato da Edward SchaeferSviluppato da Edward Schaefer•Ha valore educativo poiché non è sicuroHa valore educativo poiché non è sicuro
•Prende in input un blocco di 8 bit di testo in chiaroPrende in input un blocco di 8 bit di testo in chiaro•Prende in input una chiave di 10 bitPrende in input una chiave di 10 bit•Produce come output un blocco di 8 it di testo cifratoProduce come output un blocco di 8 it di testo cifrato
L’algoritmo di crittografiaL’algoritmo di crittografia
•Prende in input un blocco di 8 bit di testo cifratoPrende in input un blocco di 8 bit di testo cifrato
•Prende in input la chiave di 10 bit usata per la cifraturaPrende in input la chiave di 10 bit usata per la cifratura
•Produce come output un blocco di 8 it di testo in chiaroProduce come output un blocco di 8 it di testo in chiaro
L’algoritmo di decrittografiaL’algoritmo di decrittografia
3
Esegue 5 funzioni:Esegue 5 funzioni:
Permutazione iniziale (IP) (IP)Funzione complessa fk composta da permutazione
e sostituzione e che dipende dalla chiave di inputFunzione di permutazione semplice (SW) che
commuta le due metà di datiFunzione fk
Permutazione inversa della funzione di permutazione
iniziale
4•Schema Des semplificatoSchema Des semplificato
5
La funzione fk accetta come input i dati elaborati nell’algoritmo
di crittografia e una chiave di 8 bit.
Alternative per la scelta delle sottochiavi:Chiave di 16 bit costituita da due sottohiavi di 8 bit, una per ogni fk
Unica chiave di 8 bitCompromesso due sottochiavi da 8 bit selezionate da una chiave
di 10 bit.
Operazioni da farePermutazione (P10)
Scorrimento
Permutazione (P8) che produce un output di 8 bit, scelto come prima chiave
Scorrimento
Permutazione (P8) per generare la seconda chiave
6
Matematicamente:
2 1
1
k kIP f SW f IP
ovvero
Testo cifrato=IPTesto cifrato=IP-1-1(f(fk2k2(SW(f(SW(fk1k1(IP(testo in chiaro)))))(IP(testo in chiaro)))))
dove K1=P8(Shift(P10(key)))
K2=P8(Shift(Shift(P10(key)))
e per la decrittografia
Testo in chiaro=IPTesto in chiaro=IP-1-1(f(fk1k1(SW(f(SW(fk2k2(IP(testo cifrato)))))(IP(testo cifrato)))))
7
La generazione della chiave S-DES
Chiave iniziale di 10 bit condivisa dal mittente e
dal destinatario:
1 2 3 4 5 6 7 8 9 10, , , , , , , , ,k k k k k k k k k k
1 2 3 4 5 6 7 8 9 10 3 5 2 7 4 10 1 9 8 610( , , , , , , , , , ) ( , , , , , , , , , )P k k k k k k k k k k k k k k k k k k k kPermutazione P10Permutazione P10
o anche
3 5 2 7 4 10 1 9 8 6
P10P10
8
La generazione della chiave S-DES
Esempio:
A. Permutazione: (1010000010) (1000001100).
B. Shift circolare sinistro (LS-1) separatamente sui primi (Left) e sui
secondi (right)5 bit. (00001 11000)
C. P8
6 3 7 4 8 5 10 9
P8P8
D.D. Il risultato è la prima chiave kIl risultato è la prima chiave k11 (10100100). (10100100).
E. Shift circolare sinistro di due posizioni sui primi e sui secondi 5 bitE. Shift circolare sinistro di due posizioni sui primi e sui secondi 5 bit
di B, il valore (00001 11000) diviene (00100 00011).di B, il valore (00001 11000) diviene (00100 00011).
F. P8 sul risultato che genera kF. P8 sul risultato che genera k22
9
•Chiave di 10 bitChiave di 10 bit1010
P10
55 55
55 55
55 55
LS-1LS-1 LS-1LS-1
LS-2LS-2 LS-2LS-2
P8P8
P8P8
88
88
P10: permutazioneP10: permutazione
LS-1: shiftLS-1: shift
La generazione della chiave S-DES
10
Crittografia S-DES
Permutazione inizialePermutazione iniziale
2 6 3 1 4 8 5 7
IPIP
Permutazione finalePermutazione finale
4 1 3 5 7 2 8 6
IPIP-1-1
11
Crittografia S-DES
Le funzione fLe funzione fkk
)),,((),( RSKRFLRLfk
dove L e R sono i 4 bit a sinistra e i 4 bit a destra dell’input di 8 bitdove L e R sono i 4 bit a sinistra e i 4 bit a destra dell’input di 8 bit
F è un mapping che da 4 bit in ingresso restituisce 4 bit in uscita.F è un mapping che da 4 bit in ingresso restituisce 4 bit in uscita.
Sk è una sottochiave, Sk è una sottochiave, è la funzione or esclusivo bit a bit è la funzione or esclusivo bit a bit
Esempio: Esempio: L||R=10111101, F(1101,SK)=(1110) per qualche SKL||R=10111101, F(1101,SK)=(1110) per qualche SK
(1011)(1011)(1110)=(0101)(1110)=(0101) 01011101()10111101( kf
12
Crittografia S-DES
Le funzione fLe funzione fkk: mapping F: mapping F
L’input è il numero di 4 bit (n1n2n3n4).
La prima operazione è un’espansione/permutazione
4 1 2 3 2 3 4 1
E/PE/P
risultato rappresentabile anche come
13
Crittografia S-DESLe funzione fLe funzione fkk: mapping F: mapping F
La sottochiave a 8 bit kLa sottochiave a 8 bit k11=(k=(k1111,k,k1212,k,k1313,k,k1414,k,k1515,k,k1616,k,k1717,k,k1818))
è aggiunta xor al risultato precedenteè aggiunta xor al risultato precedente
Rinominando gli 8 bitRinominando gli 8 bit
14
Crittografia S-DES
I primi 4 bit (prima riga della precedente matrice sono disposti nellaI primi 4 bit (prima riga della precedente matrice sono disposti nella
S-box S0. Producono in uscita 2-bit.S-box S0. Producono in uscita 2-bit.
I rimanenti 4 bit sono posti nella S-box S1. Producono in uscita 2-bit.I rimanenti 4 bit sono posti nella S-box S1. Producono in uscita 2-bit.
S-boxS-box
15
Crittografia S-DESFunzionamento delle S-boxFunzionamento delle S-box
Il primo ed il quarto bit sono trattati come numeri a due bit cheIl primo ed il quarto bit sono trattati come numeri a due bit che
specificano una riga della S-box, il secondo ed il terzo bit di inputspecificano una riga della S-box, il secondo ed il terzo bit di input
specificano una colonna delle S-box, l’elemento di matrice individuatospecificano una colonna delle S-box, l’elemento di matrice individuato
da tali valori di riga e di colonna fornisce i due bit di outputda tali valori di riga e di colonna fornisce i due bit di output
Esempio: (pEsempio: (p0,00,0pp0,30,3)=00)=00
(p(p0,10,1pp0,20,2)=(10))=(10)
riga 0riga 0
colonna 2colonna 2S0(0,2)=3 (11 in binario)S0(0,2)=3 (11 in binario)
Successivamente iSuccessivamente i 4 bit generati da S0 e S1 sono sottoposti ad una4 bit generati da S0 e S1 sono sottoposti ad una
permutazionepermutazione
1 4 3 1
P4P4 L’output è la funzioneL’output è la funzione
FF
16
Crittografia S-DES
La funzione SwitchLa funzione Switch
La funzione switch (SW) scambia la parte sinistra con la parte destraLa funzione switch (SW) scambia la parte sinistra con la parte destra
E’ introdotta poiché la funzione fE’ introdotta poiché la funzione fkk altera solo i 4 bit più a sinistra altera solo i 4 bit più a sinistra
17
Analisi della tecnica DES semplificata
•• Con una chiave a 10 bit ci sono 210=1024 combinazioni.
• L’attacco a S-DES può essere sferrato con successo
•ogni ciphertext ci è una funzione polinomiale dei pi (plaintext)
e dei ki (key).
• Possiamo esprimere l’algoritmo di encryption come 8 equazioni
non lineari in 10 incognite
La non linearità proviene dalle S-box
◘Poniamo
(p0,0, p0,1, p0,2, p0,3)=(a,b,c,d), (p1,0, p1,1,p1,2,p1,3)=(w,x,y,z) e sia
l’uscita a 4 bit (q,r,s,t) allora l’operazione di S0 è definita dalle
equazioni:
18
Analisi della tecnica DES semplificata
••Le operazioni sono modulo 2Le operazioni sono modulo 2
• • Otteniamo equazioni simili per S1.Otteniamo equazioni simili per S1.
• • Alternando mappature lineari con mappature non lineari provenientiAlternando mappature lineari con mappature non lineari provenienti
dalle S-Box si complica l’analisi crittograficadalle S-Box si complica l’analisi crittografica
19
•I cifrari a blocchi elaborano il messaggio da
criptare viene suddiviso in blocchi di lunghezza
fissa. In genere sono utilizzati blocchi di 64 o 128 bit. Il
messaggio cifrato si ottiene elaborando indipendenemente
ogni singolo blocco.
•Possono essere considerati cifrari a semplice sostituzione.
•Devono avere alfabeti grandi per contrastare l’analisi in
frequenza
20
•I cifrari a flusso elaborano il messaggio un bit o un
byte per volta.
•La maggior parte dei cifrari moderni sono a blocco
21
Principi dei cifrari a blocco
22
Mapping reversibile Mapping irreversibileTesto in chiaro Testo cifrato Testo in chiaro Testo cifrato
00 11 00 11
01 10 01 10
10 00 10 01
11 01 11 01
Struttura di FeistelStruttura di Feistel
Una cifratura a blocchi opera un blocco di dati di dimensioneUna cifratura a blocchi opera un blocco di dati di dimensione
fissata, di solito 64 bit, e lo trasforma in un altro blocco di 64 bitfissata, di solito 64 bit, e lo trasforma in un altro blocco di 64 bit
usando una funzione selezionata dalla chiave.usando una funzione selezionata dalla chiave.
Il procedimento deve essere reversibile per garantire laIl procedimento deve essere reversibile per garantire la
decrittografia, ovvero un blocco di testo in chiaro deve produrre decrittografia, ovvero un blocco di testo in chiaro deve produrre
(a parità di chiave) un blocco cifrato univoco(a parità di chiave) un blocco cifrato univoco
23
Cifrario a blocco ideale
24
Motivazioni Struttura di FeistelMotivazioni Struttura di Feistel
Tabella di crittografia e decrittografia per la cifratura a Tabella di crittografia e decrittografia per la cifratura a
sostituzione sostituzione
25
Struttura di FeistelStruttura di Feistel
Se viene utilizzato un blocco di piccole dimensioni ad es. n=4,Se viene utilizzato un blocco di piccole dimensioni ad es. n=4,
il sistema è equivalente a una classica cifratura a sostituzioneil sistema è equivalente a una classica cifratura a sostituzionePer blocchi di grandi dimensioni la cifratura ideale a blocchiPer blocchi di grandi dimensioni la cifratura ideale a blocchi
non è convenientenon è conveniente
N=4 N=4 chiave (4bit)x(16 righe)=64chiave (4bit)x(16 righe)=64
N=64N=64 chiave=10chiave=102121 bit bitFeistel adotta un’approssimazioneFeistel adotta un’approssimazione
26
Motivazioni Struttura di FeistelMotivazioni Struttura di Feistel
La chiave per n=4 è uguale a 64 bitLa chiave per n=4 è uguale a 64 bit
In generale per una cifratura a sostituzione a blocchi aIn generale per una cifratura a sostituzione a blocchi a
n bit la chiave ha dimensioni pari a n bit la chiave ha dimensioni pari a
n n 22nn
Per un blocco di 64 bit Per un blocco di 64 bit
64 64 226464=2=27070=10=102121 bit bit
27
Shannon e i cifrari
28
Confusione e diffusione
29
La cifratura di Feistel
30
k1 F
R1L1
Round1
kn F
RnLn
Roundn
Key
Algoritmodi
generazionedella
sottochiave
Testo in chiaro
R0L0
Testo cifrato
ki F
RiLi
Roundi
Li=Ri-1
Ri=Li-1F(Ri-1, ki)
Un testo in chiaro M viene Un testo in chiaro M viene
spezzato in due parti di egualespezzato in due parti di eguale
lunghezza llunghezza l
Struttura di FeistelStruttura di Feistel
•Applicazione pratica di Applicazione pratica di
una cifratura proposta dauna cifratura proposta da
Shannon che alterna Shannon che alterna
confusione e diffusioneconfusione e diffusione
31
Parametri del ciclo di Feistel
32
Decriptazione del ciclo di FeistelDecriptazione del ciclo di Feistel
33
all’inizio degli anni ’70, ciascuno usava il proprio crittosistema per cifrare e decifrare
mancava uno standard (es: banche) Il 15 Maggio 1973, il Il 15 Maggio 1973, il National Bureau of StandardsNational Bureau of Standards (NBS) (NBS)
pubblicò un invito, nel Registro Federale, per l’emissione di un pubblicò un invito, nel Registro Federale, per l’emissione di un crittosistema standardcrittosistema standard)
nacque così il nacque così il DES DES Data Encryption Standard Data Encryption Standard, divenuto il , divenuto il crittosistema più usato nel mondocrittosistema più usato nel mondo
Il DES fu sviluppato alla IBM, come evoluzione di un DES fu sviluppato alla IBM, come evoluzione di un crittosistema più antico, LUCIFER, e fu pubblicato sul Registro crittosistema più antico, LUCIFER, e fu pubblicato sul Registro Federale il 17 Marzo 1975Federale il 17 Marzo 1975
La definizione di DES è riportata nel La definizione di DES è riportata nel Federal Information Federal Information Processing Standards Publication 46Processing Standards Publication 46, del 15 Gennaio 1977, del 15 Gennaio 1977
34
Il DES (Data Encryption Standard) è un cifrario composto sviluppato dall'IBM, modificato dalla National Security Agency (NSA) e adottato dal governo statunitense nel 1977 ufficialmente per la protezione di dati riservati ma non classificati come "segreti militari" o di "stato" (fatta eccezione per quegli atti che richiedevano un livello più alto di sicurezza), tuttora è usato da agenzie federali
35
Struttura di FeistelStruttura di Feistel
36
Caratteristiche del DES
Progettato inizialmente per essere implementato in hardware accetta una stringa di 64 bit in ingresso e la trasforma in una di 64 bit in uscita
Combina sostituzione e trasposizione Si basa sul sistema di Feistel come la maggior parte dei cifrari
simmetrici a blocchi Schema simmetrico
– Il DES è un codice cifrato a blocchi. La chiave usata per cifrare è un blocco di 64 bit suddivisa in 8 sottoblocchi di 8 bit ciascuno; l'ultimo bit di ogni sottoblocco è di controllo, di conseguenza i bit liberi che costituiscono in pratica la chiave sono 56. Accetta una stringa di 64 bit in ingresso e la trasforma in una di 64 bit in uscita
L’algoritmo comprende 16 iterazioni che mischiano testo in chiaro e valori ottenuti dalla chiave
37
Caratteristiche del DES
Il testo da cifrare viene suddiviso in blocchi di 64 bit ciascuno e vengono cifrati uno dopo l'altro in successione con uguale procedimento
Se un blocco non raggiunge la lunghezza desiderata di 64 bit si utilizza un procedimento detto "pad", che può essere implementato in diversi modi
Aggiungere zeri fino alla lunghezza stabilita Se i dati sono binari, integrare il blocco con bit che sono
l'opposto degli ultimi bit del messaggio Se i dati sono ASCII si usano invece byte generati in modo
casuale specificando nell'ultimo byte il carattere ASCII corrispondente al numero di byte aggiunti.
Una tecnica, in parte equivalente alla precedente, usa sempre bit casuali ma fornisce, negli ultimi tre bit, il numero di byte originali, cioè quelli che costituiscono il messaggio senza riempimento
38
Data Encryption Standard
DESDEStesto in chiarotesto in chiaro testo cifratotesto cifrato
chiavechiave
64 bit64 bit 64 bit64 bit
56 bit56 bit
39
L’algoritmo può essere suddiviso in tre blocchi:L’algoritmo può essere suddiviso in tre blocchi:
1. Dato il plaintext x, si costruisce la stringa x0, permutando i bit di x secondo una permutazione iniziale (fissata) IP. In particolare, x0=IP(x)=L0R0, dove L0 comprende i primi 32 bit di x0 e R0 gli ultimi 32
Struttura
40
2. LiRi, per 1i16, viene calcolato comeLi=Ri-1
Ri=Li-1 F(Ri-1,ki) dove è l’operatore di XOR, k1,k2,…,k16 sono sottochiavi di 48 bit
calcolate in funzione della chiave originaria k (formano il key schedule) e F è una funzione che prende i 32 bit della metà destra Ri-
1 e i 48 bit della subkey e:▪Espande Ri-1 a 48 bit utilizzando una tabella che definisce una espansione/permutazione E▪Ne fa l’XOR con la subkey ki e scrive il risultato come concatenazione si stringhe di 6 bit▪Il risultato a 48 bit viene elaborato da una funzione di sostituzione che utilizza 8 S-box e produce un output di 32 bit▪Permuta i 32 bit utilizzando una tabella di permutazione
Struttura
41
3. Si applica la permutazione inversa IP-1 alla stringa di bit R16L16,
ottenendo il testo cifrato y, cioè y=IP-1(R16L16)
Struttura
42
Struttura del DES
IPIP
IPIP -1 -1
iterazione 1iterazione 1
iterazione 16iterazione 16
testo in chiaro 64 bittesto in chiaro 64 bit
testo cifrato 64 bittesto cifrato 64 bit
scambioscambio
...... schedulazioneschedulazione
chiavechiave
chiavechiave
56 bit56 bit48 bit48 bit
48 bit48 bit
43
Permutazione Iniziale IP
58 50 42 34 26 18 10 260 52 44 36 28 20 12 462 54 46 38 30 22 14 664 56 48 40 32 24 16 857 49 41 33 25 17 9 159 51 43 35 27 19 11 361 53 45 37 29 21 13 563 55 47 39 31 23 15 7
11 22
5050 5858
bit inizialibit iniziali
bit permutatibit permutati6464......
Poiché il primo bit della tabella è 58,il 58° bit della stringa iniziale diviene il primo bit di quella permutata , il 50° bitdiventa il secondo e così via.
44
Permutazione Inversa IP-1
11 22
88 4040
bit inizialibit iniziali
bit permutatibit permutati
40 8 48 16 56 24 64 3239 7 47 15 55 23 63 3138 6 46 14 54 22 62 3037 5 45 13 53 21 61 2936 4 44 12 52 20 60 2835 3 43 11 51 19 59 2734 2 42 10 50 18 58 2633 1 41 9 49 17 57 25
6464......
1 2 3 4 5 6 7 89 10 11 12 13 14 15 1617 18 19 20 21 22 23 2425 26 27 28 29 30 31 3233 34 35 36 37 38 39 4041 42 43 44 45 46 47 4848 50 51 52 53 54 55 5657 58 59 60 61 62 63 64
58 50 42 34 26 18 10 260 52 44 36 28 20 12 462 54 46 38 30 22 14 664 56 48 40 32 24 16 857 49 41 33 25 17 9 159 51 43 35 27 19 11 361 53 45 37 29 21 13 563 55 47 39 31 23 15 7
45
Struttura del ciclo
Funzione di espansione E
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
46
Struttura del ciclo
47
Struttura
48
Singola iterazione DES
LLi-1i-1 RRi-1i-1
LLii
RRii
kkii
ff
parte sinistraparte sinistra32 bit32 bit
parte destraparte destra32 bit32 bit
sottochiavesottochiave48 bit48 bit
RRii
49
S-Box
50
S-Box
51
S-Box
52
S-Box
53
Caratteristiche S-Box
54
Struttura del ciclo
Permutazione finale (P)Permutazione finale (P)
55
Partendo da una chiave iniziale di 64 bits vengono effettuate diverse operazioni per generare un insieme di chiavi da utilizzare nei singoli cicli.
La scelta permutata 1 ci permetterà di ottenere 56 bits dai 64 iniziali da utilizzare come materiale di partenza per la generazione delle singole chiavi.
E' per tale motivo che le chiavi possibili sono 72,057,594,037,927,936.
56
57
Lo schema generico delle operazioni effettuate sulla chiave
è il seguente:
Vediamo adesso nello specifico le singole operazioni.
64 64 bitbit
58Vediamo adesso nello specifico le singole operazioni.
60
•Chiave iniziale
La chiave iniziale è costituita da 64 bits generati solitamente in modo
casuale ma aventi una particolarità: l'ottavo bit di ogni riga non è altro
che un controllo di disparità effettuato sui bits costituenti la riga e
non verrà utilizzato nelle successive operazioni di elaborazione
sulla chiave.
61
Scelta permutata 1
I 64 bits della chiave iniziale vengono sottoposti alla scelta permutata 1 ed èproprio attraverso questa operazione che vengono eliminati gli otto bits di controllo.
62
I 56 bits ottenuti vengono suddivisi in due parti da 28 bits per poi essere spostati singolarmente a sinistra.
63
•Spostamento
Il valore dello spostamento è variabile ed è legato al ciclo secondo
questa tabella:
64
•Scelta permutata 2 I due semiblocchi vengono quindi rielaborati utilizzando la
scelta permutata 2 (Permuted Choise 2) che è una compressione.Permuted Choise 2) che è una compressione.
Prende in ingresso 56 bit e ne restituisce 48.Prende in ingresso 56 bit e ne restituisce 48.
La coppia di blocchi Cj e Dj è determinata dalla tabellaLa coppia di blocchi Cj e Dj è determinata dalla tabella
Il valore ottenuto costituisce la prima chiave utilizzata nel primo
ciclo. La procedura continuerà poi negli altri cicli, seguendo lo
schema generale esposto in
precedenza.
65
Decifratura DES
66
IPIP
IPIP -1 -1
iterazione 1iterazione 1
iterazione 16iterazione 16
testo cifratotesto cifrato
testo in chiarotesto in chiaro
scambioscambio
...... schedulazioneschedulazione
chiavechiave
chiavechiave
kk1616
kk11
stesso algoritmostesso algoritmosottochiavi in ordine inversosottochiavi in ordine inverso
Decifratura DES
67
Per il momento sembra ancora abbastanza sicura, nonostante i numerosi attacchi brute force
La sua effettiva sicurezza è comunque una questione estremamente controversa
La maggiore preoccupazione è che esso possa avere qualche debolezza nota soltanto a NSA– Originariamente la chiave doveva essere
lunga 64 bit, fu ridotta a 56 poco prima dell’approvazione come standard
Decifratura DES
68
Effetto valanga
69
Effetto valanga
70
Numero chiavi DES = 256 7,2056 ·1016
Un computer a 500 Mhz che testa una chiave per ciclo
di clock impiega
144.115.188 secondi 834 giorni 2 anni e 3 mesi
per provare 255 3,6 ·1016 chiavi
La sicurezza del DESRicerca esaustiva
71
La sicurezza del DES
Nel 1990 Biham e Shamir inventano la criptoanalisi differenziale
Nel 1991 applicano tale tecnica al DES dimostrando che quasi tutte le modifiche all’algoritmo lo indeboliscono
Dopo aver indebolito l’algoritmo Biham e Shamir violano la versione modificata
Diffie ed Helman nel 1977 asseriscono che una chiave di 56 bit è troppo breve.
72
Attacchi al DES Nel 1995 l’istituto nazionale per gli standard e la
tecnologia (NIST, National Institute of Standards and Technology) inizia la ricerca di un nuovo algoritmo di crittografia più forte
Nel 1997 alcuni ricercatori riescono a dedurre una chiave DES utilizzando 3500 macchine in parallelo e impiegando circa 4 mesi
Nel 1998 viene costruito un “craker DES” a un costo di circa 100.000 euro, in grado di individuare una chiave des in 4 giorni
Gennaio 1999: 22 ore 15 minuti testando 245 miliardi di chiavi al secondo, Distributed.Net 100.000 computer e EFF
73
Attacchi al DES
74
Forza del DES- Attacchi analiticiOggi esistono diversi attacchi analitici al DES• Utilizzano la struttura profonda del DES• Acquisendo informazioni circa le encryptions• Possono eventualmente ricavare alcuni/tutti i bit delle subkey• Se serve dopo possono fare una ricerca esaustiva del resto• Generalmente questi sono attacchi statistici
Includono:• Criptoanalisi differenziale• Criptoanalisi lineare• Attacchi relativi alla chiave
75
Forza del DES- Attacchi di timing
Attacchi verso la reale cifratura• La struttura della chiave (peso di Hamming) ha
effetto sul tempo di cifratura/decifratura• Possibile solo nel caso in cui sia possibile
controllare questi tempi• Particolarmente problematica per le smartcard•Rappresenta solo un primo passo del possibile attacco
76
Criptoanalisi differenziale
-Uno dei più significativi avanzamenti recenti
(pubblici) nella criptoanalisi
-Nota alla NSA e alla IBM al progetto del DES
-Pubblicata negli anni 90 da Murphy et al.
-Metodo potente per l’attacco ai block cipher
-Usato per attaccare diversi cifrari a blocco
con successo variabile
-DES (come Lucifer) abbastanza resistente
77
Criptoanalisi differenziale
•Attacco statistico contro i cifrari Feistel introdotto da E. Biham e A. Shamir •Primo attacco a rompere l’algoritmo più velocemente di un attacco a forza bruta•Può essere utilizzato contro altri cifrari come ad esempio idea•Richiede 247 coppie scelte di plaintexts per avere successo
•Si presta con successo alla rottura del DES nell'ipotesi che il numero di iterazioni sia ridotto (il DES a 8 iterazioni può essere rotto in un paio di minuti su un personal computer).
78
Criptoanalisi differenziale
Si considereranno note delle coppie,(testo in chiaro - testo cifrato), con chiave segreta k uguale per tutte. • Con una differenza nota nell’input• Cercando una differenza nota nell’output
79
Criptoanalisi differenziale
•Alcune differenze di input danno luogo con
probabilità p ad alcune differenze di output•Se si trovano con probabilità più elevata istanze
di alcune coppie di differenze input/output allora:• Possibile inferire la subkey usata in un round• Dopo di ciò bisogna iterare il processo su
molti round (con probabilità decrescenti)
•collegamenti ipertestuali\sez3-6.html
80
Criptoanalisi differenziale
81
Criptoanalisi differenziale
•Vedi D. Stinson Cryptography: Theory and Practice
82
Criptoanalisi lineare
•Introdotta nel 1994 da Matsui e altri
•Si può recuperare la chiave del DES dall’analisi di 243 messaggi
noti tramite un’approssimazione lineare per descrivere il
comportamento del cifratore a blocco.
La prima applicazione sperimentale riuscì nell’attacco in 50 giorni
su dodici workstations HP 9735.
•Non è praticabile sia per le grandi richieste di dati, sia per la
difficoltà di preparare nella realtà un attacco a messaggio noto.
E’ basato sulla determinazione di approssimazioni lineari.
83
Criptoanalisi lineare
•Trova delle approssimazioni lineari con probabilità L 1/2
•ia, jb,kc sono le posizioni dei bit in P, C, K
•Fornisce delle equazioni lineari per i bit della chiave•Ottiene un bit della chiave usando un algoritmo di massima verosimiglianza
•Usa un gran numero di encryptions di tentativo
84
Criterio di Davies
L'attacco migliorato di Davies:
Crittanalisi lineare e differenziale: tecniche generali che possono essere applicate anche ad altri algoritmi,
Attacco di Davies: tecnica specializzata per il DES, proposto da Davies negli anni '80 e migliorato da Biham e Biryukov (1997). La forma più potente dell'attacco richiede 250 testi in chiaro, ha una complessità computazionale di 250 ed il 51% di probabilità
di successo.
85
Altri attacchi
Attacchi proposti su versioni con un minor numero di cicli di cifratura, permettono di valutare quanti cicli siano necessari per avere una certa sicurezza e che margine di sicurezza ha la versione completa.
Crittanalisi differenziale-lineare Proposta da Langford ed Hellman nel 1994, combina l'analisi lineare e differenziale in un singolo attacco. Una versione migliorata dell'attacco può violare una versione del DES con 9 cicli con 215,8 testi in chiaro ed una complessità temporale di 229,2
(Biham ed altri, 2002).
86
Criteri progettuali DESPresentati da Coppersmith nel 1994
7 criteri per gli S-box forniscono:
•Non linearità
• Resistenza alla criptanalisi differenziale
• Buona confusione
3 criteri per la permutazione P forniscono:
• Aumento della diffusione
87
Progetto dei cifrari a bloccoPrincipi fondamentali ancora come Feistel nel 1970
• Numero dei round
• Cifrari migliori con valore maggiore
• Funzione f
Se non lineare fornisce confusione, valanga
Esistono problemi circa la selezione degli S-box
• Schedulazione della chiave
Creazione complessa delle subkey, valanga
88
Modalità di utilizzo dei cifrari a blocco
• I Cifrari a blocchi criptano parole di lunghezza
•fissa (esempio: DES elabora blocchi di 64 bit)
• Nella realtà, con grosse moli di dati, vi sono
•molteplici blocchi da criptare
•• L’ ANSI standard ANSI X3.106-1983 Modes of
•Use ha stabilito 4 possibili modi di utilizzo dei
•cifrari a blocco
•• I modi di utilizzo usualmente considerati sono 5
Top Related