Grain (cifrario)
| Grain | |
|---|---|
| Generale | |
| Progettisti | Martin Hell, Thomas Johansson e Willi Meier |
| Prima pubblicazione | 2004 |
| Dettagli | |
| Dimensione chiave | 80 bit |
| Dim. vettore di inizializazione | 64 bit |
| Struttura | LFSR e NLFSR |
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.[1]
Descrizione
[modifica | modifica wikitesto]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
[modifica | modifica wikitesto]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
[modifica | modifica wikitesto]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
[modifica | modifica wikitesto]Il Grain 0.0 è stato crittoanalizzato nel 2006[2]: per recuperare la chiave di 80 bit sono occorsi 238 bit di keystream per una complessità di 243 computazioni.
Il Grain 1.0 sembra più robusto: ad oggi, nessun attacco più efficace della forza bruta (al costo di una complessità di 280 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/22 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[3]
Diritti d'autore
[modifica | modifica wikitesto]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
[modifica | modifica wikitesto]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.[4] 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.[1]
Note
[modifica | modifica wikitesto]- ^ a b The eSTREAM portfolio page, su ecrypt.eu.org. URL consultato il 03/06/2013 (archiviato dall'url originale il 17 dicembre 2012).
- ^ Crittoanalisi del Grain 0.0 (PDF), su ecrypt.eu.org. URL consultato il 29 settembre 2008 (archiviato dall'url originale l'11 ottobre 2006).
- ^ Slide Resynchronization Attack alla funzione di inizializzazione del Grain 1.0 (ps), su ecrypt.eu.org. URL consultato il 29 settembre 2008 (archiviato dall'url originale il 27 maggio 2011).
- ^ Specifiche del Grain-128a
Collegamenti esterni
[modifica | modifica wikitesto]- Pagina del Grain all'eSTREAM, su ecrypt.eu.org. URL consultato il 5 ottobre 2008 (archiviato dall'url originale il 6 ottobre 2008).
