POLITECNICO DI BARI I FACOLTÀ DI INGEGNERIA CORSO DI LAUREA MAGISTRALE IN INGEGNERIA INFORMATICA

RELAZIONE PER L’ESAME DI

SICUREZZA INFORMATICA

Algoritmi di cifratura

DES (a blocchi) e DES OFB (a stream)

Prof. Giuseppe Mastronardi

Gianluca Grimaldi

Carlo Pinto

Anno accademico 2011-2012

Pag. 2

Introduzione alla crittografia

La crittografia è una scienza antichissima: se gli usi in passato sono stati soprattutto di tipo

militare, il suo campo d’azione è oggi ben più vasto. Pensiamo ad esempio all’esigenza di

proteggere la privacy delle cartelle cliniche, che ormai vengono spesso memorizzate nelle banche

di dati degli ospedali; oppure si pensi ai problemi di trasferimento elettronico del denaro legati

all’impiego sempre più diffuso delle carte di credito.

La crittografia è l’arte (poiché richiede immaginazione, tecnica e ingegnosità) delle scritture

segrete. Etimologicamente deriva dalle parole greche kriptos (nascosto) e graphein (scrivere).

Le scritture segrete possono raggrupparsi in tre classi fondamentali:

le scritture invisibili (per esempio, usando il succo di limone si scrive su un foglio color

paglierino: il messaggio verrà rivelato scaldando il foglio con la fiamma di una candela);

le scritture dissimulate (all’interno di un messaggio tradizionale, si conviene di attribuire

un particolare significato ad alcune parole);

le scritture cifrate (messaggi aventi le caratteristiche proprie della segretezza in quanto si

presentano incomprensibili).

La terza classe di scritture è quella che presenta maggiori garanzie di sicurezza dall’attacco dei

decriptatori non autorizzati, ed è la classe che verrà trattata in seguito.

In un sistema crittografico il testo in chiaro, o il messaggio, viene trasformato secondo certe regole

nel testo in cifra, o crittogramma: tale operazione si chiama cifratura.

Il crittogramma viene poi spedito a destinazione tramite un canale di trasmissione, per esempio

via radio. In realtà è poco saggio fidarsi del canale di trasmissione: lungo il percorso potrebbe

esserci appostata una spia (sniffing) la quale può intercettare il crittogramma e tentare di

decifrarlo.

Anche il destinatario legittimo decifra il crittogramma ed ottiene il testo in chiaro: se il sistema di

cifra (il cosiddetto cifrario) è ben congegnato l’operazione di decifrazione o decifratura deve

risultare piuttosto semplice al destinatario legittimo, ma di complessità proibitiva alla spia.

Ciò è possibile poiché il destinatario conosce certe informazioni che devono rimanere del tutto

inaccessibili alla spia e che perciò non devono essere affidate al canale poco sicuro usato per

Pag. 3

trasmettere i crittogrammi. Tali informazioni costituiscono la chiave del cifrario. Si può quindi

facilmente intuire che il problema della distribuzione delle chiavi, è di importanza cruciale per il

funzionamento di un sistema crittografico.

Un'altra cosa da tenere ben presente è che non si possono studiare i metodi per costruire un

cifrario senza considerare parallelamente anche gli eventuali metodi per demolirlo; in termini più

tecnici non ci si può occupare di crittografia (la parte "costruttiva") senza occuparsi di

crittoanalisi (la parte "distruttiva"): insieme crittografia e crittoanalisi costituiscono una disciplina

unitaria che si chiama crittologia.

Il DES è un algoritmo di crittografia a chiave segreta perciò iniziamo con lo spiegare in cosa

consiste questa tipologia di algoritmi.

Metodo a Chiave Segreta

Questo metodo, anche detto a chiave simmetrica, utilizza un'unica chiave, per mezzo della quale,

chiunque è in grado di decriptare il messaggio.

Un esempio applicativo di questo metodo sono i Fogli Usa e Getta:

