Trivium (cifrario)
"Trivium" has been specified as an International Standard under ISO/IEC 29192-3 (Information technology - Security techniques - Lightweight cryptography - Part 3: Stream ciphers).
| Trivium | |
|---|---|
.png) | |
| Generale | |
| Progettisti | Christophe De Cannière, Bart Preneel |
| Prima pubblicazione | 2003 |
| Dettagli | |
| Dimensione chiave | 80 bit |
| Dim. vettore di inizializazione | 80 bit |
| Struttura | Registro a scorrimento (Shift register) |
| Migliore crittanalisi | |
| Nonostante la sua semplicità, il Trivium resta ancora inviolato | |
Il Trivium è un cifrario a flusso con chiave simmetrica sviluppato da Christophe De Cannière e Bart Preneel nel 2003, che lo hanno presentato come candidato per il progetto eSTREAM, dove è stato selezionato come elemento del portafoglio ufficiale per il Profilo 2, che comprende gli algoritmi ottimizzati per le implementazioni hardware. Il Trivium non è brevettato.
L'algoritmo genera fino a 264 bit di output da una chiave ed un vettore di inizializzazione (VI) lunghi entrambi 80 bit. È il più semplice degli algoritmi presentati all'eSTREAM ma, nonostante ciò, mostra una notevole resistenza alla crittanalisi.
Descrizione modifica
Il Trivium si basa su uno stato interno a 288 bit costituito da 3 registri a scorrimento (Shift register) di differenti lunghezze. La generazione del keystream è un processo iterativo che estrae i valori di 15 specifici bit dello stato e li utilizza sia per aggiornare 3 bit dello stato sia per calcolare 1 bit del keystream. Questo bit è utilizzato per cifrare o decifrare il messaggio mediante una semplice operazione di XOR. I bit dello stato interno sono poi ruotati ed il processo è ripetuto finché non sono stati generati tanti bit quanti ne servono per elaborare i dati in input.
Per inizializzare l'algoritmo vengono eseguite due operazioni, il Key setup (o inizializzazione della chiave) e l'IV setup (o inizializzazione del VI), durante le quali gli 80 bit della chiave e gli 80 bit del VI vengono scritti nei primi 160 bit dello stato interno: gli altri bit dello stato (dal 161º al 288º) vengono impostati su valori predefiniti. A questo punto vengono eseguite 4 rotazioni complete, corrispondenti a 1152 aggiornamenti (4×288 bit), simili a quelle utilizzate per generare il keystream ma con la differenza che nessun bit viene fornito in output.
Da notare che nessun nuovo bit dello stato viene usato prima di aver subìto almeno 64 rotazioni all'interno dei registri del Trivium: questa è la chiave delle prestazioni in software e della flessibilità in hardware dell'algoritmo.
Pseudo-codice modifica
Quelle che seguono sono le rappresentazioni in pseudo-codice delle funzioni interne del Trivium. Questa è la simbologia adottata:
- s1..s287 rappresentano i singoli bit dello stato interno;
- t1, t2 e t3 sono variabili di stato;
- zi rappresenta il bit di output del keystream;
- il simbolo "+" rappresenta un'operazione di XOR;
- il simbolo "x" indica un'operazione di AND;
- K1..K80 rappresentano i bit della chiave;
- IV1..IV80 rappresentano i bit del VI;
- N è la lunghezza in bit del messaggio da cifrare/decifrare.
Ecco la rappresentazione del Key setup e dell'IV setup:
(s1, s2, ..., s93) ← (K1, ..., K80, 0, ..., 0) (s94, s95, ..., s177) ← (IV1, ..., IV80, 0, ..., 0) (s178, s279, ..., s288) ← (0, ..., 0, 1, 1, 1) for i = 1 to (4 * 288) do t1 ← s66 + s91 x s92 + s93 + s171 t2 ← s162 + s175 x s176 + s177 + s264 t3 ← s243 + s286 x s287 + s288 + s69 (s1, s2, ..., s93) ← (t3, s1, ..., s92) (s94, s95, ..., s177) ← (t1, s94, ..., s176) (s178, s279, ...,s288) ← (t2, s178, ..., s287) end for
Questa è invece la rappresentazione della generazione del keystream:
for i = 1 to N do t1 ← s66 + s93 t2 ← s162 + s177 t3 ← s243 + s288 zi ← t1 + t2 + t3 t1 ← t1 + s91 x s92 + s171 t2 ← t2 + s175 x s176 + s264 t3 ← t3 + s286 x s287 + s69 (s1, s2, ..., s93) ← (t3, s1, ..., s92) (s94, s95, ..., s177) ← (t1, s94, ..., s176) (s178, s279, ..., s288) ← (t2, s178, ..., s287) end for
Prestazioni modifica
La più semplice delle implementazioni hardware del Trivium richiede solo 3488 dispositivi elettronici e produce circa 1 bit per ciclo di clock. Ma, visto che ogni bit dello stato interno non è utilizzato per almeno 64 passaggi, questo significa che 64 bit di stato possono essere generati in parallelo al costo di aumentare il numero di dispositivi elettronici fino al valore massimo di 5504. Ovviamente sono possibili soluzioni intermedie ai due estremi qui segnalati con output di 8, 16 e 32 bit calcolati in parallelo.
La stessa proprietà permette di avere discrete implementazioni in software dell'algoritmo: i test condotti all'eSTREAM hanno dimostrato come sia possibile ottenere velocità di circa 4 byte/ciclo su alcune architetture x86, valore molto positivo se comparato con i 19 cicli/byte ottenuti sulla stessa piattaforma dall'AES.
Sicurezza modifica
Non si conosce al 2008 un attacco migliore per recuperare la chiave segreta della forza bruta, che richiede un tempo di calcolo di 2135. Un attacco capace di recuperare lo stato interno è invece stato descritto nel 2006 da Alexander Maximov e Alex Biryukov, i quali hanno dimostrato come questo attacco richieda un tempo di 283,5 [1]
Curiosità modifica
Il nome Trivium deriva dall'omonimo termine latino che significa "trivio" ed è stato scelto sia perché la rappresentazione grafica dell'algoritmo ricorda proprio un incrocio di 3 vie sia perché l'aggettivo triviale, che è derivato da trivio, significa volgare ma anche comune o semplice, ad indicare la semplicità della struttura dell'algoritmo.
Note modifica
Voci correlate modifica
Collegamenti esterni modifica
- Il Trivium all'eSTREAM, su ecrypt.eu.org. URL consultato il 5 ottobre 2008 (archiviato dall'url originale il 23 settembre 2015).
- Le specifiche del Trivium (PDF), su ecrypt.eu.org.
