Trivium (cifrario)
# 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).

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^{64}$ 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:

* 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:

Questa è invece la rappresentazione della generazione del keystream:

## 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^{135}.$ 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.

