DES: applicazioni ed evoluzioni Calzetta Emilia Cervone Vincenzo Reti di calcolatori Prof. Alfredo...

DES: applicazioni ed DES: applicazioni ed evoluzionievoluzioni

DES: applicazioni ed DES: applicazioni ed evoluzionievoluzioni

Calzetta Emilia Calzetta Emilia

Cervone Vincenzo Cervone Vincenzo

Reti di calcolatoriReti di calcolatoriProf. Alfredo PetrosinoProf. Alfredo Petrosino

22

Programmazione didatticaProgrammazione didatticaProgrammazione didatticaProgrammazione didattica

Titolo:Titolo: DES: evoluzioni ed applicazioni DES: evoluzioni ed applicazioni

Classe:Classe: 5^ I.T.I. 5^ I.T.I.

Contenuti:Contenuti:

Cenni sulla crittografia; DES: Introduzione storica; La Struttura del DES: Cenni sulla crittografia; DES: Introduzione storica; La Struttura del DES: codifica e decodifica; Le modalità operative ed applicative del DES: codifica e decodifica; Le modalità operative ed applicative del DES: Electronic Codebook Chaining, Cipher Block Chaining, Cipher Feedback, Electronic Codebook Chaining, Cipher Block Chaining, Cipher Feedback, Output Feedback; Crittoanalisi del DES; Esercizi.Output Feedback; Crittoanalisi del DES; Esercizi.

Obiettivi:Obiettivi: Comprendere la struttura e l’utilizzo degli algoritmi crittografici a Comprendere la struttura e l’utilizzo degli algoritmi crittografici a

chiave privatachiave privata Comprendere l’importanza della sicurezza in un sistema informaticoComprendere l’importanza della sicurezza in un sistema informatico Demotivare gli alunni a intraprendere azioni di intrusione nei sistemi Demotivare gli alunni a intraprendere azioni di intrusione nei sistemi

informaticiinformatici

33

Programmazione didatticaProgrammazione didatticaProgrammazione didatticaProgrammazione didatticaPrerequisiti e verifica:Prerequisiti e verifica:Il prerequisito richiesto è la conoscenza di base della crittografia. La Il prerequisito richiesto è la conoscenza di base della crittografia. La verifica sarà svolta durante il corso sia sotto forma di dialogo e verifica sarà svolta durante il corso sia sotto forma di dialogo e sperimentazione e sia mediate esercizi, prove pratiche e tesine sia di sperimentazione e sia mediate esercizi, prove pratiche e tesine sia di gruppo che individuali.gruppo che individuali.

Modalità di lavoro:Modalità di lavoro:lezioni frontalilezioni frontaliutilizzo del laboratorioutilizzo del laboratorio

Riferimenti:Riferimenti:Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. Standard, Springer Verlag, 1993. Cryptography and Network Security: Principles and Practice (3rd Edition)Cryptography and Network Security: Principles and Practice (3rd Edition)by William Stallings, 2003by William Stallings, 2003Don Coppersmith. (1994). The data encryption standard (DES) and its Don Coppersmith. (1994). The data encryption standard (DES) and its strength against attacks. IBM Journal of Research and Development, strength against attacks. IBM Journal of Research and Development, 38(3), 243–250.38(3), 243–250.Joan Daemen and Vincent Rijmen, "The Design of Rijndael: AES - The Joan Daemen and Vincent Rijmen, "The Design of Rijndael: AES - The Advanced Encryption Standard." Springer-Verlag, 2002Advanced Encryption Standard." Springer-Verlag, 2002

44

Crittografia: cenni storiciCrittografia: cenni storiciCrittografia: cenni storiciCrittografia: cenni storiciCrittografiaCrittografia

““cryptos" =cryptos" = segreto segreto “grafien” =“grafien” = scrittura scrittura

La crittografia tratta i metodi per rendere un messaggio La crittografia tratta i metodi per rendere un messaggio “segreto” in modo da non essere comprensibile a persone non “segreto” in modo da non essere comprensibile a persone non autorizzate, è una scienza antica nata dall’esigenza di riservare autorizzate, è una scienza antica nata dall’esigenza di riservare solo al destinatario la facoltà di comprendere il significato di un solo al destinatario la facoltà di comprendere il significato di un messaggio. messaggio. Nel corso della storia la crittografia è stata usata per scopi Nel corso della storia la crittografia è stata usata per scopi civili e militari e oggi assume importanza ancor maggiore con civili e militari e oggi assume importanza ancor maggiore con l’espansione delle reti.l’espansione delle reti.

Si hanno traccia di applicazioni di crittografia (in special modo Si hanno traccia di applicazioni di crittografia (in special modo sulle comunicazioni) risalenti persino agli antichi egizi.sulle comunicazioni) risalenti persino agli antichi egizi.

Uno dei più antichi cifrari che si conoscano è il "Cifrario di Uno dei più antichi cifrari che si conoscano è il "Cifrario di Cesare", utilizzato dagli imperatori romani e basato sulla Cesare", utilizzato dagli imperatori romani e basato sulla trasposizione delle lettere. trasposizione delle lettere.

55

Codice di CesareCodice di Cesare "… se vi era qualche questione riservata egli usava scrivere in cifra, e

questa cifra consisteva in una disposizione apparentemente caotica delle lettere, sicché era impossibile ricostruire la parola originale. Chi voglia scoprirne il senso e decifrarla sappia che bisogna sostituire a ogni lettera la terza che segue nell'alfabeto; vale a dire dove è scritto A bisogna leggere D e così di seguito." Svetonio - Svetonio - Vita del Divo GiulioVita del Divo Giulio

Per cifrare: chiave = chiave = 33

CADE CADE FDGH FDGH

Crittografia: cenni storiciCrittografia: cenni storiciCrittografia: cenni storiciCrittografia: cenni storici

A A

B B C C DD EEF F

GG HH I I L L MM N N ……

DD EEF F

GG HH I I L L

MM N N OO PP QQ ……

66

La prima lettera dell'alfabeto ebraico ‘La prima lettera dell'alfabeto ebraico ‘aleph’aleph’ viene sostituita con viene sostituita con l'ultima ‘l'ultima ‘taw’taw’ e la seconda ‘ e la seconda ‘bethbeth’ con la penultima ‘’ con la penultima ‘shin’shin’. Da qui il . Da qui il

nome Atbash.nome Atbash.

EsempioEsempio: nella Bibbia, Geremia, 25: : nella Bibbia, Geremia, 25: “… “… il re di Sesacil re di Sesac”; si tratta invece del re di Babel.”; si tratta invece del re di Babel.

Il cifrario ebraico (ATBASH) Il cifrario ebraico (ATBASH)


77

Il cifrario Albam (ROT-13)Il cifrario Albam (ROT-13)Ad ogni lettera si sostituisce quella che la segue 13 posti più Ad ogni lettera si sostituisce quella che la segue 13 posti più avanti nell'alfabeto.avanti nell'alfabeto.

AA BB CC DD EE FF GG HH II JJ KK LL MM NN OO PP QQ RR ……

| | | | | | | | | | | | | | | | | |NN OO PP QQ RR SS TT UU VV WW XX YY ZZ AA BB CC DD EE ……

I cifrari Albam e Atbash, sono reversibili, cioè, se sono applicati I cifrari Albam e Atbash, sono reversibili, cioè, se sono applicati due (o un numero pari di) volte di seguito ad un testo, si due (o un numero pari di) volte di seguito ad un testo, si ottiene il testo originale.ottiene il testo originale.


ESERCIZIO

http://www.tglman.com/ao42/codici.html

88

Crittografia modernaCrittografia moderna Crittografia modernaCrittografia moderna

Gli antichi cifrari sono stati sostituiti nel corso della storia dai Gli antichi cifrari sono stati sostituiti nel corso della storia dai sistemi crittografici, ma il problema da risolvere non è sistemi crittografici, ma il problema da risolvere non è cambiato: cambiato:

Bob e Alice vogliono comunicare in modo “sicuro”Bob e Alice vogliono comunicare in modo “sicuro”Carmen (l’intrusa) può intercettare, rimuovere o aggiungere Carmen (l’intrusa) può intercettare, rimuovere o aggiungere messaggimessaggiCarmen vuole modificare, conoscere o impedire la Carmen vuole modificare, conoscere o impedire la comunicazione comunicazione

BobBobAliceAlice

CarmenCarmen

99

Un sistema crittografico è un sistema in grado di cifrare e Un sistema crittografico è un sistema in grado di cifrare e decifrare un messaggio attraverso l’uso di un algoritmo e di decifrare un messaggio attraverso l’uso di un algoritmo e di una chiave (una stringa alfanumerica). Il messaggio che dovrà una chiave (una stringa alfanumerica). Il messaggio che dovrà essere cifrato viene chiamato testo in chiaro (plaintext) essere cifrato viene chiamato testo in chiaro (plaintext) mentre il risultato dell’algoritmo crittografico testo cifrato mentre il risultato dell’algoritmo crittografico testo cifrato (ciphertext). (ciphertext).


Il sistema crittografico deve soddisfare i seguenti requisiti di Il sistema crittografico deve soddisfare i seguenti requisiti di sicurezza:sicurezza:

Disponibilità Disponibilità

RiservatezzaRiservatezza

IntegritàIntegrità

AutenticazioneAutenticazione

Non ripudiazioneNon ripudiazione

1010

Requisiti di disponibilitáRequisiti di disponibilitá: : Rendere disponibili a ciascun Rendere disponibili a ciascun utente abilitato le informazioni alle quali ha diritto di utente abilitato le informazioni alle quali ha diritto di accedere, nei tempi e nei modi previsti.accedere, nei tempi e nei modi previsti.


Requisiti di integritàRequisiti di integrità:: Impedire l’alterazione diretta o Impedire l’alterazione diretta o indiretta delle informazioni, sia da parte di utenti e processi indiretta delle informazioni, sia da parte di utenti e processi non autorizzati, che a seguito di eventi accidentali. Se i dati non autorizzati, che a seguito di eventi accidentali. Se i dati vengono alterati e’ necessario fornire strumenti per poterlo vengono alterati e’ necessario fornire strumenti per poterlo verificare facilmente.verificare facilmente.

1111

