Abstract
NTRU 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-ciphertext side-channel attacks on the latest variants of NTRU, i.e., NTRU-HPS and NTRU-HRSS as in Round 3 submissions. Both methods utilize the leakage from the polynomial modular reduction to recover the long-term secret key. For the first attack, although the side-channel leakage does not directly reveal the secret polynomial \(\textbf{f}\), we recover differences between adjacent coefficients using appropriately chosen ciphertexts, and finally reconstruct \(\textbf{f}\) through linear algebra. The second attack is based on the inherent relation between the secret key and the public key in NTRU-HPS: we first reveal the “invisible” secret polynomial \(\textbf{g}\) with chosen ciphertexts and then use \(\textbf{g}\) and the public polynomial \(\textbf{h}\) to compute \(\textbf{f}\). In theory, these attacks only need 4 and 2 ciphertexts, respectively. We then practically apply those attacks on all reference implementations of four instances in the PQClean library and show that the accuracy of secret-key recovery can reach 100% with only few traces (4 to 24 and 2 to 6, respectively). We also observe similar leakage in optimized implementations in the pqm4 library and propose an according analysis scheme.
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
References
Alagic, G., et al.: Status report on the second round of the NIST post-quantum cryptography standardization process. Rep. NISTIR 8309, US Department of Commerce, NIST, July 2020. https://doi.org/10.6028/NIST.IR.8309
Alagic, G., et al.: Status report on the first round of the NIST post-quantum cryptography standardization process. Rep. NISTIR 8240, US Department of Commerce, NIST, January 2019. https://doi.org/10.6028/NIST.IR.8240
Alagic, G., et al.: Status report on the third round of the NIST post-quantum cryptography standardization process. Technical report NISTIR 8413, US Department of Commerce, NIST, July 2022. https://doi.org/10.6028/NIST.IR.8413
An, S., Kim, S., Jin, S., Kim, H., Kim, H.: Single trace side channel analysis on NTRU implementation. Appl. Sci. 8(11) (2018). https://doi.org/10.3390/app8112014
Askeland, A., Rønjom, S.: A side-channel assisted attack on NTRU. Cryptology ePrint Archive, Paper 2021/790 (2021). https://eprint.iacr.org/2021/790
Atici, A.C., Batina, L., Gierlichs, B., Verbauwhede, I.: Power analysis on NTRU implementations for RFIDs: First results. In: RFIDSec 2008 (2008)
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
Chen, C., et al.: NTRU: algorithm specifications and supporting documentation. Technical report, NIST (2020). https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions
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.) AFRICACRYPT 2018. LNCS, vol. 10831, pp. 282–305. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-89339-6_16
Ding, J., Deaton, J., Schmidt, K., Vishakha, Zhang, Z.: A simple and efficient key reuse attack on NTRU cryptosystem. Cryptology ePrint Archive, Paper 2019/1022 (2019). https://eprint.iacr.org/2019/1022
Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a new high speed public key cryptosystem. presented at the rump session of Crypto 96 (1996)
Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054868
Huang, W.L., Chen, J.P., Yang, B.Y.: Power analysis on NTRU Prime. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2020(1), 123–151 (2019). https://doi.org/10.13154/tches.v2020.i1.123-151
Hülsing, A., Rijneveld, J., Schanck, J., Schwabe, P.: High-speed key encapsulation from NTRU. In: Fischer, W., Homma, N. (eds.) CHES 2017. LNCS, vol. 10529, pp. 232–252. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66787-4_12
Jaulmes, É., Joux, A.: A chosen-ciphertext attack against NTRU. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 20–35. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44598-6_2
Kannwischer, M.J., Rijneveld, J., Schwabe, P., Stoffelen, K.: PQM4: post-quantum crypto library for the ARM Cortex-M4. https://github.com/mupq/pqm4
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: 2021 IEEE International Symposium on Hardware Oriented Security and Trust (HOST), pp. 35–45. IEEE (2021). https://doi.org/10.1109/HOST49136.2021.9702284
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
Lee, M., Song, J.E., Choi, D., Han, D.: Countermeasures against power analysis attacks for the NTRU public key cryptosystem. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E93.A(1), 153–163 (2010). https://doi.org/10.1587/transfun.E93.A.153
Mujdei, C., Beckers, A., Mera, J.M.B., Karmakar, A., Wouters, L., Verbauwhede, I.: Side-channel analysis of lattice-based post-quantum cryptography: Exploiting polynomial multiplication. Cryptology ePrint Archive, Paper 2022/474 (2022). https://eprint.iacr.org/2022/474
Park, A., Han, D.G.: Chosen ciphertext simple power analysis on software 8-bit implementation of Ring-LWE encryption. In: 2016 IEEE Asian Hardware-Oriented Security and Trust (AsianHOST), pp. 1–6 (2016). https://doi.org/10.1109/AsianHOST.2016.7835555
Ravi, P., Ezerman, M.F., Bhasin, S., Chattopadhyay, A., Sinha Roy, S.: Will you cross the threshold for me? Generic side-channel assisted chosen-ciphertext attacks on NTRU-based KEMs. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2022(1), 722–761 (2022). https://doi.org/10.46586/tches.v2022.i1.722-761
Schanck, J.M.: A comparison of NTRU variants. Cryptology ePrint Archive, Paper 2018/1174 (2018). https://eprint.iacr.org/2018/1174
Sim, B., et al.: Single-trace attacks on message encoding in lattice-based KEMs. IEEE Access 8, 183175–183191 (2020). https://doi.org/10.1109/ACCESS.2020.3029521
Tizpaz-Niari, S., Cerný, P., Trivedi, A.: Data-driven debugging for functional side channels. In: 27th Annual Network and Distributed System Security (NDSS) Symposium, San Diego, California, USA, 23–26 February 2020. The Internet Society (2020). https://doi.org/10.14722/ndss.2020.24269
Ueno, R., Xagawa, K., Tanaka, Y., Ito, A., Takahashi, J., Homma, N.: Curse of re-encryption: a generic power/EM analysis on post-quantum KEMs. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2022(1), 296–322 (2021). https://doi.org/10.46586/tches.v2022.i1.296-322
Xu, Z., Pemberton, O., Sinha Roy, S., Oswald, D., Yao, W., Zheng, Z.: Magnifying side-channel leakage of lattice-based cryptosystems with chosen ciphertexts: the case study of Kyber. IEEE Trans. Comput. 71(9), 2163–2176 (2022). https://doi.org/10.1109/TC.2021.3122997
Zhang, X., Cheng, C., Ding, R.: Small leaks sink a great ship: an evaluation of key reuse resilience of PQC third round finalist NTRU-HRSS. In: Gao, D., Li, Q., Guan, X., Liao, X. (eds.) ICICS 2021. LNCS, vol. 12919, pp. 283–300. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-88052-1_17
Zheng, X., Wang, A., Wei, W.: First-order collision attack on protected NTRU cryptosystem. Microprocess. Microsyst. 37(6), 601–609 (2013). https://doi.org/10.1016/j.micpro.2013.04.008
Acknowledgements
This work is partially supported by the National Key Research and Development Program of China (2020YFB1005700) and by the Engineering and Physical Sciences Research Council (EPSRC) under grants EP/R012598/1 and EP/V000454/1. We thank the anonymous reviewers for the valuable comments and Sitong Zong for her helpful proofreading advice.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Xu, Z., Pemberton, O., Oswald, D., Zheng, Z. (2023). Reveal the Invisible Secret: Chosen-Ciphertext Side-Channel Attacks on NTRU. In: Buhan, I., Schneider, T. (eds) Smart Card Research and Advanced Applications. CARDIS 2022. Lecture Notes in Computer Science, vol 13820. Springer, Cham. https://doi.org/10.1007/978-3-031-25319-5_12
Download citation
DOI: https://doi.org/10.1007/978-3-031-25319-5_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-25318-8
Online ISBN: 978-3-031-25319-5
eBook Packages: Computer ScienceComputer Science (R0)