GOST (cifrario)
# GOST (cifrario)

Il cifrario a blocchi GOST, definito nello standard GOST 28147-89, è un algoritmo crittografico a chiave simmetrica sviluppato negli anni settanta dall'allora Unione Sovietica come alternativa all'americano DES, di cui ricalca a grandi linee la struttura. Su questo cifrario è basato l'omonimo algoritmo di hash GOST.

Inizialmente marcato come "Top Secret", fu declassato a "Secret" nel 1990 e, dopo la dissoluzione dell'URSS (1991), fu distribuito al pubblico dominio nel 1994.

## L'algoritmo

Il GOST lavora su blocchi di dati di 64 bit ed impiega una chiave lunga 256 bit; utilizza S-box a 512 bit che possono essere segrete: in questo caso la lunghezza effettiva della chiave viene incrementata a 768 bit. Nonostante questo, un attacco a chiave scelta può risalire al contenuto delle S-box in circa $2^{32}$ cifrature (Saarinen, 1998).

Il GOST è una rete di Feistel a 32 passaggi, basati su una funzione molto semplice: ad ogni blocco di dati viene sommato modulo $2^{32}$ una sottochiave, poi il risultato viene combinato con le S-box ed infine viene ruotato di 11 bit a sinistra. Il diagramma a destra illustra queste operazioni (una linea rappresenta 32 bit di dati).

La rotazione della chiave è molto semplice: la chiave a 256 bit viene divisa in 8 sottochiavi da 32 bit ciascuna, ed ogni sottochiave è utilizzata nell'algoritmo 4 volte. Nei primi 24 passaggi le sottochiavi sono utilizzate secondo l'ordine originale mentre negli ultimi 8 passaggi esse sono utilizzate in ordine inverso.

Le S-box del GOST, costituite da 8 S-box 4 × 4, accettano un input di 4 bit e producono un output di 4 bit. Le S-box sono dipendenti dall'implementazione: il mittente ed il destinatario del messaggio cifrato devono utilizzare, per la comunicazione, S-box identiche. Per aumentare la sicurezza è possibile anche tenere segrete le S-box.

I documenti originali del GOST non indicavano nessuna S-box, segno che queste dovevano essere fornite in qualche modo agli utilizzatori dell'algoritmo. Questo portò a speculare circa il fatto che ad organizzazioni che il governo sovietico voleva spiare venivano fornite di proposito S-box crittograficamente deboli per poter violare con facilità i loro messaggi.

Un produttore di microprocessori crittografici con GOST integrato dichiarò che creava in proprio le S-box utilizzando un generatore di numeri pseudo-casuali (Bruce Schneier, 1996).

Ecco un esempio di S-box utilizzate dalla Banca Centrale Russa:

| # | S-Box |
| - | - |
| 1 | 4 10 9 2 13 8 0 14 6 11 1 12 7 15 5 3 |
| 2 | 14 11 4 12 6 13 15 10 2 3 8 1 0 7 5 9 |
| 3 | 5 8 1 13 10 3 4 2 14 15 12 7 6 0 9 11 |
| 4 | 7 13 10 1 0 8 9 15 14 4 6 12 11 2 5 3 |
| 5 | 6 12 7 1 5 15 13 8 4 10 9 14 0 3 11 2 |
| 6 | 4 11 10 0 7 2 1 13 3 6 8 5 9 12 15 14 |
| 7 | 13 11 4 1 3 15 5 9 0 10 14 7 6 8 2 12 |
| 8 | 1 15 13 0 5 7 10 4 9 2 3 14 6 11 8 12 |

## Crittoanalisi del GOST

Se paragonato al DES, da cui trae ispirazione, il GOST ha una funzione interna molto semplice. Nonostante questo gli sviluppatori del GOST cercarono di compensare questa semplicità con un elevato numero di passaggi (32), una chiave a 256 bit e S-box segrete.

Un altro punto debole del GOST è che l'effetto valanga si presenta più lentamente che nel DES: questo a causa del fatto che il GOST presenta nella sua struttura una rotazione al posto di una permutazione. Anche questa debolezza è compensata dall'elevato numero di passaggi utilizzati.

Non c'è molto materiale crittoanalitico pubblicato sul GOST ma ad un primo esame l'algoritmo sembra sicuro (Schneier, 1996): l'elevato numero di passaggi rende difficile utilizzare contro questo algoritmo la crittoanalisi lineare e differenziale dato che l'effetto valanga sarà anche lento ad apparire ma si può propagare per ben 32 passaggi.