Requisiti di riservatezzaRequisiti di riservatezza: : Nessun utente deve poter Nessun utente deve poter ottenere o dedurre dal sistema informazioni che non è ottenere o dedurre dal sistema informazioni che non è autorizzato a conoscere. Se una informazione è protetta, o se autorizzato a conoscere. Se una informazione è protetta, o se esiste una comunicazione in atto fra due utenti o processi in esiste una comunicazione in atto fra due utenti o processi in un certo contesto, il sistema non deve permettere di dedurre un certo contesto, il sistema non deve permettere di dedurre informazioni riservate.informazioni riservate.


Requisiti di autenticazioneRequisiti di autenticazione: : Ciascun utente deve poter Ciascun utente deve poter verificare l’autenticità delle informazioni. Si richiede di poter verificare l’autenticità delle informazioni. Si richiede di poter verificare se una informazione, non necessariamente verificare se una informazione, non necessariamente riservata, e’ stata manipolata. riservata, e’ stata manipolata.

Firmato e

certificato

Requisiti di non ripudiazioneRequisiti di non ripudiazione: : Nessun Nessun utente deve poter ripudiare o negare utente deve poter ripudiare o negare messaggi da lui spediti o firmati. Questo evita messaggi da lui spediti o firmati. Questo evita che le informazioni e i messaggi siano negati che le informazioni e i messaggi siano negati dal firmatario in tempi successivi (es. firma di dal firmatario in tempi successivi (es. firma di un contratto)un contratto)

1212

I sistemi crittografici sono di 2 tipi:I sistemi crittografici sono di 2 tipi: Sistemi crittografici Simmetrici (detti anche a chiave Sistemi crittografici Simmetrici (detti anche a chiave simmetrica o a chiave segreta) simmetrica o a chiave segreta) Sistemi crittografici Asimmetrici (detti anche a chiave Sistemi crittografici Asimmetrici (detti anche a chiave asimmetrica o a chiave pubblica).asimmetrica o a chiave pubblica).

Simmetrici:Simmetrici:

permettono al mittente e al destinatario di usare la permettono al mittente e al destinatario di usare la medesima chiave;medesima chiave;

l’operazione di decifratura è relativamente semplice nel l’operazione di decifratura è relativamente semplice nel caso in cui si conosca la chiave.caso in cui si conosca la chiave.

Asimmetrici:Asimmetrici:

Usano una chiave pubblica e una privata;Usano una chiave pubblica e una privata;

Un messaggio viene cifrato con la chiave privata e decifrato Un messaggio viene cifrato con la chiave privata e decifrato con quella pubblica;con quella pubblica;


1313

Schema: algoritmi simmetriciSchema: algoritmi simmetrici Schema: algoritmi simmetriciSchema: algoritmi simmetrici

BobBobAliceAlice

CarmenCarmen

I’love I’love youyou

BobBob

I’love I’love youyou

BobBob

1414

DES: Data Encryption Standard DES: Data Encryption Standard (storia)(storia)DES: Data Encryption Standard DES: Data Encryption Standard (storia)(storia)Il DES nasce nella metà degli anni 70 dai laboratori di ricerca Il DES nasce nella metà degli anni 70 dai laboratori di ricerca dell’IBM.dell’IBM.Nel 1972 l'NBS (National Bureau of Standards) dopo aver Nel 1972 l'NBS (National Bureau of Standards) dopo aver concluso una serie di studi sulla sicurezza informatica per il concluso una serie di studi sulla sicurezza informatica per il governo statunitense definì la necessità dell'individuazione di governo statunitense definì la necessità dell'individuazione di un algoritmo di cifratura in modo da favorire la comunicazione un algoritmo di cifratura in modo da favorire la comunicazione protetta tra le varie organizzazioni governative statunitensi. protetta tra le varie organizzazioni governative statunitensi. Dopo essersi consultata con l'NSA (National Security Agency) il Dopo essersi consultata con l'NSA (National Security Agency) il 15 maggio 1972 venne presentata la prima richiesta pubblica di 15 maggio 1972 venne presentata la prima richiesta pubblica di uno standard di cifratura definito secondo criteri rigorosi. uno standard di cifratura definito secondo criteri rigorosi. Nessuno degli algoritmi presentati superò i test dell'NSA e Nessuno degli algoritmi presentati superò i test dell'NSA e quindi il 27 agosto 1974 fù diramato un secondo bando. L’IBM quindi il 27 agosto 1974 fù diramato un secondo bando. L’IBM sottopose come candidato il suo algoritmo di cifratura sottopose come candidato il suo algoritmo di cifratura sviluppato tra il 1973 e il 1974. Questo algoritmo chiamato sviluppato tra il 1973 e il 1974. Questo algoritmo chiamato LuciferLucifer fù sviluppato da un team guidato da fù sviluppato da un team guidato da Horst FeistelHorst Feistel e si e si basava su una chiave da 128basava su una chiave da 128 bit.bit. L'attività di ricerca continuò e L'attività di ricerca continuò e la chiave fù portata da 128 a 56 bit, i risultati raggiunti la chiave fù portata da 128 a 56 bit, i risultati raggiunti apparvero in una serie di pubblicazioni e documenti ufficiali. apparvero in una serie di pubblicazioni e documenti ufficiali.

1515

DES: Data Encryption Standard DES: Data Encryption Standard (storia)(storia)DES: Data Encryption Standard DES: Data Encryption Standard (storia)(storia)Il 17 marzo 1975, il DES fu pubblicato nel Il 17 marzo 1975, il DES fu pubblicato nel Federal Register.Federal Register. Lo Lo standard proposto fù subito messo in discussione da standard proposto fù subito messo in discussione da Martin Martin HellmanHellman e e Whitfield DiffieWhitfield Diffie che citavano la brevità della lunghezza che citavano la brevità della lunghezza della chiave e le misteriose S-box come prova di un'interferenza della chiave e le misteriose S-box come prova di un'interferenza impropria da parte della NSA. impropria da parte della NSA. Il sospetto che aleggiava era che l'algoritmo fosse stato Il sospetto che aleggiava era che l'algoritmo fosse stato indebolito di nascosto dall'agenzia di indebolito di nascosto dall'agenzia di intelligenceintelligence in modo che in modo che essi, ma nessun altro, potessero facilmente leggere messaggi essi, ma nessun altro, potessero facilmente leggere messaggi cifrati. cifrati. Il Il Select Committee on IntelligenceSelect Committee on Intelligence del Senato degli Stati Uniti del Senato degli Stati Uniti esaminò le azioni della NSA per determinare se ci fosse stato un esaminò le azioni della NSA per determinare se ci fosse stato un coinvolgimento improprio. Nel resoconto delle indagini coinvolgimento improprio. Nel resoconto delle indagini pubblicato nel 1978, il Comitato scrisse, "pubblicato nel 1978, il Comitato scrisse, "L'NSA non alterò il L'NSA non alterò il progetto dell'algoritmo in alcun modo. L'IBM inventò e progettò progetto dell'algoritmo in alcun modo. L'IBM inventò e progettò l'algoritmo, prese tutte le decisioni pertineti e fu d'accordo nel l'algoritmo, prese tutte le decisioni pertineti e fu d'accordo nel ritenere che la lunghezza della chiave fosse più che adeguata a ritenere che la lunghezza della chiave fosse più che adeguata a tutti gli usi commerciali al quale il DES era destinatotutti gli usi commerciali al quale il DES era destinato". ".

1616

Nonostante le critiche, il DES fu approvato come standard Nonostante le critiche, il DES fu approvato come standard federale nel novembre 1976 e pubblicato il 15 gennaio 1977 federale nel novembre 1976 e pubblicato il 15 gennaio 1977 come FIPS (Federal Information Processing Standard) PUB 46. È come FIPS (Federal Information Processing Standard) PUB 46. È stato in seguito riconfermato come standard nel 1983, 1988 stato in seguito riconfermato come standard nel 1983, 1988 (riesaminato come FIPS-46-1), 1993 (FIPS-46-2) e nuovamente (riesaminato come FIPS-46-1), 1993 (FIPS-46-2) e nuovamente nel 1998 (FIPS-46-3), nel quale si introduce il "Triple DES".nel 1998 (FIPS-46-3), nel quale si introduce il "Triple DES".

Il 26 maggio 2002, il DES è stato finalmente rimpiazzato Il 26 maggio 2002, il DES è stato finalmente rimpiazzato dall'AES, l'Advanced Encryption Standard. Ancora oggi, ad ogni dall'AES, l'Advanced Encryption Standard. Ancora oggi, ad ogni modo, il DES è ancora largamente utilizzato.modo, il DES è ancora largamente utilizzato.

L'introduzione del DES è stata un catalizzatore per ricerche L'introduzione del DES è stata un catalizzatore per ricerche accademiche sulla crittografia, in particolare sui metodi di accademiche sulla crittografia, in particolare sui metodi di violazione dei cifrari a blocchi. Bruce Schneier scrive: violazione dei cifrari a blocchi. Bruce Schneier scrive: ""Ufficiosamente, la NSA ha definito il DES come uno dei propri Ufficiosamente, la NSA ha definito il DES come uno dei propri più grandi errori. Se avessero saputo che i dettagli sarebbero più grandi errori. Se avessero saputo che i dettagli sarebbero stati rilasciati pubblicamente in modo che chiunque avrebbe stati rilasciati pubblicamente in modo che chiunque avrebbe potuto scrivere il software, non sarebbero stati d'accordopotuto scrivere il software, non sarebbero stati d'accordo." ."

DES: Data Encryption Standard DES: Data Encryption Standard (storia)(storia)DES: Data Encryption Standard DES: Data Encryption Standard (storia)(storia)

1717

Nel 1990 in seguito alla pubblicazione da parte di Eli Biham e Nel 1990 in seguito alla pubblicazione da parte di Eli Biham e Adi Shamir della crittanalisi differenziale, un metodo per Adi Shamir della crittanalisi differenziale, un metodo per violare i cifrari a blocchi, si scoprì che Le S-box del DES erano violare i cifrari a blocchi, si scoprì che Le S-box del DES erano molto resistenti agli attacchi facendo fortemente sospettare molto resistenti agli attacchi facendo fortemente sospettare che l'IBM conoscesse le techiche di crittoanalisi differenziale che l'IBM conoscesse le techiche di crittoanalisi differenziale già negli anni '70. già negli anni '70.

