#Nicolini Massimiliano

Crittografia Rijndael – AES 128/256

Rijndael è un’evoluzione del primo algoritmo sviluppato da Daemen e Rijmen, Square. Square era stato sviluppato per SHARK.

A differenza del DES, Rijndael è una rete a sostituzione e permutazione, non una rete di Feistel, che implementa comunque il principio crittografico di Shannon di “confusione e diffusione”. AES è veloce sia se sviluppato in software sia se sviluppato in hardware,  è relativamente semplice da implementare, richiede poca memoria ed offre un buon livello di protezione/sicurezza, motivi che complessivamente l’hanno preferito agli altri algoritmi proposti.

Il nuovo standard di cifratura sta sostituendo i precedenti standard e la sua diffusione continua ad aumentare. Formalmente, AES non è equivalente al Rijndael (sebbene nella pratica siano intercambiabili) dato che il Rijndael gestisce differenti dimensioni di blocchi e di chiavi. Nell’AES il blocco è invece di dimensione fissa (128 bit) e la chiave può essere di 128, 192 o 256 bit mentre il Rijndael specifica solo che il blocco e la chiave devono essere un multiplo di 32 bit con 128 bit come minimo e 256 bit come massimo.

AES opera utilizzando matrici di 4×4 byte chiamate stati (states). Quando l’algoritmo ha blocchi di 128 bit in input, la matrice State ha 4 righe e 4 colonne; se il numero di blocchi in input diventa di 32 bit più lungo, viene aggiunta una colonna allo State, e così via fino a 256 bit. In pratica, si divide il numero di bit del blocco in input per 32 e il quoziente specifica il numero di colonne.

C’è un passaggio iniziale:

1. AddRoundKey – Ogni byte della tabella viene combinato con la chiave di sessione, la chiave di sessione viene calcolata dal gestore delle chiavi.

Successivamente per cifrare sono previsti diversi round o cicli di processamento: ogni round (fase) dell’AES (eccetto l’ultimo) consiste dei seguenti quattro passaggi:

1. SubBytes – Sostituzione non lineare di tutti i byte che vengono rimpiazzati secondo una specifica tabella.
2. ShiftRows – Spostamento dei byte di un certo numero di posizioni dipendente dalla riga di appartenenza.
3. MixColumns – Combinazione dei byte con un’operazione lineare, i byte vengono trattati una colonna per volta.
4. AddRoundKey – Ogni byte della tabella viene combinato con la chiave di sessione, la chiave di sessione viene calcolata dal gestore delle chiavi.

Il numero di round o cicli di processamento/elaborazione crittografica dei quattro passaggi precedenti è 10 con l’ultimo round che salta il passaggio MixColumns. A seguito la descrizione di ogni singolo passaggio.

La fase di decifratura non è identica a quella di cifratura dal momento che gli step sono eseguiti in ordine inverso. Tuttavia, si può definire un cifrario inverso equivalente ai passi dell’algoritmo usato per la cifratura, usando la funzione inversa a ogni step e un differente key schedule. Funziona siccome il risultato non cambia quando si scambiano la fase di SubBytes con quella di ShiftRows, e quella di MixColumns con una fase aggiuntiva di AddRoundKey.

SubBytes

Nel passaggio SubBytes ogni byte della matrice viene modificato tramite la S-box a 8 bit. Questa operazione provvede a fornire la non linearità all’algoritmo. La S-box utilizzata è derivata da una funzione inversa nel campo finito GF(2⁸), conosciuta per avere delle ottime proprietà di non linearità. Per evitare un potenziale attacco basato sulle proprietà algebriche la S-box è costruita combinando la funzione inversa con una trasformazione affine invertibile. La S-box è stata scelta con cura per non possedere né punti fissi né punti fissi opposti.

Nel passaggio SubBytes, ogni byte della matrice è sostituito con i dati contenuti nella trasformazione S; b_ij = S(a_ij).

ShiftRows

Il passaggio ShiftRows provvede a spostare le righe della matrice di un parametro, e dipende dal numero di riga. Nell’AES la prima riga resta invariata, la seconda viene spostata di un posto verso sinistra, la terza di due posti e la quarta di tre. In questo modo l’ultima colonna dei dati in ingresso andrà a formare la diagonale della matrice in uscita. (Rijndael utilizza un disegno leggermente diverso per via delle matrici di lunghezza non fissa.)

Tutte le operazioni sono effettuate utilizzando l’indice della colonna “modulo” il numero di colonne.

MixColumns