La chiave segreta è di tipo numerico e ha un valore per ciascuna lettera, che non rappresenta altro

che la traslazione che la lettera del messaggio da criptare dovrà subire, nell'alfabeto, per ottenere

una nuova lettera che costituirà il messaggio criptato.

Esempio:

S A L V E → messaggio da criptare

9 0 2 1 0 → chiavi segrete

B A N W E → messaggio criptato

Da notare che ovviamente, cambiando la chiave segreta, cambia il messaggio criptato; di

conseguenza se il destinatario non conosce la chiave segreta, è impossibile che possa decifrare il

messaggio.

Pag. 4

Confusione e Diffusione

Lo scopo principale di un algoritmo di cifratura è garantire la segretezza di un messaggio da

scambiare fra due o più interlocutori. Per fare ciò è necessario utilizzare algoritmi che applichino in

maniera sistematica i principi di confusione e diffusione.

Queste due proprietà, identificate da Shannon nel 1949 nel suo lavoro “La teoria della

comunicazione nei sistemi crittografici”, sono alla base dei principali algoritmi di cifratura.

Il principio di confusione consiste nello scambiare sistematicamente i simboli del messaggio in

chiaro con altri simboli, a formare un messaggio criptato apparentemente senza senso. In realtà

alla base della cifratura c’è una chiave segreta, per mezzo della quale chiunque ne sia in suo

possesso e conosca l’algoritmo di cifratura è in grado di risalire al messaggio originale. Per questo

motivo la confusione non è una protezione sufficiente da possibili attacchi di malintenzionati.

Ecco quindi la necessità di introdurre il principio di diffusione che consiste nel rendere l’algoritmo

di cifratura più complesso in maniera tale da rendere il testo cifrato quanto più indipendente, per

ordine e struttura dei simboli, dal testo in chiaro.

Principio di Kerchoff

Secondo il principio di Kerchoff, “La sicurezza del sistema si deve basare sull'idea che il ‘nemico’

conosca ogni aspetto relativo al sistema; l'unica variabile aleatoria è una sequenza di numeri

casuali che potrà essere utilizzata come chiave”. Di conseguenza l’effettiva sicurezza di un

algoritmo di cifratura a chiave simmetrica dipende dalla complessità delle azioni di sostituzione e

traslazione dei simboli, in dipendenza proprio dalla chiave segreta.

Pag. 5

Algoritmi simmetrici e asimmetrici

Gli algoritmi crittografici possono essere classificati sotto due principali categorie riguardanti il tipo

della chiave utilizzata: simmetrici (con chiave segreta) ed asimmetrici (con chiave pubblica).

Negli algoritmi a chiave simmetrica (o segreta) il mittente usa una chiave per crittare il messaggio

e il ricevente usa la medesima chiave per decrittare quanto ricevuto. Le due persone che vogliono

comunicare devono quindi trovare un modo sicuro per scambiarsi la chiave.

Negli algoritmi a chiave asimmetrica (o a doppia chiave) ci sono due tipi di chiavi: una privata in

mano solo al mittente dei messaggi ed una pubblica che viene messa a disposizione di tutti. La

chiave pubblica della persona A permette di decrittare i messaggi crittati con la sua chiave privata,

ma non permette di crearli, evidenziandone, quindi, l’autenticità. D’altra parte, se A vuole

Pag. 6

mandare un messaggio a B, deve crittare il messaggio usando la chiave pubblica di B. Solo B è in

grado di decrittare il messaggio mandato da A utilizzando la sua chiave privata, questo perché la

chiave privata e pubblica di ogni persona sono collegate matematicamente.

Algoritmo di cifratura a blocchi: DES

Il DES (Data Encryption Standard) è un cifrario simmetrico che utilizza un metodo di codifica a

blocchi, per cui è necessario dividere il messaggio in pezzi da 64 bit.

Esso utilizza una chiave di 64 bit, di cui 56 sono effettivi ed 8 sono di parità.

