Skip to main content
Springer Nature Link
Log in

A Lattice Attack on CRYSTALS-Kyber with Correlation Power Analysis

  • Conference paper
  • First Online:
Information Security and Cryptology – ICISC 2023 (ICISC 2023)

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

Included in the following conference series:

Abstract

CRYSTALS-Kyber is a key-encapsulation mechanism, whose security is based on the hardness of solving the learning-with-errors (LWE) problem over module lattices. As in its specification, Kyber prescribes the usage of the Number Theoretic Transform (NTT) for efficient polynomial multiplication. Side-channel assisted attacks against Post-Quantum Cryptography (PQC) algorithms like Kyber remain a concern in the ongoing standardization process of quantum-computer-resistant cryptosystems. Among the attacks, correlation power analysis (CPA) is emerging as a popular option because it does not require detailed knowledge about the attacked device and can reveal the secret key even if the recorded power traces are extremely noisy. In this paper, we present a two-step attack to achieve a full-key recovery on lattice-based cryptosystems that utilize NTT for efficient polynomial multiplication. First, we use CPA to recover a portion of the secret key from the power consumption of these polynomial multiplications in the decryption process. Then, using the information, we are able to fully recover the secret key by constructing an LWE problem with a smaller lattice rank and solving it with lattice reduction algorithms. Our attack can be expanded to other cryptosystems using NTT-based polynomial multiplication, including Saber. It can be further parallelized and experiments on simulated traces show that the whole process can be done within 20 min on a 16-core machine with 200 traces. Compared to other CPA attacks targeting NTT in the cryptosystems, our attack achieves lower runtime in practice. Furthermore, we can theoretically decrease the number of traces needed by using lattice reduction if the same measurement is used. Our lattice attack also outperforms the state-of-the-art result on integrating side-channel hints into lattices, however, the improvement heavily depends on the implementation of the NTT chosen by the users.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 59.99
Price excludes VAT (USA)
Softcover Book
USD 74.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    We ran the experiment using the BKZ implementation from fpylll in Sage9.2. See https://github.com/fplll/fpylll.