Quando nel 1994, furono pubblicati i criteri di progetto Quando nel 1994, furono pubblicati i criteri di progetto originali delle S-box si capì che l'IBM aveva scoperto la originali delle S-box si capì che l'IBM aveva scoperto la crittanalisi differenziale negli anni '70 e che dopo aver reso crittanalisi differenziale negli anni '70 e che dopo aver reso sicuro il DES, gli fu richiesto dalla NSA di mantenere segreta sicuro il DES, gli fu richiesto dalla NSA di mantenere segreta questa tecnica. questa tecnica.

QQuesto accadde perché la crittanalisi differenziale può essere uesto accadde perché la crittanalisi differenziale può essere una tecnica molto potente usata contro vari schemi e quindi una tecnica molto potente usata contro vari schemi e quindi avrebbe potuto generare problemi di sicurezza nazionale.avrebbe potuto generare problemi di sicurezza nazionale.

DES: Data Encryption Standard DES: Data Encryption Standard (storia)(storia)DES: Data Encryption Standard DES: Data Encryption Standard (storia)(storia)

1818

DES: struttura generaleDES: struttura generale DES: struttura generaleDES: struttura generale Il DES codifica blocchi di 64 bit e usa una chiave di 56 bit. Il DES codifica blocchi di 64 bit e usa una chiave di 56 bit.

La chiave in realtà è lunga 64 bit ma solo 56 di questi sono La chiave in realtà è lunga 64 bit ma solo 56 di questi sono effettivamente effettivamente

utilizzati dall'algoritmo in quanto 8 bit sono utilizzati solo per utilizzati dall'algoritmo in quanto 8 bit sono utilizzati solo per

il controllo di paritàil controllo di parità

1919

La chiave (k) è memorizzata sfruttando 64 bit, dove l'ottavo, il La chiave (k) è memorizzata sfruttando 64 bit, dove l'ottavo, il 16-esimo, ... , il 64-esimo, sono i bit di parità per i sette bit 16-esimo, ... , il 64-esimo, sono i bit di parità per i sette bit precedenti. Possiamo immaginare i 64 bit della chiave k divisi in precedenti. Possiamo immaginare i 64 bit della chiave k divisi in 8 byte, dove per ognuno di questi l'ottavo bit definisce la parità 8 byte, dove per ognuno di questi l'ottavo bit definisce la parità del byte.del byte.

Quindi concretamente ci sono solo 56 bit su cui può variare la Quindi concretamente ci sono solo 56 bit su cui può variare la chiave per un totale di 2chiave per un totale di 256 56 possibili combinazionipossibili combinazioni

XOR (0+0=0, 1+0=1, 0+1=1, 1+1=0)XOR (0+0=0, 1+0=1, 0+1=1, 1+1=0)

DES: struttura generaleDES: struttura generale DES: struttura generaleDES: struttura generale

2020

DES: struttura generaleDES: struttura generale DES: struttura generaleDES: struttura generale

permutazione iniziale di 64 bit

le sedici iterazioni che trasformano la stringa in input sono uguali nel senso che la funzione che le realizza è sempre la stessa (ad ogni iterazione cambia solo la chiave utilizzata)scambia i 32 bit più a sinistra con quelli più a destra della stringa prodotta come output alla 16-esima iterazione

sfruttando la sola chiave k, produce le chiavi k1, k2, ..., k16 di 48 bit ciascuna, per le iterazioni da 1 a 16.

2121

DES: Permutazione IPDES: Permutazione IP DES: Permutazione IPDES: Permutazione IP

Sia x un testo in chiaro di 64 bit: l'algoritmo costruisce una Sia x un testo in chiaro di 64 bit: l'algoritmo costruisce una stringa binaria permutando la stringa iniziale mediante la stringa binaria permutando la stringa iniziale mediante la permutazione iniziale fissata IPpermutazione iniziale fissata 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

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

Il primo valore della tabella specifica Il primo valore della tabella specifica che il primo bit della stringa che il primo bit della stringa permutata IP(x) è il 58-esimo bit della permutata IP(x) è il 58-esimo bit della stringa da permutare x; il secondo stringa da permutare x; il secondo elemento della tabella, 50, ne specifica elemento della tabella, 50, ne specifica il secondo e così via. il secondo e così via.

2222

Passo 3: L'output dell'algoritmo è ottenuto applicando la Passo 3: L'output dell'algoritmo è ottenuto applicando la permutazione IPpermutazione IP-1-1 a R a R1616LL1616. Si noti l'ordine inverso delle ultime . Si noti l'ordine inverso delle ultime due stringhe di bit Rdue stringhe di bit R1616 e L e L1616 dovuto allo scambio di 32 bit dovuto allo scambio di 32 bit

11 22

88 4040

bit bit inizialiiniziali

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

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

DES: permutazione inversa IPDES: permutazione inversa IP-1-1 DES: permutazione inversa IPDES: permutazione inversa IP-1-1

Questa tabella si legge nello stesso Questa tabella si legge nello stesso modo della precedente. Queste modo della precedente. Queste permutazioni sono solo una scelta dello permutazioni sono solo una scelta dello standard, potremmo infatti fare a meno standard, potremmo infatti fare a meno della permutazione iniziale e finale della permutazione iniziale e finale senza perdere in sicurezza.senza perdere in sicurezza.

2323

Il DES effettua 16 iterazioni. Per 1 Il DES effettua 16 iterazioni. Per 1 i i 16 l'input della i-esima 16 l'input della i-esima iterazione è una stringa di 64 bit divisa in due parti, Literazione è una stringa di 64 bit divisa in due parti, L i-1i-1 e R e Ri-1i-1, , ognuna di 32 bit (chiamate rispettivamente parte sinistra e parte ognuna di 32 bit (chiamate rispettivamente parte sinistra e parte destra della stringa). I valori di output Ldestra della stringa). I valori di output Lii e R e Rii sono prodotti in sono prodotti in

base alla seguente regola: base alla seguente regola: LLii=R=Ri-1 i-1 e Re Rii=L=Li-1i-1 f(Rf(Ri-1 i-1 , k, kii))

DES: iterazioniDES: iterazioni DES: iterazioniDES: iterazioni

L'operatore L'operatore denota denota la funzione xor bit a bit la funzione xor bit a bit delle due stringhe, ed f delle due stringhe, ed f è una funzione che, è una funzione che, data la chiave kdata la chiave kii e la e la sottostringa Rsottostringa Ri-1 i-1 , , produce una stringa produce una stringa lunga 32 bit. lunga 32 bit.

kk11, k, k22, ..., k, ..., k1616 sono le sono le chiavi prodotte dal chiavi prodotte dal processo di processo di schedulazione. All'i-schedulazione. All'i-esima iterazione verrà esima iterazione verrà usata la sola chiave kusata la sola chiave kii..

Li-1LLii--11 Ri-1

RRii--11

LiLLii Ri

RRii

kikkiifff

parte sinistraparte sinistra32 bit32 bit

parte destraparte destra32 bit32 bit

sottochiavesottochiave48 bit48 bit

singola iterazionesingola iterazione

2424

DES: funzione di FeistelDES: funzione di Feistel DES: funzione di FeistelDES: funzione di Feistel La funzione f prende in input una stringa A di 32 bit, una stringa La funzione f prende in input una stringa A di 32 bit, una stringa K di 48 bit, e fornisce in output una stringa di 32 bit.K di 48 bit, e fornisce in output una stringa di 32 bit.

JJ

AA

EEEE(A)E(A)

PPP

S1S1S1 S2S2S2 S3S3S3 S4S4S4 S5S5S5 S6S6S6 S7S7S7

CC1 1 CC2 2 CC3 3 CC4 4 CC5 5 CC6 6 CC7 7 CC88

BB1 1 BB2 2 BB3 3 BB4 4 BB5 5 BB6 6 BB7 7 BB88

48 bit48 bit48 bit48 bit

32 bit32 bit

S8S8S8

La stringa A di 32 bit viene La stringa A di 32 bit viene espansa dalla funzione E in espansa dalla funzione E in una stringa 48 bit. Viene una stringa 48 bit. Viene computato lo xor bit a bit tra computato lo xor bit a bit tra K e E(A), che è una stringa di K e E(A), che è una stringa di 48 bit. La sequenza viene 48 bit. La sequenza viene divisa in 8 sottosequenze di 6 divisa in 8 sottosequenze di 6 bit ciascuna, dette bit ciascuna, dette sottosequenze Bsottosequenze B11, B, B22, ..., B, ..., B88. . L'S-box Si (per 1 L'S-box Si (per 1 i i 8) 8) prende in input Bi (a 6 bit) e prende in input Bi (a 6 bit) e da in output una sequenza a 4 da in output una sequenza a 4 bit, che chiamiamo Ci. bit, che chiamiamo Ci.

La stringa CLa stringa C11,C,C22,...,C,...,C88 (a 32 (a 32 bit) viene permutata tramite bit) viene permutata tramite la permutazione P e questo è la permutazione P e questo è il valore f(A, K).il valore f(A, K).

K

2525

32 1 2 3 4 54 5 6 7 8 98 9 10 11 12 1312 13 14 15 16 1716 17 18 19 20 2120 21 22 23 24 2524 25 26 27 28 2928 29 30 31 32 1

32 1 2 3 4 54 5 6 7 8 98 9 10 11 12 1312 13 14 15 16 1716 17 18 19 20 2120 21 22 23 24 2524 25 26 27 28 2928 29 30 31 32 1

La funzione E duplica e permuta 16 bit dei 32 di A La funzione E duplica e permuta 16 bit dei 32 di A

in base allo schema della tabella Ein base allo schema della tabella E

Espansione (E)Espansione (E) e e permutazione (P)permutazione (P) Espansione (E)Espansione (E) e e permutazione (P)permutazione (P)

11 22

11 3232


bit dopo espansionebit dopo espansione4848

22

33 ......Tabella ETabella E

Tabella PTabella P

La tabella P specifica la permutazione PLa tabella P specifica la permutazione P

2626

L'unico punto in cui il sistema DES non utilizza funzioni di tipo L'unico punto in cui il sistema DES non utilizza funzioni di tipo lineare (cioè gli xor, le permutazioni e le espansioni) è nelle S-lineare (cioè gli xor, le permutazioni e le espansioni) è nelle S-box, che costituiscono il fulcro dell'algoritmo. box, che costituiscono il fulcro dell'algoritmo.

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 0110 0111 111100 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 701 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 810 4 1 7 8 13 6 2 11 15 12 9 7 3 10 5 011 15 12 10 2 4 9 1 7 5 11 3 14 10 0 6 13

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 0110 0111 111100 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 701 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 810 4 1 7 8 13 6 2 11 15 12 9 7 3 10 5 011 15 12 10 2 4 9 1 7 5 11 3 14 10 0 6 13

