Crittoanalisi lineare e tabelle di approssimazione

La crittanalisi lineare (Matsui, 1993) è un attacco con testo in chiaro noto che individua approssimazioni lineari (XOR di bit specifici) di un cifrario valide con probabilità p ≠ 1/2. Utilizzando molte coppie testo in chiaro-testo cifrato, il bias statistico rivela alcuni bit della chiave.

Un'approssimazione lineare per una S-box è la seguente: la somma di bit selezionati dell'input XOR la somma di bit selezionati dell'output = 0 (mod 2) con probabilità p. Si esprime come: P[a·x XOR b·y = 0] = 1/2 + ε, dove a,b sono maschere di bit ed ε è il bias (|ε| >> 0 è desiderabile).

La LAT conta, per ogni maschera di input a e maschera di output b, il numero di input x per cui (a·x) XOR (b·S(x)) = 0. Sottraendo 2^{n-1} si ottiene il bias. Una buona S-box ha |max_bias| = 1 (probabilità 1/2 ± 1/2^{n/2}), il valore più uniforme possibile.

Per approssimazioni lineari indipendenti attraverso più round, i bias si moltiplicano: ε_total = 2^{r-1} * ε_1 * ε_2 * ... * ε_r. Ogni approssimazione di round dimezza il bias effettivo. Dopo molti round, il bias totale tende a 0, richiedendo un numero esponenzialmente maggiore di coppie per essere rilevato.

Per attaccare un cifrario di r round, si trova un percorso lineare ε attraverso r-1 round. Si raccolgono N = 1/ε^2 testi in chiaro noti. Per ogni candidata k' al byte della chiave dell'ultimo round, si decifra parzialmente l'ultimo round tramite XOR e si verifica se l'approssimazione lineare è valida più di N/2 volte. La k' corretta mostra il bias corretto.

Nel 1993 Matsui attaccò DES a 16 round utilizzando un'approssimazione lineare di 14 round con bias 2^{-21.4}. Furono necessari 2^{43} testi in chiaro noti. Nella fase 1 recuperò 26 bit della chiave; i 30 rimanenti furono ottenuti tramite ricerca esaustiva. Fu il primo attacco pratico più veloce della forza bruta sull'intera chiave DES.

La S-box di AES ha una voce LAT massima pari a |ε| = 4/256 = 1/64 per S-box. La strategia Wide Trail limita ad almeno 25 il numero di S-box attive in qualsiasi percorso di 4 round. Il bias totale è ≤ (1/64)^{25/2} ≈ 2^{-75}. Sono necessari 2^{150} testi in chiaro noti, una quantità impraticabile.

Differenziale: coppie di testi in chiaro noti o scelti; sfrutta le differenze in output. Lineare: testi in chiaro noti; sfrutta approssimazioni lineari statistiche. Entrambi, negli attacchi pratici, utilizzano testi in chiaro scelti. Entrambi sono criteri di progettazione: le S-box devono resistere a tutti e due, con un valore massimo della DDT basso e un valore massimo della LAT basso.

Si utilizzano simultaneamente più approssimazioni lineari per ridurre la complessità dei dati. Nyberg e Leander hanno esteso il metodo di Matsui: la combinazione di M approssimazioni riduce i dati di un fattore log(M). Il metodo è stato applicato a PRESENT, SIMON e ad altri cifrari leggeri.

L'approssimazione lineare applicata ai cifrari a flusso cerca una correlazione tra il keystream e una funzione lineare dell'output di un LFSR. Questa correlazione, se diversa da zero, consente di recuperare la chiave più velocemente rispetto alla ricerca esaustiva. Ha influenzato la progettazione delle funzioni di combinazione non lineari nei cifrari a flusso.

La crittanalisi integrale (Knudsen-Wagner) sceglie un insieme di testi in chiaro in cui alcuni byte assumono tutti i 256 valori, mentre gli altri rimangono fissi. Dopo diversi round, lo XOR di tutti gli output in determinate posizioni è 0, cioè bilanciato. Sfrutta la struttura di AES e rompe in modo efficiente AES a round ridotti.

Che cosa afferma il lemma del piling-up sulla combinazione di approssimazioni lineari?

La crittanalisi lineare individua approssimazioni lineari distorte delle S-box. AES resiste grazie alla sua S-box ottimizzata per la LAT e alla progettazione Wide Trail. Matsui ha violato DES con 2^43 testi in chiaro noti utilizzando un percorso di 14 round. Prossimo argomento: attacchi del compleanno e ricerca delle collisioni.