Fondamenti della crittoanalisi differenziale

La crittanalisi differenziale (Biham e Shamir, 1990) è un attacco con testo in chiaro scelto che analizza come le differenze nelle coppie di testi in chiaro si propagano attraverso un cifrario. Individuando differenze in input che producono differenze in output prevedibili con alta probabilità, l'attaccante recupera statisticamente alcuni bit della chiave.

Per i cifrari basati su XOR: differenza ΔX = X XOR X'. Per i cifrari basati sull'addizione: differenza ΔX = X - X' mod 2^n. Le differenze XOR sono le più comuni, poiché XOR commuta con l'uso di chiavi XOR, facendo annullare gli effetti della pianificazione della chiave nelle coppie differenziali.

Una coppia differenziale (P, P') ha differenza in input ΔP = P XOR P'. Dopo la cifratura si ottiene (C, C'), con differenza in output ΔC = C XOR C'. Un differenziale utile è ΔP → ΔC con alta probabilità p: molte coppie (P, P') con differenza ΔP producono la differenza in output ΔC.

La DDT (Differential Distribution Table) conta, per ogni differenza in input Δx e differenza in output Δy, quanti input x soddisfano S(x) XOR S(x XOR Δx) = Δy. Dividendo per 2^n si ottiene la probabilità. Una buona S-box ha valore massimo della DDT pari a 2 (probabilità 1/2^{n-1}), quindi non presenta differenziali forti.

Per un cifrario a blocchi con r round, si cerca una sequenza ΔP → ΔU1 → ΔU2 → ... → ΔU_{r-1} in cui ogni transizione di round abbia una probabilità nota. Si moltiplicano le probabilità dei vari round: la probabilità complessiva è p = p1 * p2 * ... * p_{r-1}. L'attacco utilizza 2/p coppie per recuperare la chiave dell'ultimo round.

Con un differenziale di r-1 round ad alta probabilità, si raccolgono N = 2/p coppie di testi in chiaro. Per ogni candidata alla chiave dell'ultimo round K', si decifrano entrambi i cifrati per un round, si applica XOR ai risultati e si verifica se la differenza corrisponde a ΔU_{r-1}. La K' corretta corrisponde circa N/2 volte; le chiavi errate corrispondono circa N/2^{bit_size} volte.

La S-box di AES è l'inverso moltiplicativo su GF(2^8), seguito da una trasformazione affine. Il valore massimo della sua DDT è 4 su 256, con probabilità differenziale ≤ 4/256 = 1/64 per S-box. AES ha 4 S-box per round, ma la progettazione Wide Trail garantisce che i percorsi differenziali completi abbiano probabilità inferiore a 2^{-100}.

La progettazione Wide Trail di Joan Daemen, utilizzata in AES/Rijndael, definisce il numero di rami B di MixColumns. Qualsiasi percorso differenziale non banale attraverso un round attiva almeno B S-box attive. 4 round × 4 S-box per round garantiscono almeno 25 S-box attive, con probabilità < 2^{-100}.

I differenziali troncati specificano solo una parte della differenza, ad esempio quali colonne sono attive, non i valori esatti delle differenze. Consentono attacchi su un numero maggiore di round, dove i differenziali completi sono troppo deboli. Sono utilizzati contro AES a round ridotti, SERPENT e altri cifrari SPN.

Un differenziale impossibile è una coppia (ΔP, ΔC) che non può mai verificarsi con alcuna chiave. Qualsiasi chiave che associ una coppia osservata (P, P') con questa differenza viene eliminata. Raccogliendo un numero sufficiente di coppie, tutte le chiavi errate vengono eliminate e rimane quella corretta.

L'attacco boomerang (Wagner, 1999) combina due differenziali brevi in un attacco adattivo con testo in chiaro e testo cifrato scelti. Divide il cifrario in due metà, ciascuna con un differenziale breve ad alta probabilità, consentendo di attaccare un numero di round maggiore di quello raggiungibile con un singolo differenziale.

La crittanalisi differenziale sfrutta la propagazione di differenze tra input e output con alta probabilità. AES la contrasta grazie alla sua S-box ottimizzata per la DDT e alla progettazione Wide Trail. Prossimo argomento: crittanalisi lineare e tabelle delle approssimazioni.