Questa chiave permette di ottenere da ciascuna parola in chiaro di 64 bit, una corrispondente

parola cifrata da 64 bit.

In particolare, per ciascuna parola Xi viene utilizzata una chiave ki ricavata dalla chiave principale k.

Fasi dell’algoritmo

L'algoritmo è composto da 3 fasi:

1. a partire dalla prima stringa X, detta plaintext, viene costruita una stringa X0 secondo

l'espressione:

X0 = PI( X ) = L0R0 dove PI rappresenta la permutazione iniziale, L0 sono i primi 32 bit, mentre

R0 sono gli ultimi 32 bit di X0 ;

2. Inoltre LiRi viene calcolata, per 1 < i < 16 con le espressioni:

Li = Ri-1

Ri = Li-1 XOR ƒ( Ri-1, ki-1 )

dove le varie k0, … , k15 sono le sottochiavi di 48 bit calcolate a partire dalla chiave k di 56

bit mediante la matrice di permutazione T, ed f è una particolare funzione;

3. Infine, viene applicata la permutazione finale PF alla stringa L16R16 ottenendo il testo cifrato

c, cioé c = L16R16 .

Pag. 7

LA CODIFICA: la funzione f

La funzione f prende come argomenti in ingresso la stringa Ri-1 di 32 bit e la stringa ki-1 di 48

bit. L'uscita invece sarà di 32 bit, poiché la funzione andrà in XOR a Li-1 per comporre la Ri;

PI PF

T

P

Pag. 8

Quindi, si procede ad espandere la stringa Ri-1 da 32 a 48 bit (cioè la stessa lunghezza di

ki-1 ), utilizzando un'espansione EP fissata, che consiste nel permutare i 32 bit di Ri-1, avendo

cura di riscriverne la metà per due volte;

Ora si può calcolare EP( Ri-1 ) XOR ki-1 ;

La stringa generata dall'ultimo calcolo sarà di 48 bit, perciò è necessario comprimerla.

Questo avviene tramite una funzione di compressione che fa utilizzo dei cosiddetti S – Box,

in fulcro dell'algoritmo del DES;

La stringa prodotta, di 32 bit, verrà permutata attraverso la matrice di permutazione P

fissata, a produrre la ƒ( Ri-1, ki-1 ) .

EP P

Pag. 9

Gli S – BOX

L'operazione EP( Ri-1 ) XOR ki-1 produce una stringa di uscita di 48 bit.

Questa stringa viene suddivisa in 8 sottostringhe da 6 bit ciascuna: B = B1B2B3B4B5B6

Di conseguenza si utilizzano degli Si, per 1 < i < 8, che non sono altro che delle tabelle da 4x16 e i

cui elementi sono numeri interi compresi tra 0 e 15.

Quindi, ciascuna S – Box prenderà in ingresso 6 bit e ne produrrà 4, ecco come:

1. il primo e ultimo bit della stringa da 6 bit, B1 e B6 saranno in codice binario la relativa riga

dell'S1 ( infatti le righe sono 4, cioè 22 );

2. i restanti 4 bit servono ad indirizzare la colonna della tabella;

3. a quel punto verrà individuato un elemento, che sarà compreso tra 0 e 15 e che in binario è

composto da 4 bit, che sarà la nostra stringa compressa da 6 a 4 bit.

Iterando questo processo per ciascuna delle 8 parole da 6 bit, si otterranno 8 parole da 4 bit, cioè

una parola da 32 bit. Quest'ultima attraverso la matrice di permutazione P andrà a formare la Ri.

Pag. 10

Calcolo delle sottochiavi

La chiave principale k è costituita da 56 bit, cui vengono aggiunti 8 bit di parità, rispettivamente

nelle posizioni [8, 16, 24, 32, 40, 48, 56, 64], ovvero nelle posizioni multiple di 8.

Questi bit sono di parità dispari, ovvero ogni byte assumerà un valore dispari di “1”.

