Skip to main content
SpringerLink
Log in

Breaking and Protecting the Crystal: Side-Channel Analysis of Dilithium in Hardware

  • Conference paper
  • First Online:
Post-Quantum Cryptography (PQCrypto 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14154))

Included in the following conference series:

Abstract

The lattice-based CRYSTALS-Dilithium signature scheme has been selected for standardization by the NIST. As part of the selection process, a large number of implementations for platforms like x86, ARM Cortex-M4, or – on the hardware side – Xilinx Artix-7 have been presented and discussed by experts. While software implementations have been subject to side-channel analysis with several attacks being published, an analysis of Dilithium hardware implementations and their peculiarities has not taken place. With this work, we aim to fill this gap, presenting an analysis of vulnerable operations and practically showing a successful profiled Simple Power Analysis (SPA) and a Correlation Power Analysis (CPA) on a recent hardware implementation by Beckwith et al. Our SPA attack requires 700 000 profiling traces and targets the first Number-Theoretic Transform (NTT) stage. After finishing profiling, we can identify pairs of coefficients with 1 101 traces. The full CPA attack finds secret coefficients with as low as 66 000 traces. In response, we present specific countermeasures and show that they effectively prevent both attacks.

L. Kogelheide—The respective work has been conducted as an employee of TÜV Informationstechnik GmbH.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Azouaoui, M., et al.: Protecting Dilithium against leakage: revisited sensitivity analysis and improved implementations. Cryptology ePrint Archive, Paper 2022/1406 (2022). https://eprint.iacr.org/2022/1406

  2. Bache, F., Güneysu, T.: Boolean masking for arithmetic additions at arbitrary order in hardware. Appl. Sci. 12(5), 2274 (2022)

    Article  Google Scholar 

  3. Barthe, G., et al.: Masking the GLP lattice-based signature scheme at any order. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 354–384. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_12

    Chapter  Google Scholar 

  4. Beckwith, L., Nguyen, D.T., Gaj, K.: High-performance hardware implementation of CRYSTALS-Dilithium. In: International Conference on Field-Programmable Technology, (IC)FPT 2021, Auckland, New Zealand, 6–10 December 2021, pp. 1–10. IEEE (2021)

    Google Scholar 

  5. Brier, E., Clavier, C., Olivier, F.: Correlation power analysis with a leakage model. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 16–29. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28632-5_2

    Chapter  Google Scholar 

  6. Bronchain, O., Cassiers, G.: Bitslicing arithmetic/Boolean masking conversions for fun and profit with application to lattice-based KEMs. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2022(4), 553–588 (2022)

    Article  Google Scholar 

  7. Chari, S., Jutla, C.S., Rao, J.R., Rohatgi, P.: Towards sound approaches to counteract power-analysis attacks. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 398–412. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_26

    Chapter  Google Scholar 

  8. Chari, S., Rao, J.R., Rohatgi, P.: Template attacks. In: Kaliski, B.S., Koç, K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 13–28. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36400-5_3

    Chapter  Google Scholar 

  9. Chen, Z., Karabulut, E., Aysu, A., Ma, Y., Jing, J.: An efficient non-profiled side-channel attack on the CRYSTALS-Dilithium post-quantum signature. In: 39th IEEE International Conference on Computer Design, ICCD 2021, Storrs, CT, USA, 24–27 October 2021, pp. 583–590. IEEE (2021)

    Google Scholar 

  10. Choudary, O., Kuhn, M.G.: Efficient template attacks. In: Francillon, A., Rohatgi, P. (eds.) CARDIS 2013. LNCS, vol. 8419, pp. 253–270. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08302-5_17

    Chapter  Google Scholar 

  11. Ducas, L., et al.: CRYSTALS-Dilithium - algorithm specifications and supporting documentation (version 3.1). Technical report (2021). https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf

  12. Fritzmann, T., et al.: Masked accelerators and instruction set extensions for post-quantum cryptography. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2022(1), 414–460 (2022)

    Google Scholar 

  13. Gierlichs, B., Lemke-Rust, K., Paar, C.: Templates vs. stochastic methods. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 15–29. Springer, Heidelberg (2006). https://doi.org/10.1007/11894063_2

    Chapter  Google Scholar 

  14. Goubin, L., Patarin, J.: DES and differential power analysis the “duplication’’ method. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 158–172. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48059-5_15

    Chapter  MATH  Google Scholar 

  15. Güneysu, T., Moradi, A.: Generic side-channel countermeasures for reconfigurable devices. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 33–48. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23951-9_3

    Chapter  Google Scholar 

  16. Karabulut, E., Alkim, E., Aysu, A.: Single-trace side-channel attacks on \(\omega \)-small polynomial sampling: with applications to NTRU, NTRU Prime, and CRYSTALS-DILITHIUM. In: IEEE International Symposium on Hardware Oriented Security and Trust, HOST 2021, Tysons Corner, VA, USA, 12–15 December 2021, pp. 35–45. IEEE (2021)

    Google Scholar 

  17. Kocher, P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68697-5_9

    Chapter  Google Scholar 

  18. Land, G., Sasdrich, P., Güneysu, T.: A hard crystal - implementing Dilithium on reconfigurable hardware. In: Grosso, V., Pöppelmann, T. (eds.) CARDIS 2021. LNCS, vol. 13173, pp. 210–230. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-97348-3_12

    Chapter  Google Scholar 

  19. Mangard, S., Oswald, E., Popp, T.: Power Analysis Attacks - Revealing the Secrets of Smart Cards. Springer, New York (2007). https://doi.org/10.1007/978-0-387-38162-6

    Book  MATH  Google Scholar 

  20. Marzougui, S., Ulitzsch, V., Tibouchi, M., Seifert, J.-P.: Profiling side-channel attacks on Dilithium: a small bit-fiddling leak breaks it all. Cryptology ePrint Archive, Report 2022/106 (2022). https://eprint.iacr.org/2022/106

  21. Migliore, V., Gérard, B., Tibouchi, M., Fouque, P.-A.: Masking Dilithium. In: Deng, R.H., Gauthier-Umaña, V., Ochoa, M., Yung, M. (eds.) ACNS 2019. LNCS, vol. 11464, pp. 344–362. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-21568-2_17

    Chapter  MATH  Google Scholar 

  22. 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). https://eprint.iacr.org/2018/821

  23. Ravi, P., Jhanwar, M.P., Howe, J., Chattopadhyay, A., Bhasin, S.: Exploiting determinism in lattice-based signatures: practical fault attacks on pqm4 implementations of NIST candidates. In: Galbraith, S.D., Russello, G., Susilo, W., Gollmann, D., Kirda, E., Liang, Z. (eds.) ASIACCS 2019: 14th ACM Symposium on Information, Computer and Communications Security, Auckland, New Zealand, 9–12 July 2019, pp. 427–440. ACM Press (2019)

    Google Scholar 

  24. Schneider, T., Moradi, A., Güneysu, T.: Arithmetic addition over Boolean masking. In: Malkin, T., Kolesnikov, V., Lewko, A.B., Polychronakis, M. (eds.) ACNS 2015. LNCS, vol. 9092, pp. 559–578. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-28166-7_27

    Chapter  MATH  Google Scholar 

  25. Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 20–22 November 1994, pp. 124–134. IEEE Computer Society Press (1994)

    Google Scholar 

  26. Veyrat-Charvillon, N., Medwed, M., Kerckhof, S., Standaert, F.-X.: Shuffling against side-channel attacks: a comprehensive study with cautionary note. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 740–757. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_44

    Chapter  Google Scholar 

  27. Zhao, C., et al.: A compact and high-performance hardware architecture for CRYSTALS-Dilithium. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2022(1), 270–295 (2022)

    MathSciNet  Google Scholar 

