# Grain (cifrario)

Il Grain è un cifrario a flusso proposto per l'eSTREAM nel 2004 da Martin Hell, Thomas Johansson e Willi Meier. È stato inserito nel portafoglio finale dell'eSTREAM per il Profilo 2, vale a dire per implementazioni in hardware a limitate capacità. L'algoritmo esiste in 2 versioni: la prima è denominata Grain v1 ed utilizza una chiave da 80 bit ed un vettore di inizializzazione (initialization vector, o IV) di 64 bit, la seconda è denominata Grain-128 ed usa una chiave da 128 bit ed un VI di 80 bit.

## Descrizione

La funzione interna del Grain lavora con blocchi dati di 160 bit costituiti da un registro a scorrimento a retroazione lineare (LFSR) di 80 bit ed un registro a scorrimento a retroazione non lineare (NLFSR) sempre ad 80 bit.
L'algoritmo aggiorna un bit dell'LFSR ed un bit dell'NLFSR per ogni bit di testo cifrato da una funzione di filtro non lineare. L'NLFSR ad 80 bit è aggiornato con l'input proveniente dall'iterazione fra l'output generato da una funzione booleana non lineare 5-a-1 ed 1 bit generato dall'LFSR. L'LFSR ad 80 bit è aggiornato con una funzione lineare 6-a-1. Durante l'esecuzione, l'output dell'algoritmo è riutilizzato come input lineare per aggiornare sia l'input dell'NLFSR che dell'LFSR.
Nella versione originale del Grain, denominata Grain Version 0.0, 1 bit dell'NLFSR e 4 bit dell'LFSR erano utilizzati come input di una funzione booleana non lineare 5-a-1 e l'output era combinato linearmente con 1 bit dell'NLFSR per generare l'output del Grain.
Nella versione aggiornata, denominata Grain Version 1.0, 1 bit dell'NLFSR e 4 bit dell'LFSR vengono passati come input alla funzione booleana non lineare 5-a-1 (fortemente modificata) e l'output è combinato linearmente con 7 bit dell'NLFSR e poi pubblicato come output finale.

## Inizializzazione del Grain

L'inizializzazione del cifrario avviene caricando la chiave da 80 bit direttamente nell'NLFSR e l'IV da 64 bit nell'LFSR. I restanti 16 bit di quest'ultimo vengono caricati con una sequenza di bit 1. L'algoritmo viene poi eseguito 160 volte, durante le quali l'output non è pubblicato ma viene riutilizzato come input per aggiornare sia l'NLFSR che l'LFSR.
Circa la diffusione dei bit operata dalla procedura di inizializzazione, gli autori del Grain dichiarano che "con l'inizializzazione eseguita con 2 differenti IV che differiscono per un solo bit, la probabilità che un bit del registro di rotazione sia lo stesso in entrambi i casi è pari a 0,5. Le simulazioni mostrano che questo valore è ottenuto dopo 160 rotazioni."

## Prestazioni

L'algoritmo è disegnato per poter eseguire fino a 16 passaggi in parallelo, consentendo implementazioni molto veloci al prezzo però di un aumentato utilizzo delle risorse hardware.

## Sicurezza

Il Grain 0.0 è stato crittoanalizzato nel 2006: per recuperare la chiave di 80 bit sono occorsi 2$^{38}$ bit di keystream per una complessità di 2$^{43}$ computazioni.
Il Grain 1.0 sembra più robusto: ad oggi, nessun attacco più efficace della forza bruta (al costo di una complessità di 2$^{80}$ computazioni) sembra sia in grado di forzare l'algoritmo. Tuttavia, nel settembre del 2006 Ozgul Kucuk ha pubblicato un documento in cui riportava che per ogni coppia (chiave, IV) esiste una coppia (chiave', IV') tale che presenti una probabilità di 1/2$^2$ che generi un keystream spostato di 1 bit. Anche se, per ammissione dello stesso autore, questo fatto non è sfruttabile per condurre un vero e proprio attacco, indica certamente una debolezza dell'algoritmo che deve essere studiata maggiormente

## Diritti d'autore

Grain è brevettato ed i diritti d'autore sono detenuti dagli autori del codice. È concessa la possibilità di usare, copiare, modificare o distribuire l'algoritmo a patto di non inserire il Grain in prodotti coperti da brevetto.

## Grain-128a

La crittanalisi della versione a 128 bit ha manifestato alcuni margini di miglioramento dell'algoritmo che ha portato gli autori a sviluppare una nuova versione del Grain-128 denominata Grain-128a. Questa versione integra anche un algoritmo di autenticazione del messaggio. Rispetto al Grain v1 ad 80 bit, l'implementazione di questa nuova versione occupa più risorse e lavora ad una velocità dimezzata: a causa di ciò il Grain-128a non è stato inserito nel portafoglio dell'eSTREAM.