Abstract
Shuffling is a well-known countermeasure against side-channel attacks. It typically uses the Fisher-Yates (FY) algorithm to generate a random permutation which is then utilized as the loop iterator to index the processing of the variables inside the loop. The processing order is scrambled as a result, making side-channel attacks more difficult. Recently, a side-channel attack on a masked and shuffled implementation of Saber requiring 61,680 power traces to extract the long-term secret key was reported. In this paper, we present an attack that can recover the long-term secret key of Saber from 4,608 traces. The key idea behind the 13-fold improvement is to recover FY indexes directly, rather than by extracting the message Hamming weight and bit flipping, as in the previous attack. We capture a power trace during the execution of the decryption algorithm for a given ciphertext, recover FY indexes 0 and 255, and extract the corresponding two message bits. Then, we modify the ciphertext to cyclically rotate the message, capture a power trace, and extract the next two message bits with FY indexes 0 and 255. In this way, all message bits can be extracted. By recovering messages contained in \(k*l\) chosen ciphertexts constructed using a new method based on error-correcting codes of length l, where k is the module rank, we recover the long-term secret key. To demonstrate the generality of the presented approach, we also recover the secret key from a masked and shuffled implementation of CRYSTALS-Kyber, which NIST recently selected as a new public-key encryption and key-establishment algorithm to be standardized.
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.
ChipWhisperer-Pro has an option of streaming, however, streaming can be used only at a maximum of 10 MHz sampling frequency.
- 2.
In the notation [l, w, d], l is the codeword length, w is the dataword length, and d is the code distance. A code distance is the minimum Hamming distance between any two codewords of the code.
References
Announcing the commercial national security algorithm suite 2.0. National Security Agency, U.S Department of Defense (2022). https://media.defense.gov/2022/Sep/07/2003071834/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS_.PDF
Agrawal, Dakshi, Archambeault, Bruce, Rao, Josyula R.., Rohatgi, Pankaj: The EM side—channel(s). In: Kaliski, Burton S.., Koç, çetin K.., Paar, Christof (eds.) CHES 2002. LNCS, vol. 2523, pp. 29–45. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36400-5_4
Azouaoui, M., et al.: Post-quantum authenticated encryption against chosen-ciphertext side-channel attacks. IACR Trans. Cryptogr. Hardw. Embed. Syst. 372–396 (2022). https://doi.org/10.46586/tches.v2022.i4.372-396
Beirendonck, M.V., et al.: A side-channel-resistant implementation of saber. J. Emerg. Technol. Comput. Syst. 17(2) (2021). https://doi.org/10.1145/3429983
Bhasin, S., et al.: Attacking and defending masked polynomial comparison for lattice-based cryptography. IACR Trans. Cryptogr. Hardw. Embed. Syst. 334–359 (2021). https://doi.org/10.46586/tches.v2021.i3.334-359
Bos, J.W., et al.: Masking kyber: first-and higher-order implementations. IACR Trans. Cryptogr. Hardw. Embed. Syst 2021(4), 173–214 (2021). https://doi.org/10.46586/tches.v2021.i4.173-214
Chari, Suresh, Jutla, Charanjit S.., Rao, Josyula R.., Rohatgi, Pankaj: Towards sound approaches to counteract power-analysis attacks. In: Wiener, Michael (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 398–412. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_26
Chen, C., et al.: NTRU algorithm specifications and supporting documentation (2020). https://csrc.nist.gov/projects/postquantum-cryptography/round-3-submissions
Coron, Jean-Sébastien., Kizhvatov, Ilya: An efficient method for random delay generation in embedded software. In: Clavier, Christophe, Gaj, Kris (eds.) CHES 2009. LNCS, vol. 5747, pp. 156–170. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04138-9_12
Dachman-Soled, Dana, Ducas, Léo., Gong, Huijing, Rossi, Mélissa.: LWE with side information: attacks and concrete security estimation. In: Micciancio, Daniele, Ristenpart, Thomas (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 329–358. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_12
D’Anvers, J., et al.: Saber algorithm specifications and supporting documentation (2020). https://www.esat.kuleuven.be/cosic/pqcrypto/saber/files/saberspecround3.pdf
D’Anvers, J.P., et al.: Revisiting higher-order masked comparison for lattice-based cryptography: algorithms and bit-sliced implementations. Cryptology ePrint Archive, 2022/110 (2022). https://eprint.iacr.org/2022/110
Heinz, D., et al.: First-order masked Kyber on ARM Cortex-M4. Cryptology ePrint Archive, Report 2022/058 (2022). https://eprint.iacr.org/2022/058
Hoffmann, C., et al.: Towards leakage-resistant post-quantum CCA-secure public key encryption. Cryptology ePrint Archive, Report 2022/873 (2022). https://eprint.iacr.org/2022/873
Hofheinz, Dennis, Hövelmanns, Kathrin, Kiltz, Eike: A modular analysis of the Fujisaki-Okamoto transformation. In: Kalai, Yael, Reyzin, Leonid (eds.) TCC 2017. LNCS, vol. 10677, pp. 341–371. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_12
Kocher, Paul, Jaffe, Joshua, Jun, Benjamin: Differential power analysis. In: Wiener, Michael (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_25
Kocher, Paul C..: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, Neal (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68697-5_9
Kundu, S., et al.: Higher-order masked Saber. Cryptology ePrint Archive, Report 2022/389 (2022). https://eprint.iacr.org/2022/389
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
Ngo, K., Dubrova, E., Guo, Q., Johansson, T.: A side-channel attack on a masked IND-CCA secure saber KEM implementation. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2021(4), 676–707 (2021). https://doi.org/10.46586/tches.v2021.i4.676-707
Ngo, K., Dubrova, E., Johansson, T.: Breaking masked and shuffled CCA secure saber KEM by power analysis. In: Proceedings of the 5th Workshop on Attacks and Solutions in Hardware Security, pp. 51–61. ACM (2021)
Ngo, K., Wang, R., Dubrova, E., Paulsrud, N.: Side-channel attacks on lattice-based KEMs are not prevented by higher-order masking. Cryptology ePrint Archive, Report 2022/919 (2022). https://eprint.iacr.org/2022/919
Paulsrud, N.: A side channel attack on a higher-order masked software implementation of saber. Master’s thesis, KTH (2022)
Ravi, P., et al.: On exploiting message leakage in (few) NIST PQC candidates for practical message recovery and key recovery attacks. Crypt. ePrint Arch., 2020/1559 (2020). https://eprint.iacr.org/2020/1559
Schwabe, P., et al.: CRYSTALS-Kyber algorithm specifications and supporting documentation (2020). https://csrc.nist.gov/projects/postquantum-cryptography/round-3-submissions
Shen, M., et al.: Find the bad apples: an efficient method for perfect key recovery under imperfect SCA oracles - a case study of Kyber. Cryptology ePrint Archive, Report 2022/563 (2022). https://eprint.iacr.org/2022/563
Sim, B.Y., et al.: Single-trace attacks on the message encoding of lattice-based kems. Cryptology ePrint Archive, Report 2020/992 (2020). https://eprint.iacr.org/2020/992
Tsai, T.T., et al.: Leakage-resilient certificate-based authenticated key exchange protocol. IEEE Open J. Comput. Soc. 3, 137–148 (2022). https://doi.org/10.1109/OJCS.2022.3198073
Veyrat-Charvillon, Nicolas, Medwed, Marcel, Kerckhof, Stéphanie., Standaert, François-Xavier.: Shuffling against side-channel attacks: a comprehensive study with cautionary note. In: Wang, Xiaoyun, Sako, Kazue (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 740–757. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_44
Wang, J., et al.: Practical side-channel attack on masked message encoding in latticed-based KEM. Cryptology ePrint Archive, Report 2022/859 (2022). https://eprint.iacr.org/2022/859
Wang, R., Ngo, K., Dubrova, E.: A message recovery attack on LWE/LWR-based PKE/KEMs using amplitude-modulated EM emanations. In: International Conference on Information Security and Cryptology (2022). https://eprint.iacr.org/2022/852
Wang, R., Ngo, K., Dubrova, E.: Side-channel analysis of Saber KEM using amplitude-modulated EM emanations. In: Proceedings of the 25th Euromicro Conference on Digital System Design (2022). https://eprint.iacr.org/2022/807
Welch, B.L.: The generalization of ‘Student’s’ problem when several different population variances are involved. Biometrika 34(1/2), 28–35 (1947)
Xu, Z., et al.: Magnifying side-channel leakage of lattice-based cryptosystems with chosen ciphertexts: the case study of Kyber. Cryptology ePrint Archive, Paper 2020/912 (2020). https://doi.org/10.1109/TC.2021.3122997
Yajing, C., et al.: Template attack of LWE/LWR-based schemes with cyclic message rotation. Entropy 24(10), 15 (2022). https://doi.org/10.3390/e24101489
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
Corresponding authors
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
Backlund, L., Ngo, K., Gärtner, J., Dubrova, E. (2023). Secret Key Recovery Attack on Masked and Shuffled Implementations of CRYSTALS-Kyber and Saber. In: Zhou, J., et al. Applied Cryptography and Network Security Workshops. ACNS 2023. Lecture Notes in Computer Science, vol 13907. Springer, Cham. https://doi.org/10.1007/978-3-031-41181-6_9
Download citation
DOI: https://doi.org/10.1007/978-3-031-41181-6_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-41180-9
Online ISBN: 978-3-031-41181-6
eBook Packages: Computer ScienceComputer Science (R0)