Construction of Hadamard-based MixColumns Matrices Resistant to Related-Differential Cryptanalysis

Sonu Jha; Shun Li; Danilo Gligoroski

doi:10.62056/a6ksdk5vt

Construction of Hadamard-based MixColumns Matrices Resistant to Related-Differential Cryptanalysis

Authors

Sonu Jha, Shun Li, Danilo Gligoroski

Sonu Jha

Norwegian University of Science and Technology, Trondheim, Norway
sonu dot k dot jha at ntnu dot no

Shun Li

Chinese Academy of Sciences, Beijing, China
lishun at ucas dot ac dot cn

Danilo Gligoroski

Norwegian University of Science and Technology, Trondheim, Norway
danilog at ntnu dot no

Keywords: AES Linear Layers Hadamard Matrices Related Differentials Counter-measures MDS-Matrix-Construction.

Abstract

In this paper, we study MDS matrices that are specifically designed to prevent the occurrence of related differentials. We investigate MDS matrices with a Hadamard structure and demonstrate that it is possible to construct 4 X 4 Hadamard matrices that effectively eliminate related differentials. Incorporating these matrices into the linear layer of AES-like block-ciphers/hash functions significantly mitigates the attacks that exploit the related differentials property. The central contribution of this paper is to identify crucial underlying relations that determine whether a given 4 X 4 Hadamard matrix exhibits related differentials. By satisfying these relations, the matrix ensures the presence of related differentials, whereas failing to meet them leads to the absence of such differentials. This offers effective mitigation of recently reported attacks on reduced-round AES. Furthermore, we propose a faster search technique to exhaustively verify the presence or absence of related differentials in 8 X 8 Hadamard matrices over finite field of characteristic 2 which requires checking only a subset of involutory matrices in the set. Although most existing studies on constructing MDS matrices primarily focus on lightweight hardware/software implementations, our research additionally introduces a novel perspective by emphasizing the importance of MDS matrix construction in relation to their resistance against differential cryptanalysis.

References

[AES01]

Advanced Encryption Standard (AES). National Institute of Standards and Technology (NIST), FIPS PUB 197, U.S. Department of Commerce. November 2001.

Google Scholar ePrint

[AF14]

Daniel Augot and Matthieu Finiasz. Direct construction of recursive MDS diffusion layers using shortened BCH codes. In Fast Software Encryption: 21st International Workshop, FSE 2014, London, UK, March 3-5, 2014. Revised Selected Papers 21, pages 3–17. 2014. Springer. DOI: 10.1007/978-3-662-46706-0_1

Google Scholar ePrint

[Ber13]

Thierry P Berger. Construction of recursive MDS diffusion layers from Gabidulin codes. In Progress in Cryptology–INDOCRYPT 2013: 14th International Conference on Cryptology in India, Mumbai, India, December 7-10, 2013. Proceedings 14, pages 274–285. 2013. Springer. DOI: 10.1007/978-3-319-03515-4_18

Google Scholar ePrint

[BKL16]

Christof Beierle, Thorsten Kranz, and Gregor Leander. Lightweight Multiplication in GF(2n) with Applications to MDS Matrices. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I, volume 9814 of Lecture Notes in Computer Science, pages 625–653. 2016. Springer. DOI: 10.1007/978-3-662-53018-4_23

Google Scholar ePrint

[BR00]

Paulo Barreto and Vincent Rijmen. The Anubis block cipher. https://tinyurl.com/3bnfnekc. First open NESSIE Workshop, Leuven. 2000.

Google Scholar ePrint

[CLM16]

Victor Cauchois, Pierre Loidreau, and Nabil Merkiche. Direct construction of quasi-involutory recursive-like MDS matrices from 2-cyclic codes. IACR Transactions on Symmetric Cryptology, 2016. DOI: 10.13154/TOSC.V2016.I2.80-98

Google Scholar ePrint

[DL18]

Sébastien Duval and Gaëtan Leurent. MDS Matrices with Lightweight Circuits. IACR Trans. Symmetric Cryptol., 2018(2):48–78, 2018. DOI: 10.13154/tosc.v2018.i2.48-78

Google Scholar ePrint

[DR02]

Joan Daemen and Vincent Rijmen. The design of Rijndael: AES-the advanced encryption standard. Information Security and Cryptography, 2002. DOI: 10.1007/978-3-662-04722-4

Google Scholar ePrint

[DR09]

Joan Daemen and Vincent Rijmen. New Criteria for Linear Maps in AES-like Ciphers. Cryptogr. Commun., 1(1):47–69, 2009. DOI: 10.1007/s12095-008-0003-x

Google Scholar ePrint

[GBR22]

Navid Ghaedi Bardeh and Vincent Rijmen. New Key-Recovery Attack on Reduced-Round AES. IACR Transactions on Symmetric Cryptology, 2022(2):43–62, Jun. 2022. DOI: 10.46586/tosc.v2022.i2.43-62

Google Scholar ePrint

[GPP11]