Il passaggio MixColumns prende i quattro byte di ogni colonna e li combina utilizzando una trasformazione lineare invertibile. Utilizzati in congiunzione, ShiftRows e MixColumns provvedono a far rispettare il criterio di confusione e diffusione nell’algoritmo (teoria di Shannon). Ogni colonna è trattata come un polinomio

Nel passaggio MixColumns ogni colonna di byte viene moltiplicata per un polinomio fisso c(x).

AddRoundKey

Il passaggio AddRoundKey combina con uno XOR la chiave di sessione con la matrice ottenuta dai passaggi precedenti (State). Una chiave di sessione viene ricavata dalla chiave primaria ad ogni round (con dei passaggi più o meno semplici, ad esempio uno shift di posizione dei bit) grazie al Key Scheduler.

Nel passaggio AddRoundKeys ogni byte della matrice viene combinato con la sua sottochiave tramite un’operazione di XOR.

Sicurezza della chiave AES

La National Security Agency (NSA) segnalava che tutti i finalisti del processo di standardizzazione erano dotati di una sicurezza sufficiente per diventare l’AES, ma che fu scelto il Rijndael per via della sua flessibilità nel trattare chiavi di lunghezza diversa, per la sua semplice implementazione in hardware e in software e per le sue basse richieste di memoria che ne consentono un’implementazione anche in dispositivi con scarse risorse come le smart card.

L’AES può essere utilizzato per proteggere le informazioni secretate. Per il livello SECRET è sufficiente una chiave a 128 bit mentre per il livello Top secret si consigliano chiavi a 192 o 256 bit. Questo significa che per la prima volta il pubblico ha accesso ad una tecnologia crittografica che NSA ritiene adeguata per proteggere i documenti TOP SECRET. Si è discusso sulla necessità di utilizzare chiavi lunghe (192 o 256 bit) per i documenti TOP SECRET. Alcuni ritengono che questo indichi che l’NSA ha individuato un potenziale attacco che potrebbe forzare una chiave relativamente corta (128 bit), mentre la maggior parte degli esperti ritiene che le raccomandazioni della NSA siano basate principalmente sul volersi garantire un elevato margine di sicurezza per i prossimi decenni contro un potenziale attacco esaustivo.

La maggior parte degli algoritmi crittografici viene forzata riducendo il numero di round. L’AES effettua 10 round per la chiave a 128 bit, 12 round per la chiave a 192 bit e 14 round per la chiave a 256 bit. Al 2006, i migliori attacchi sono riusciti a forzare l’AES con 7 round e chiave di 128 bit, 8 round e chiave di 192 bit e 9 round e chiave di 256 bit. 

Alcuni crittografi hanno fatto notare che la differenza tra i round effettuati dall’AES e quelli massimi prima che l’algoritmo non sia più forzabile è ridotta (specialmente con chiavi corte). Questi temono che miglioramenti nelle tecniche di analisi possano permettere di forzare l’algoritmo senza verificare tutte le chiavi. Attualmente una ricerca esaustiva è impraticabile: la chiave a 128 bit produce 3,4×1038 combinazioni diverse. Uno dei migliori attacchi a forza bruta è stato svolto dal progetto distributed.net su una chiave a 64 bit per l’algoritmo RC5; l’attacco ha impiegato quasi 5 anni, utilizzando il tempo libero di migliaia di CPU di volontari. Anche considerando che la potenza dei computer aumenta nel tempo, servirà ancora molto tempo prima che una chiave da 128 bit sia attaccabile con il metodo forza bruta. Molte banche mettono a disposizione per l’home banking dei propri clienti chiavi a 256 bit con il risultato che si ottiene una cifratura ben 2^128 volte più sicura di quella a 128 bit sebbene quest’ultima possa considerarsi altamente sicura ed invalicabile dai moderni PC.

Un altro dubbio riguardante l’AES deriva dalla sua struttura matematica. A differenza della maggior parte degli algoritmi a blocchi, per l’AES esiste un’approfondita descrizione matematica . Sebbene non sia mai stata utilizzata per condurre un attacco su misura, questo non esclude che in futuro questa descrizione non venga utilizzata per condurre un attacco basato sulle sue proprietà matematiche.

Nel 2002 l’attacco teorico chiamato attacco XSL annunciato da Nicolas Courtois e Josef Pieprzyk ha mostrato un potenziale punto debole dell’AES (e di altri cifrari). Sebbene l’attacco sia matematicamente corretto, è impraticabile nella realtà per via dell’enorme tempo macchina richiesto per metterlo in pratica. Miglioramenti nell’attacco hanno ridotto il tempo macchina richiesto e quindi, in un futuro, questo attacco potrebbe diventare attuabile. Ultimamente, alcuni esperti hanno fatto delle osservazioni agli autori dell’attacco. Sembra che abbiano commesso degli errori teorici e che, in realtà, le loro stime siano ottimistiche. Allo stato attuale, la reale pericolosità dell’attacco XSL è un punto interrogativo. Comunque, attualmente, l’AES è considerato un algoritmo veloce, sicuro e gli attacchi, fino ad ora presentati, si sono rivelati degli interessanti studi teorici ma di scarsa utilità nella pratica.

In data 1º luglio 2009 è stato pubblicato un attacco correlato alla chiave migliore del metodo forza bruta su tutti i round di AES-256 e AES-192. L’attacco in questione risulta comunque, per stessa ammissione degli autori (come chiarito nelle conclusioni dello studio), essere ancora solo teoricamente realizzabile e non dovrebbe influire in alcun modo sulla sicurezza delle odierne applicazioni che fanno uso di questo cifrario. Secondo Bruce Schneier comunque questa scoperta potrebbe influire negativamente sulla scelta di AES come blocco costitutivo del nuovo algoritmo di hash in fase di definizione SHA-3.

Cifrario MARS

In crittografia il MARS è un cifrario a blocchi che è stato presentato da IBM come candidato al processo di standardizzazione dell’Advanced Encryption Standard. Il MARS è stato selezionato come finalista dell’AES nell’agosto del 1999 dopo che alla conferenza AES2 del marzo 1999 era stato votato come quinto ed ultimo algoritmo finalista. Il gruppo di sviluppatori che ha progettato il MARS include Don Coppersmith, che ha partecipato anche alla creazione del Data Encryption Standard (DES) circa 20 anni prima.

Secondo quanto dichiarato ufficialmente da IBM, il MARS è, insieme al Serpent, uno dei pochi algoritmi finalisti dell’AES specificatamente sviluppati per resistere anche a tecniche di crittanalisi future. Curioso è il fatto che anche il gruppo di sviluppo del Twofish fece una dichiarazione simile per il suo cifrario.

Il MARS opera su blocchi dati di 128 bit e può usare chiavi di lunghezza variabile da 128 a 448 bit (con incrementi di 32 bit). A differenza della maggioranza dei cifrari a blocchi il MARS ha una struttura eterogenea denominata rete di Feistel non bilanciata: ci sono infatti 8 passaggi “in avanti” ed 8 passaggi “indietro”. Questi 16 passaggi sono preceduti e seguiti da altri 8 passaggi definiti di “mescolamento” ed indipendenti dalla chiave di cifratura.

Le sotto-chiavi con lunghe sequenze di 1 e 0 possono portare ad attacchi efficienti contro il MARS. I due bit meno significativi delle sotto-chiavi usate nelle operazioni di moltiplicazione nei passaggi interni sono sempre impostate ad 1. Per questo ci sono sempre due input che non sono modificati attraverso il processo moltiplicativo, ed altri due che hanno output fissi (relativamente alla sotto-chiave).

Eli Biham, Bruce Schneier, Bart Preneel, Lars Knudsen ed altri esperti hanno proposto diversi attacchi su versioni del MARS con un numero ridotto di passaggi. Il più efficiente di questi è quello di Kelsey, Kohno e Schneier condotto ad una versione del MARS con 11 passaggi e che sfrutta l’attacco a boomerang: l’attacco permette di violare il cifrario utilizzando 265 testi in chiaro scelti.

Secure Hash Algorithm

Con il termine SHA (acronimo dell’inglese Secure Hash Algorithm) si indica una famiglia di cinque diverse funzioni crittografiche di hash sviluppate a partire dal 1993 dalla National Security Agency (NSA) e pubblicato dal NIST come standard federale dal governo degli USA (FIPS PUB 180-4).

Come ogni algoritmo di hash, l’SHA produce un message digest, o “impronta del messaggio”, di lunghezza fissa partendo da un messaggio di lunghezza variabile. La sicurezza di un algoritmo di hash risiede nel fatto che la funzione non sia invertibile (non sia cioè possibile risalire al messaggio originale conoscendo solo questo dato) e che non deve essere mai possibile creare intenzionalmente due messaggi diversi con lo stesso digest. Gli algoritmi della famiglia sono denominati SHA-1, SHA-224, SHA-256, SHA-384 e SHA-512: le ultime 4 varianti sono spesso indicate genericamente come SHA-2, per distinguerle dal primo. Il primo produce un digest del messaggio di soli 160 bit, mentre gli altri producono digest di lunghezza in bit pari al numero indicato nella loro sigla (SHA-256 produce un digest di 256 bit). L’SHA-1 è il più diffuso algoritmo della famiglia SHA ed è utilizzato in numerose applicazioni e protocolli nonostante sia ormai insicuro e verrà presto sostituito dagli altri, più moderni ed efficienti.

