MAYO Key Recovery by Fixing Vinegar Seeds
Authors
Sönke Jendral, Elena Dubrova
Sönke Jendral
KTH Royal Institute of Technology, Stockholm, Sweden
jendral at kth dot se
jendral at kth dot se
Elena Dubrova
KTH Royal Institute of Technology, Stockholm, Sweden
dubrova at kth dot se
dubrova at kth dot se
Keywords:
Fault injection
MAYO
Multivariate cryptography
Post-quantum digital signature
Key recovery attack
Abstract
As the industry prepares for the transition to post-quantum secure public key cryptographic algorithms, vulnerability analysis of their implementations is gaining importance. A theoretically secure cryptographic algorithm should also be able to withstand the challenges of physical attacks in real-world environments. MAYO is a candidate in the ongoing second round of the NIST post-quantum standardization process for selecting additional digital signature schemes. This paper demonstrates three first-order single-execution fault injection attacks on the official MAYO implementation on the ARM Cortex-M4. By using voltage glitching to disrupt the computation of the vinegar seed during the signature generation, we enable the recovery of the secret key directly from the faulty signatures. Our experimental results show that the success rates of the fault attacks in a single execution are 36%, 82%, and 99%, respectively. They emphasize the importance of developing countermeasures against fault attacks prior to the widespread deployment of post-quantum algorithms like MAYO.
References
[ACK+23]
Thomas Aulbach, Fabio Campos, Juliane Krämer, Simona Samardjiska, and Marc Stöttinger. Separating Oil and Vinegar with a Single Trace Side-Channel Assisted Kipnis-Shamir Attack on UOV. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2023(3):221–245, 2023. DOI: 10.46586/TCHES.V2023.I3.221-245
[AHKS22]
Amin Abdulrahman, Vincent Hwang, Matthias J. Kannwischer, and Amber Sprenkels. Faster Kyber and Dilithium on the Cortex-M4. In Giuseppe Ateniese and Daniele Venturi, editors, Applied Cryptography and Network Security - 20th International Conference, ACNS 2022, Rome, Italy, June 20-23, 2022, Proceedings, volume 13269 of Lecture Notes in Computer Science, pages 853–871. 2022. Springer. DOI: 10.1007/978-3-031-09234-3_42
[AKKM22]
Thomas Aulbach, Tobias Kovats, Juliane Krämer, and Soundes Marzougui. Recovering Rainbow's Secret Key with a First-Order Fault Attack. In Lejla Batina and Joan Daemen, editors, Progress in Cryptology - AFRICACRYPT 2022, pages 348–368, Cham. 2022. Springer Nature Switzerland. DOI: 10.1007/978-3-031-17433-9_15
[AMSU24]
Thomas Aulbach, Soundes Marzougui, Jean-Pierre Seifert, and Vincent Quentin Ulitzsch. MAYo or MAY-not: Exploring Implementation Security of the Post-Quantum Signature Scheme MAYO Against Physical Attacks. In Workshop on Fault Detection and Tolerance in Cryptography, FDTC 2024, Halifax, NS, Canada, September 4, 2024, pages 28–33. 2024. IEEE. DOI: 10.1109/FDTC64268.2024.00012
[BBBP13]
Alessandro Barenghi, Guido Marco Bertoni, Luca Breveglieri, and Gerardo Pelosi. A fault induction technique based on voltage underfeeding with application to attacks against AES and RSA. J. Syst. Softw., 86(7):1864–1878, 2013. DOI: 10.1016/J.JSS.2013.02.021
[BBPP09]
Alessandro Barenghi, Guido Bertoni, Emanuele Parrinello, and Gerardo Pelosi. Low Voltage Fault Attacks on the RSA Cryptosystem. In Luca Breveglieri, Israel Koren, David Naccache, Elisabeth Oswald, and Jean-Pierre Seifert, editors, Sixth International Workshop on Fault Diagnosis and Tolerance in Cryptography, FDTC 2009, Lausanne, Switzerland, 6 September 2009, pages 23–31. 2009. IEEE Computer Society. DOI: 10.1109/FDTC.2009.30
[BCC+23]
Ward Beullens, Fabio Campos, Sofía Celi, Basil Hess, and Matthias J. Kannwischer. MAYO. June 2023.
[BCC+24]
Ward Beullens, Fabio Campos, Sofía Celi, Basil Hess, and Matthias J. Kannwischer. Nibbling MAYO: Optimized Implementations for AVX2 and Cortex-M4. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2024(2):252–275, 2024. DOI: 10.46586/TCHES.V2024.I2.252-275
[BCD+23]
Ward Beullens, Ming-Shing Chen, Jintai Ding, Boru Gong, Matthias J. Kannwischer, Jacques Patarin, Bo-Yuan Peng, Dieter Schmidt, Cheng-Jhih Shih, Chengdong Tao, and Bo-Yin Yang. UOV: Unbalanced Oil and Vinegar. May 2023.
[BDPVA11]
Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. Cryptographic sponge functions. 2011.
[Bel05]
Fabrice Bellard. QEMU, a Fast and Portable Dynamic Translator. In Proceedings of the FREENIX Track: 2005 USENIX Annual Technical Conference, April 10-15, 2005, Anaheim, CA, USA, pages 41–46. 2005. USENIX.
[Beu21]
Ward Beullens. Improved Cryptanalysis of UOV and Rainbow. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part I, volume 12696 of Lecture Notes in Computer Science, pages 348–373. 2021. Springer. DOI: 10.1007/978-3-030-77870-5_13
[Beu22]
Ward Beullens. MAYO: Practical Post-quantum Signatures from Oil-and-Vinegar Maps. In Riham AlTawy and Andreas Hülsing, editors, Selected Areas in Cryptography, pages 355–376, Cham. 2022. Springer International Publishing. DOI: 10.1007/978-3-030-99277-4_17
[Beu24]
Ward Beullens. MAYO: Overview + Updates. NIST PQC Seminar. September 2024.
[BFP19]
Claudio Bozzato, Riccardo Focardi, and Francesco Palmarini. Shaping the Glitch: Optimizing Voltage Fault Injection Attacks. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2019(2):199–224, 2019. DOI: 10.13154/tches.v2019.i2.199-224
[BPB10]
Stanislav Bulygin, Albrecht Petzoldt, and Johannes Buchmann. Towards Provable Security of the Unbalanced Oil and Vinegar Signature Scheme under Direct Attacks. In Guang Gong and Kishan Chand Gupta, editors, Progress in Cryptology - INDOCRYPT 2010 - 11th International Conference on Cryptology in India, Hyderabad, India, December 12-15, 2010. Proceedings, volume 6498 of Lecture Notes in Computer Science, pages 17–32. 2010. Springer. DOI: 10.1007/978-3-642-17401-8_3
[CDSLN20]
Domenico Cotroneo, Luigi De Simone, Pietro Liguori, and Roberto Natella. ProFIPy: Programmable Software Fault Injection as-a-Service. In 2020 50th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 364-372. 2020. DOI: 10.1109/DSN48063.2020.00052
[DHHB08]
Ashish Darbari, Bashir Al Hashimi, Peter Harrod, and Daryl Bradley. A New Approach for Transient Fault Injection Using Symbolic Simulation. In 2008 14th IEEE International On-Line Testing Symposium, pages 93-98. 2008. DOI: 10.1109/IOLTS.2008.59
[DYC+08]
Jintai Ding, Bo-Yin Yang, Chia-Hsin Owen Chen, Ming-Shing Chen, and Chen-Mou Cheng. New Differential-Algebraic Attacks and Reparametrization of Rainbow. In Steven M. Bellovin, Rosario Gennaro, Angelos D. Keromytis, and Moti Yung, editors, Applied Cryptography and Network Security, 6th International Conference, ACNS 2008, New York, NY, USA, June 3-6, 2008. Proceedings, volume 5037 of Lecture Notes in Computer Science, pages 242–257. 2008. DOI: 10.1007/978-3-540-68914-0_15
[FKNT22]
Hiroki Furue, Yutaro Kiyomura, Tatsuya Nagasawa, and Tsuyoshi Takagi. A New Fault Attack on UOV Multivariate Signature Scheme. In Jung Hee Cheon and Thomas Johansson, editors, Post-Quantum Cryptography, pages 124–143, Cham. 2022. Springer International Publishing. DOI: 10.1007/978-3-031-17234-2_7
[GJN20]
Qian Guo, Thomas Johansson, and Alexander Nilsson. A Key-Recovery Timing Attack on Post-quantum Primitives Using the Fujisaki-Okamoto Transformation and Its Application on FrodoKEM. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17-21, 2020, Proceedings, Part II, volume 12171 of Lecture Notes in Computer Science, pages 359–386. 2020. Springer. DOI: 10.1007/978-3-030-56880-1_13
[HGA+21]
Florian Hauschild, Kathrin Garb, Lukas Auer, Bodo Selmke, and Johannes Obermaier. ARCHIE: A QEMU-Based Framework for Architecture-Independent Evaluation of Faults. In 18th Workshop on Fault Detection and Tolerance in Cryptography, FDTC 2021, Milan, Italy, September 17, 2021, pages 20–30. 2021. IEEE. DOI: 10.1109/FDTC53659.2021.00013
[HSP21]
Max Hoffmann, Falk Schellenberg, and Christof Paar. ARMORY: Fully Automated and Exhaustive Fault Simulation on ARM-M Binaries. IEEE Trans. Inf. Forensics Secur., 16:1058–1073, 2021. DOI: 10.1109/TIFS.2020.3027143
[HTS11]
Yasufumi Hashimoto, Tsuyoshi Takagi, and Kouichi Sakurai. General Fault Attacks on Multivariate Public Key Cryptosystems. In Bo-Yin Yang, editor, Post-Quantum Cryptography, pages 1–18, Berlin, Heidelberg. 2011. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-25405-5_1
[JMD24]
Sönke Jendral, John Preuß Mattsson, and Elena Dubrova. A Single-Trace Fault Injection Attack on Hedged Module Lattice Digital Signature Algorithm (ML-DSA). In Workshop on Fault Detection and Tolerance in Cryptography, FDTC 2024, Halifax, NS, Canada, September 4, 2024, pages 34–43. 2024. IEEE. DOI: 10.1109/FDTC64268.2024.00013
[KCN21]
Alec Kirkley, George T. Cantwell, and M. E. J. Newman. Belief propagation for networks with loops. Science Advances, 7(17):eabf1211, 2021. DOI: 10.1126/sciadv.abf1211
[Kin76]
James C. King. Symbolic execution and program testing. Commun. ACM, 19(7):385–394, July 1976. DOI: 10.1145/360248.360252
[KL19]
Juliane Krämer and Mirjam Loiero. Fault Attacks on UOV and Rainbow. In Ilia Polian and Marc Stöttinger, editors, Constructive Side-Channel Analysis and Secure Design, pages 193–214, Cham. 2019. Springer International Publishing. DOI: 10.1007/978-3-030-16350-1_11
[KS98]
Aviad Kipnis and Adi Shamir. Cryptanalysis of the Oil & Vinegar Signature Scheme. In Hugo Krawczyk, editor, Advances in Cryptology - CRYPTO '98, 18th Annual International Cryptology Conference, Santa Barbara, California, USA, August 23-27, 1998, Proceedings, volume 1462 of Lecture Notes in Computer Science, pages 257–266. 1998. Springer. DOI: 10.1007/BFB0055733
[Lan22]
Julien Lancia. Detecting fault injection vulnerabilities in binaries with symbolic execution. In 2022 14th International Conference on Electronics, Computers and Artificial Intelligence (ECAI), pages 1-8. 2022. DOI: 10.1109/ECAI54874.2022.9847500
[LFBP24]
Guilhem Lacombe, David Feliot, Etienne Boespflug, and Marie-Laure Potet. Combining static analysis and dynamic symbolic execution in a toolchain to detect fault injection vulnerabilities. Journal of Cryptographic Engineering, 14(1):147–164, April 2024. DOI: 10.1007/s13389-023-00310-8
[MIS20]
Koksal Mus, Saad Islam, and Berk Sunar. QuantumHammer: A Practical Hybrid Attack on the LUOV Signature Scheme. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 1071–1084, New York, NY, USA. 2020. Association for Computing Machinery. DOI: 10.1145/3372297.3417272
[MTO24]
Kit Murdock, Martin Thompson, and David F. Oswald. FaultFinder: Lightning-fast, Multi-architectural Fault Injection Simulation. In Chip-Hong Chang, Ulrich Rührmair, Jakub Szefer, Lejla Batina, and Francesco Regazzoni, editors, Proceedings of the 2024 Workshop on Attacks and Solutions in Hardware Security, ASHES 2024, Salt Lake City, UT, USA, October 14-18, 2024, pages 78–88. 2024. ACM. DOI: 10.1145/3689939.3695788
[{Nat}15]
National Institute of Standards and Technology. SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. Technical report number NIST FIPS 202, National Institute of Standards and Technology. August 2015.
[{Nat}23]
National Institute of Standards and Technology. NIST Announces Additional Digital Signature Candidates for the PQC Standardization Process. June 2023.
[{Nat}24a]
National Institute of Standards and Technology. Module-Lattice-Based Digital Signature Standard. Technical report number NIST FIPS 204, National Institute of Standards and Technology. August 2024.
[{Nat}24b]
National Institute of Standards and Technology. Module-Lattice-Based Key Encapsulation Mechanism Standard. Technical report number NIST FIPS 203, National Institute of Standards and Technology. August 2024.
[{Nat}24c]
National Institute of Standards and Technology. Stateless Hash-Based Digital Signature Standard. Technical report number NIST FIPS 205, National Institute of Standards and Technology. August 2024.
[ND15]
Anh Quynh Nguyen and Hoang Vu Dang. Unicorn: Next generation CPU emulator framework. BlackHat USA, 476, 2015.
[O'F16]
Colin O'Flynn. Fault Injection using Crowbars on Embedded Systems. IACR Cryptol. ePrint Arch., 2016.
[Pat97]
Jacques Patarin. The oil and vinegar signature scheme. In Presented at the Dagstuhl Workshop on Cryptography September 1997. 1997.
[P{\'{e}}b24]
Pierre Pébereau. One Vector to Rule Them All: Key Recovery from One Vector in UOV Schemes. In Markku-Juhani O. Saarinen and Daniel Smith-Tone, editors, Post-Quantum Cryptography - 15th International Workshop, PQCrypto 2024, Oxford, UK, June 12-14, 2024, Proceedings, Part II, volume 14772 of Lecture Notes in Computer Science, pages 92–108. 2024. Springer. DOI: 10.1007/978-3-031-62746-0_5
[PNKI13]
Karthik Pattabiraman, Nithin M. Nakka, Zbigniew T. Kalbarczyk, and Ravishankar K. Iyer. SymPLFIED: Symbolic Program-Level Fault Injection and Error Detection Framework. IEEE Transactions on Computers, 62(11):2292-2307, 2013. DOI: 10.1109/TC.2012.219
[PPM17]
Robert Primas, Peter Pessl, and Stefan Mangard. Single-Trace Side-Channel Attacks on Masked Lattice-Based Encryption. In Wieland Fischer and Naofumi Homma, editors, Cryptographic Hardware and Embedded Systems - CHES 2017 - 19th International Conference, Taipei, Taiwan, September 25-28, 2017, Proceedings, volume 10529 of Lecture Notes in Computer Science, pages 513–533. 2017. Springer. DOI: 10.1007/978-3-319-66787-4_25
[Risnd]
Riscure. Riscure FiSim. https://github.com/Keysight/FiSim. n.d..
[RRB+19]
Prasanna Ravi, Debapriya Basu Roy, Shivam Bhasin, Anupam Chattopadhyay, and Debdeep Mukhopadhyay. Number "Not Used" Once - Practical Fault Attack on pqm4 Implementations of NIST Candidates. In Ilia Polian and Marc Stöttinger, editors, Constructive Side-Channel Analysis and Secure Design - 10th International Workshop, COSADE 2019, Darmstadt, Germany, April 3-5, 2019, Proceedings, volume 11421 of Lecture Notes in Computer Science, pages 232–250. 2019. Springer. DOI: 10.1007/978-3-030-16350-1_13
[SK20]
Kyung-Ah Shim and Namhun Koo. Algebraic Fault Analysis of UOV and Rainbow With the Leakage of Random Vinegar Values. IEEE Transactions on Information Forensics and Security, 15:2429-2439, 2020. DOI: 10.1109/TIFS.2020.2969555
[SMA+24]
Oussama Sayari, Soundes Marzougui, Thomas Aulbach, Juliane Krämer, and Jean-Pierre Seifert. HaMAYO: A Fault-Tolerant Reconfigurable Hardware Implementation of the MAYO Signature Scheme. In Romain Wacquez and Naofumi Homma, editors, Constructive Side-Channel Analysis and Secure Design - 15th International Workshop, COSADE 2024, Gardanne, France, April 9-10, 2024, Proceedings, volume 14595 of Lecture Notes in Computer Science, pages 240–259. 2024. Springer. DOI: 10.1007/978-3-031-57543-3_13
[SWS+16]
Yan Shoshitaishvili, Ruoyu Wang, Christopher Salls, Nick Stephens, Mario Polino, Andrew Dutcher, John Grosen, Siji Feng, Christophe Hauser, Christopher Krügel, and Giovanni Vigna. SOK: (State of) The Art of War: Offensive Techniques in Binary Analysis. In IEEE Symposium on Security and Privacy, SP 2016, San Jose, CA, USA, May 22-26, 2016, pages 138–157. 2016. IEEE Computer Society. DOI: 10.1109/SP.2016.17
[YFW00]
Jonathan S. Yedidia, William T. Freeman, and Yair Weiss. Generalized Belief Propagation. In Todd K. Leen, Thomas G. Dietterich, and Volker Tresp, editors, Advances in Neural Information Processing Systems 13, Papers from Neural Information Processing Systems (NIPS) 2000, Denver, CO, USA, pages 689–695. 2000. MIT Press.
PDF
History
Submitted: 2024-10-04
Accepted: 2024-12-03
Published: 2025-01-13
Accepted: 2024-12-03
Published: 2025-01-13
How to cite
Sönke Jendral and Elena Dubrova, MAYO Key Recovery by Fixing Vinegar Seeds. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/ab0ljbkrz.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.