Teorema dell'impilamento

In crittanalisi il teorema dell'impilamento (piling-up lemma) è un principio utilizzato nella crittanalisi lineare per costruire le approssimazioni lineari dei cifrari a blocchi. È stato introdotto da Mitsuru Matsui nel 1993 come uno strumento analitico della crittanalisi lineare.

Teoria

Il teorema dell'impilamento permette al crittanalista di determinare la probabilità che la seguente equazione sia valida:

$X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0$

dove le x indicano variabili binarie (vale a dire con valore 0 o 1).

Poniamo P(A) come indice della "probabilità che A sia vera": se è uguale a 1, A è certo che si verifichi; se è uguale a 0, A non si può verificare. Prima di tutto consideriamo il teorema dell'impilamento per 2 variabili binarie:

$P(X_{1}=i)=\left\lbrace {\begin{matrix}p_{1}&{\hbox{for }}i=0\\1-p_{1}&{\hbox{for }}i=1\end{matrix}}\right.$

$P(X_{2}=j)=\left\lbrace {\begin{matrix}p_{2}&{\hbox{for }}j=0\\1-p_{2}&{\hbox{for }}j=1\end{matrix}}\right.$

Adesso consideriamo:

$P(X_{1}\oplus X_{2}=0)$

A causa delle proprietà dell'operazione di XOR, questa equazione è equivalente a

$P(X_{1}=X_{2})$

X₁ = X₂ = 0 e X₁ = X₂ = 1 sono eventi mutuamente esclusivi, per cui possiamo dire che

$P(X_{1}=X_{2})=P(X_{1}=X_{2}=0)+P(X_{1}=X_{2}=1)=P(X_{1}=0,X_{2}=0)+P(X_{1}=1,X_{2}=1)$

Adesso dobbiamo impostare l'assunto centrale del teorema dell'impilamento: le variabili binarie che stiamo trattando sono indipendenti: questo significa che lo stato di una non ha effetto sullo stato di nessuna delle altre. Possiamo così espandere la funzione della probabilità come segue:

$P(X_{1}\oplus X_{2}=0)$	$=P(X_{1}=0)P(X_{2}=0)+P(X_{1}=1)P(X_{2}=1)\$
	$=p_{1}p_{2}+(1-p_{1})(1-p_{2})\$
	$=p_{1}p_{2}+(1-p_{1}-p_{2}+p_{1}p_{2})\$
	$=2p_{1}p_{2}-p_{1}-p_{2}+1\$

Adesso esprimiamo le probabilità p₁ e p₂ come ½ + ε₁ e ½ + ε₂, dove le ε indicano la quantità dello scostamento dalla probabilità rapportata a ½.

$P(X_{1}\oplus X_{2}=0)$	$=2(1/2+\varepsilon _{1})(1/2+\varepsilon _{2})-(1/2+\varepsilon _{1})-(1/2+\varepsilon _{2})+1\$
	$=1/2+\varepsilon _{1}+\varepsilon _{2}+2\varepsilon _{1}\varepsilon _{2}-1/2-\varepsilon _{1}-1/2-\varepsilon _{2}+1\$
	$=1/2+2\varepsilon _{1}\varepsilon _{2}\$

Lo scostamento dalla probabilità ε_1,2 per le somme XOR qui sopra è così 2ε₁ε₂.

Questa formula può essere estesa a più X come segue:

$P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0)=1/2+2^{n-1}\prod _{i=1}^{n}\varepsilon _{i}$

È da notare che se nessuna delle ε è pari a 0, cioè che lo scostamento dalla probabilità di una delle variabili binarie è 0, allora lo scostamento dalla probabilità dell'intera funzione della probabilità sarà pari a ½.

Una definizione un po' diversa dello scostamento è

$\varepsilon _{i}=P(X_{i}=1)-P(X_{i}=0),$

infatti due segni meno danno il valore precedente. Il vantaggio è che adesso con

$\varepsilon _{total}=P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=1)-P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0)$

abbiamo

$\varepsilon _{total}=\prod _{i=1}^{n}\varepsilon _{i},$

aggiungendo i valori di variabili casuali per moltiplicare i loro scostamenti (seconda definizione).

Pratica

In pratica le X sono approssimazione delle S-box (componenti di sostituzione) dei cifrari a blocchi. Di solito i valori X sono i dati in ingresso delle S-box ed i valori Y sono i corrispondenti dati in uscita. Guardando semplicemente alle S-box, il crittanalista può dire quali sono i valori degli scostamenti. Il trucco sta nel trovare le combinazioni di valori in ingresso ed in uscita che hanno probabilità pari a 0 o 1. Più l'approssimazione si avvicinerà a 0 o 1, più utile sarà per la crittanalisi lineare.

Nella pratica, le variabili binarie non sono comunque indipendenti, così come si intende nel significato ipotizzato dal teorema dell'impilamento. Questa considerazione deve essere tenuta a mente quando si applica il teorema, dato che non si tratta di una formula crittanalitica automatica.

Bibliografia

• Mitsuru Matsui: Linear Cryptanalysis Method for DES Cipher - EUROCRYPT 1993

Voci correlate

• Crittanalisi lineare
• Crittanalisi