Sicurezza Informatica

P E R X Y

Ciphertext: IJIXCRNEDOPYUEHPCERR

Cosı̀, in questo esempio, la chiave è 42513. Per cifrare, si scrive la colonna etichettata 1 (in que-

sto caso colonna 4), poi la colonna etichettata con 2 (in questo caso colonna 2) e cosi via fino

a formare il ciphertext. Un cifrario a trasposizione pura è facilmente riconoscibile perché ha la

stesse frequenze di lettere del plaintext. Dobbiamo far notare che il nostro messaggio era più corto

rispetto allo schema di trasposizione colonnare che abbiamo scelto, pertanto in questi casi vengono

aggiunti dei caratteri random inutili al plaintext originale. Per il tipo di trasposizione colonnare

appena mostrato, la crittoanalisi è abbastanza semplice.

23

Il cifrario a trasposizione colonnare può essere reso molto più sicuro eseguendo più di una volta

la fase di trasposizione. Il risultato è una permutazione più complessa che non è facilmente

ricostrubile. Cosı̀, se il plaintext precedente viene crittografato utilizzando lo stesso algoritmo, ma

applicato due volte, mantenendo la stessa chiave, avremo:

Plaintext: uccidere John Ripper

Chiave: 4 2 5 1 3

Tras Col: U C C I D

E R E J O

H N R I P

P E R X Y

Tras Col: I J I X C

R N E D O

P Y U E H

P C E R R

Ciphertext: XDERJNYCCOHRIRPPIEUE

In questo modo, ciò che verrà fuori, sarà difficilmente ricostrubile poiché una cifratura doppia

mescola ancora di più le lettere del plaintext originale.

24

3.5 DES: Data Encryption Standard

In crittografia il Data Encryption Standard (DES) è un algoritmo di cifratura scelto come

standard dal FIPS per il governo degli Stati Uniti d’America nel 1976 ed in seguito diventato di

utilizzo internazionale. Si basa su un algoritmo a chiave simmetrica con chiave a 64 bit (ma solo

56 utili poiché 8 sono di controllo). Questo algoritmo all’inizio ha suscitato molte discussioni per

via della sua chiave di cifratura corta e per via di alcune scelte progettuali che erano segretate.

Si supponeva che dietro queste scelte vi fosse la National Security Agency (NSA) e l’inserimento

di una backdoor. Di conseguenza il DES è stato oggetto di un’intensa analisi di tipo accademico

che ha contribuito in modo notevole allo sviluppo delle conoscenze che sono alla base dei moderni

algoritmi di cifratura e delle moderne tecniche di crittoanalisi.

Attualmente DES è considerato insicuro per moltissime applicazioni. La sua insicurezza deriva

dalla chiave utilizzata per cifrare i messaggi, che è di soli 56 bit. Nel gennaio del 1999 distribu-

ted.net e Electronic Frontier Foundation collaborarono per rompere pubblicamente una chiave di

crittazione, e ci riuscirono in 22 ore e 15 minuti. Con le potenze di calcolo disponibili oggi, si

può forzare una chiave DES in poche ore esaminando tutte le possibili combinazioni. In alcuni

documenti parlando del DES si utilizza anche la sigla DEA (Data Encryption Algorithm), ossia il

nome originale dell’algoritmo cosı̀ come fu ideato da IBM.

3.5.1 Algoritmo di crittazione DES

Lo schema generale per l’algoritmo di crittazione DES è illustrato in Figura 8. Come per

qualsiasi schema di crittografia, ci sono due input per la funzione di codifica: il plaintext da

cifrare e la chiave. In questo caso, il plaintext deve essere di lunghezza pari a 64 bit la chiave di

lunghezza pari a 56 bit (poiché 8 sono di controllo).

Figura 8: Rappresentazione generale dell’algoritmo di crittazione DES

25

Il lato sinistro della Figura ci mostra come l’elaborazione del plaintext procede in tre fasi:

• Prima Fase