Download references

Acknowledgments

We thank the reviewers for their constructive comments. Furthermore, we thank Pascal Sasdrich for the fruitful discussions. This work was supported by the German Research Foundation under Germany’s Excellence Strategy - EXC 2092 CASA - 390781972, through the H2020 project PROMETHEUS (grant agreement ID 780701), CONVOLVE (grant agreement ID 101070374), and by the Federal Ministry of Education and Research of Germany through the QuantumRISC (16KIS1038), PQC4Med (16KIS1044), and 6GEM (16KISK038) projects.

Author information

Authors and Affiliations

  1. TÜV Informationstechnik GmbH, Essen, Germany

    Hauke Steffen

  2. Horst Görtz Institute for IT Security, Ruhr University Bochum, Bochum, Germany

    Georg Land & Tim Güneysu

  3. BWI GmbH, Bonn, Germany

    Lucie Kogelheide

  4. DFKI GmbH, Cyber-Physical Systems, Bremen, Germany

    Tim Güneysu

Authors
  1. Hauke Steffen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Georg Land
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lucie Kogelheide
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Tim Güneysu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Georg Land or Lucie Kogelheide .

Editor information

Editors and Affiliations

  1. Lund University, Lund, Sweden

    Thomas Johansson

  2. National Institute of Standards and Technology, Gaithersburg, MD, USA

    Daniel Smith-Tone

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Steffen, H., Land, G., Kogelheide, L., Güneysu, T. (2023). Breaking and Protecting the Crystal: Side-Channel Analysis of Dilithium in Hardware. In: Johansson, T., Smith-Tone, D. (eds) Post-Quantum Cryptography. PQCrypto 2023. Lecture Notes in Computer Science, vol 14154. Springer, Cham. https://doi.org/10.1007/978-3-031-40003-2_25

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-40003-2_25

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-40002-5

  • Online ISBN: 978-3-031-40003-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation