A Note on Related-Tweakey Impossible Differential Attacks
Authors
Xavier Bonnetain, Virginie Lallemand
Abstract
In this note we review the technique proposed at ToSC 2018 by Sadeghi et al. for attacks built upon several related-tweakey impossible differential trails. We show that the initial encryption queries are improper and lead the authors to misevaluate a filtering value in the key recovery phase. We identified 4 other papers (from Eurocrypt, DCC, and 2 from ToSC) that follow on the results of Sadeghi et al. and in three of them the flawed technique was reused.
We thus present a careful analysis of these types of attacks and give generic complexity formulas similar to the ones proposed by Boura et al. at Asiacrypt 2014. We apply these to the aforementioned papers and provide patched versions of their attacks. The main consequence is an increase in the memory complexity. We show that in many cases (a notable exception being quantum impossible differentials) it is possible to recover the numeric time estimates of the flawed analysis, and in all cases we were able to build a correct attack reaching the same number of rounds.
References
[ALP+19]
Elena Andreeva, Virginie Lallemand, Antoon Purnal, Reza Reyhanitabar, Arnab Roy, and Damian Vizár. Forkcipher: A New Primitive for Authenticated Encryption of Very Short Messages. In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology – ASIACRYPT 2019, Part II, volume 11922 of Lecture Notes in Computer Science, pages 153–182. December 2019. Springer, Cham. DOI: 10.1007/978-3-030-34621-8_6
[BA08]
Behnam Bahrak and Mohammad Reza Aref. Impossible differential attack on seven-round AES-128. IET Inf. Secur., 2(2):28–32, 2008. DOI: 10.1049/IET-IFS:20070078
[BBS99]
Eli Biham, Alex Biryukov, and Adi Shamir. Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials. In Jacques Stern, editor, Advances in Cryptology – EUROCRYPT'99, volume 1592 of Lecture Notes in Computer Science, pages 12–23. May 1999. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48910-X_2
[BDL20]
Augustin Bariant, Nicolas David, and Gaëtan Leurent. Cryptanalysis of Forkciphers. IACR Transactions on Symmetric Cryptology, 2020(1):233–265, 2020. DOI: 10.13154/tosc.v2020.i1.233-265
[BJK+16]
Christof Beierle, Jérémy Jean, Stefan Kölbl, Gregor Leander, Amir Moradi, Thomas Peyrin, Yu Sasaki, Pascal Sasdrich, and Siang Meng Sim. The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology – CRYPTO 2016, Part II, volume 9815 of Lecture Notes in Computer Science, pages 123–153. August 2016. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-53008-5_5
[BNS14]
Christina Boura, María Naya-Plasencia, and Valentin Suder. Scrutinizing and Improving Impossible Differential Attacks: Applications to CLEFIA, Camellia, LBlock and Simon. In Palash Sarkar and Tetsu Iwata, editors, Advances in Cryptology – ASIACRYPT 2014, Part I, volume 8873 of Lecture Notes in Computer Science, pages 179–199. December 2014. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-45611-8_10
[BS91]
Eli Biham and Adi Shamir. Differential Cryptanalysis of DES-like Cryptosystems. In Alfred J. Menezes and Scott A. Vanstone, editors, Advances in Cryptology – CRYPTO'90, volume 537 of Lecture Notes in Computer Science, pages 2–21. August 1991. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-38424-3_1
[DNS24]
Nicolas David, María Naya-Plasencia, and André Schrottenloher. Quantum impossible differential attacks: applications to AES and SKINNY. Designs, Codes and Cryptography, 92(3):723–751, 2024. DOI: 10.1007/s10623-023-01280-y
[HGSE23]
Hosein Hadipour, Simon Gerhalter, Sadegh Sadeghi, and Maria Eichlseder. Improved Search for Integral, Impossible-Differential and Zero-Correlation Attacks: Application to Ascon, ForkSKINNY, SKINNY, MANTIS, PRESENT and QARMAv2. https://eprint.iacr.org/archive/2023/1701/20231123:125414. Cryptology ePrint Archive, Report 2023/1701, version 20231123:125414. 2023.
[HGSE24]
Hosein Hadipour, Simon Gerhalter, Sadegh Sadeghi, and Maria Eichlseder. Improved Search for Integral, Impossible Differential and Zero-Correlation Attacks Application to Ascon, ForkSKINNY, SKINNY, MANTIS, PRESENT and QARMAv2. IACR Transactions on Symmetric Cryptology, 2024(1):234–325, 2024. DOI: 10.46586/tosc.v2024.i1.234-325
[HSE22]
Hosein Hadipour, Sadegh Sadeghi, and Maria Eichlseder. Finding the Impossible: Automated Search for Full Impossible Differential, Zero-Correlation, and Integral Attacks. Cryptology ePrint Archive, Report 2022/1147. 2022.
[HSE23]
Hosein Hadipour, Sadegh Sadeghi, and Maria Eichlseder. Finding the Impossible: Automated Search for Full Impossible-Differential, Zero-Correlation, and Integral Attacks. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, Part IV, volume 14007 of Lecture Notes in Computer Science, pages 128–157. April 2023. Springer, Cham. DOI: 10.1007/978-3-031-30634-1_5
[Jea16]
Jérémy Jean. TikZ for Cryptographers. https://www.iacr.org/authors/tikz/. 2016.
[JNP14]
Jérémy Jean, Ivica Nikolic, and Thomas Peyrin. Tweaks and Keys for Block Ciphers: The TWEAKEY Framework. In Palash Sarkar and Tetsu Iwata, editors, Advances in Cryptology – ASIACRYPT 2014, Part II, volume 8874 of Lecture Notes in Computer Science, pages 274–288. December 2014. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-45608-8_15
[Knu98]
Lars Knudsen. DEAL-a 128-bit block cipher. complexity, 258(2):216, 1998.
[NSS20a]
Yusuke Naito, Yu Sasaki, and Takeshi Sugawara. Lightweight Authenticated Encryption Mode Suitable for Threshold Implementation. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, Part II, volume 12106 of Lecture Notes in Computer Science, pages 705–735. May 2020. Springer, Cham. DOI: 10.1007/978-3-030-45724-2_24
[NSS20b]
Yusuke Naito, Yu Sasaki, and Takeshi Sugawara. Lightweight Authenticated Encryption Mode Suitable for Threshold Implementation. Cryptology ePrint Archive, Report 2020/542. 2020.
[NSS22]
Yusuke Naito, Yu Sasaki, and Takeshi Sugawara. Secret Can Be Public: Low-Memory AEAD Mode for High-Order Masking. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, Part III, volume 13509 of Lecture Notes in Computer Science, pages 315–345. August 2022. Springer, Cham. DOI: 10.1007/978-3-031-15982-4_11
[SMB18]
Sadegh Sadeghi, Tahereh Mohammadi, and Nasour Bagheri. Cryptanalysis of Reduced round SKINNY Block Cipher. IACR Transactions on Symmetric Cryptology, 2018(3):124–162, 2018. DOI: 10.13154/tosc.v2018.i3.124-162
[ZWF07]
Wentao Zhang, Wenling Wu, and Dengguo Feng. New Results on Impossible Differential Cryptanalysis of Reduced AES. In Kil-Hyun Nam and Gwangsoo Rhee, editors, ICISC 07: 10th International Conference on Information Security and Cryptology, volume 4817 of Lecture Notes in Computer Science, pages 239–250. November 2007. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-76788-6_19
PDF
History
Submitted: 2024-07-09
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Xavier Bonnetain and Virginie Lallemand, A Note on Related-Tweakey Impossible Differential Attacks. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/abbn-4c2h.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.