L'utilità dei bit di parità, però, si ferma al controllo degli errori; il calcolo delle sottochiavi si servirà

solo dei 56 bit di informazione vera e propria.

Quindi, si utilizza sui 56 bit la matrice di permutazione T, ad ottenere T(k) = G0D0, di cui i primi 28

bit sono la stringa G0, mentre gli ultimi 28 sono di D0.

La permutazione T si effettua solo su G0D0; successivamente, a partire da G1D1,i vari GiDi saranno

calcolati dalla permutazione ( o shift sinistro, in questo caso ) SH.

Pag. 11

Quando ad ogni permutazione o shift sinistro si applicherà la permutazione CT, si otterranno le

varie subkey.

La permutazione CT, serve, però, solo ad ottenere le subkey; mentre i vari GiDi si calcolano SOLO

permutando attraverso lo shift sinistro SH.

N.B. SH è uno shift a sinistra ciclico di 1 o 2 posti, in dipendenza dal numero di iterate effettuate:

1 posto se l'iterata è la numero 1,2,9 o 16; 2 negli altri casi.

Infine ciascuna ki , di 56 bit, viene sottoposta ad un'ulteriore permutazione che permette di

ottenere Ki' = CT( Gi,Di ) di 48 bit.

Per ciò che concerne la decodifica, basta utilizzare lo stesso algoritmo, avendo cura di applicare le

sottochiavi in ordine inverso [k16, k15, … , k1]. L'ingresso sarà il messaggio c crittografato, mentre

l'output il messaggio iniziale in chiaro.

CT

Pag. 12

DES OFB (Output Feedback)

In questa variante, l'algoritmo procede così:

viene cifrato con il DES classico un vettore iniziale VI, con la chiave k, a formare Ci;

questo testo Ci viene messo in XOR al primo plaintext, a formare la prima porzione di

messaggio cifrato CFRi;

viene codificato Ci con il DES classico e la chiave k;

il testo formato Ci+1 viene messo in XOR al secondo plaintext, a formare la seconda

porzione di messaggio cifrato CFRi+1;

e così via.

Pag. 13

Per quanto riguarda la decriptazione, a differenza del DES classico, l’OFB DES ha una struttura che

gli consente di riapplicare le stesse operazioni della fase di cifratura, senza cambiare l’ordine di

applicazione delle subkey.

NB. È importante sottolineare che questo algoritmo di cifratura non si basa solo sulla chiave

segreta, bensì dipende fortemente dal vettore iniziale Vi generato con metodo random.

Per questa ragione l’algoritmo è più sicuro in riferimento alla segretezza del messaggio da cifrare;

ma costringe il destinatario, oltre a conoscere la chiave segreta, a farsi inviare dal mittente la

sequenza di bit del vettore iniziale. Quindi, potenzialmente, la sicurezza di questa variante del DES

dipende da quanto è sicuro il canale di comunicazione attraverso il quale mittente e destinatario si

scambiano chiave segreta e vettore iniziale.

Pag. 14

IMPLEMENTAZIONE

Le librerie

ASCII_convertion.h

Innanzitutto, il tool è stato pensato per poter dare la possibilità all’utente di criptare un file di

testo inserendo una semplice chiave composta da caratteri ASCII. Di conseguenza si è reso

necessario implementare una libreria di funzioni e procedure, in grado di gestire la conversione da

caratteri ASCII a caratteri esadecimali (e viceversa), quest’ultimi molto più pratici da gestire ai fini

della criptazione.

Binary_convertion.h

Oltre all’utilizzo dei caratteri esadecimali, il tool prevede l’utilizzo della rappresentazione binaria

soprattutto perché nel DES sono presenti operazioni come permutazioni, traslazioni e XOR bit a

bit.

Pag. 15

Perm_matrices.h

Alla base dell’algoritmo del DES ci sono varie operazioni di permutazione e shift.

