Unpacking Needs Protection
A Single-Trace Secret Key Recovery Attack on Dilithium
Authors
Ruize Wang, Kalle Ngo, Joel Gärtner, Elena Dubrova
Kalle Ngo
KTH Royal Institute of Technology, Stockholm, Sweden
kngo at kth dot se
kngo at kth dot se
Joel Gärtner
KTH Royal Institute of Technology, Stockholm, Sweden
jgartner at kth dot se
jgartner at kth dot se
Elena Dubrova
KTH Royal Institute of Technology, Stockholm, Sweden
dubrova at kth dot se
dubrova at kth dot se
Keywords:
Dilithium
post-quantum digital signature
key recovery attack
side-channel attack
lattice reduction
Abstract
Most of the previous attacks on Dilithium exploit side-channel information which is leaked during the computation of the polynomial multiplication cs1, where s1 is a small-norm secret and c is a verifier's challenge. In this paper, we present a new attack utilizing leakage during secret key unpacking in the signing algorithm. The unpacking is also used in other post-quantum cryptographic algorithms, including Kyber, because inputs and outputs of their API functions are byte arrays. Exploiting leakage during unpacking is more challenging than exploiting leakage during the computation of cs1 since c varies for each signing, while the unpacked secret key remains constant. Therefore, post-processing is required in the latter case to recover a full secret key. We present two variants of post-processing. In the first one, a half of the coefficients of the secret s1 and the error s2 is recovered by profiled deep learning-assisted power analysis and the rest is derived by solving linear equations based on t = As1 + s2, where A and t are parts of the public key. This case assumes knowledge of the least significant bits of t, t0. The second variant uses lattice reduction to derive s1 without the knowledge of t0. However, it needs a larger portion of s1 to be recovered by power analysis. We evaluate both variants on an ARM Cortex-M4 implementation of Dilithium-2. The experiments show that the attack assuming the knowledge of t0 can recover s1 from a single trace captured from a different from profiling device with a non-negligible probability.
References
[ABC+23]
Melissa Azouaoui, Olivier Bronchain, Gaëtan Cassiers, Clément Hoffmann, Yulia Kuzovkova, Joost Renes, Tobias Schneider, Markus Schönauer, François-Xavier Standaert, and Christine van Vredendaal. Protecting Dilithium against Leakage: Revisited Sensitivity Analysis and Improved Implementations. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2023(4):58–79, 2023. DOI: 10.46586/tches.v2023.i4.58-79
[AHKS22]
Amin Abdulrahman, Vincent Hwang, Matthias J Kannwischer, and Amber Sprenkels. Faster Kyber and Dilithium on the Cortex-M4. In International Conference on Applied Cryptography and Network Security, pages 853–871. 2022. Springer. DOI: 10.1007/978-3-031-09234-3_42
[APS15]
Martin Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of Learning with Errors. Journal of Mathematical Cryptology, 9, October 2015. DOI: 10.1515/jmc-2015-0016
[APSQ06]
Cédric Archambeau, Eric Peeters, F -X Standaert, and J -J Quisquater. Template attacks in principal subspaces. In Cryptographic Hardware and Embedded Systems-CHES 2006: 8th International Workshop, Yokohama, Japan, October 10-13, 2006. Proceedings 8, pages 1–14. 2006. Springer. DOI: 10.1007/11894063_1
[AR21]
Amund Askeland and Sondre Rønjom. A Side-Channel Assisted Attack on NTRU. https://eprint.iacr.org/2021/790. Cryptology ePrint Archive, Paper 2021/790. 2021.
[BAE+24]
Olivier Bronchain, Melissa Azouaoui, Mohamed ElGhamrawy, Joost Renes, and Tobias Schneider. Exploiting small-norm polynomial multiplication with physical attacks: Application to CRYSTALS-Dilithium. IACR Transactions on Cryptographic Hardware and Embedded Systems, Mar. 2024. DOI: 10.46586/tches.v2024.i2.359-383
[BBB+24]
Estuardo Alpirez Bock, Gustavo Banegas, Chris Brzuska, Łukasz Chmielewski, Kirthivaasan Puniamurthy, and Milan Šorf. Breaking DPA-protected Kyber via the pair-pointwise multiplication. In International Conference on Applied Cryptography and Network Security, pages 101–130. 2024. Springer. DOI: 10.1007/978-3-031-54773-7_5
[BCO04]
Eric Brier, Christophe Clavier, and Francis Olivier. Correlation Power Analysis with a Leakage Model. In Marc Joye and Jean-Jacques Quisquater, editors, Cryptographic Hardware and Embedded Systems, pages 16–29. 2004. Springer. DOI: 10.1007/978-3-540-28632-5_2
[BDGL16]
Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New Directions in Nearest Neighbor Searching with Applications to Lattice Sieving. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 10–24, USA. 2016. Society for Industrial and Applied Mathematics. DOI: 10.1137/1.9781611974331.ch2
[BDK+21]
Shi Bai, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien. Stehlé. CRYSTALS-Dilithium Algorithm Specifications and Supporting Documentation. , 2021.
[BFD20]
Martin Brisfors, Sebastian Forsmark, and Elena Dubrova. How Deep Learning Helps Compromising USIM. In Proc. of the 19th Smart Card Research and Advanced Application Conference (CARDIS'2020). Nov. 2020. DOI: 10.1007/978-3-030-68487-7_9
[BMD22]
Martin Brisfors, Michail Moraitis, and Elena Dubrova. Do not rely on clock randomization: A side-channel attack on a protected hardware implementation of AES. In International Symposium on Foundations and Practice of Security, pages 38–53. 2022. Springer. DOI: 10.1007/978-3-031-30122-3_3
[BNGD23]
Linus Backlund, Kalle Ngo, Joel Gärtner, and Elena Dubrova. Secret Key Recovery Attack on Masked and Shuffled Implementations of CRYSTALS-Kyber and Saber. In International Conference on Applied Cryptography and Network Security, pages 159–177. 2023. Springer. DOI: 10.1007/978-3-031-41181-6_9
[BP18]
Leon Groot Bruinderink and Peter Pessl. Differential fault attacks on deterministic lattice signatures. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018. DOI: 10.13154/tches.v2018.i3.21-43
[Bri21]
Martin Brisfors. Advanced Side-Channel Analysis of USIMs, Bluetooth SoCs and MCUs. Master's thesis, School of EECS, KTH, 2021.
[BVC+23]
Alexandre Berzati, Andersson Calle Viera, Maya Chartouny, Steven Madec, Damien Vergnaud, and David Vigilant. Exploiting intermediate value leakage in Dilithium: a template-based approach. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2023(4):188–210, 2023. DOI: 10.46586/tches.v2023.i4.188-210
[CDP17]
Eleonora Cagli, Cécile Dumas, and Emmanuel Prouff. Convolutional Neural Networks with Data Augmentation Against Jitter-Based Countermeasures. In Cryptographic Hardware and Embedded Systems – CHES 2017, pages 45–68. 2017. DOI: 10.1007/978-3-319-66787-4_3
[CGTZ23]
Jean-Sébastien Coron, François Gérard, Matthias Trannoy, and Rina Zeitoun. Improved gadgets for the high-order masking of Dilithium. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2023(4):110–145, 2023. DOI: 10.46586/tches.v2023.i4.110-145
[Che13]
Yuanmi Chen. Réduction de réseau et sécurité concrete du chiffrement completement homomorphe. PhD thesis, Paris 7, 2013.
[CJRR99]
Suresh Chari, Charanjit S. Jutla, Josyula R. Rao, and Pankaj Rohatgi. Towards Sound Approaches to Counteract Power-Analysis Attacks. In Advances in Cryptology - CRYPTO '99, volume 1666, pages 398-412. 1999. Springer. DOI: 10.1007/3-540-48405-1_26
[CKA+21]
Zhaohui Chen, Emre Karabulut, Aydin Aysu, Yuan Ma, and Jiwu Jing. An Efficient Non-Profiled Side-Channel Attack on the CRYSTALS-Dilithium Post-Quantum Signature. In 2021 IEEE 39th International Conference on Computer Design (ICCD), pages 583-590. 2021. DOI: 10.1109/ICCD53106.2021.00094
[CPM+18]
Giovanni Camurati, Sebastian Poeplau, Marius Muench, Tom Hayes, and Aurélien Francillon. Screaming channels: When electromagnetic side channels meet radio transceivers. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 163–177. 2018. DOI: 10.1145/3243734.3243802
[{CW3}a]
CW308 UFO Board. https://rtfm.newae.com/Targets/CW308%20UFO/.
[{CW3}b]
CW308T-STM32F4 target board. https://rtfm.newae.com/Targets/UFO%20Targets/CW308T-STM32F/.
[DMC19]
Quang Do, Ben Martini, and Kim-Kwang Raymond Choo. The role of the adversary model in applied security research. Computers & Security, 81:156–181, 2019. DOI: 10.1016/j.cose.2018.12.002
[DNGW23]
Elena Dubrova, Kalle Ngo, Joel Gärtner, and Ruize Wang. Breaking a fifth-order masked implementation of CRYSTALS-Kyber by copy-paste. In Proceedings of the 10th ACM Asia Public-Key Cryptography Workshop, pages 10–20. 2023. DOI: 10.1145/3591866.3593072
[DSDGR20]
Dana Dachman-Soled, Léo Ducas, Huijing Gong, and Mélissa Rossi. LWE with Side Information: Attacks and Concrete Security Estimation. In Advances in Cryptology – CRYPTO 2020, volume 12171, pages 329–358. 2020. Springer. DOI: 10.1007/978-3-030-56880-1_12
[FDK20]
Apostolos P. Fournaris, Charis Dimopoulos, and Odysseas Koufopavlou. Profiling Dilithium Digital Signature Traces for Correlation Differential Side Channel Attacks. In Alex Orailoglu, Matthias Jung, and Marc Reichenbach, editors, Embedded Computer Systems: Architectures, Modeling, and Simulation, pages 281–294, Cham. 2020. Springer International Publishing. DOI: 10.1007/978-3-030-60939-9_19
[FIP23]
PUB FIPS. FIPS 204 (Draft): Module-Lattice-Based Digital Signature Standard. National Institute of Standards and Technology, 2023. https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.ipd.pdf
[HCM24]
Suvadeep Hajra, Siddhartha Chowdhury, and Debdeep Mukhopadhyay. EstraNet: An Efficient Shift-Invariant Transformer Network for Side-Channel Analysis. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2024(1):336–374, 2024. DOI: 10.46586/tches.v2024.i1.336-374
[HGA+19]
Caio Hoffman, Catherine Gebotys, Diego F Aranha, Mario Cortes, and Guido Araujo. Circumventing uniqueness of XOR arbiter PUFs. In 2019 22nd Euromicro Conference on Digital System Design (DSD), pages 222–229. 2019. IEEE. DOI: 10.1109/DSD.2019.00041
[HLK+21]
Jaeseung Han, Taeho Lee, Jihoon Kwon, Joohee Lee, Il-Ju Kim, Jihoon Cho, Dong-Guk Han, and Bo-Yeon Sim. Single-trace attack on NIST round 3 candidate Dilithium using machine learning-based profiling. IEEE Access, 9:166283–166292, 2021. DOI: 10.1109/ACCESS.2021.3135600
[JNWD23]
Sönke Jendral, Kalle Ngo, Ruize Wang, and Elena Dubrova. A Single-Trace Message Recovery Attack on a Masked and Shuffled Implementation of CRYSTALS-Kyber. https://eprint.iacr.org/2023/1587. Cryptology ePrint Archive, Paper 2023/1587. 2023.
[KJJ99]
Paul Kocher, Joshua Jaffe, and Benjamin Jun. Differential Power Analysis. In Advances in Cryptology — CRYPTO' 99, pages 388–397. 1999. Springer. DOI: 10.1007/3-540-48405-1_25
[Koc96]
Paul C. Kocher. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In Proc. of the 16th Annual Int. Cryptology Conf. on Advances in Cryptology, pages 104–113. 1996. DOI: 10.1007/3-540-68697-5_9
[KPH+19]
Jaehun Kim, Stjepan Picek, Annelie Heuser, Shivam Bhasin, and Alan Hanjalic. Make Some Noise. Unleashing the Power of Convolutional Neural Networks for Profiled Side-channel Analysis. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019(3):148-179, May 2019. DOI: 10.13154/tches.v2019.i3.148-179
[KRSS19]
Matthias J. Kannwischer, Joost Rijneveld, Peter Schwabe, and Ko Stoffelen. pqm4: Testing and Benchmarking NIST PQC on ARM Cortex-M4. https://eprint.iacr.org/2019/844. Cryptology ePrint Archive, Paper 2019/844. 2019.
[LHWLL82]
Arjen K. Lenstra, Jr. Hendrik W. Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261:515–534, 1982.
[Lyu09]
Vadim Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In International Conference on the Theory and Application of Cryptology and Information Security, pages 598–616. 2009. Springer. DOI: 10.1007/978-3-642-10366-7_35
[Lyu18]
Vadim Lyubashevsky. Round 1 Official Comment: CRYSTALS-Dilithium. https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/official-comments/CRYSTALS-DILITHIUM-official-comment.pdf. NIST PQC Project document. 19 September 2018.
[LZS+20]
Yuejun Liu, Yongbin Zhou, Shuo Sun, Tianyu Wang, Rui Zhang, and Ming Jingdian. On the Security of Lattice-Based Fiat-Shamir Signatures in the Presence of Randomness Leakage. IEEE Transactions on Information Forensics and Security, PP:1-1, December 2020. DOI: 10.1109/TIFS.2020.3045904
[MGTF19]
Vincent Migliore, Benoît Gérard, Mehdi Tibouchi, and Pierre-Alain Fouque. Masking Dilithium: Efficient implementation and side-channel evaluation. In Applied Cryptography and Network Security: 17th International Conference, ACNS 2019, Bogota, Colombia, June 5–7, 2019, Proceedings 17, pages 344–362. 2019. Springer. DOI: 10.1007/978-3-030-21568-2_17
[Moo22]
Dustin Moody. Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process. Nistir 8309, 2022. https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413.pdf DOI: 10.6028/NIST.IR.8413
[MPP16]
Houssem Maghrebi, Thibault Portigliatti, and Emmanuel Prouff. Breaking Cryptographic Implementations Using Deep Learning Techniques. In Claude Carlet, M. Anwar Hasan, and Vishal Saraswat, editors, Security, Privacy, and Applied Cryptography Engineering, pages 3–26, Cham. 2016. Springer International Publishing. DOI: 10.1007/978-3-319-49445-6_1
[MSB16]
Houssem Maghrebi, Victor Servant, and Julien Bringer. There Is Wisdom in Harnessing the Strengths of Your Enemy: Customized Encoding to Thwart Side-Channel Attacks. In Fast Software Encryption, pages 223–243. 2016. DOI: 10.1007/978-3-662-52993-5_12
[MTS23]
John Mattsson, Erik Thormarker, and Ben Smeets. Migration to quantum-resistant algorithms in mobile networks. https://www.ericsson.com/en/blog/2023/2/quantum-resistant-algorithms-mobile-networks. Ericsson blog. 8 February 2023.
[MUTS22]
Soundes Marzougui, Vincent Ulitzsch, Mehdi Tibouchi, and Jean-Pierre Seifert. Profiling Side-Channel Attacks on Dilithium: A Small Bit-Fiddling Leak Breaks It All. Cryptology ePrint Archive, Paper 2022/106. 2022.
[Nat22]
Announcing the Commercial National Security Algorithm Suite 2.0. National Security Agency, U.S Department of Defense, September 2022.
[ND22]
Kalle Ngo and Elena Dubrova. Side-Channel Analysis of the Random Number Generator in STM32 MCUs. In Proc. of the Great Lakes Symposium on VLSI (GLSVLSI '22). 2022. DOI: 10.1145/3526241.3530324
[New]
NewAE Technology Inc.. ChipWhisperer. https://rtfm.newae.com/Capture/ChipWhisperer-Pro/.
[OVCG24]
Paco Azevedo Oliveira, Andersson Calle Viera, Benoît Cogliati, and Louis Goubin. Uncompressing Dilithium's public key. Cryptology ePrint Archive, 2024. https://eprint.iacr.org/2024/1373
[PCP20]
Guilherme Perin, Łukasz Chmielewski, and Stjepan Picek. Strength in numbers: Improving generalization with ensembles in machine learning-based profiled side-channel analysis. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020. DOI: 10.13154/tches.v2020.i4.337-364
[PSK+18]
Stjepan Picek, Ioannis Petros Samiotis, Jaehun Kim, Annelie Heuser, Shivam Bhasin, and Axel Legay. On the Performance of Convolutional Neural Networks for Side-Channel Analysis. In Anupam Chattopadhyay, Chester Rebeiro, and Yuval Yarom, editors, Security, Privacy, and Applied Cryptography Engineering, pages 157–176, Cham. 2018. Springer International Publishing. DOI: 10.1007/978-3-030-05072-6_10
[QLZ+23a]
Zehua Qiao, Yuejun Liu, Yongbin Zhou, Jingdian Ming, Chengbin Jin, and Huizhong Li. Practical Public Template Attacks on CRYSTALS-Dilithium With Randomness Leakages. IEEE Transactions on Information Forensics and Security, 18:1-14, 2023. DOI: 10.1109/TIFS.2022.3215913
[QLZ+23b]
Zehua Qiao, Yuejun Liu, Yongbin Zhou, Mingyao Shao, and Shuo Sun. When NTT Meets SIS: Efficient Side-channel Attacks on Dilithium and Kyber. https://eprint.iacr.org/2023/1866. Cryptology ePrint Archive, Paper 2023/1866. 2023.
[RJH+18]
Prasanna Ravi, Mahabir Prasad Jhanwar, James Howe, Anupam Chattopadhyay, and Shivam Bhasin. Side-channel Assisted Existential Forgery Attack on Dilithium - A NIST PQC candidate. https://eprint.iacr.org/2018/821. Cryptology ePrint Archive, Paper 2018/821. 2018.
[SE94]
Claus-Peter Schnorr and Martin Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical programming, 66:181–199, 1994. DOI: 10.1007/BF01581144
[SG10]
Michael Schneider and Nicholas Gama. Darmstadt SVP Challenges. https://www.latticechallenge.org/svp-challenge/index.php. 2010.
[SKL+20]
Bo-Yeon Sim, Jihoon Kwon, Joohee Lee, Il-Ju Kim, Tae-Ho Lee, Jaeseung Han, Hyojin Yoon, Jihoon Cho, and Dong-Guk Han. Single-trace attacks on message encoding in lattice-based KEMs. IEEE Access, 8:183175–183191, 2020. DOI: 10.1109/ACCESS.2020.3029521
[SLKG23]
Hauke Steffen, Georg Land, Lucie Kogelheide, and Tim Güneysu. Breaking and protecting the Crystal: Side-channel analysis of Dilithium in hardware. In International Conference on Post-Quantum Cryptography, pages 688–711. 2023. Springer. DOI: 10.1007/978-3-031-40003-2_25
[SPH22]
Bo-Yeon Sim, Aesun Park, and Dong-Guk Han. Chosen-ciphertext Clustering Attack on CRYSTALS-KYBER using the Side-channel Leakage of Barrett Reduction. IEEE Internet of Things Journal, 2022. DOI: 10.1109/JIOT.2022.3179683
[Tim19]
Benjamin Timon. Non-profiled deep learning-based side-channel attacks with sensitivity analysis. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019. DOI: 10.13154/tches.v2019.i2.107-131
[VC+12]
Veyrat-Charvillon and others. Shuffling against Side-Channel Attacks: A Comprehensive Study with Cautionary Note. In Advances in Cryptology – ASIACRYPT 2012, pages 740–757. 2012. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-34961-4_44
[WBFD19]
Huanyu Wang, Martin Brisfors, Sebastian Forsmark, and Elena Dubrova. How Diversity Affects Deep-Learning Side-Channel Attacks. In 2019 IEEE Nordic Circuits and Systems Conference (NORCAS): NORCHIP and International Symposium of System-on-Chip (SoC), pages 1-7. 2019. DOI: 10.1109/NORCHIP.2019.8906945
[WD21]
Huanyu Wang and Elena Dubrova. Tandem deep learning side-channel attack on FPGA implementation of AES. SN Computer Science, 2(5):373, 2021. DOI: 10.1007/s42979-021-00755-w
[WFBD20]
Huanyu Wang, Sebastian Forsmark, Martin Brisfors, and Elena Dubrova. Multi-source training deep learning side-channel attacks. In IEEE 50th International Symposium on Multiple-Valued Logic (ISMVL'2020). 2020. DOI: 10.1109/ISMVL49045.2020.00-29
[WP20]
Lichao Wu and Stjepan Picek. Remove some noise: On pre-processing of side-channel measurements with autoencoders. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020. DOI: 10.13154/tches.v2020.i4.389-415
PDF
History
Submitted: 2024-07-03
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Ruize Wang, Kalle Ngo, Joel Gärtner, and Elena Dubrova, Unpacking Needs Protection. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/a0fh89n4e.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.