Jian Guo, Thomas Peyrin, and Axel Poschmann. The PHOTON family of lightweight hash functions. In Advances in Cryptology–CRYPTO 2011: 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings 31, pages 222–239. 2011. Springer. DOI: 10.1007/978-3-642-22792-9_13

Google Scholar ePrint

[GPPR11]

Jian Guo, Thomas Peyrin, Axel Poschmann, and Matt Robshaw. The LED block cipher. In Cryptographic Hardware and Embedded Systems–CHES 2011: 13th International Workshop, Nara, Japan, September 28–October 1, 2011. Proceedings 13, pages 326–341. 2011. Springer. DOI: 10.1007/978-3-642-23951-9_22

Google Scholar ePrint

[GPV17]

Kishan Chand Gupta, Sumit Kumar Pandey, and Ayineedi Venkateswarlu. Towards a general construction of recursive MDS diffusion layers. Designs, Codes and Cryptography, 82:179–195, 2017. DOI: 10.1007/S10623-016-0261-0

Google Scholar ePrint

[JPST17]

Jérémy Jean, Thomas Peyrin, Siang Meng Sim, and Jade Tourteaux. Optimizing Implementations of Lightweight Building Blocks. IACR Trans. Symmetric Cryptol., 2017(4):130–168, 2017. DOI: 10.13154/tosc.v2017.i4.130-168

Google Scholar ePrint

[KLSW17]

Thorsten Kranz, Gregor Leander, Ko Stoffelen, and Friedrich Wiemer. Shorter linear straight-line programs for MDS matrices. IACR Transactions on Symmetric Cryptology, 2017. DOI: 10.13154/TOSC.V2017.I4.188-211

Google Scholar ePrint

[LS16]

Meicheng Liu and Siang Meng Sim. Lightweight MDS Generalized Circulant Matrices. In Thomas Peyrin, editor, Fast Software Encryption - 23rd International Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers, volume 9783 of Lecture Notes in Computer Science, pages 101–120. 2016. Springer. DOI: 10.1007/978-3-662-52993-5_6

Google Scholar ePrint

[LSL⁺19]

Shun Li, Siwei Sun, Chaoyun Li, Zihao Wei, and Lei Hu. Constructing low-latency involutory MDS matrices with lightweight circuits. IACR Transactions on Symmetric Cryptology, 2019. DOI: 10.13154/TOSC.V2019.I1.84-117

Google Scholar ePrint

[LSS⁺20]

Shun Li, Siwei Sun, Danping Shi, Chaoyun Li, and Lei Hu. Lightweight Iterative MDS Matrices: How Small Can We Go?. IACR Transactions on Symmetric Cryptology, 2019, Issue 4:147-170, 2020. DOI: 10.13154/tosc.v2019.i4.147-170

Google Scholar ePrint

[LW16]

Yongqiang Li and Mingsheng Wang. On the Construction of Lightweight Circulant Involutory MDS Matrices. In Thomas Peyrin, editor, Fast Software Encryption - 23rd International Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers, volume 9783 of Lecture Notes in Computer Science, pages 121–139. 2016. Springer. DOI: 10.1007/978-3-662-52993-5_7

Google Scholar ePrint

[LW17]

Chaoyun Li and Qingju Wang. Design of Lightweight Linear Diffusion Layers from Near-MDS Matrices. IACR Trans. Symmetric Cryptol., 2017(1):129–155, 2017. DOI: 10.13154/tosc.v2017.i1.129-155

Google Scholar ePrint

[MS77]

F. Jessie MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. Elsevier 1977.

Google Scholar ePrint

[PSA⁺18]

Meltem Kurt Pehlivanoğlu, Muharrem Tolga Sakallı, Sedat Akleylek, Nevcihan Duru, and Vincent Rijmen. Generalisation of Hadamard matrix to generate involutory MDS matrices for lightweight cryptography. IET Information Security, 12(4):348-355, 2018. DOI: https://doi.org/10.1049/iet-ifs.2017.0156

Google Scholar ePrint

[RBH17]

Sondre Rønjom, Navid Ghaedi Bardeh, and Tor Helleseth. Yoyo Tricks with AES. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part I, volume 10624 of LNCS, pages 217–243. December 2017. Springer, Heidelberg. DOI: 10.1007/978-3-319-70694-8_8

Google Scholar ePrint

[SKOP15]

Siang Meng Sim, Khoongming Khoo, Frédérique Oggier, and Thomas Peyrin. Lightweight MDS Involution Matrices. In Gregor Leander, editor, Fast Software Encryption, pages 471–493, Berlin, Heidelberg. 2015. Springer Berlin Heidelberg. DOI: 10.1007/978-3-662-48116-5_23

Google Scholar ePrint

[SS16a]

Sumanta Sarkar and Siang Meng Sim. A Deeper Understanding of the XOR Count Distribution in the Context of Lightweight Cryptography. In David Pointcheval, Abderrahmane Nitaj, and Tajjeeddine Rachidi, editors, Progress in Cryptology - AFRICACRYPT 2016 - 8th International Conference on Cryptology in Africa, Fes, Morocco, April 13-15, 2016, Proceedings, volume 9646 of Lecture Notes in Computer Science, pages 167–182. 2016. Springer. DOI: 10.1007/978-3-319-31517-1_9

