Profiling Side-Channel Attacks on Dilithium: A Small Bit-Fiddling Leak Breaks It All
Authors: 
Vincent Quentin Ulitzsch, Soundes Marzougui, Mehdi Tibouchi, Jean-Pierre SeifertAuthors Info & Claims
Pages 3 - 32
Abstract
We present an end-to-end (equivalent) key recovery attack on the Dilithium lattice-based signature scheme, one of the winners of the NIST postquantum cryptography competition. The attack is based on a small side-channel leakage we identified in a bit unpacking procedure inside Dilithium signature generation. We then combine machine-learning based profiling with various algorithmic techniques, including least squares regression and integer linear programming, in order to leverage this small leakage into essentially full key recovery: we manage to recover, from a moderate number of side-channel traces, enough information to sign arbitrary messages. We confirm the practicality of our technique using concrete experiments against the ARM Cortext-M4 implementation of Dilithium, and verify that our attack is robust to real-world conditions such as noisy power measurements. This attack appears difficult to protect against reliably without strong side-channel countermeasures such as masking of the entire signing algorithm, and underscores the necessity of implementing such countermeasures despite their known high cost.
References
[1]
Aranha DF, Orlandi C, Takahashi A, and Zaverucha G Canteaut A and Ishai Y Security of hedged fiat–Shamir signatures under fault attacks Advances in Cryptology – EUROCRYPT 2020 2020 Cham Springer 644-674
[2]
Archambeau C, Peeters E, Standaert F-X, and Quisquater J-J Goubin L and Matsui M Template attacks in principal subspaces Cryptographic Hardware and Embedded Systems - CHES 2006 2006 Heidelberg Springer 1-14
[3]
Bai, S., et al.: Dilithium reference implementation. https://github.com/pq-crystals/dilithium. Accessed 14 Apr 2020
[4]
Bai, S., et al.: Dilithium official website (2020). https://pq-crystals.org/dilithium/index.shtml. Accessed 20 Dec 2020
[5]
Bai S and Galbraith SD Benaloh J An improved compression technique for signatures based on learning with errors Topics in Cryptology – CT-RSA 2014 2014 Cham Springer 28-47
[6]
Bartkewitz T and Lemke-Rust K Mangard S Efficient template attacks based on probabilistic multi-class support vector machines Smart Card Research and Advanced Applications 2013 Heidelberg Springer 263-276
[7]
Bernstein, D.J., Lange, T.: eBACS: ECRYPT Benchmarking of Cryptographic Systems. https://bench.cr.yp.to/. Accessed 20 Dec 2020
[8]
Bootle J, Delaplace C, Espitau T, Fouque P-A, and Tibouchi M Peyrin T and Galbraith S LWE without modular reduction and improved side-channel attacks against BLISS Advances in Cryptology – ASIACRYPT 2018 2018 Cham Springer 494-524
[9]
Brisfors M, Forsmark S, and Dubrova E Liardet P-Y and Mentens N How deep learning helps compromising USIM Smart Card Research and Advanced Applications 2021 Cham Springer 135-150
[10]
Camurati, G., Poeplau, S., Muench, M., Hayes, T., Francillon, A.: Screaming channels: when electromagnetic side channels meet radio transceivers. In: Lie, D., Mannan, M., Backes, M., Wang, X. (eds.) ACM CCS 2018, pp. 163–177. ACM Press, October 201.
[11]
Chen Y, Genise N, and Mukherjee P Galbraith SD and Moriai S Approximate trapdoors for lattices and smaller hash-and-sign signatures Advances in Cryptology – ASIACRYPT 2019 2019 Cham Springer 3-32
[12]
Dachman-Soled D, Ducas L, Gong H, and Rossi M Micciancio D and Ristenpart T LWE with side information: attacks and concrete security estimation Advances in Cryptology – CRYPTO 2020 2020 Cham Springer 329-358
[13]
Ducas L, Durmus A, Lepoint T, and Lyubashevsky V Canetti R and Garay JA Lattice signatures and bimodal gaussians Advances in Cryptology – CRYPTO 2013 2013 Heidelberg Springer 40-56
[14]
Ducas L, Lyubashevsky V, and Prest T Sarkar P and Iwata T Efficient identity-based encryption over NTRU lattices Advances in Cryptology – ASIACRYPT 2014 2014 Heidelberg Springer 22-41
[15]
Espitau, T., et al.: Mitaka: a simpler, parallelizable, maskable variant of falcon. In: Dunkelman, O., Dziembowski, S. (eds.) Advances in Cryptology – EUROCRYPT 2022. EUROCRYPT 2022. LNCS, vol. 13277, pp. 222–253. Springer, Cham (2022).
[16]
Fournaris AP, Dimopoulos C, and Koufopavlou O Orailoglu A, Jung M, and Reichenbach M Profiling dilithium digital signature traces for correlation differential side channel attacks Embedded Computer Systems: Architectures, Modeling, and Simulation 2020 Cham Springer 281-294
[17]
Gamrath, G., et al.: The SCIP Optimization Suite 7.0. Technical report, Optimization Online, March 2020
[18]
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 197–206. ACM Press, May 2008.
[19]
Goldreich O, Goldwasser S, and Halevi S Kaliski BS Public-key cryptosystems from lattice reduction problems Advances in Cryptology — CRYPTO ’97 1997 Heidelberg Springer 112-131
[20]
Groot Bruinderink, L., Pessl, P.: Differential fault attacks on deterministic lattice signatures. IACR TCHES 2018(3), 21–43 (2018).
[21]
Güneysu T, Lyubashevsky V, and Pöppelmann T Prouff E and Schaumont P Practical lattice-based cryptography: a signature scheme for embedded systems Cryptographic Hardware and Embedded Systems – CHES 2012 2012 Heidelberg Springer 530-547
[22]
Hoffstein J, Howgrave-Graham N, Pipher J, Silverman JH, and Whyte W Joye M NTRUSign: digital signatures using the NTRU lattice Topics in Cryptology — CT-RSA 2003 2003 Heidelberg Springer 122-140
[23]
Kim, J., Picek, S., Heuser, A., Bhasin, S., Hanjalic, A.: Make some noise: unleashing the power of convolutional neural networks for profiled side-channel analysis. IACR TCHES 2019(3), 148–179 (2019).
[24]
Kirshanova E and May A Paterson MB How to find ternary LWE keys using locality sensitive hashing Cryptography and Coding 2021 Cham Springer 247-264
[25]
Kocher P, Jaffe J, and Jun B Wiener M Differential power analysis Advances in Cryptology — CRYPTO’ 99 1999 Heidelberg Springer 388-397
[26]
Li L, Jamieson K, DeSalvo G, Rostamizadeh A, and Talwalkar A Hyperband: a novel bandit-based approach to hyperparameter optimization J. Mach. Learn. Res. 2017 18 1 6765-6816
[27]
Lyubashevsky V Matsui M Fiat-Shamir with aborts: applications to lattice and factoring-based signatures Advances in Cryptology – ASIACRYPT 2009 2009 Heidelberg Springer 598-616
[28]
Lyubashevsky, V., et al.: CRYSTALS-DILITHIUM. Technical report, National Institute of Standards and Technology (2020). https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions
[29]
Maghrebi H, Portigliatti T, and Prouff E Carlet C, Hasan MA, and Saraswat V Breaking cryptographic implementations using deep learning techniques Security, Privacy, and Applied Cryptography Engineering 2016 Cham Springer 3-26
[30]
Marzougui, S., Wisiol, N., Gersch, P., Krämer, J., Seifert, J.P.: Machine-learning side-channel attacks on the galactics constant-time implementation of bliss. arXiv preprint arXiv:2109.09461 (2021)
[31]
May A Malkin T and Peikert C How to meet ternary LWE keys Advances in Cryptology – CRYPTO 2021 2021 Cham Springer 701-731
[32]
Micciancio D and Peikert C Pointcheval D and Johansson T Trapdoors for lattices: simpler, tighter, faster, smaller Advances in Cryptology – EUROCRYPT 2012 2012 Heidelberg Springer 700-718
[33]
Migliore V, Gérard B, Tibouchi M, and Fouque P-A Deng RH, Gauthier-Umaña V, Ochoa M, and Yung M Masking dilithium Applied Cryptography and Network Security 2019 Cham Springer 344-362
[34]
Nguyen P Wiener M Cryptanalysis of the goldreich-goldwasser-halevi cryptosystem from crypto ’97 Advances in Cryptology — CRYPTO’ 99 1999 Heidelberg Springer 288-304
[35]
Nguyen PQ and Regev O Vaudenay S Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures Advances in Cryptology - EUROCRYPT 2006 2006 Heidelberg Springer 271-288
[36]
NIST: Post-quantum cryptography standardization. https://csrc.nist.gov/projects/post-quantum-cryptography (2016–present)
[37]
O’Flynn C and Chen ZD Prouff E ChipWhisperer: an open-source platform for hardware embedded security research Constructive Side-Channel Analysis and Secure Design 2014 Cham Springer 243-260
[38]
Prest, T., et al.: FALCON. Technical report, National Institute of Standards and Technology (2020). https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions
[39]
Ravi, P., Jhanwar, M.P., Howe, J., Chattopadhyay, A., Bhasin, S.: Side-channel assisted existential forgery attack on Dilithium - A NIST PQC candidate. Cryptology ePrint Archive, Report 2018/821 (2018)
[40]
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6) (2009)
[41]
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5) (1997)
[42]
Sim, B.Y., et al.: Single-trace attacks on message encoding in lattice-based kems. IEEE Access 8, 183175–183191 (2020).
Recommendations
Side-channel and Fault-injection attacks over Lattice-based Post-quantum Schemes (Kyber, Dilithium): Survey and New Results
In this work, we present a systematic study of Side-Channel Attacks (SCA) and Fault Injection Attacks (FIA) on structured lattice-based schemes, with main focus on Kyber Key Encapsulation Mechanism (KEM) and Dilithium signature scheme, which are leading ...
Reveal the Invisible Secret: Chosen-Ciphertext Side-Channel Attacks on NTRU
Smart Card Research and Advanced ApplicationsAbstractNTRU is a well-known lattice-based cryptosystem that has been selected as one of the four key encapsulation mechanism finalists in Round 3 of NIST’s post-quantum cryptography standardization. This paper presents two succinct and efficient chosen-...
FriendlyFoe: Adversarial Machine Learning as a Practical Architectural Defense against Side Channel Attacks
PACT '24: Proceedings of the 2024 International Conference on Parallel Architectures and Compilation TechniquesMachine learning (ML)-based side channel attacks have become prominent threats to computer security. These attacks are often powerful, as ML models easily find patterns in signals. To address this problem, this paper proposes dynamically applying ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Aug 2022
484 pages
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 12 May 2024
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 17 Nov 2024
Other Metrics
Citations
Cited By
View allView Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in