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