Per questo motivo è stata implementata una funzione procedura che, per ogni matrice di

permutazione, fornisse in output il blocco risultante.

DES_support.h

La libreria più importante del tool implementa le operazioni fondamentali dell’algoritmo del DES:

1. Una procedura per il calcolo delle 16 subkey, a partire dalla chiave segreta;

2. Una procedura che svolge le operazioni della funzione F, descritta in precedenza;

3. La procedura di criptazione che, preso il blocco del messaggio in chiaro e la chiave segreta,

fornisce il blocco cifrato;

4. La procedura di decriptazione che, preso il blocco cifrato e la chiave segreta, fornisce il

blocco decifrato.

Pag. 16

Conclusioni

La produzione del tool, in entrambe le sue varianti, è solo il prodotto finale di una serie di

operazioni preliminari che abbiamo dovuto svolgere. Innanzitutto, è stato necessario analizzare,

studiare e capire quali sono le logiche alla base degli algoritmi di cifratura, e perché un algoritmo si

dice robusto rispetto ad un altro. Ci siamo soffermati sullo studio del DES perché si tratta di un

algoritmo tra i più conosciuti e perciò esistono centinaia di tool che ne implementano le funzioni.

In realtà, avendo ben chiara nella mente l'idea di cosa dovesse svolgere un algoritmo di

criptazione, non abbiamo riscontrato in nessun programma, contemporaneamente, tutte le

caratteristiche desiderate, e cioè:

1. chiarezza del layout: l'utente deve poter capire in maniera intuitiva cosa deve fare per

criptare un file di testo;

2. semplicità di utilizzo in fase di cifratura: l'utente deve poter visualizzare il testo criptato e

poterlo copiare e incollare, senza dover andare ad aprire directory e subdirectory alla

ricerca del file criptato;

3. semplicità di utilizzo in fase di decrifratura: l'utente, in possesso della chiave, è in grado di

decriptare in maniera rapida e con pochi gesti del mouse qualsiasi file di testo criptato con

la medesima chiave.

Il concetto alla base dell'implementazione dell'algoritmo e conseguentemente del tool è stato

questo: “Oggigiorno qualsiasi email web application, qualsiasi meccanismo di accounting, qualsiasi

meccanismo di protezione di carte di credito, e persino la SIM del nostro cellulare è basato

sull'utilizzo di una password.”

Per questo motivo, la maggior parte degli utenti è costretta a tenere con sé decine di password

differenti (o per lo meno si spera siano scelte differenti), che obiettivamente sono difficili da

ricordare; quindi, un tool semplice da usare, al fine di criptare le nostre password con un'unica

chiave da ricordare, può rivelarsi estremamente comodo.

Infatti, basta inserire le PW in un file di testo, scegliere una chiave segreta più o meno mnemonica

(in alfabeto ASCII), e così abbiamo la possibilità di creare un file criptato da tenere sul nostro PC.

Quando non ricordiamo una PW è sufficiente aprire il file nel tool, inserire la chiave segreta, per

poter visualizzare immediatamente il contenuto decriptato.

Pag. 17

In conclusione, il nostro lavoro è stato estremamente formativo, in quanto oltre ad approcciarci al

lavoro in team, ci ha permesso di accumulare moltissime nuove conoscenze, che potremo

sfruttare, in futuro, anche in ambiente lavorativo.

Bibliografia

1. Appunti e dispense sulla Sicurezza Informatica del Prof. Giuseppe Mastronardi, Politecnico di

Bari.

2. J.O. Grabbe, “The DES Algorithm Illustrated”, Laissez Faire City Times, 1992.

3. www.qt-italia.org

4. http://qt.digia.com/product/developer-tools/

5. http://harbourlanguage.blogspot.it/2011/03/tutorial-qt.html

6.http://educate.intel.com/en/TheJourneyInside/InstructionalStrategies/IS_DigitalInformation/iwb_image7

.htm ASCII Table.