Lemme d'empilement

Le lemme d'empilement (le Piling-up Lemma en anglais) est un résultat statistique introduit par Mitsuru Matsui en 1993 dans le cadre de la cryptanalyse linéaire. Ce lemme permet de quantifier le biais statistique présent dans une approximation linéaire d'un algorithme de chiffrement symétrique par bloc.

Formulation mathématique

Une équation linéaire dans le cadre de la cryptanalyse linéaire se présente sous la forme d'un ou-exclusif de variables binaires :

$X_{1}\oplus X_{2}\oplus ...\oplus X_{N}=0$

Soit $N~$ variables aléatoires, indépendantes et binaires (le résultat de l'événement est soit 0, soit 1), $X_{1},X_{2},...,X_{N}~$, la probabilité que cette équation soit correcte est :

$P(X_{1}\oplus X_{2}\oplus ...\oplus X_{N}=0)=1/2+2^{N-1}\prod _{i=1}^{N}\epsilon _{i}$

avec $\epsilon _{i}~$, le biais linéaire de la variable aléatoire $X_{i}~$. Ce biais peut être positif ou négatif et quantifie l'écart par rapport à une distribution uniforme où l'espérance d'une variable aléatoire binaire est 1/2. Plus le biais est important, plus un algorithme de chiffrement est susceptible d'être attaqué via la cryptanalyse linéaire.

Raisonnement

Soit $P(A)~$, la probabilité que l'événement A arrive. Avec une probabilité de 1, l'événement se produira. Inversement, une probabilité de 0 indique l'impossibilité de cet événement. Dans le cadre du lemme d'empilement, nous avons donc affaire à des variables aléatoires, binaires et considérées comme indépendantes.

Considérons d'abord le lemme pour deux variables aléatoires :

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

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

Considérons maintenant la probabilité d'une équation linéaire avec ces deux variables :

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

Grâce aux propriétés de XOR, ceci est équivalent à :

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

X₁ = X₂ = 0 et X₁ = X₂ = 1 sont des événements mutuellement exclus et de ce fait :

$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)~$

Nous partons dès lors du principe que les variables sont indépendantes. C’est-à-dire que l'état d'une variable ne va pas influencer l'état d'une autre. On peut ainsi étendre la probabilité au résultat suivant :

$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\$

Nous exprimons maintenant les probabilités p₁ et p₂ comme ½ + ε₁ et ½ + ε₂, où les ε sont des biais de probabilités — la quantité de déviation de la probabilité par rapport à ½.

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

Ainsi, le biais ε_1,2 pour la somme de XOR ci-dessus est de 2ε₁ε₂.

Cette formule peut s'étendre pour un nombre infini de variables comme suit :

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

Si un ε est à zéro, c’est-à-dire qu'une des variables est non-biaisée, alors l'ensemble de la fonction ne sera pas biaisée et égale à ½.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Piling-up lemma » (voir la liste des auteurs).

Annexes

Bibliographie

• [Matsui 1994] (en) Mitsuru Matsui, « Linear Cryptanalysis Method for DES Cipher », dans T. Helleseth, Advances in Cryptology — EUROCRYPT ’93, vol. 765, Springer, coll. « Lecture Notes in Computer Science », 1994 (ISBN 978-3-540-57600-6, ISSN 0302-9743, DOI 10.1007/3-540-48285-7_33, lire en ligne [PDF]), p. 386–397.

Articles connexes

• Cryptanalyse différentielle