La sicurezza di SHA-1 è stata appunto compromessa dai crittoanalisti. Sebbene non siano ancora noti attacchi alle varianti SHA-2, esse hanno un algoritmo simile a quello di SHA-1 per cui sono in atto sforzi per sviluppare algoritmi di hashing alternativi e migliorati. Un concorso aperto per la realizzazione di una nuova funzione SHA-3 venne annunciato nel Federal Register il 2 novembre 2007 dal NIST e attraverso una competizione pubblica, simile a quella adottata per il processo di sviluppo dell’AES,ha portato in data 2 ottobre 2012 ad annunciare come vincitore l’algoritmo Keccak. Opera di un team di analisti italiani e belgi, il Keccak sembra dunque destinato a venire gradualmente incluso e adottato nelle soluzioni di sicurezza informatica più variegate.

Il 23 febbraio 2017 un team di Google ha annunciato la prima tecnica pratica per generare una collisione hash.

La funzione di hash o funzione hash produce una sequenza di bit, detta digest, (o una stringa) strettamente correlata con i dati in ingresso. La parola viene dal termine inglese hash, dal verbo to hash, ovvero sminuzzare, pasticciare, che designa originariamente una polpettina fatta di avanzi di carne e verdure; per estensione, indica un composto eterogeneo cui viene data una forma incerta: “To make a hash of something” vuol dire, infatti, creare confusione, o fare una cosa piuttosto male.

Nel linguaggio matematico e informatico, l’hash è una funzione non invertibile che mappa una stringa di lunghezza arbitraria in una stringa di lunghezza predefinita. Esistono numerosi algoritmi che realizzano funzioni hash con particolari proprietà che dipendono dall’applicazione.

Nelle applicazioni crittografiche si chiede, per esempio, che la funzione hash abbia le seguenti proprietà:

resistenza alla preimmagine: sia computazionalmente intrattabile la ricerca di una stringa in input che dia un hash uguale a un dato hash;

resistenza alla seconda preimmagine: sia computazionalmente intrattabile la ricerca di una stringa in input che dia un hash uguale a quello di una data stringa;

resistenza alle collisioni: sia computazionalmente intrattabile la ricerca di una coppia di stringhe in input che diano lo stesso hash.

Nelle applicazioni di basi di dati la funzione hash è usata per realizzare una particolare struttura dati chiamata hash table. In questa applicazione non occorrono proprietà crittografiche e generalmente l’unica proprietà richiesta è che non ci siano hash più probabili di altri.

L’algoritmo di hash elabora qualunque mole di bit (in informatica si dice che elabora dati “grezzi”). Si tratta di una famiglia di algoritmi che soddisfa questi requisiti:

L’algoritmo restituisce una stringa di numeri e lettere a partire da un qualsiasi flusso di bit di qualsiasi dimensione (può essere un file, ma anche una stringa). L’output è detto digest.

L’algoritmo non è invertibile, ossia non è possibile ricostruire il documento originale a partire dalla stringa che viene restituita in output ovvero è una funzione unidirezionale, quest’ultima caratteristica non è indispensabile se si usano gli hash per controllare gli errori nei trasferimenti dei dati, dove le eventuali funzioni di criptaggio possono venir svolte in altre aree del protocollo.

Non esiste una corrispondenza biunivoca tra l’hash e il testo. Dato che i testi possibili, con dimensione finita maggiore dell’hash, sono più degli hash possibili, per il principio dei cassetti ad almeno un hash corrisponderanno più testi possibili. Quando due testi producono lo stesso hash, si parla di collisione, e la qualità di una funzione di hash è misurata direttamente in base alla difficoltà nell’individuare due testi che generino una collisione. Per sconsigliare l’utilizzo di algoritmi di hashing in passato considerati sicuri è stato infatti sufficiente che un singolo gruppo di ricercatori riuscisse a generare una collisione. Questo è quello che è avvenuto ad esempio per gli algoritmi SNEFRU, MD2, MD4, MD5 e SHA-1.

Un hash crittograficamente sicuro non dovrebbe permettere di risalire, in un tempo confrontabile con l’utilizzo dell’hash stesso, ad un testo che possa generarlo.

La lunghezza dei valori di hash varia a seconda degli algoritmi utilizzati. Il valore più comunemente adottato è di 128 bit, che offre una buona affidabilità in uno spazio relativamente ridotto. Tuttavia va registrata la possibilità d’uso di hash di dimensione maggiore (SHA, ad esempio, può anche fornire stringhe di 224, 256, 384 e 512 bit) e minore (che però è fortemente sconsigliato).