DES: S-BOXDES: S-BOX DES: S-BOXDES: S-BOX

S-BOX S1S-BOX S1

Dato Bi (l'input a 6 bit dell‘S-box Si), il primo e l'ultimo bit di Bi 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 vengono interpretati come indice di riga, mentre i bit centrali come indice di colonna. Si consulta la tabella Si alle coordinate come indice di colonna. Si consulta la tabella Si alle coordinate prescritte e il valore trovato nell'S-box è un decimale la cui prescritte e il valore trovato nell'S-box è un decimale la cui conversione binaria dà i 4 bit outputconversione binaria dà i 4 bit output

2727

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 0110 0111 111100 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 701 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 810 4 1 7 8 13 6 2 11 15 12 9 7 3 10 5 011 15 12 10 2 4 9 1 7 5 11 3 14 10 0 6 13

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 0110 0111 111100 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 701 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 810 4 1 7 8 13 6 2 11 15 12 9 7 3 10 5 011 15 12 10 2 4 9 1 7 5 11 3 14 10 0 6 13

Box S1Box S1

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 0110 0111 111100 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 701 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 810 4 1 7 8 13 6 2 11 15 12 9 7 3 10 5 011 15 12 10 2 4 9 1 7 5 11 3 14 10 0 6 13

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 0110 0111 111100 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 701 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 810 4 1 7 8 13 6 2 11 15 12 9 7 3 10 5 011 15 12 10 2 4 9 1 7 5 11 3 14 10 0 6 13

Input BInput B11 = 101110 = 101110

1010primo ed ultimo bitprimo ed ultimo bit

output Soutput S11= 11 ---> in binario = 1011= 11 ---> in binario = 1011

DES: S-BOX (esempio) DES: S-BOX (esempio) DES: S-BOX (esempio) DES: S-BOX (esempio)

2828

DES: proprietà delle S-boxDES: proprietà delle S-box DES: proprietà delle S-boxDES: proprietà delle S-box I criteri di progettazione delle S-box non sono completamente I criteri di progettazione delle S-box non sono completamente noti. Si conoscono solo alcune proprietà:noti. Si conoscono solo alcune proprietà:

Ogni riga è una permutazione degli interi 0,..,15Ogni riga è una permutazione degli interi 0,..,15

Nessuna S-box è una funzione affine o lineare dei suoi inputNessuna S-box è una funzione affine o lineare dei suoi input

Cambiando un solo bit di input ad una S-box variano almeno Cambiando un solo bit di input ad una S-box variano almeno due bit nell'outputdue bit nell'output

Per ogni S-box S e per ogni input x a 6 bit: S(x) e Per ogni S-box S e per ogni input x a 6 bit: S(x) e S(xS(x001100) differiscono in almeno due bit001100) differiscono in almeno due bit

Per ogni S-box, per ogni input x e per ogni bit d,g, S(x) Per ogni S-box, per ogni input x e per ogni bit d,g, S(x) S(xS(x11dg00)11dg00)

Per ogni S-box, se fissiamo un bit di input e osserviamo il Per ogni S-box, se fissiamo un bit di input e osserviamo il valore di un fissato bit di output, il numero degli input per i valore di un fissato bit di output, il numero degli input per i quali il bit di output vale 0 è circa uguale al numero degli quali il bit di output vale 0 è circa uguale al numero degli input per i quali tale bit vale 1input per i quali tale bit vale 1

Verificare per esercizio queste proprietà sulla S-BOX S1Verificare per esercizio queste proprietà sulla S-BOX S1

2929

DES: schedulazione delle DES: schedulazione delle chiavichiavi DES: schedulazione delle DES: schedulazione delle chiavichiavi

LS1LSLS11

chiave kchiave k

PC1PC1PC1

PC2PC2PC2

PC2PC2PC2

kk11

kk1616

CC00 DD00

LS1LSLS11

CC11 DD11

CC1616 DD1616

LS16LSLS1616 LS16

LSLS1616

48 bit48 bit

48 bit48 bit 56 bit56 bit

56 bit56 bit

............

......

Le chiavi usate durante i vari round sono ricavate dalla chiave k Le chiavi usate durante i vari round sono ricavate dalla chiave k di 64 bit escludendo gli 8 bit utilizzati per il controllo di parità e di 64 bit escludendo gli 8 bit utilizzati per il controllo di parità e permutando i rimanenti 56 bit tramite la permutazione PC1 che permutando i rimanenti 56 bit tramite la permutazione PC1 che calcolerà PC1(k) = Ccalcolerà PC1(k) = C00DD0 0 dove Cdove C00 e D e D00 sono i primi e gli ultimi 28 sono i primi e gli ultimi 28 bit di PC1(k). bit di PC1(k). Sia Per 1 Sia Per 1 i i 16 16

computiamocomputiamo

CCii = LS = LSii(C(Ci-1i-1););

DDii = LS = LSii(D(Di-1i-1););

KKii = PC = PC22(C(CiiDDii))

LSLSii è uno shift ciclico a è uno shift ciclico a sinistra di una o due sinistra di una o due posizioni a seconda posizioni a seconda del valore di i.del valore di i.

PC2 infine è una PC2 infine è una compressione di una compressione di una stringa di input a 56 stringa di input a 56 bit, in una stringa di bit, in una stringa di output a 48 bit.output a 48 bit.

3030

Permutazione PC1Permutazione PC1 Permutazione PC1Permutazione PC1

11 22

11 6464


bit dopo permutazionebit dopo permutazione5656

5757

33 ......

57 49 41 33 25 17 9 1 58 50 42 34 26 1810 2 59 51 43 35 27 19 11 3 60 52 44 3663 55 47 39 31 23 15 7 62 54 46 38 30 2214 6 61 53 45 37 29 21 13 5 28 20 12 4

57 49 41 33 25 17 9 1 58 50 42 34 26 1810 2 59 51 43 35 27 19 11 3 60 52 44 3663 55 47 39 31 23 15 7 62 54 46 38 30 2214 6 61 53 45 37 29 21 13 5 28 20 12 4

I bit in posizione 8, 16, 24, 32, 40, 48, 56, 64 sono di parità e I bit in posizione 8, 16, 24, 32, 40, 48, 56, 64 sono di parità e non compaiono, essi servono per rivelare un errore in ogni byte.non compaiono, essi servono per rivelare un errore in ogni byte.

3131

La funzione shift a sinistra LSLa funzione shift a sinistra LSii La funzione shift a sinistra LSLa funzione shift a sinistra LSii

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 161 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 161 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

iterazioniterazionee shiftshift

Lo shift LSi riguarda una sola Lo shift LSi riguarda una sola posizione alle iterazioni 1, 2, 9 posizione alle iterazioni 1, 2, 9 e 16, e due posizioni a tutte le e 16, e due posizioni a tutte le altre iterazionialtre iterazioni

Totale shift nelle 16 iterazioni Totale shift nelle 16 iterazioni = 28 posizioni= 28 posizioni

LS1LSLS11

chiave kchiave k

PC1PC1PC1

PC2PC2PC2

PC2PC2PC2

kk11

kk1616

CC00 DD00

LS1LSLS11

CC11 DD11

CC1616 DD1616

LS16LSLS1616 LS16

LSLS1616

48 bit48 bit

48 bit48 bit 56 bit56 bit

56 bit56 bit

............

......

3232

Compressione-permutazione Compressione-permutazione PC2PC2 Compressione-permutazione Compressione-permutazione PC2PC2

11 22

11 5656


bit dopo bit dopo compressione

8 bit soppressi in posizione 9, 18, 22, 25, 35, 38, 8 bit soppressi in posizione 9, 18, 22, 25, 35, 38,

43 e 5443 e 54

4848

1414

33 ......

14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 426 8 16 7 27 20 13 26 41 52 31 37 47 55 30 4051 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32

14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 426 8 16 7 27 20 13 26 41 52 31 37 47 55 30 4051 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32

3333

Decifratura del DESDecifratura del DES Decifratura del DESDecifratura del DES

IPIPIPIP

IPIP -1 -1IPIP -1 -1

iterazione 1iterazione 1iterazione 1iterazione 1

iterazione 16iterazione 16iterazione 16iterazione 16

testo cifratotesto cifrato

scambioscambioscambioscambio

...... schedulazioneschedulazione

chiavechiave

schedulazioneschedulazione

chiavechiave

Chiave kChiave k

kk1616

kk11

Per decifrare si usa lo stesso algoritmo e la Per decifrare si usa lo stesso algoritmo e la stessa chiave K usati per cifrare, eccezion stessa chiave K usati per cifrare, eccezion fatta per la schedulazione delle chiavi ad fatta per la schedulazione delle chiavi ad ogni round, che è invertita.ogni round, che è invertita.

ESERCIZIO

3434

l'ECB (Electronic Codebook chaining). l'ECB (Electronic Codebook chaining). Un messaggio in chiaro xUn messaggio in chiaro x11xx22…x…xnn, dove ogni x, dove ogni xi i rappresenta un rappresenta un blocco di 64 bit) viene cifrato applicando ripetutamente ad ogni blocco di 64 bit) viene cifrato applicando ripetutamente ad ogni blocco xblocco xii l'algoritmo DES, sempre con la stessa chiave k, l'algoritmo DES, sempre con la stessa chiave k, producendo un testo cifrato yproducendo un testo cifrato y11yy22…y…ynn..Quindi i valori dei blocchi yQuindi i valori dei blocchi yii sono dati da: y sono dati da: yii = DES = DESkk(x(xii))

Modalità del DES: ECBModalità del DES: ECBModalità del DES: ECBModalità del DES: ECB

3535

L'unico problema con questo metodo si ha quando il messaggio L'unico problema con questo metodo si ha quando il messaggio è costituito da un numero di bit che non è un multiplo di 64, è costituito da un numero di bit che non è un multiplo di 64, cioè quando l'ultimo blocco non contiene esattamente 64 bit, cioè quando l'ultimo blocco non contiene esattamente 64 bit, ma di meno. La soluzione per questo caso non è definita dallo ma di meno. La soluzione per questo caso non è definita dallo standard, ma bisogna convenire su come risolverlo.standard, ma bisogna convenire su come risolverlo.