Google Scholar ePrint

[SS16b]

Sumanta Sarkar and Habeeb Syed. Lightweight Diffusion Layer: Importance of Toeplitz Matrices. IACR Trans. Symmetric Cryptol., 2016(1):95–113, 2016. DOI: 10.13154/tosc.v2016.i1.95-113

Google Scholar ePrint

[SS17]

Sumanta Sarkar and Habeeb Syed. Analysis of Toeplitz MDS Matrices. In Josef Pieprzyk and Suriadi Suriadi, editors, Information Security and Privacy - 22nd Australasian Conference, ACISP 2017, Auckland, New Zealand, July 3-5, 2017, Proceedings, Part II, volume 10343 of Lecture Notes in Computer Science, pages 3–18. 2017. Springer. DOI: 10.1007/978-3-319-59870-3_1

Google Scholar ePrint

[TTKS18]

Dylan Toh, Jacob Teo, Khoongming Khoo, and Siang Meng Sim. Lightweight MDS serial-type matrices with minimal fixed XOR count. In Progress in Cryptology–AFRICACRYPT 2018: 10th International Conference on Cryptology in Africa, Marrakesh, Morocco, May 7–9, 2018, Proceedings 10, pages 51–71. 2018. Springer. DOI: 10.1007/978-3-319-89339-6_4

Google Scholar ePrint

[WWW13]

Shengbao Wu, Mingsheng Wang, and Wenling Wu. Recursive Diffusion Layers for (Lightweight) Block Ciphers and Hash Functions. In Lars R. Knudsen and Huapeng Wu, editors, SAC 2012, volume 7707 of LNCS, pages 355–371. August 2013. Springer, Heidelberg. DOI: 10.1007/978-3-642-35999-6_23

Google Scholar ePrint

[XZL⁺20]

Zejun Xiang, Xiangyong Zeng, Da Lin, Zhenzhen Bao, and Shasha Zhang. Optimizing Implementations of Linear Layers. IACR Trans. Symm. Cryptol., 2020(2):120–145, 2020. DOI: 10.13154/tosc.v2020.i2.120-145

Google Scholar ePrint

[ZWS18]

Lijing Zhou, Licheng Wang, and Yiru Sun. On Efficient Constructions of Lightweight MDS Matrices. IACR Trans. Symmetric Cryptol., 2018(1):180–200, 2018. DOI: 10.13154/tosc.v2018.i1.180-200

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a6ksdk5vt

History

Submitted: 2025-01-13
Accepted: 2025-03-11
Published: 2025-04-08

How to cite

Sonu Jha, Shun Li, and Danilo Gligoroski, Construction of Hadamard-based MixColumns Matrices Resistant to Related-Differential Cryptanalysis. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/a6ksdk5vt.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{10.62056/a6ksdk5vt,
         author={Sonu Jha and Shun Li and Danilo Gligoroski},
         title={Construction of Hadamard-based MixColumns Matrices Resistant to Related-Differential Cryptanalysis},
         volume={2},
         number={1},
         year={2025},
         date={2025-04-08},
         issn={3006-5496},
         doi={10.62056/a6ksdk5vt},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}

TY  - JOUR
AU  - Sonu Jha
AU  - Shun Li
AU  - Danilo Gligoroski
PY  - 2025
TI  - Construction of Hadamard-based MixColumns Matrices Resistant to Related-Differential Cryptanalysis
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 2
IS  - 1
DO  - 10.62056/a6ksdk5vt
UR  - https://doi.org/10.62056/a6ksdk5vt
AB  - <p>  In this paper, we study MDS matrices that are specifically designed to prevent the occurrence of related differentials. We investigate MDS matrices with a Hadamard structure and demonstrate that it is possible to construct 4 X 4 Hadamard matrices that effectively eliminate related differentials. Incorporating these matrices into the linear layer of AES-like block-ciphers/hash functions significantly mitigates the attacks that exploit the related differentials property. The central contribution of this paper is to identify crucial underlying relations that determine whether a given 4 X 4 Hadamard matrix exhibits related differentials. By satisfying these relations, the matrix ensures the presence of related differentials, whereas failing to meet them leads to the absence of such differentials. This offers effective mitigation of recently reported attacks on reduced-round AES. Furthermore, we propose a faster search technique to exhaustively verify the presence or absence of related differentials in 8 X 8 Hadamard matrices over finite field of characteristic 2 which requires checking only a subset of involutory matrices in the set. Although most existing studies on constructing MDS matrices primarily focus on lightweight hardware/software implementations, our research additionally introduces a novel perspective by emphasizing the importance of MDS matrix construction in relation to their resistance against differential cryptanalysis. </p>
ER  -

Sonu Jha, Shun Li, and Danilo Gligoroski, Construction of Hadamard-based MixColumns Matrices Resistant to Related-Differential Cryptanalysis. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/a6ksdk5vt.