Innanzitutto, il plaintext di 64 bit passa attraverso una permutazione iniziale (indicata

con IP - Initial Permutation) che riorganizza i bit producendo l’input permutato.

• Seconda Fase

Successivamente, vi è una fase costituita da 16 applicazioni della stessa funzione, che coin-

volge entrambe le funzioni di permutazione e sostituzione. L’output al termine dei 16 cicli di

funzione, consiste di 64 bit che sono in funzione del plaintext iniziale e della chiave. La metà

sinistra e la metà destra dell’output vengono poi scambiate producendo cosı̀ un pre-output.

• Terza Fase

Infine, il pre-output viene fatto passare attraverso una permutazione che è l’inversa della per-

mutazione iniziale IP, producendo il ciphertext di 64 bit. Tale permutazione viene chiamata

−1

permutazione finale (indicata con FP o IP - Final Permutation).

La parte destra della Figura invece, mostra il modo in cui viene utilizzata la chiave da 56 bit.

Inizialmente, la chiave viene fatto passare attraverso una funzione di permutazione. Successiva-

mente, per ciascuno dei 16 cicli di funzione, viene prodtta una sottochiave (K ) generata dalla

i

combinazione di uno spostamento circolare verso sinistra e da una permutazione. Facciamo

notare che la permutazione iniziale è diversa dalla permutazione che viene poi applicata durante i

16 cicli di funzione. Quest’ultima è la stessa per ogni ciclo, ma le sottochiavi prodotte sono diverse

a causa degli spostamenti ripetuti dei bit della chiave.

Permutazione Iniziale e Finale - IP e FP

La permutazione iniziale e la permutazione finale sono definiti da tabelle, come mostrato nel-

la Figura 9. Le tabelle devono essere interpretate nel modo seguente. L’input per una tabella

consiste di 64 bit numerati da 1 a 64. Le 64 voci nella tabella di permutazione contengono una

permutazione dei numeri da 1 a 64. Ogni voce nella tabella di permutazione indica la posizione

numerata dei bit dell’input nell’output, che consiste anche questo di 64 bit.

Figura 9: Tabelle di Permutazione Iniziale e Finale (IP e FP)

26

Dettagli di un singolo ciclo

La figura 10, mostra la struttura interna di uno dei 16 cicli della stessa funzione. Partiamo

dall’analizzare il lato sinistro della Figura. La metà destra e la metà sinistra, di ogni valore

intermedio a 64 bit, sono trattate come entità separate a 32 bit, etichettate rispettivamente con

L (quella di sinistra) ed R (quella di destra). L’intero processo che avviene in ciascun ciclo, può

essere riassunto con le seguenti formule: L = R

i i−1

⊕

R = L F (R , K )

i i−1 i−1 i

Figura 10: Uno dei 16 cicli di funzione dell’algoritmo DES

La chiave del ciclo K , è di 48 bit, mentre l’input R è di 32 bit. Inizialmente R viene esteso a

i

48 bit utilizzando una tabella (Figura 11a) che definisce una funzione di permutazione con

espansione, la quale comporta la duplicazione di 16 bit di R. Successivamente, i risultanti 48

bit sono sottoposti ad una funzione di OR Esclusivo (XOR) con K . Questo risultato, sempre di

i

48 bit, passa attraverso una funzione di sostituzione che produce un output di 32 bit, i quali

vengono elaborati da una funzione di permutazione descritta da un’altra tabella (Figura 11b).

Figura 11: Tabelle di permutazione con espansione (E) e permutazione (P)

27

Il ruolo delle S-Box nella funzione F , è illustrato nella Figura 12. La sostituzione consiste di un

insieme di otto S-box, ognuno dei quali accetta 6 bit come input e produce 4 bit come output.

Queste trasformazioni sono definite nella tabella in Figura 13, che va interpretata come segue:

il primo e l’ultimo bit dei 6 dati in input al box S , formano un numero binario di 2 bit. Tale

