Matrice MDS

En algèbre et en cryptologie, une matrice MDS est une matrice possédant des propriétés particulières liées aux codes optimaux^[1]. Les propriétés de ces matrices sont particulières et bien connues, ce qui participe notamment à l'analyse des algorithmes de chiffrement par bloc qui les utilisent. Plus précisément, dans une série d'articles scientifiques portant sur les propriétés des réseaux de substitution-permutation, Heys et Tavares^[2],[3] ont montré que remplacer la couche de permutation par une couche linéaire de diffusion améliorait la résistance aux attaques cryptanalytiques, notamment la cryptanalyse linéaire et différentielle^[4]. Pour cette raison, le terme de « matrice de diffusion MDS » est parfois employé.

Du fait de ces propriétés, les matrices MDS sont au cœur de la conception ou de l'analyse des algorithmes modernes de chiffrement par bloc, dont AES, SHARK^[5], Square, Twofish^[6], Anubis, KHAZAD, Manta, Hierocrypt, Kalyna et Camellia. Les matrices MDS interviennent également, quoique de manière moins systématique, dans le design de certains algorithmes de hachage (par exemple Whirlpool).

Définition

Soit ${\displaystyle K=\mathbb {F} _{q}}$un corps fini, et ${\displaystyle M}$ une matrice ${\displaystyle k\times k}$ à coefficients dans ${\displaystyle K}$. On dit que ${\displaystyle M}$est une « matrice (de diffusion) MDS » si le code de matrice génératrice ${\displaystyle {\begin{pmatrix}I_{k}|M\end{pmatrix}}}$, où ${\displaystyle I_{k}}$est la matrice identité, est un code MDS^{[Note 1]}. Il existe plusieurs définitions équivalentes, qui peuvent être utilisées pour construire de telles matrices explicitement (voir ci-dessous) ; notamment, une matrice est MDS si et seulement si tous ses mineurs sont inversibles.

Par extension, on appelle encore matrice MDS les matrices binaires obtenues via une réalisation du corps ${\displaystyle K}$sur le corps ${\displaystyle \mathbb {F} _{2}}$.

Construction

À partir de codes MDS

Une méthode courante pour construire des matrices MDS consiste à générer un code de Reed-Solomon sur ${\displaystyle \mathbb {F} _{2^{m}}}$, puis mettre sa matrice génératrice sous forme systématique ${\displaystyle {\begin{pmatrix}I_{k}|M\end{pmatrix}}}$.

Prenons par exemple ${\displaystyle K=\mathbb {F} _{8}\simeq \mathbb {F} _{2}[X]/(X^{3}+X+1)}$et construisons sur ${\displaystyle K}$un code de Reed-Solomon de paramères [6, 3, 4], alors on obtient la matrice génératrice sous forme systématique ${\displaystyle {\begin{pmatrix}I_{3}|M\end{pmatrix}}}$avec

$${\displaystyle M={\begin{pmatrix}1&X&X^{3}\\1&X^{6}&X^{6}\\1&X^{4}&X^{5}\end{pmatrix}}}$$

On peut obtenir à partir de ${\displaystyle M}$une matrice binaire en remplaçant chaque ${\displaystyle X^{m}}$par la puissance correspondante de la matrice compagnon du polynôme ${\displaystyle X^{3}+X+1}$ , on obtient alors

$${\displaystyle M_{b}={\begin{pmatrix}{\begin{array}{c|c|c}{\begin{array}{ccc}1&0&0\\0&1&0\\0&0&1\end{array}}&{\begin{array}{ccc}0&1&0\\0&0&1\\1&1&1\end{array}}&{\begin{array}{ccc}1&1&0\\0&1&1\\1&1&1\end{array}}\\\hline {\begin{array}{ccc}1&0&0\\0&1&0\\0&0&1\end{array}}&{\begin{array}{ccc}1&0&1\\1&0&0\\0&1&0\end{array}}&{\begin{array}{ccc}1&0&1\\1&0&0\\0&1&0\end{array}}\\\hline {\begin{array}{ccc}1&0&0\\0&1&0\\0&0&1\end{array}}&{\begin{array}{ccc}0&1&1\\1&1&1\\1&0&1\end{array}}&{\begin{array}{ccc}1&1&1\\1&0&1\\1&0&0\end{array}}\end{array}}\end{pmatrix}}}$$Utiliser une représentation différente de ${\displaystyle \mathbb {F} _{8}}$donnerait des matrices ${\displaystyle M}$et ${\displaystyle M_{b}}$différentes et non isomorphes.