L'idea potrebbe essere quella di inserire del testo opportuno L'idea potrebbe essere quella di inserire del testo opportuno alla fine del blocco, in modo tale che, in fase di decifratura, alla fine del blocco, in modo tale che, in fase di decifratura, possa essere semplice distinguere il testo aggiunto da quello possa essere semplice distinguere il testo aggiunto da quello originale. originale.

Una possibile soluzione è quella di aggiungere al messaggio Una possibile soluzione è quella di aggiungere al messaggio originale la sequenza 100...0, in modo da completare l'ultimo originale la sequenza 100...0, in modo da completare l'ultimo blocco a 64 bit. Naturalmente, questa operazione deve essere blocco a 64 bit. Naturalmente, questa operazione deve essere fatta anche quando l'ultimo blocco è già di 64 bit, in modo da fatta anche quando l'ultimo blocco è già di 64 bit, in modo da stabilire un criterio generale.stabilire un criterio generale.

Questo significa che, in fase di decifratura si sa con certezza Questo significa che, in fase di decifratura si sa con certezza che la stringa finale del messaggio decifrato, cioè la stringa che la stringa finale del messaggio decifrato, cioè la stringa 100...0, è stata aggiunta in fase di cifratura, e quindi non viene 100...0, è stata aggiunta in fase di cifratura, e quindi non viene considerata come facente parte del messaggio originario.considerata come facente parte del messaggio originario.

ModalitàModalità del DES: ECBdel DES: ECBModalitàModalità del DES: ECBdel DES: ECB

3636

L'operazione di decifratura considera un blocco alla volta del L'operazione di decifratura considera un blocco alla volta del messaggio, così come accadeva per la cifratura, applicando messaggio, così come accadeva per la cifratura, applicando però in questo caso l'algoritmo di decifratura DES.però in questo caso l'algoritmo di decifratura DES.

ModalitàModalità del DES: ECBdel DES: ECBModalitàModalità del DES: ECBdel DES: ECB

Il vantaggio di questo metodo Il vantaggio di questo metodo sta nella sua rapidità di sta nella sua rapidità di esecuzione. esecuzione.

Lo svantaggio è dato dal fatto Lo svantaggio è dato dal fatto che, durante la trasmissione del che, durante la trasmissione del messaggio, potrebbe verificarsi messaggio, potrebbe verificarsi sia la perdita di un blocco che sia la perdita di un blocco che l'attacco da parte di un nemico. l'attacco da parte di un nemico.

In particolare, quest'ultimo In particolare, quest'ultimo potrebbe sostituire un blocco con potrebbe sostituire un blocco con un altro, senza la possibilità che un altro, senza la possibilità che colui che riceve il messaggio colui che riceve il messaggio possa accorgersene.possa accorgersene.

Per esempio egli potrebbe Per esempio egli potrebbe cambiare in un messaggio il cambiare in un messaggio il blocco "do" con "do not" senza blocco "do" con "do not" senza essere scoperto. Questo è dovuto essere scoperto. Questo è dovuto alla mancanza di dipendenza tra alla mancanza di dipendenza tra i vari blocchii vari blocchi

3737

Modalità del DES: CBCModalità del DES: CBC Modalità del DES: CBCModalità del DES: CBC CBC (Cipher Block Chaining)CBC (Cipher Block Chaining)Dato un messaggio in chiaro xDato un messaggio in chiaro x11xx22 ...x ...xnn ed una chiave nascosta k, ed una chiave nascosta k, in questa modalità un generico yin questa modalità un generico yii è dato da: è dato da:

yyii = DES = DESkk(y(yi-1i-1 x xii), 1 ), 1 i i n n con ycon y00 = IV(vettore di inizializzazione a 64 bit). = IV(vettore di inizializzazione a 64 bit).

Quest'ultimo viene poi utilizzato per fare lo xor bit a bit col blocco successivo del messaggio in chiaro x2, quindi si applica alla stringa così ottenuta l'algoritmo DES sempre con la stessa chiave k, ottenendo il blocco cifrato y2 e così via. Con questo metodo, si definisce in qualche modo un legame tra yi ed il blocco precedente yi-1.

Il procedimento di cifratura considera inizialmente il vettore IV, di 64 bit, quindi effettua lo xor bit a bit tra questi ed i primi 64 bit del messaggio in chiaro, infine applica alla stringa così ottenuta l'algoritmo di cifratura DES con chiave k, ottenendo il blocco cifrato y1.

3838

Per decifrare operiamo all'inverso del caso della cifratura, cioè si Per decifrare operiamo all'inverso del caso della cifratura, cioè si applica yapplica y11 come input del DES come input del DES-1-1 (algoritmo di decifratura) con la (algoritmo di decifratura) con la stessa chiave k, ottenendo quindi la stringa che stessa chiave k, ottenendo quindi la stringa che precedentemente definiva lo xor bit a bit tra xprecedentemente definiva lo xor bit a bit tra x11 ed IV, che ed IV, che costituiva l'input del DES. Ora poiché si vuole calcolare xcostituiva l'input del DES. Ora poiché si vuole calcolare x11 si si effettua l'operazione inversa, cioè lo xor bit a bit del valore in effettua l'operazione inversa, cioè lo xor bit a bit del valore in output del DES-1 con IV e ottenendo xoutput del DES-1 con IV e ottenendo x11. In generale quindi: . In generale quindi: xxii = y = yi-1i-1 DES DESkk-1(y-1(yii) per 1 ) per 1 i i n n

Modalità del DES: CBCModalità del DES: CBC Modalità del DES: CBCModalità del DES: CBC

Il vantaggio di questo schema è Il vantaggio di questo schema è che se si cambia un solo bit del che se si cambia un solo bit del messaggio originario cambia di messaggio originario cambia di conseguenza anche la parte conseguenza anche la parte rimanente del messaggio.rimanente del messaggio.

Questa caratteristica elimina la Questa caratteristica elimina la possibilità di un attacco tramite possibilità di un attacco tramite sostituzione di un blocco. Infatti, sostituzione di un blocco. Infatti, in una tale evenienza il in una tale evenienza il messaggio sarebbe messaggio sarebbe irrimediabilmente compromesso. irrimediabilmente compromesso.

Lo svantaggio di tale metodo è Lo svantaggio di tale metodo è che in esso vengono eseguite più che in esso vengono eseguite più operazioni rispetto all'ECB, e operazioni rispetto all'ECB, e quindi rispetto ad esso è più quindi rispetto ad esso è più lentolento.

3939

Modalità del DES: CFBModalità del DES: CFB Modalità del DES: CFBModalità del DES: CFB CFB (Cipher Feedback)CFB (Cipher Feedback)In questa modalità viene fornito un vettore di inizializzazione IV, In questa modalità viene fornito un vettore di inizializzazione IV, che è una stringa di 64 bit. Sia xche è una stringa di 64 bit. Sia x11xx22…x…xnn il messaggio in chiaro. il messaggio in chiaro. Allora il generico yAllora il generico yii è definito da: è definito da:

yyii = x = xii DES DESkk (y (yi-1i-1) con 1 ) con 1 i i n n

4040

Esiste una versione più generale detta Cipher Feedback con j bit. Esiste una versione più generale detta Cipher Feedback con j bit. Per essa si considera inizialmente una stringa di 64 bit Per essa si considera inizialmente una stringa di 64 bit (costituita dal vettore IV), che si può immaginare suddivisa in (costituita dal vettore IV), che si può immaginare suddivisa in due parti, di 64-j bit a sinistra e j bit a destra. Quindi si cifra tale due parti, di 64-j bit a sinistra e j bit a destra. Quindi si cifra tale stringa usando l'algoritmo di cifratura DES con chiave k.stringa usando l'algoritmo di cifratura DES con chiave k.

Modalità del DES: CFB j-bitModalità del DES: CFB j-bitModalità del DES: CFB j-bitModalità del DES: CFB j-bit

Ad ogni passo, da j bit del testo in chiaro otteniamo j bit del testo cifrato.

Della stringa cifrata così ottenuta vengono considerati solo i j bit più a sinistra. Quindi si effettua lo xor bit a bit tra questi j bit ed i prossimi j bit del messaggio in chiaro, ottenendo j bit del messaggio cifrato. Tali j bit così definiti rientrano nel circuito, in quanto al passo successivo il vettore originale di 64 bit viene shiftato di j posizioni a sinistra, e gli ultimi j bit di tale vettore diventano i j bit del messaggio cifrato.

4141

La decifratura avviene in maniera analoga alla cifratura. E’ La decifratura avviene in maniera analoga alla cifratura. E’ importante osservare che per la decifratura viene usato ancora importante osservare che per la decifratura viene usato ancora l’algoritmo DES e non il DESl’algoritmo DES e non il DES-1-1. . L'unica variante significativa in tale schema è data dal fatto che L'unica variante significativa in tale schema è data dal fatto che i j bit del messaggio cifrato, vengono utilizzati per effettuare lo i j bit del messaggio cifrato, vengono utilizzati per effettuare lo xor bit a bit con i j bit più a sinistra dell'output del DES, oltre a xor bit a bit con i j bit più a sinistra dell'output del DES, oltre a costituire in seguito i nuovi j bit più a destra del vettore iniziale costituire in seguito i nuovi j bit più a destra del vettore iniziale (su cui viene applicato l'algoritmo DES), definendo così j bit del (su cui viene applicato l'algoritmo DES), definendo così j bit del messaggio in chiaro.messaggio in chiaro.

Modalità del DES: CFB j-bitModalità del DES: CFB j-bitModalità del DES: CFB j-bitModalità del DES: CFB j-bit

Il vantaggio di questo schema è dato dal Il vantaggio di questo schema è dato dal fatto che il valore di j può essere scelto a fatto che il valore di j può essere scelto a piacimento. piacimento.

Per esempio alcune applicazioni scelgono Per esempio alcune applicazioni scelgono j = 8, che significa cifrare 8 bit (1 byte) j = 8, che significa cifrare 8 bit (1 byte) alla volta del messaggio in chiaro. alla volta del messaggio in chiaro. Questa scelta si presta particolarmente Questa scelta si presta particolarmente alla cifratura on-line; infatti con j = 8 può alla cifratura on-line; infatti con j = 8 può essere trasmesso un carattere alla volta.essere trasmesso un carattere alla volta.

Lo svantaggio di questo metodo è che Lo svantaggio di questo metodo è che per valori di j piccoli esso diventa per valori di j piccoli esso diventa sicuramente più oneroso di quelli visti in sicuramente più oneroso di quelli visti in precedenza.precedenza.

4242

Anche in questa modalità si utilizza una stringa iniziale di 64 bit Anche in questa modalità si utilizza una stringa iniziale di 64 bit (vettore IV). Come primo passo viene costruita la sequenza: (vettore IV). Come primo passo viene costruita la sequenza: zz00zz11zz22zz33…. dove z…. dove z00 = IV e z = IV e zii = DES = DESkk(z(zii-1) con chiave k segreta. -1) con chiave k segreta.

Come si può notare tale stringa è del tutto indipendente dal Come si può notare tale stringa è del tutto indipendente dal messaggio in chiaro. Quindi sia xmessaggio in chiaro. Quindi sia x11xx22...x...xnn il messaggio in chiaro; il messaggio in chiaro; il messaggio cifrato è definito da yil messaggio cifrato è definito da y11yy22…y…ynn dove: y dove: yii = x = xi i zzii

Modalità del DES: Modalità del DES: Output Feedback Output Feedback Modalità del DES: Modalità del DES: Output Feedback Output Feedback

Anche per tale metodo c'è la Anche per tale metodo c'è la variante a j bit, che è analoga a variante a j bit, che è analoga a quella del CFB, l'unica diversità quella del CFB, l'unica diversità sta nel fatto che il feed-back sta nel fatto che il feed-back (cioè il riutilizzo di una certa (cioè il riutilizzo di una certa parte dell'informazione) non parte dell'informazione) non riguarda j bit del testo cifrato, riguarda j bit del testo cifrato, ma i j bit più a sinistra della ma i j bit più a sinistra della stringa in output prodotta dal stringa in output prodotta dal DES. DES.

4343

Per la decifratura si può notare che la prima parte del metodo è Per la decifratura si può notare che la prima parte del metodo è uguale a quello che viene utilizzata per effettuare la cifratura uguale a quello che viene utilizzata per effettuare la cifratura (ciò è valido dal momento che la sequenza del messaggio in (ciò è valido dal momento che la sequenza del messaggio in chiaro generata da questa prima parte è indipendente dal chiaro generata da questa prima parte è indipendente dal messaggio in chiaro, così come dal messaggio cifrato). messaggio in chiaro, così come dal messaggio cifrato). Quindi, ad ogni passo si considerano i j bit più a sinistra delle Quindi, ad ogni passo si considerano i j bit più a sinistra delle stringhe fornite in output dall'algoritmo DES, e si effettua lo xor stringhe fornite in output dall'algoritmo DES, e si effettua lo xor bit a bit con j bit del messaggio cifrato, ottenendo così j bit del bit a bit con j bit del messaggio cifrato, ottenendo così j bit del messaggio in chiaro.messaggio in chiaro.

Modalità del DES: Modalità del DES: Output Feedback Output Feedback Modalità del DES: Modalità del DES: Output Feedback Output Feedback

ESERCIZIO

4444

Applicazioni del DESApplicazioni del DES Applicazioni del DESApplicazioni del DES L'algoritmo DES può essere usato come standard sia per la L'algoritmo DES può essere usato come standard sia per la cifratura che per l'autenticazione dei dati.cifratura che per l'autenticazione dei dati.

Cifratura DatiCifratura Dati:: è semplice vedere come il DES può essere è semplice vedere come il DES può essere usato per cifrare un testo in chiaro di 64 bit, tuttavia la usato per cifrare un testo in chiaro di 64 bit, tuttavia la lunghezza dei testi è raramente limitata a 64 bit. Per testi più lunghezza dei testi è raramente limitata a 64 bit. Per testi più lunghi possono essere utilizzate le modalità di operative viste lunghi possono essere utilizzate le modalità di operative viste in precedenza. Ognuna di tali modalità ha vantaggi e in precedenza. Ognuna di tali modalità ha vantaggi e svantaggi. svantaggi.

Per esempio l'ECB è eccellente per la cifratura delle chiavi; CFB Per esempio l'ECB è eccellente per la cifratura delle chiavi; CFB è usato tipicamente per cifrare caratteri individuali; OFB è è usato tipicamente per cifrare caratteri individuali; OFB è tipicamente usato per cifrare comunicazioni via satellite (in cui tipicamente usato per cifrare comunicazioni via satellite (in cui è necessario ridurre al minimo la possibilità di errori alla è necessario ridurre al minimo la possibilità di errori alla stazione ricevente); ed infine entrambi CBC e CFB possono stazione ricevente); ed infine entrambi CBC e CFB possono essere usati per l'autenticazione di dati. essere usati per l'autenticazione di dati.

Tuttavia per essi non esistono delle analisi formali che Tuttavia per essi non esistono delle analisi formali che dimostrino qual'è il più sicuro, a meno che non si faccia uso di dimostrino qual'è il più sicuro, a meno che non si faccia uso di ipotesi molto restrittive.ipotesi molto restrittive.

4545

Applicazioni del DESApplicazioni del DES Applicazioni del DESApplicazioni del DES Autenticazione DatiAutenticazione Dati: Originariamente il DES fu introdotto per : Originariamente il DES fu introdotto per permettere la cifratura e la decifratura di dati usati sul permettere la cifratura e la decifratura di dati usati sul computer. Tuttavia la sua applicazione si è estesa anche alla computer. Tuttavia la sua applicazione si è estesa anche alla autenticazione dei dati. autenticazione dei dati.

Tale necessità è nata dalla difficoltà di riconoscere se in un Tale necessità è nata dalla difficoltà di riconoscere se in un messaggio c'erano state delle modifiche o meno, durante la fase messaggio c'erano state delle modifiche o meno, durante la fase di trasmissione. Più in particolare, nel caso in cui i dati erano di trasmissione. Più in particolare, nel caso in cui i dati erano cifrati con una delle due modalità CFB o CBC, allora queste cifrati con una delle due modalità CFB o CBC, allora queste possono essere usate per produrre un Codice di Autenticazione possono essere usate per produrre un Codice di Autenticazione del Messaggio (MAC). del Messaggio (MAC).

Il MAC viene posto alla fine del messaggio in chiaro, ed è usato Il MAC viene posto alla fine del messaggio in chiaro, ed è usato per convincere chi riceve il messaggio che esso non è stato per convincere chi riceve il messaggio che esso non è stato alterato da nessuno. Così il MAC garantisce l'integrità (o alterato da nessuno. Così il MAC garantisce l'integrità (o autenticità) del messaggio (ma non la sua segretezza).autenticità) del messaggio (ma non la sua segretezza).

4646

yy11,y,y22,…,…yynn

Applicazioni del DES: MACApplicazioni del DES: MAC Applicazioni del DES: MACApplicazioni del DES: MAC La modalità di operazione CBC viene usata per produrre un MAC La modalità di operazione CBC viene usata per produrre un MAC (Message Authentication Code) nel seguente modo: (Message Authentication Code) nel seguente modo:

BobBobAliceAlice

CarmenCarmen

xx11,x,x22,…,…xxnn


MAC=MAC= yynn

xx11,x,x22,…,…xxnn,y,ynn



yy

nn

Si noti che un nemico che vuole attaccare il sistema Si noti che un nemico che vuole attaccare il sistema non può produrre un MAC valido poiché non non può produrre un MAC valido poiché non conosce la chiave di cifratura. Quindi se Carmen conosce la chiave di cifratura. Quindi se Carmen intercetta il messaggio xintercetta il messaggio x11,x,x22... x... xnn,y,ynn e cambia uno o e cambia uno o più bit di tale messaggio, è altamente improbabile più bit di tale messaggio, è altamente improbabile che riesca a cambiare anche il MAC evitando che che riesca a cambiare anche il MAC evitando che Bob si accorga delle modifiche.Bob si accorga delle modifiche.

4747

BobBob


Applicazioni del DESApplicazioni del DES Applicazioni del DESApplicazioni del DES

Cifratura ed Autenticazione dei DatiCifratura ed Autenticazione dei Dati: è spesso desiderabile : è spesso desiderabile combinare autenticità e segretezza. Questo potrebbe essere combinare autenticità e segretezza. Questo potrebbe essere fatto usando due chiavi: fatto usando due chiavi:


CarmenCarmen



MAC=MAC= yynn



yy

nnxxxxxxxxxxxxxxxxxxxx

xxxxxxxxxxxxxxxxxxxx

AliceAlice

4848

Applicazioni del DESApplicazioni del DES Applicazioni del DESApplicazioni del DES Trasferimento Elettronico di Fondi (EFT) (ANSI X9.9)Trasferimento Elettronico di Fondi (EFT) (ANSI X9.9):: probabilmente l'uso più significativo del DES è quello probabilmente l'uso più significativo del DES è quello riguardante la protezione dei messaggi di trasferimento, riguardante la protezione dei messaggi di trasferimento, relativi a vendite al dettaglio ed all'ingrosso. I dati protetti relativi a vendite al dettaglio ed all'ingrosso. I dati protetti tramite DES sono relativi a trasferimenti di fondi che variano tramite DES sono relativi a trasferimenti di fondi che variano da $50 a svariati milioni di dollari. da $50 a svariati milioni di dollari.

In particolare il governo degli Stati Uniti è responsabile di In particolare il governo degli Stati Uniti è responsabile di trasferimenti di miliardi di dollari al giorno. Per far sì che questi trasferimenti di miliardi di dollari al giorno. Per far sì che questi trasferimenti siano sicuri, il Dipartimento del Tesoro Americano trasferimenti siano sicuri, il Dipartimento del Tesoro Americano ha dato inizio alla politica precedentemente citata ha dato inizio alla politica precedentemente citata sull'autenticazione dei messaggi EFT. sull'autenticazione dei messaggi EFT.

Anche la Banca federale coopera con il Tesoro per la buona Anche la Banca federale coopera con il Tesoro per la buona riuscita di queste operazioni. Uno dei sistemi che si sta riuscita di queste operazioni. Uno dei sistemi che si sta considerando consiste di strumenti manuali contenenti chiavi considerando consiste di strumenti manuali contenenti chiavi DES usati nella cifratura di messaggi finanziari. Questi DES usati nella cifratura di messaggi finanziari. Questi strumenti forniscono la chiave per l'autenticazione delle firme strumenti forniscono la chiave per l'autenticazione delle firme di documenti cartacei. di documenti cartacei.

4949

Applicazioni del DESApplicazioni del DES Applicazioni del DESApplicazioni del DES Immagazzinamento Dati e Sistemi di Posta (ANSI X9.19)Immagazzinamento Dati e Sistemi di Posta (ANSI X9.19):: il DES viene utilizzato per la cifratura di password per l'accesso il DES viene utilizzato per la cifratura di password per l'accesso a sistemi computerizzati. L'algoritmo confronta la cifratura a sistemi computerizzati. L'algoritmo confronta la cifratura della stringa data in input come password con quella della stringa data in input come password con quella conservata in memoria, ed attiva o nega l'accesso al sistema a conservata in memoria, ed attiva o nega l'accesso al sistema a seconda che il match fra le due stringhe abbia o meno esito seconda che il match fra le due stringhe abbia o meno esito positivo. positivo.

Il DES può anche essere utilizzato per la protezione di file in Il DES può anche essere utilizzato per la protezione di file in memoria. Una pubblicazione speciale dell'NBS descrive un memoria. Una pubblicazione speciale dell'NBS descrive un sistema di notarizzazione di chiavi che può essere integrato in sistema di notarizzazione di chiavi che può essere integrato in un sistema computerizzato, per proteggere file da modifiche e un sistema computerizzato, per proteggere file da modifiche e divulgazioni e per provvedere a una firma digitale usando il divulgazioni e per provvedere a una firma digitale usando il DES. DES.

Il sistema di notarizzazione che incorpora il DES può anche Il sistema di notarizzazione che incorpora il DES può anche essere usato congiunto ad un sistema di posta per provvedere essere usato congiunto ad un sistema di posta per provvedere della posta sicura. Un software di cifratura/decifratura che della posta sicura. Un software di cifratura/decifratura che contiene le informazioni necessarie a decifrare ed autenticare contiene le informazioni necessarie a decifrare ed autenticare un file di posta è automaticamente aggiunto al file che è un file di posta è automaticamente aggiunto al file che è trasmesso al ricevente. Quest'ultimo in seguito potrà decifrare trasmesso al ricevente. Quest'ultimo in seguito potrà decifrare ed autenticare il file facilmente sfruttando quest'informazione. ed autenticare il file facilmente sfruttando quest'informazione.

5050

DES: CrittoanalisiDES: Crittoanalisi DES: CrittoanalisiDES: Crittoanalisi ““La sicurezza di un sistema crittografico deve dipendere solo La sicurezza di un sistema crittografico deve dipendere solo

dalla segretezza della chiavedalla segretezza della chiave e non dalla segretezza del e non dalla segretezza del metodometodo” ”

Auguste Kerckhoffs von Nieuwenhof (1835-1903)Auguste Kerckhoffs von Nieuwenhof (1835-1903)

Per poter comprendere meglio l’aspetto della sicurezza di un Per poter comprendere meglio l’aspetto della sicurezza di un sistema crittografico dobbiamo metterci nei panni della «spia» sistema crittografico dobbiamo metterci nei panni della «spia» che intercetta il messaggio. La spia cercherà di decrittare che intercetta il messaggio. La spia cercherà di decrittare (questo è il termine esatto) il messaggio e quindi dovrà (questo è il termine esatto) il messaggio e quindi dovrà conoscere l’algoritmo utilizzato per la cifratura e la chiave. Un conoscere l’algoritmo utilizzato per la cifratura e la chiave. Un principio fondamentale della crittologia moderna afferma che:principio fondamentale della crittologia moderna afferma che:La sicurezza di un crittosistema non deve dipendere dalla La sicurezza di un crittosistema non deve dipendere dalla segretezza dell’algoritmo usato, ma solo dalla segretezza della segretezza dell’algoritmo usato, ma solo dalla segretezza della chiavechiave

Questo principio, apparso per la prima volta nel 1883 nel libro Questo principio, apparso per la prima volta nel 1883 nel libro «La criptographie militarie» di Kerckhoffs un filologo olandese, «La criptographie militarie» di Kerckhoffs un filologo olandese, è fondamentale per una corretta visione del problema è fondamentale per una corretta visione del problema sicurezza.sicurezza.

5151

Un primo semplice attacco è quello di forza bruta: provare tutte Un primo semplice attacco è quello di forza bruta: provare tutte le possibili chiavi. La lunghezza della chiave determina il numero le possibili chiavi. La lunghezza della chiave determina il numero di chiavi possibili e quindi la fattibilità dell'attacco.di chiavi possibili e quindi la fattibilità dell'attacco.

Lo spazio delle chiavi del DES è formato da 2Lo spazio delle chiavi del DES è formato da 25656 elementi, che in elementi, che in notazione decimale equivale a circa 72 milioni di miliardi di notazione decimale equivale a circa 72 milioni di miliardi di combinazioni distinte, per cui un ipotetico computer a 500 MHz combinazioni distinte, per cui un ipotetico computer a 500 MHz che può sondare una chiave ad ogni ciclo di clock impiegherebbe che può sondare una chiave ad ogni ciclo di clock impiegherebbe 144 milioni di secondi ad esaminarle tutte. 144 milioni di secondi ad esaminarle tutte.

Tuttavia, a dispetto delle 2Tuttavia, a dispetto delle 25656 chiavi possibili, in media bastano chiavi possibili, in media bastano 225555 tentativi. Questo consegue dalla proprietà di tentativi. Questo consegue dalla proprietà di complementazione del DES:complementazione del DES:C = DESC = DESKK(M) allora ¬C = (M) allora ¬C =

DESDES¬K¬K(¬M). (¬M).

DES: CrittoanalisiDES: Crittoanalisi DES: CrittoanalisiDES: Crittoanalisi

Ma anche supponendo che sia Ma anche supponendo che sia sufficiente esaminare solo la metà sufficiente esaminare solo la metà delle chiavi occorrerebbero delle chiavi occorrerebbero comunque ben 834 giorni, pari a 2 comunque ben 834 giorni, pari a 2 anni e 3 mesi di lavoro anni e 3 mesi di lavoro continuativo! continuativo!

5252

A livello teorico, furono avanzate varie proposte per un A livello teorico, furono avanzate varie proposte per un computer in grado di violare il DES. computer in grado di violare il DES.

Nel 1977, Diffie ed Hellman proposero una macchina del costo Nel 1977, Diffie ed Hellman proposero una macchina del costo stimato di 20 milioni di dollari in grado di trovare una chiave stimato di 20 milioni di dollari in grado di trovare una chiave DES in un solo giorno. Nel 1993 Wiener propose una macchina DES in un solo giorno. Nel 1993 Wiener propose una macchina per la ricerca della chiave, del costo di un milione di dollari, in per la ricerca della chiave, del costo di un milione di dollari, in grado di trovarla in 7 ore. grado di trovarla in 7 ore.

La vulnerabilità del DES fu dimostrata praticamente nel 1998 La vulnerabilità del DES fu dimostrata praticamente nel 1998 quando fu costruita appositamente la DES-Crack dall‘quando fu costruita appositamente la DES-Crack dall‘ Electronic Frontier Foundation (EFF), un gruppo per la difesa dei diritti un gruppo per la difesa dei diritti civili nel ciberspazio, del costo di circa 250.0000 dollari. Fu civili nel ciberspazio, del costo di circa 250.0000 dollari. Fu costruita per dimostrare che il DES era violabile in pratica, non costruita per dimostrare che il DES era violabile in pratica, non solo in teoria. Questa macchina violò con la sola forza bruta solo in teoria. Questa macchina violò con la sola forza bruta una chiave in pochi giorni di ricerca.una chiave in pochi giorni di ricerca.

Inoltre è stata pubblicata laInoltre è stata pubblicata la documentazione completa del del progetto DES-Crack in modo da consentire ad altri gruppi di progetto DES-Crack in modo da consentire ad altri gruppi di scienziati di riprodurre e di migliorare la macchina realizzata scienziati di riprodurre e di migliorare la macchina realizzata dall'EFF. dall'EFF.


http://www.eff.org/pub/Privacy/Crypto_misc/DESCracker/

5353

Il miglior attacco al DES conosciuto è senza dubbio quello Il miglior attacco al DES conosciuto è senza dubbio quello definito dal metodo della Crittoanalisi differenziale, introdotto definito dal metodo della Crittoanalisi differenziale, introdotto da E. Biham e A. Shamir. da E. Biham e A. Shamir.

Esso defininisce un attacco che si presta con successo alla Esso defininisce un attacco che si presta con successo alla rottura del DES nell'ipotesi che il numero di iterazioni sia ridotto 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 (il DES a 8 iterazioni può essere rotto in un paio di minuti su un personal computer).personal computer).

Tuttavia quando il numero di iterazioni sale a 16 o più, attacchi Tuttavia quando il numero di iterazioni sale a 16 o più, attacchi di questo tipo hanno complessità uguale a quella che si avrebbe di questo tipo hanno complessità uguale a quella che si avrebbe con un algoritmo di ricerca nello spazio delle chiavi. con un algoritmo di ricerca nello spazio delle chiavi.

Per violare tutti i 16 Per violare tutti i 16 cicli, la crittanalisi cicli, la crittanalisi differenziale richiede differenziale richiede 247 testi in chiaro 247 testi in chiaro scelti (chosen scelti (chosen plaintext)plaintext)


ESERCIZIO

5454

Weak-KeyWeak-KeyWeak-KeyWeak-KeyTra le 256 chiavi possibili ve ne sono di particolari per le quali le Tra le 256 chiavi possibili ve ne sono di particolari per le quali le sottochiavi prodotte dalla fase di schedulazione sono tutte sottochiavi prodotte dalla fase di schedulazione sono tutte uguali. Queste chiavi sono dette weak key (chiavi deboli). Quindi uguali. Queste chiavi sono dette weak key (chiavi deboli). Quindi se cifriamo un testo cifrato con una weak key otteniamo il testo se cifriamo un testo cifrato con una weak key otteniamo il testo in chiaro. in chiaro.

Questo succede perché, visto che le sottochiavi prodotte dal Questo succede perché, visto che le sottochiavi prodotte dal processo di schedulazione sono le stesse sia nel caso della processo di schedulazione sono le stesse sia nel caso della cifratura che della decifratura, queste due operazioni coincidono.cifratura che della decifratura, queste due operazioni coincidono.

Le weak key sono quelle Le weak key sono quelle composte da tutti 0, tutti composte da tutti 0, tutti 1, oppure da una metà da 1, oppure da una metà da tutti 0 e l'altra da tutti 1. tutti 0 e l'altra da tutti 1. Tali chiavi diminuiscono la Tali chiavi diminuiscono la sicurezza del sistema in sicurezza del sistema in quanto basta trovare una quanto basta trovare una sola sottochiave ksola sottochiave kii per per scoprire tutte le altre.scoprire tutte le altre.