i

numero binario verrà utilizzato per selezionare una delle quattro sostituzioni definite dalle quattro

righe nella tabella per S (Figura 13). Invece, la parte centrale, formata dai quattro bit rimanenti,

i

è utilizzata per selezionare una delle sedici colonne. Il valore nella cella, selezionata dalla riga e

dalla colonna, è poi convertito in una rappresentazione binaria di 4 bit per produrre l’output.

Ad esempio, in S1, dato come input il valore 011001, avremo che:

• la riga sarà data dai bit 01 (011001)

In decimale avremo che 01 = 1, quindi indica la RIGA 1;

• la colonna sarà data dai bit 1100 (011001)

In decimale avremo che 1100 = 12, quindi indica la COLONNA 12;

Trasformando in decimale questi due valori, otterremo rispettivamente la riga 1 e la colonna

12. Ricordiamo che le colonne vanno da 0 ad m mentre le righe da 0 ad n. Il valore decimale

contenuto nella cella identificata da questi due paramentri è 9, quindi l’output sarà 1001.

Figura 12: Panoramica del funzionamento di S-Box

28

Figura 13: S-Box

3.5.2 Algoritmo di decrittazione DES

La decrittazione in DES avviene attraverso lo stesso algoritmo utilizzato per la crittazione, ad

eccezione che l’applicazione delle sottochiavi (chiavi di ciclo) è invertita.

29

3.5.3 Problematiche del DES

Come abbiamo detto nella nostra trattazione iniziale, DES si basa su un algoritmo che vuole in

input blocchi di 64 bit e una chiave simmetrica di 56 bit. Questo algoritmo, viste le caratteristiche,

ha suscitato molte discussioni per via della sua chiave di cifratura corta e per via di alcune scelte

progettuali che erano segretate. Furono molti gli esperti che investirono denaro per la costruzione

di macchine potenti in grado di provare che l’algoritmo DES poteva essere violato. Come abbia-

mo detto, nel gennaio del 1999 due società importanti collaborarono per rompere pubblicamente

una chiave di crittazione, e ci riuscirono in 22 ore e 15 minuti. Ad oggi, con una moderna bot-

net, una chiave di crittazione DES può essere rotta in poche ore. Possiamo quindi affermare che

la lunghezza delle chiavi DES di soli 56 bit è piuttosto inadeguata, infatti banche e altre insti-

tuzioni, da vari anni stanno aggiornando i loro sistemi di pagamento con chiavi sempre più lunghe.

Date le vulnerabilità di DES per un attacco a forza bruta, c’è stato un considerevole interesse

a trovare un’alternativa. Per preservare l’investimento che era stato fatto fino a quel momento in

apparecchiature specifiche in grado di utilizzare l’algortimo in questione, si è pensato di ricorrere

alla crittografia multipla con DES.

3.5.4 Doppio DES

L’esempio più semplice di crittografia multipla con DES è il Doppio DES. Nacque l’idea di pro-

gettare un cifrario a blocchi alternativo al DES singolo: si è pensato, infatti, di cifrare due volte

il messaggio in chiaro con due chiavi diverse (una per ogni passo di cifratura). Il cifrario a bloc-

chi che si ottiene apportando tali modifiche al DES originario, viene quindi definito Doppio DES.

Cifratura Doppio DES

Il Doppio DES prevede due fasi di cifratura del plaintext, utilizzando due chiavi diverse.

Dato il plaintext P e 2 chiavi K e K a 56 bit:

1 2

• prima cifriamo P con la chiave K , ottendo un pre-output X;

1

• poi cifriamo X con la chiave K , ottenendo il ciphertext C;

2

Quindi, il testo cifrato viene generato cosı̀ come segue:

C = E(K , E(K , P ))

2 1

Figura 14: Cifratura con Doppio DES

30

Decifratura Doppio DES

La decifratura è analoga alla cifratura, ma richiede che le chiavi siano applicate nell’ordine inver