References

  1. Avanzi, R., et al.: CRYSTALS-Kyber (version 3.02) - submission to round 3 of the NIST post-quantum project. Specification document (2021)

    Google Scholar 

  2. Bos, J., et al.: CRYSTALS - Kyber: a CCA-secure module-lattice-based KEM. In: 2018 IEEE European Symposium on Security and Privacy (EuroS&P), pp. 353–367 (2018). https://doi.org/10.1109/EuroSP.2018.00032

  3. Bos, J., et al.: Kyber (2023). https://github.com/pq-crystals/kyber

  4. Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS 2012, pp. 309–325. Association for Computing Machinery (2012). https://doi.org/10.1145/2090236.2090262

  5. Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) Advances in Cryptology - ASIACRYPT 2011, pp. 1–20 (2011)

    Google Scholar 

  6. Chung, C.M.M., Hwang, V., Kannwischer, M.J., Seiler, G., Shih, C.J., Yang, B.Y.: NTT multiplication for NTT-unfriendly rings. Cryptology ePrint Archive, Paper 2020/1397 (2020). https://eprint.iacr.org/2020/1397

  7. Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19, 297–301 (1965)

    Article  MathSciNet  Google Scholar 

  8. Dachman-Soled, D., Ducas, L., Gong, H., Rossi, M.: LWE with side information: attacks and concrete security estimation. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part II. LNCS, vol. 12171, pp. 329–358. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_12

    Chapter  Google Scholar 

  9. D’Anvers, J.P., Karmakar, A., Sinha Roy, S., Vercauteren, F.: Saber: module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM. In: Joux, A., Nitaj, A., Rachidi, T. (eds.) Progress in Cryptology - AFRICACRYPT 2018, pp. 282–305 (2018)

    Google Scholar 

  10. ELMO: Evaluating leaks for the arm cortex-m0. https://github.com/sca-research/ELMO. Accessed 17 Oct 2022

  11. Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 537–554. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_34

    Chapter  Google Scholar 

  12. Guerreau, M., Martinelli, A., Ricosset, T., Rossi, M.: The hidden parallelepiped is back again: power analysis attacks on Falcon. Cryptology ePrint Archive, Paper 2022/057 (2022). https://eprint.iacr.org/2022/057

  13. Hamburg, M., et al.: Chosen ciphertext k-trace attacks on masked CCA2 secure Kyber. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2021(4), 88–113 (2021). https://doi.org/10.46586/tches.v2021.i4.88-113. https://tches.iacr.org/index.php/TCHES/article/view/9061

  14. Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415–440 (1987). http://www.jstor.org/stable/3689974

  15. Kocher, P., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_25

    Chapter  Google Scholar 

  16. 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 

  17. Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. J. ACM 60(6) (2013). https://doi.org/10.1145/2535925

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

    Book  Google Scholar 

  19. May, A., Nowakowski, J.: Too many hints - when LLL breaks LWE. Cryptology ePrint Archive, Paper 2023/777 (2023). https://eprint.iacr.org/2023/777

  20. McCann, D., Oswald, E., Whitnall, C.: Towards practical tools for side channel aware software engineering: grey box’ modelling for instruction leakages. In: Proceedings of the 26th USENIX Conference on Security Symposium, pp. 199–216 (2017)

    Google Scholar 

  21. Mujdei, C., Wouters, L., Karmakar, A., Beckers, A., Mera, J.M.B., Verbauwhede, I.: Side-channel analysis of lattice-based post-quantum cryptography: exploiting polynomial multiplication. ACM Trans. Embed. Comput. Syst. (2022). https://doi.org/10.1145/3569420

  22. National Institute of Standards and Technology. Post-quantum cryptography standardization. https://csrc.nist.gov/projects/post-quantum-cryptography. Accessed 12 Oct 2022

  23. Pessl, P., Primas, R.: More practical single-trace attacks on the number theoretic transform. Cryptology ePrint Archive, Paper 2019/795 (2019). https://eprint.iacr.org/2019/795

  24. Primas, R., Pessl, P., Mangard, S.: Single-trace side-channel attacks on masked lattice-based encryption. Cryptology ePrint Archive, Paper 2017/594 (2017). https://eprint.iacr.org/2017/594

  25. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, vol. 56, pp. 84–93 (2005). https://doi.org/10.1145/1568318.1568324

  26. Shor, P.: Algorithms for quantum computation: Discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124–134 (1994). https://doi.org/10.1109/SFCS.1994.365700

Download references

Acknowledgement

This work was partially supported by JSPS KAKENHI Grant Number 19K20267, Japan, and JST CREST Grant Number JPMJCR2113, Japan.

Author information

Authors and Affiliations

  1. The University of Tokyo, Tokyo, Japan

    Yen-Ting Kuo & Atsushi Takayasu

Authors
  1. Yen-Ting Kuo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Atsushi Takayasu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yen-Ting Kuo .

Editor information

Editors and Affiliations

  1. Hansung University, Seoul, Korea (Republic of)

    Hwajeong Seo

  2. Sungshin Women's University, Seoul, Korea (Republic of)

    Suhri Kim

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Kuo, YT., Takayasu, A. (2024). A Lattice Attack on CRYSTALS-Kyber with Correlation Power Analysis. In: Seo, H., Kim, S. (eds) Information Security and Cryptology – ICISC 2023. ICISC 2023. Lecture Notes in Computer Science, vol 14561. Springer, Singapore. https://doi.org/10.1007/978-981-97-1235-9_11

Download citation

  • DOI: https://doi.org/10.1007/978-981-97-1235-9_11

  • Published:

  • Publisher Name: Springer, Singapore

  • Print ISBN: 978-981-97-1234-2

  • Online ISBN: 978-981-97-1235-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation