[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

A Side-Channel Attack on a Higher-Order Masked CRYSTALS-Kyber Implementation

  • Conference paper
  • First Online:
Applied Cryptography and Network Security (ACNS 2024)

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

Included in the following conference series:

Abstract

In response to side-channel attacks on masked implementations of post-quantum cryptographic algorithms, a new bitsliced higher-order masked implementation of CRYSTALS-Kyber has been presented at CHES’2022. The bitsliced implementations are typically more difficult to break by side-channel analysis because they execute a single instruction across multiple bits in parallel. However, in this paper, we reveal new vulnerabilities in the masked Boolean to arithmetic conversion procedure of this implementation that make the shared and secret key recovery possible. We also present a new chosen ciphertext construction method which maximizes secret key recovery probability for a given message bit recovery probability. We demonstrate practical shared and secret key recovery attacks on the first-, second- and third-order masked implementations of Kyber-768 in ARM Cortex-M4 using profiled deep learning-based power analysis.

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
£29.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
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 87.50
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 109.99
Price includes VAT (United Kingdom)
  • 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

Notes

  1. 1.

    We refer to [18, 25] for details since our leakage analysis does not rely on that.

  2. 2.

    The Hamming weight of an arithmetic share may remain the same if a non-zero value is subtracted.

References

  1. Announcing the commercial national security algorithm suite 2.0. National Security Agency, U.S Department of Defense, September 2022. https://media.defense.gov/2022/Sep/07/2003071834/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS_.PDF

  2. Amiet, D., Curiger, A., Leuenberger, L., Zbinden, P.: Defeating NewHope with a single trace. In: Ding, J., Tillich, J.-P. (eds.) PQCrypto 2020. LNCS, vol. 12100, pp. 189–205. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44223-1_11

    Chapter  Google Scholar 

  3. Avanzi, R., et al.: CRYSTALS-Kyber algorithm specifications and supporting documentation (2021). https://pq-crystals.org/kyber/data/kyber-specification-round3-20210131.pdf

  4. Azouaoui, M., Kuzovkova, Y., Schneider, T., van Vredendaal, C.: Post-quantum authenticated encryption against chosen-ciphertext side-channel attacks. IACR Trans. Crypt. Hardw. Embed. Syst. 2022, 372–396 (2022)

    Google Scholar 

  5. Backlund, L., Ngo, K., Gartner, J., Dubrova, E.: Secret key recovery attacks on masked and shuffled implementations of CRYSTALS-Kyber and Saber. Cryptology ePrint Archive, Paper 2022/1692 (2022). https://eprint.iacr.org/2022/1692

  6. Bhasin, S., D’Anvers, J.P., Heinz, D., Pöppelmann, T., Beirendonck, M.V.: Attacking and defending masked polynomial comparison for lattice-based cryptography. Cryptology ePrint Archive, Paper 2021/104 (2021). https://eprint.iacr.org/2021/104

  7. Bos, J.W., Gourjon, M., Renes, J., Schneider, T., Van Vredendaal, C.: Masking Kyber: first-and higher-order implementations. IACR Trans. Crypt. Hardw. Embed. Syst. 2021, 173–214 (2021)

    Google Scholar 

  8. Brisfors, M.: Advanced Side-Channel Analysis of USIMs, Bluetooth SoCs and MCUs. Master’s thesis, School of EECS, KTH (2021)

    Google Scholar 

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

    Google Scholar 

  10. D’Anvers, J.P., Beirendonck, M.V., Verbauwhede, I.: Revisiting higher-order masked comparison for lattice-based cryptography: algorithms and bit-sliced implementations. Cryptology ePrint Archive, Paper 2022/110 (2022). https://eprint.iacr.org/2022/110

  11. D’Anvers, J.P., Heinz, D., Pessl, P., Van Beirendonck, M., Verbauwhede, I.: Higher-order masked ciphertext comparison for lattice-based cryptography. IACR Trans. Crypt. Hardw. Embed. Syst. 2022, 115–139 (2022)

    Google Scholar 

  12. Do, Q., Martini, B., Choo, K.K.R.: The role of the adversary model in applied security research. Comput. Secur. 81, 156–181 (2019)

    Article  Google Scholar 

  13. Dubrova, E., Ngo, K., Gärtner, J., Wang, R.: Breaking a fifth-order masked implementation of crystals-kyber by copy-paste. In: Proceedings of the 10th ACM Asia Public-Key Cryptography Workshop, pp. 10–20 (2023)

    Google Scholar 

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

  15. Guo, Q., Nabokov, D., Nilsson, A., Johansson, T.: SCA-LDPC: a code-based framework for key-recovery side-channel attacks on post-quantum encryption schemes. Cryptology ePrint Archive (2023)

    Google Scholar 

  16. Hajra, S., Saha, S., Alam, M., Mukhopadhyay, D.: TransNet: shift invariant transformer network for side channel analysis. Cryptology ePrint Archive, Paper 2021/827 (2021). https://eprint.iacr.org/2021/827

  17. Hamburg, M., et al.: Chosen ciphertext k-trace attacks on masked CCA2 secure Kyber. IACR Trans. Crypt. Hardw. Embed. Syst. 2021, 88–113 (2021)

    Google Scholar 

  18. Heinz, D., Kannwischer, M.J., Land, G., Pöppelmann, T., Schwabe, P., Sprenkels, D.: First-order masked Kyber on ARM Cortex-M4. Cryptology ePrint Archive, Paper 2022/058 (2022). https://eprint.iacr.org/2022/058

  19. Hoffmann, C., Libert, B., Momin, C., Peters, T., Standaert, F.X.: Towards leakage-resistant post-quantum CCA-secure public key encryption. Cryptology ePrint Archive, Paper 2022/873 (2022). https://eprint.iacr.org/2022/873

  20. Ji, Y., Wang, R., Ngo, K., Dubrova, E., Backlund, L.: A side-channel attack on a hardware implementation of CRYSTALS-Kyber. Cryptology ePrint Archive, Paper 2022/1452 (2022). https://eprint.iacr.org/2022/1452

  21. Kannwischer, M.J., Petri, R., Rijneveld, J., Schwabe, P., Stoffelen, K.: PQM4: post-quantum crypto library for the ARM Cortex-M4. https://github.com/mupq/pqm4

  22. Maghrebi, H., Portigliatti, T., Prouff, E.: Breaking cryptographic implementations using deep learning techniques. In: Carlet, C., Hasan, M.A., Saraswat, V. (eds.) SPACE 2016. LNCS, vol. 10076, pp. 3–26. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-49445-6_1

    Chapter  Google Scholar 

  23. Moody, D.: Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process. NISTIR 8309, pp. 1–27 (2022). https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413.pdf

  24. Ngo, K., Dubrova, E., Guo, Q., Johansson, T.: A side-channel attack on a masked IND-CCA secure Saber KEM implementation. IACR Trans. Crypt. Hardw. Embed. Syst. 2012, 676–707 (2021)

    Google Scholar 

  25. Oder, T., Schneider, T., Pöppelmann, T., Güneysu, T.: Practical CCA2-secure and masked ring-LWE implementation. IACR Trans. Crypt. Hardw. Embed. Syst. 2018, 142–174 (2018)

    Google Scholar 

  26. Picek, S., Samiotis, I.P., Kim, J., Heuser, A., Bhasin, S., Legay, A.: On the performance of convolutional neural networks for side-channel analysis. In: Chattopadhyay, A., Rebeiro, C., Yarom, Y. (eds.) SPACE 2018. LNCS, vol. 11348, pp. 157–176. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-05072-6_10

    Chapter  Google Scholar 

  27. Rajendran, G., Ravi, P., D’Anvers, J.P., Bhasin, S., Chattopadhyay, A.: Pushing the limits of generic side-channel attacks on LWE-based KEMs-parallel PC oracle attacks on Kyber KEM and beyond. IACR Trans. Crypt. Hardw. Embed. Syst. 2023, 418–446 (2023)

    Google Scholar 

  28. Ravi, P., Bhasin, S., Roy, S.S., Chattopadhyay, A.: On exploiting message leakage in (few) NIST PQC candidates for practical message recovery attacks. IEEE Trans. Inf. Forensics Secur. 17, 684–699 (2021)

    Article  Google Scholar 

  29. Ravi, P., Roy, S.S., Chattopadhyay, A., Bhasin, S.: Generic side-channel attacks on CCA-secure lattice-based PKE and KEMs. IACR Trans. Crypt. Hardw. Embed. Syst. 2020, 307–335 (2020)

    Google Scholar 

  30. Rodriguez, R.C., Bruguier, F., Valea, E., Benoit, P.: Correlation electromagnetic analysis on an FPGA implementation of CRYSTALS-Kyber. Cryptology ePrint Archive, Paper 2022/1361 (2022). https://eprint.iacr.org/2022/1361

  31. Schneider, T., Paglialonga, C., Oder, T., Güneysu, T.: Efficiently masking binomial sampling at arbitrary orders for lattice-based crypto. In: Lin, D., Sako, K. (eds.) PKC 2019. LNCS, vol. 11443, pp. 534–564. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17259-6_18

    Chapter  Google Scholar 

  32. Shen, M., Cheng, C., Zhang, X., Guo, Q., Jiang, T.: Find the bad apples: an efficient method for perfect key recovery under imperfect SCA oracles - a case study of Kyber. IACR Trans. Crypt. Hardw. Embed. Syst. 2023, 89–112 (2023)

    Google Scholar 

  33. Sim, B.Y., et al.: Single-trace attacks on message encoding in lattice-based KEMs. IEEE Access 8, 183175–183191 (2020)

    Article  Google Scholar 

  34. Tsai, T.T., Huang, S.S., Tseng, Y.M., Chuang, Y.H., Hung, Y.H.: Leakage-resilient certificate-based authenticated key exchange protocol. IEEE Open J. Comput. Soc. 3, 137–148 (2022)

    Article  Google Scholar 

  35. 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. Crypt. Hardw. Embed. Syst. 2022, 296–322 (2022)

    Google Scholar 

  36. Wang, H., Forsmark, S., Brisfors, M., Dubrova, E.: Multi-source training deep learning side-channel attacks. In: IEEE 50th International Symposium on Multiple-Valued Logic, ISMVL 2020 (2020)

    Google Scholar 

  37. Wang, J., Cao, W., Chen, H., Li, H.: Practical side-channel attack on message encoding in masked Kyber. In: 2022 IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), pp. 882–889. IEEE (2022)

    Google Scholar 

  38. Wang, R., Ngo, K., Dubrova, E.: A message recovery attack on LWE/LWR-based PKE/KEMs using amplitude-modulated EM emanations. In: Seo, SH., Seo, H. (eds.) Information Security and Cryptology, ICISC 2022. LNCS, vol. 13849, pp. 450–471. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-29371-9_22

  39. Wang, R., Wang, H., Dubrova, E.: Far field EM side-channel attack on AES using deep learning. In: Proceedings of the 4th ACM Workshop on Attacks and Solutions in Hardware Security, pp. 35–44 (2020)

    Google Scholar 

  40. Wu, L., Picek, S.: Remove some noise: On pre-processing of side-channel measurements with autoencoders. IACR Trans. Crypt. Hardw. Embed. Syst. 2020, 389–415 (2020)

    Google Scholar 

  41. Xu, Z., Pemberton, O.M., Roy, S.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, 2163–2176 (2021)

    Article  Google Scholar 

  42. Yajing, C., Yan, Y., Zhu, C., Guo, P.: Template attack of LWE/LWR-based schemes with cyclic message rotation. Entropy 24(10), 1489 (2022)

    Article  Google Scholar 

Download references

Acknowledgments

This work was supported in part by the Swedish Civil Contingencies Agency (Grant No. 2020-11632) and the Swedish Research Council (Grant No. 2018-04482).

Author information

Authors and Affiliations

  1. KTH Royal Institute of Technology, Stockholm, Sweden

    Ruize Wang, Martin Brisfors & Elena Dubrova

Authors
  1. Ruize Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Martin Brisfors
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Elena Dubrova
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ruize Wang .

Editor information

Editors and Affiliations

  1. New York University Abu Dhabi, Abu Dhabi, United Arab Emirates

    Christina Pöpper

  2. Radboud University Nijmegen, Nijmegen, The Netherlands

    Lejla Batina

Rights and permissions

Reprints and permissions

Copyright information

© 2024 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

Wang, R., Brisfors, M., Dubrova, E. (2024). A Side-Channel Attack on a Higher-Order Masked CRYSTALS-Kyber Implementation. In: Pöpper, C., Batina, L. (eds) Applied Cryptography and Network Security. ACNS 2024. Lecture Notes in Computer Science, vol 14585. Springer, Cham. https://doi.org/10.1007/978-3-031-54776-8_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-54776-8_12

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-54775-1

  • Online ISBN: 978-3-031-54776-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation