A Side-Channel Attack on a Higher-Order Masked CRYSTALS-Kyber Implementation
Pages 301 - 324
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.
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, and Zbinden P Ding J and Tillich J-P Defeating NewHope with a single trace Post-Quantum Cryptography 2020 Cham Springer 189-205
[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, and van Vredendaal C Post-quantum authenticated encryption against chosen-ciphertext side-channel attacks IACR Trans. Crypt. Hardw. Embed. Syst. 2022 2022 372-396
[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 JW, Gourjon M, Renes J, Schneider T, and Van Vredendaal C Masking Kyber: first-and higher-order implementations IACR Trans. Crypt. Hardw. Embed. Syst. 2021 2021 173-214
[8]
Brisfors, M.: Advanced Side-Channel Analysis of USIMs, Bluetooth SoCs and MCUs. Master’s thesis, School of EECS, KTH (2021)
[9]
Bronchain O and Cassiers G Bitslicing arithmetic/Boolean masking conversions for fun and profit: with application to lattice-based KEMs IACR Trans. Crypt. Hardw. Embed. Syst. 2022 2022 553-588
[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 JP, Heinz D, Pessl P, Van Beirendonck M, and Verbauwhede I Higher-order masked ciphertext comparison for lattice-based cryptography IACR Trans. Crypt. Hardw. Embed. Syst. 2022 2022 115-139
[12]
Do Q, Martini B, and Choo KKR The role of the adversary model in applied security research Comput. Secur. 2019 81 156-181
[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)
[14]
Fujisaki E and Okamoto T Wiener M Secure integration of asymmetric and symmetric encryption schemes Advances in Cryptology — CRYPTO’ 99 1999 Heidelberg Springer 537-554
[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)
[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 2021 88-113
[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, and Prouff E Carlet C, Hasan MA, and Saraswat V Breaking cryptographic implementations using deep learning techniques Security, Privacy, and Applied Cryptography Engineering 2016 Cham Springer 3-26
[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, and Johansson T A side-channel attack on a masked IND-CCA secure Saber KEM implementation IACR Trans. Crypt. Hardw. Embed. Syst. 2021 2012 676-707
[25]
Oder T, Schneider T, Pöppelmann T, and Güneysu T Practical CCA2-secure and masked ring-LWE implementation IACR Trans. Crypt. Hardw. Embed. Syst. 2018 2018 142-174
[26]
Picek S, Samiotis IP, Kim J, Heuser A, Bhasin S, and Legay A Chattopadhyay A, Rebeiro C, and Yarom Y On the performance of convolutional neural networks for side-channel analysis Security, Privacy, and Applied Cryptography Engineering 2018 Cham Springer 157-176
[27]
Rajendran G, Ravi P, D’Anvers JP, Bhasin S, and 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 2023 418-446
[28]
Ravi P, Bhasin S, Roy SS, and Chattopadhyay A On exploiting message leakage in (few) NIST PQC candidates for practical message recovery attacks IEEE Trans. Inf. Forensics Secur. 2021 17 684-699
[29]
Ravi P, Roy SS, Chattopadhyay A, and Bhasin S Generic side-channel attacks on CCA-secure lattice-based PKE and KEMs IACR Trans. Crypt. Hardw. Embed. Syst. 2020 2020 307-335
[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, and Güneysu T Lin D and Sako K Efficiently masking binomial sampling at arbitrary orders for lattice-based crypto Public-Key Cryptography – PKC 2019 2019 Cham Springer 534-564
[32]
Shen M, Cheng C, Zhang X, Guo Q, and 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 2023 89-112
[33]
Sim BY et al. Single-trace attacks on message encoding in lattice-based KEMs IEEE Access 2020 8 183175-183191
[34]
Tsai TT, Huang SS, Tseng YM, Chuang YH, and Hung YH Leakage-resilient certificate-based authenticated key exchange protocol IEEE Open J. Comput. Soc. 2022 3 137-148
[35]
Ueno R, Xagawa K, Tanaka Y, Ito A, Takahashi J, and Homma N Curse of re-encryption: a generic power/EM analysis on post-quantum KEMs IACR Trans. Crypt. Hardw. Embed. Syst. 2022 2022 296-322
[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)
[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)
[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).
[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)
[40]
Wu L and Picek S Remove some noise: On pre-processing of side-channel measurements with autoencoders IACR Trans. Crypt. Hardw. Embed. Syst. 2020 2020 389-415
[41]
Xu Z, Pemberton OM, Roy SS, Oswald D, Yao W, and Zheng Z Magnifying side-channel leakage of lattice-based cryptosystems with chosen ciphertexts: the case study of Kyber IEEE Trans. Comput. 2021 71 2163-2176
[42]
Yajing C, Yan Y, Zhu C, and Guo P Template attack of LWE/LWR-based schemes with cyclic message rotation Entropy 2022 24 10 1489
Recommendations
A Side-Channel Attack on a Masked Hardware Implementation of CRYSTALS-Kyber
ASHES '23: Proceedings of the 2023 Workshop on Attacks and Solutions in Hardware SecurityNIST has recently selected CRYSTALS-Kyber as a new public key encryption and key establishment algorithm to be standardized. This makes it important to evaluate the resistance of CRYSTALS-Kyber implementations to side-channel attacks. Software ...
Breaking a Fifth-Order Masked Implementation of CRYSTALS-Kyber by Copy-Paste
APKC '23: Proceedings of the 10th ACM Asia Public-Key Cryptography WorkshopCRYSTALS-Kyber has been selected by the NIST as a public-key encryption and key encapsulation mechanism to be standardized. It is also included in the NSA’s suite of cryptographic algorithms recommended for national security systems. This makes it ...
A Shared Key Recovery Attack on a Masked Implementation of CRYSTALS-Kyber’s Encapsulation Algorithm
Foundations and Practice of SecurityAbstractIn July 2022, NIST selected CRYSTALS-Kyber as a new post-quantum secure public key encryption and key encapsulation mechanism to be standardized. To safeguard its shared and secret keys from side-channel attacks (SCA), countermeasures such as ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Mar 2024
475 pages
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 05 March 2024
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024