Cryptanalyse intégrale

La cryptanalyse intégrale est une technique formalisée par David Wagner et Lars Knudsen pour attaquer des chiffrements insensibles à la cryptanalyse différentielle. Elle nécessite de disposer d'un grand nombre de paires de textes clairs et chiffrés. Le but est de prédire la valeur des intégrales après un certain nombre de tours dans un chiffrement de bloc.

Explication mathématique

Dualité avec la cryptanalyse différentielle

La cryptanalyse intégrale est la duale de la cryptanalyse différentielle dans le sens où l'on ne s'intéresse pas aux propagations de différences dans la structure de chiffrement mais à la somme de plusieurs valeurs. L'opération d'intégration utilisée dans ce type d'attaque est à mettre en rapport avec son équivalent analytique. Toutefois une différence majeure apparaît : on considère un nombre fini de vecteurs dans le cas de la cryptanalyse intégrale.

Formellement, si l'on considère un ensemble fini $S~$ de vecteurs, chaque composante d'un vecteur provient d'un groupe abélien additif si bien qu'il est possible d'additionner les vecteurs composante par composante. On peut ainsi formuler une définition de l'intégrale qui est équivalente à l'addition vectoriel classique en géométrie :

$\int S=\sum _{v\in S}v=\left(\sum _{v\in S}v^{1},\sum _{v\in S}v^{2},...,\sum _{v\in S}v^{n}\right)$

Séparation des cas

Plusieurs cas sont considérés :

1. la n^e composante est identique pour tous les vecteurs
2. la n^e composante est différente pour tous les vecteurs
3. l'intégrale des vecteurs aboutit à une valeur connue à l'avance

Par l'application de divers théorèmes, des informations peuvent être obtenues à partir du résultat de l'intégrale. Si le nombre de vecteurs considérés est égal à l'ordre du groupe et que la n-ième composante est constante pour tous les vecteurs alors la n-ième composante de l'intégrale sera l'élément neutre du groupe (par exemple : 1+1+1+1 = 0 mod 4, 2+2+2+2 = 0 mod 4, etc.)

Applications

Knudsen et Wagner donnent un exemple sur Rijndael en considérant 256 textes clairs de 16 octets chacun (128 bits, soit la taille du bloc de Rijndael). Les textes partagent 15 octets qui sont identiques pour tous les textes, le 16^e diffère pour chacun d'entre eux (ce qui fait 256 textes distincts finalement).

On chiffre chacun des messages avec trois tours de Rijndael. On obtient 256 sorties de 16 octets (valeurs partiellement chiffrées) qui correspondent aux vecteurs précédemment évoqués. En intégrant ces 256 vecteurs, on obtient un vecteur dont les composantes sont toutes identiques. Cela permet de mener une attaque sur quatre tours en procédant à une intégration lors du déchiffrement (on modifie un seul octet de la clé et on regarde si l'octet dans l'intégration est en concordance avec l'octet de l'intégration lors du chiffrement).

La cryptanalyse intégrale a également fait ses preuves sur d'autres chiffrements comme MISTY1, SAFER ou Square.

Liens externes

• (en) https://www.cosic.esat.kuleuven.be/nessie/reports/phase2/uibwp5-015-1.pdf Integral cryptanalysis, papier de Knudsen et Wagner
• (en) https://www.cosic.esat.kuleuven.be/nessie/reports/phase2/uclwp5-002.pdf Attaque sur SAFER