Recherche exhaustive

Toutes les matrices MDS ne découlent pas de la construction ci-dessus. En particulier, il peut être souhaitable de doter la matrice de propriétés supplémentaires (qu'elle soit circulante, par exemple, afin d'en simplifier l'implémentation). Dans ces cas, il n'est pas rare de procéder à une recherche exhaustive^[7],[8],[9].

Applications

Les matrices MDS sont de bonnes matrices de diffusion et sont utilisées à cette fin dans les algorithmes de chiffrement par bloc. Ainsi, l'étape MixColumns de l'AES/Rijndael peut être vu comme la multiplication par une matrice MDS circulante, à savoir

$${\displaystyle M={\begin{pmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{pmatrix}}}$$

où les coefficients appartiennent au corps fini AES isomorphe à ${\displaystyle \mathbb {F} _{256}}$. Cette matrice est un élément clé dans la stratégie de conception de l'AES, dite « wide trail » ^[10],[11].

Notes et références

Notes

1. C'est-à-dire qu'il atteint la borne de Singleton.

Références

1. Nora El Amrani, Codes additifs et matrices MDS pour la cryptographie, Université de Limoges, 24 février 2016 (lire en ligne)
2. (en) H. M. Heys et S. E. Tavares, « The design of substitution-permutation networks resistant to differential and linear cryptanalysis », CCS '94 Proceedings of the 2nd ACM Conference on Computer and communications security, ACM,‎ 2 novembre 1994, p. 148–155 (ISBN 0897917324, DOI 10.1145/191177.191206, lire en ligne, consulté le 11 août 2018)
3. (en) H.M. Heys et S.E. Tavares, « Avalanche characteristics of substitution-permutation encryption networks », IEEE Transactions on Computers, vol. 44, n^o 9,‎ 1995, p. 1131–1139 (ISSN 0018-9340, DOI 10.1109/12.464391, lire en ligne, consulté le 11 août 2018)
4. (en) Anne Canteaut et Joëlle Roué, « Differential Attacks Against SPN: A Thorough Analysis », dans Lecture Notes in Computer Science, Springer International Publishing, 2015 (ISBN 9783319186801, DOI 10.1007/978-3-319-18681-8_4, lire en ligne), p. 45–62
5. (en) Vincent Rijmen, Joan Daemen, Bart Preneel et Antoon Bosselaers, « The cipher SHARK », dans Fast Software Encryption, Springer Berlin Heidelberg, 1996 (ISBN 9783540608653, DOI 10.1007/3-540-60865-6_47, lire en ligne), p. 99–111
6. (en) Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall et Niels Ferguson, « Twofish: A 128-Bit Block Cipher - Schneier on Security », sur www.schneier.com, 15 juin 1998 (consulté le 10 août 2018)
7. (en) Daniel Augot et Matthieu Finiasz, « Exhaustive search for small dimension recursive MDS diffusion layers for block ciphers and hash functions », 2013 IEEE International Symposium on Information Theory, IEEE,‎ juillet 2013 (ISBN 9781479904464, DOI 10.1109/isit.2013.6620487, lire en ligne, consulté le 11 août 2018)
8. (en) Siang Meng Sim, Khoongming Khoo, Frédérique Oggier et Thomas Peyrin, « Lightweight MDS Involution Matrices », dans Fast Software Encryption, Springer Berlin Heidelberg, 2015 (ISBN 9783662481158, DOI 10.1007/978-3-662-48116-5_23, lire en ligne), p. 471–493
9. (en) Kishan Chand Gupta, Sumit Kumar Pandey et Ayineedi Venkateswarlu, « On the direct construction of recursive MDS matrices », Designs, Codes and Cryptography, vol. 82, n^os 1-2,‎ 14 juin 2016, p. 77–94 (ISSN 0925-1022 et 1573-7586, DOI 10.1007/s10623-016-0233-4, lire en ligne, consulté le 11 août 2018)
10. (en) Joan Daemen et Vincent Rijmen, « Security of a Wide Trail Design », dans Progress in Cryptology — INDOCRYPT 2002, Springer Berlin Heidelberg, 2002 (ISBN 9783540002635, DOI 10.1007/3-540-36231-2_1, lire en ligne), p. 1–11
11. (en) Carlos Cid, Sean Murphy et Matthew Robshaw, Algebraic Aspects of the Advanced Encryption Standard, 2006 (DOI 10.1007/978-0-387-36842-9, lire en ligne)