Le funzioni hash svolgono un ruolo essenziale nella crittografia: sono utili per verificare l’integrità di un messaggio, poiché l’esecuzione dell’algoritmo su un testo anche minimamente modificato fornisce un message digest completamente differente rispetto a quello calcolato sul testo originale, rivelando la tentata modifica.

Le funzioni di hash possono essere anche utilizzate per la creazione di firme digitali, in quanto permettono la rapida creazione della firma anche per file di grosse dimensioni, senza richiedere calcoli lunghi e complessi: è infatti computazionalmente più conveniente eseguire con rapidità un hashing del testo da firmare, e poi autenticare solo quello, evitando così l’esecuzione dei complessi algoritmi di crittografia asimmetrica su moli di dati molto grandi.

La firma digitale è definita come il digest di un documento che poi viene crittografato con chiave privata (e non con quella pubblica, come avviene di solito). La firma digitale è l’unico caso in cui l’uso delle chiavi è invertito: la chiave pubblica serve a decrittare la firma e trovare poi il digest iniziale attraverso l’hash, mentre quella privata serve a crittografare una stringa anziché ad aprirla.

Un ulteriore uso delle funzioni di hash si ha nella derivazione di chiavi da password o passphrase: a partire da un valore arbitrario in ingresso (una stringa o un array di larghe dimensioni) si deriva in modo crittograficamente sicuro (ovvero non è possibile abbreviare il calcolo con una qualche scorciatoia) una chiave di dimensioni adatte alla cifratura. È appena il caso di dire, tuttavia, che a meno di prendere debite contromisure (come l’uso di un salt crittografico), l’utilità di questa procedura è esclusivamente pratica: infatti la sicurezza della chiave derivata è equivalente a quella della stringa di ingresso ai fini di un attacco a dizionario. Di contro, è certamente più comodo per un essere umano ricordare una stringa piuttosto che una lunga sequenza numerica.

Nel contesto delle funzioni hash, ci si riferisce a diversi concetti di sicurezza:

Sicurezza debole: dato un messaggio M, è computazionalmente “difficile” trovare un secondo messaggio M’ tale che h(M)=h(M’).

Sicurezza forte: è computazionalmente “difficile” trovare una coppia di messaggi M,M’ tali che h(M)=h(M’).

Questi due concetti di sicurezza vengono distinti anche per via degli effetti che essi possono produrre nel caso in cui ne siano privi: per quanto riguarda ad esempio la possibilità di effettuare una firma digitale, un algoritmo che non garantisca la sicurezza forte, ma quella debole, sarebbe comunque utile dal momento che il messaggio M non può essere “controllato” e bisognerebbe quindi trovare un secondo messaggio M’ con uguale funzione di hash, il che sarebbe appunto computazionalmente difficile.

È possibile utilizzare le funzioni di hash per creare una hash table, che è una struttura dati molto efficiente per le operazioni di ricerca. La hash table contiene dati associati ad una chiave di ricerca e viene spesso utilizzato nei database per indicizzare gli elementi che saranno oggetto di ricerca. Questa tecnica (detta di hashing) permette di realizzare funzioni di ricerca che riescono ad individuare l’elemento desiderato in un tempo costante, indipendente (almeno in teoria) dal numero di elementi presenti nell’indice.

L’uso delle funzioni hash per trovare errori nelle trasmissioni è molto comune. La funzione hash viene calcolata dal mittente a partire dai dati e il suo valore è inviato insieme ai dati. Il ricevente calcola di nuovo la funzione hash, e se i valori hash non corrispondono, significa che è avvenuto un errore durante la trasmissione. Questo metodo consente un controllo dell’integrità dei dati migliore della più tradizionale checksum.

Gli algoritmi di hash, in particolare SHA1 e MD5, sono largamente utilizzati nell’ambito dell’informatica forense per validare e in qualche modo “firmare” digitalmente i dati acquisiti, tipicamente le copie forensi. La recente legislazione impone infatti una catena di custodia che permetta di preservare i reperti informatici da eventuali modifiche successive all’acquisizione: tramite i codici hash è possibile in ogni momento verificare che quanto repertato sia rimasto immutato nel tempo. Se i codici hash corrispondono, entrambe le parti in un procedimento giudiziario hanno la ragionevole certezza di lavorare sulla stessa versione dei reperti, garantendo quindi una uniformità di analisi e in genere di risultati. I risultati dei codici hash vengono ormai calcolati di default dalla maggioranza dei software per acquisizione forense e allegati alle copie forensi salvate.