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
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We ran the experiment using the BKZ implementation from fpylll in Sage9.2. See https://github.com/fplll/fpylll.
References
Avanzi, R., et al.: CRYSTALS-Kyber (version 3.02) - submission to round 3 of the NIST post-quantum project. Specification document (2021)
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
Bos, J., et al.: Kyber (2023). https://github.com/pq-crystals/kyber
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
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)
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
Cooley, J.W., Tukey, J.W.: An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19, 297–301 (1965)
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
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)
ELMO: Evaluating leaks for the arm cortex-m0. https://github.com/sca-research/ELMO. Accessed 17 Oct 2022
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
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
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
Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415–440 (1987). http://www.jstor.org/stable/3689974
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
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
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
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
May, A., Nowakowski, J.: Too many hints - when LLL breaks LWE. Cryptology ePrint Archive, Paper 2023/777 (2023). https://eprint.iacr.org/2023/777
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)
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
National Institute of Standards and Technology. Post-quantum cryptography standardization. https://csrc.nist.gov/projects/post-quantum-cryptography. Accessed 12 Oct 2022
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
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
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
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
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
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
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)