Cryptanalyse Mod n

En cryptologie, la cryptanalyse mod n est une attaque applicable aux chiffrements par bloc et aux chiffrements par flot. C'est une forme de cryptanalyse partitionnelle utilisant l'arithmétique modulaire. Elle exploite le fait que le comportement opératoire de l'algorithme est inégal sur l'anneau Z/nZ formé par les classes d'équivalence (classes de congruence) modulo n. La méthode fut suggérée en premier en 1999 par John Kelsey, Bruce Schneier et David Wagner et appliquée sur RC5P (une variante de RC5) et M6 (une famille de code en bloc utilisée dans le standard FireWire).

Analyse mod 3 de RC5P

Pour RC5P, l'analyse fut conduite modulo 3. Il fut observé que les opérations dans le chiffrement (rotation et addition, les deux sur des mots 32 bits) étaient quelque peu biaisées sur les classes de congruence mod 3. Pour illustrer cette approche, considérons la rotation gauche par un seul bit :

$X<<<1=\left\{{\begin{matrix}2X,&{\mbox{si }}X<2^{31}\\2X+1-2^{32},&{\mbox{si }}X\geq 2^{31}\end{matrix}}\right.$

Alors, parce que

$2^{32}\equiv 1{\pmod {3}}$,

Nous pouvons déduire que

$X<<<1\equiv 2X{\pmod {3}}$.

Ainsi, la rotation gauche par un seul bit possède une description simple modulo 3. L'analyse pour d'autres opérations (rotation dépendante des données et addition modulaire) révèle des biais statistiques notables. Bien qu'il existe certains problèmes théoriques d'analyse d'opérations en combinatoire, le biais peut être détecté expérimentalement si le chiffrement est considéré dans son ensemble. Dans l'article de Kelsey (1999), les expériences furent conduites sur sept passages. Se basant sur ceci, les cryptanalystes conjecturèrent que dix-neuf ou vingt passages de RC5P peuvent être distingués d'un flux aléatoire. Il existe aussi une méthode correspondante pour retrouver la clé secrète.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Mod n cryptanalysis » (voir la liste des auteurs)

, dont les références étaient :

• (en) John Kelsey, Bruce Schneier et David Wagner, « Mod n Cryptanalysis, with Applications Against RC5P and M6 », dans Fast Software Encryption 1999, p. 139-155
• (en) Vincent Rijmen, « « mod n » Cryptanalysis of Rabbit », Livre blanc, dans Cryptico, December 1, 2003. (PDF)
• (en) Toshio Tokita et Tsutomu Matsumoto, « On Applicability of Differential Cryptanalysis, Linear Cryptanalysis and Mod n Cryptanalysis to an Encryption Algorithm M8 (ISO9979-20) », dans IPSJ Journal, vol. 42, n° 8