Le quattro weak key in rappresentazione esadecimale

5555

Critiche al DESCritiche al DES Critiche al DESCritiche al DES L'algoritmo di per sé è molto semplice e tutte le funzioni sono L'algoritmo di per sé è molto semplice e tutte le funzioni sono funzioni lineari (gli xor e le permutazioni) tranne le S-box, esse funzioni lineari (gli xor e le permutazioni) tranne le S-box, esse infatti rispondono a dei criteri che non sono completamente noti, infatti rispondono a dei criteri che non sono completamente noti, ed è per questo che si teme che l'NSA abbia nascosto in esse ed è per questo che si teme che l'NSA abbia nascosto in esse delle trapdoor in modo tale da poter decifrare facilmente delle trapdoor in modo tale da poter decifrare facilmente messaggi intercettati.messaggi intercettati.

Perché solo 16 iterazioni e non 24 o 32? Fu dimostrato che con Perché solo 16 iterazioni e non 24 o 32? Fu dimostrato che con 8 iterazioni, il testo cifrato era una funzione random di ogni bit 8 iterazioni, il testo cifrato era una funzione random di ogni bit del testo in chiaro e di ogni bit della chiave. Perché allora non del testo in chiaro e di ogni bit della chiave. Perché allora non fermare DES dopo 8 iterazioni? E. Biham e A. Shamir hanno fermare DES dopo 8 iterazioni? E. Biham e A. Shamir hanno dimostrato nel 1990 che con meno di 16 iterazioni si può rompere dimostrato nel 1990 che con meno di 16 iterazioni si può rompere il DES con un attacco più efficiente di un attacco brute force che il DES con un attacco più efficiente di un attacco brute force che esamina 2esamina 25656 chiavi. Con 16 iterazioni i due attacchi sono chiavi. Con 16 iterazioni i due attacchi sono equivalenti.equivalenti.

La maggiore critica al DES è che la dimensione delle chiavi, 2La maggiore critica al DES è che la dimensione delle chiavi, 25656, , è troppo piccolo per essere realmente sicuro. Ci si chiede quindi: è troppo piccolo per essere realmente sicuro. Ci si chiede quindi: perché DES usa una chiave a 56 bit mentre LUCIFER ne usava perché DES usa una chiave a 56 bit mentre LUCIFER ne usava 128? Un attacco brute force su una chiave a 128 bit non è 128? Un attacco brute force su una chiave a 128 bit non è nemmeno immaginabile mentre sono noti attacchi brute force nemmeno immaginabile mentre sono noti attacchi brute force con chiave a 64 bit.con chiave a 64 bit.

5656

EserciziEsercizi EserciziEsercizi Siano xSiano x11…x…xnn n blocchi di 64 bit e siano y n blocchi di 64 bit e siano y11…y…ynn gli n blocchi gli n blocchi ottenuti cifrando xottenuti cifrando x11…x…xnn con DES. Si supponga che a causa di un con DES. Si supponga che a causa di un errore di trasmissione, il blocco yerrore di trasmissione, il blocco y11 non sia trasmesso non sia trasmesso correttamente (alcuni 0 diventano 1 o viceversa). Analizzare correttamente (alcuni 0 diventano 1 o viceversa). Analizzare quanti e quali blocchi sono decifrati non correttamente se la quanti e quali blocchi sono decifrati non correttamente se la modalità operativa utilizzata per la cifratura è: modalità operativa utilizzata per la cifratura è:

a. ECBa. ECB

b. CBCb. CBC

c. CFBc. CFB

d. OFBd. OFB

Soluzione: per le modalità ECB e OFB, soltanto il primo blocco Soluzione: per le modalità ECB e OFB, soltanto il primo blocco sarà decifrato non correttamente; per le modalità CBC e CFB, i sarà decifrato non correttamente; per le modalità CBC e CFB, i primi due blocchi saranno decifrati non correttamente.primi due blocchi saranno decifrati non correttamente.

5757

cifratura

decifratura

DESDESDESDES

x1 x2 xn

y1 y2 yn

… … DESDESDESDES DESDESDESDES

DESDES-1-1DESDES-1-1

y1 y2 yn

… … DESDES-1-1DESDES-1-1DESDES-1-1DESDES-1-1

x1 x2 xn

Non Non correttocorretto


corretticorretti

Electronic codebook chaining Electronic codebook chaining (ECB)(ECB)

Electronic codebook chaining Electronic codebook chaining (ECB)(ECB)

5858

decifratura

yy11yy11

DESDESDESDES DESDESDESDES DESDESDESDES

yy22yy22

x1x1 x2

x2 xnxn

kk kk kk

IVIV ……

……

xx11xx11

DESDES-1-1DESDES-1-1DESDES-1-1DESDES-1-1

DESDES-1-1DESDES-1-1

xx22xx22

y1y1 y2

y2 ynyn

kk kk kk

IVIV

……

……

cifratura

xxnnxxnn

yynnyynn


Non correttiNon corretticorretticorretti

Cipher Block ChainingCipher Block Chaining CBCCBC Cipher Block ChainingCipher Block Chaining CBCCBC

5959

Cipher feedbackCipher feedback CFBCFB Cipher feedbackCipher feedback CFBCFB

yy

11

yynnDESDESDESDESIVIV DESDESDESDES

xx

11

xxnn

DESDESDESDES……

k k k

xx22cifratura

decifratura

xxnnDESDESDESDESIVIV DESDESDESDES

yynn

DESDESDESDES……

k k k

yy22

xx

11

yy

11

yy22

xx22


Non correttiNon corretticorretticorretti

6060

64-bit Output feedback64-bit Output feedback 64-bit Output feedback64-bit Output feedback

Cifratura Decifratura

DESDESDESDESk

64 bit del 64 bit del testo testo

in chiaroin chiaro

shift di 64 bit

DESDESDESDES

64 bit del 64 bit del testo testo

in chiaroin chiaro

k

shift di 64 bit

64 bit testo cifrato64 bit testo cifrato 64 bit testo cifrato64 bit testo cifrato

yy11 non corretto non correttoxx1 1 xx22 … x … xnn

correttcorrettii

non non correttocorretto

6161

Si consideri il crittosistema DES. E’ possibile utilizzare la Si consideri il crittosistema DES. E’ possibile utilizzare la proprietà del complemento per migliorare il running time della proprietà del complemento per migliorare il running time della ricerca esaustiva in un attacco known plaintext? E in un attacco ricerca esaustiva in un attacco known plaintext? E in un attacco chosen plaintext? Giustificare le risposte.chosen plaintext? Giustificare le risposte.

Soluzione: Soluzione: Non è noto come sia possibile utilizzare la proprietà Non è noto come sia possibile utilizzare la proprietà del complemento per migliorare il running time della ricerca del complemento per migliorare il running time della ricerca esaustiva in un attacco known plaintext.esaustiva in un attacco known plaintext.

Invece, tale proprietà consente il miglioramento del running Invece, tale proprietà consente il miglioramento del running time della ricerca esaustiva di un fattore ½ nel caso di un time della ricerca esaustiva di un fattore ½ nel caso di un attacco chosen plaintext. Infatti, supponiamo che k sia la chiave attacco chosen plaintext. Infatti, supponiamo che k sia la chiave segreta da trovare. In un attacco chosen plaintext, si segreta da trovare. In un attacco chosen plaintext, si considerino due coppie (m, c1) e (m’, c2), dove m’ indica il considerino due coppie (m, c1) e (m’, c2), dove m’ indica il complemento di m. Per la proprietà del complemento, per ogni complemento di m. Per la proprietà del complemento, per ogni possibile chiave h si ha c=DES(h,m) e c’=DES(h’,m’), dove c’ e possibile chiave h si ha c=DES(h,m) e c’=DES(h’,m’), dove c’ e h’ indicano il complemento di c e h, rispettivamente. Pertanto, h’ indicano il complemento di c e h, rispettivamente. Pertanto, se cse cc1, allora kc1, allora kh e se c’h e se c’c2 allora kc2 allora kh’. Quindi le due chiavi h’. Quindi le due chiavi candidate h e h’ possono essere eliminate mediante una singola candidate h e h’ possono essere eliminate mediante una singola cifratura DES durante la ricerca esaustiva. cifratura DES durante la ricerca esaustiva.

EserciziEsercizi EserciziEsercizi

6262

EserciziEserciziEserciziEsercizi

Quindi dalla stringa RQuindi dalla stringa R1616LL1616 possiamo risalire alla stringa R possiamo risalire alla stringa R1515LL1515 utilizzando la sottochiave kutilizzando la sottochiave k1616. Questo è vero per tutte le . Questo è vero per tutte le iterazioni, quindi utilizzando lo stesso algoritmo di cifratura iterazioni, quindi utilizzando lo stesso algoritmo di cifratura DES, con le sottochiavi schedulate in ordine inverso, possiamo DES, con le sottochiavi schedulate in ordine inverso, possiamo effettuare la decifratura DES.effettuare la decifratura DES.

Dimostrare che la decifratura DES può essere effettuata Dimostrare che la decifratura DES può essere effettuata applicando l’algoritmo di cifratura DES al testo cifrato con le applicando l’algoritmo di cifratura DES al testo cifrato con le chiavi schedulate in ordine inverso.chiavi schedulate in ordine inverso.

Soluzione: Nella fase di cifratura DES dopo avere effettuato lo Soluzione: Nella fase di cifratura DES dopo avere effettuato lo scambio di 32 bit successivo alla sedicesima iterazione, scambio di 32 bit successivo alla sedicesima iterazione, abbiamo la stringa di 64 bit Rabbiamo la stringa di 64 bit R1616LL1616, dove, dove

LL1616= R= R1515

RR1616=L=L1515 f(R f(R1515,k,k1616))

da cui otteniamo:da cui otteniamo:

RR1515= L= L1616

LL1515=R=R1616 f(R f(R1515,k,k1616) = R) = R1616 f(L f(L1616,k,k1616).).

DES: applicazioni ed evoluzioni Calzetta Emilia Cervone Vincenzo Reti di calcolatori Prof. Alfredo...

Documents

Transcript of DES: applicazioni ed evoluzioni Calzetta Emilia Cervone Vincenzo Reti di calcolatori Prof. Alfredo...