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
La struttura del Trivium: notare la triplice rotazione, da cui il nome dell'algoritmo
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 2⁶⁴ 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

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

Quelle che seguono sono le rappresentazioni in pseudo-codice delle funzioni interne del Trivium. Questa è la simbologia adottata:

1. s1..s287 rappresentano i singoli bit dello stato interno;
2. t1, t2 e t3 sono variabili di stato;
3. zi rappresenta il bit di output del keystream;
4. il simbolo "+" rappresenta un'operazione di XOR;
5. il simbolo "x" indica un'operazione di AND;
6. K1..K80 rappresentano i bit della chiave;
7. IV1..IV80 rappresentano i bit del VI;
8. 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

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

Non si conosce al 2008 un attacco migliore per recuperare la chiave segreta della forza bruta, che richiede un tempo di calcolo di 2¹³⁵. 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 2^83,5

Curiosità

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.

Voci correlate

• Cifrario a flusso
• eSTREAM

Collegamenti esterni

• 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. URL consultato il 5 ottobre 2008 (archiviato dall'url originale il 20 agosto 2008).