0 Lalgoritmo DES semplificato Cifratura di flussi e cifratura a blocchi La cifratura di Feistel...

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


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


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


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


•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


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


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.

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



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


•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


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


•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


81


•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.

http://it.wikibooks.org/w/index.php?title=Testi_in_chiaro&action=edit



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).

http://it.wikibooks.org/w/index.php?title=Crittanalisi_differenziale-lineare&action=edit



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

0 Lalgoritmo DES semplificato Cifratura di flussi e cifratura a blocchi La cifratura di Feistel...

Documents

Transcript of 0 Lalgoritmo DES semplificato Cifratura di flussi e cifratura a blocchi La cifratura di Feistel...