Crittanalisi lineare

La crittanalisi lineare è una forma generale di crittanalisi basata sulla ricerca di approssimazioni affini al comportamento di un cifrario. Gli attacchi sono stati sviluppati per i cifrari a blocchi e quelli a flusso. La crittanalisi lineare è una delle due tecniche di attacco più utilizzate contro i cifrari a blocchi: l'altra è la crittanalisi differenziale.

La scoperta della crittanalisi lineare è attribuita a Mitsuru Matsui, che per primo l'applicò al cifrario FEAL nel 1992. Successivamente Matsui pubblicò un attacco al DES, probabilmente il primo esperimento di crittanalisi del cifrario riportato da un accademico. L'attacco non è però generalmente praticabile, dato che richiede 2⁴³ testi in chiaro noti.

Sono state suggerite una gran varietà di migliorie all'attacco, incluse l'uso di approssimazioni lineari multiple o l'incorporazione di espressioni non lineari.

Dai nuovi cifrari in genere ci si attende che i loro sviluppatori pubblichino anche il livello di sicurezza contro la crittanalisi lineare.

Analisi

Ci sono due parti distinte nella crittanalisi lineare. La prima è la costruzione delle equazioni lineari che legano il testo in chiaro, il testo cifrato ed i bit della chiave che hanno un elevato valore di distorsione, vale a dire, quelli la cui probabilità di stima (all'interno dello spazio di tutti i possibili valori delle loro variabili) è la più vicina possibile a 0 o ad 1. La seconda è l'utilizzo di queste equazioni lineari congiuntamente con le coppie note di testi cifrati e testi in chiaro per derivare i bit della chiave.

Costruzione delle equazioni lineari

Un'equazione lineare, per gli scopi della crittanalisi lineare, esprime l'uguaglianza di due espressioni che consistono di valori binari combinati con un'operazione di OR esclusivo (XOR). Ad esempio, la seguente equazione indica che la somma XOR del primo e del terzo bit del testo in chiaro (contenuti all'interno del blocco di un cifrario a blocchi) ed il primo bit del testo cifrato è uguale al secondo bit della chiave:

$P_{1}\oplus P_{3}\oplus C_{1}=K_{2}.$

In un cifrario reale, non dovrebbe essere possibile creare tali equazioni che siano valide per tutto il tempo. In un cifrario ideale, qualsiasi equazione lineare che lega con una relazione il testo in chiaro, il testo cifrato ed i bit della chiave dovrebbe poter essere valida con una probabilità di 1/2. Dato che ci si attende che le equazioni trattate nella crittanalisi lineare non siano valide per tutto il tempo, sono spesso più correttamente indicate come approssimazioni lineari.

La procedura per costruire le approssimazioni è differente da cifrario a cifrario. Nel tipo più classico di cifrario a blocchi, una rete a sostituzione e permutazione, l'analisi si concentra principalmente sulle S-box, l'unica parte non lineare del cifrario (vale a dire che l'operazione eseguita da una S-box non può essere codificata con una equazione lineare). Per S-box abbastanza piccole, è possibile numerare ogni possibile equazione lineare che lega l'input dell'S-box con i bit in output, calcolare le loro distorsioni e scegliere le migliori. Le approssimazioni lineari delle S-box devono poi essere combinate con le altre operazioni del cifrario, come la permutazione ed il mescolamento della chiave, per arrivare alle approssimazioni lineari dell'intero cifrario. Il teorema dell'impilamento è uno strumento utile per questo processo di combinazione. Ci sono anche altre tecniche per migliorare iterativamente le approssimazioni lineari (Matsui, 1994).

Derivazione dei bit della chiave

Una volta ottenuta un'approssimazione lineare nella forma:

$P_{i_{1}}\oplus P_{i_{2}}\oplus \cdots \oplus C_{j_{1}}\oplus C_{j_{2}}\oplus \cdots =K_{k_{1}}\oplus K_{k_{2}}\oplus \cdots$

è possibile applicare un semplice algoritmo (Algoritmo 2 di Matsui) usando coppie note di testo in chiaro e testo cifrato per prevedere i valori dei bit della chiave coinvolti nell'approssimazione.

Per ogni serie di valori dei bit della chiave posti nella parte destra, indicato come chiave parziale, bisogna contare quante volte l'approssimazione è vera per tutte le coppie note di testo in chiaro e testo cifrato: questo conteggio è chiamato T. La chiave parziale il cui T ha la differenza assoluta da metà del numero delle coppie di testo in chiaro e testo cifrato più grande è indicata come la più probabile serie di valori per quei bit della chiave. Si ha questo risultato perché si assume che la chiave parziale corretta renderà vera l'approssimazione con un'elevata distorsione. È importante notare che il valore della distorsione è qui, a differenza del valore della stessa probabilità, significante.

Questa procedura può essere ripetuta con altre approssimazioni lineari, ottenendo valori finali per i bit della chiave, finché il numero di bit della chiave non noti è basso abbastanza da poterli recuperare con un attacco a forza bruta.

Bibliografia

• Mitsuru Matsui, A. Yamagishi: A new method for known plaintext attack of FEAL cipher - EUROCRYPT 1992
• M. Matsui: Linear cryptanalysis method for DES cipher - EUROCRYPT 1993
• M. Matsui: The first experimental cryptanalysis of the data encryption standard - CRYPTO 1994

Voci correlate

• Teorema dell'impilamento
• Crittanalisi differenziale

Collegamenti esterni

• Una guida sulla crittanalisi lineare (e differenziale) dei cifrari a blocchi, su engr.mun.ca.