Cracking the Mask: SASCA Against Local-Masked NTT for CRYSTALS-Kyber

Rafael Carrera Rodriguez; Florent Bruguier; Emanuele Valea; Pascal Benoit

doi:10.62056/aesgbnja5

Cracking the Mask: SASCA Against Local-Masked NTT for CRYSTALS-Kyber

Authors

Rafael Carrera Rodriguez, Florent Bruguier, Emanuele Valea, Pascal Benoit

Rafael Carrera Rodriguez

LIRMM, University of Montpellier, CNRS, Montpellier, France
Univ. Grenoble Alpes, CEA, List, Grenoble, France
rafael dot carrera-rodriguez at lirmm dot fr

Florent Bruguier

LIRMM, University of Montpellier, CNRS, Montpellier, France
florent dot bruguier at lirmm dot fr

Emanuele Valea

Univ. Grenoble Alpes, CEA, List, Grenoble, France
emanuele dot valea at cea dot fr

Pascal Benoit

LIRMM, University of Montpellier, CNRS, Montpellier, France
pascal dot benoit at lirmm dot fr

Abstract

Soft-Analytical Side-Channel Attacks (SASCAs) on lattice-based cryptography implementations have become a prominent vector of attack in the recent years, specially against the Number-Theoretic Transform (NTT). To address this issue, local masking with twiddle factors has been proposed as a countermeasure to protect the NTT against such attacks. In this paper we propose an adaptation of SASCA to local-masked NTT implementations, by modifying the factor graph representation to include the masking nodes. We evaluate the success rate of the attack with respect to the level of noise of simulated traces and the number of masks $u$ per layer. We show that the attack proves very successful in the lower values of $u$, by even outperforming the attack on the unmasked case. When $u$ is increased there is a gradual augmentation of security, which comes with an important overhead on performance. Thus, we question the practicality of this countermeasure when compared to other analyzed countermeasures in the state of the art, such as shuffling.

References

[ABD⁺21]

Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Kyber: Algorithm Specifications and Supporting Documentation. 2021.

Google Scholar ePrint

[ADPS16]

Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum Key Exchange - A New Hope. In Thorsten Holz and Stefan Savage, editors, 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, August 10-12, 2016, pages 327–343. 2016. USENIX Association.

Google Scholar ePrint

[AG01]

Mehdi-Laurent Akkar and Christophe Giraud. An Implementation of DES and AES, Secure against Some Attacks. In Cetin K. Koç, David Naccache, and Christof Paar, editors, Cryptographic Hardware and Embedded Systems — CHES 2001, pages 309–318, Berlin, Heidelberg. 2001. Springer. DOI: 10.1007/3-540-44709-1_26

Google Scholar ePrint

[CB23]

Gaëtan Cassiers and Olivier Bronchain. SCALib: A Side-Channel Analysis Library. Journal of Open Source Software, 8(86):5196, June 2023. DOI: 10.21105/joss.05196

Google Scholar ePrint

[CBVB23]

Rafael Carrera Rodriguez, Florent Bruguier, Emanuele Valea, and Pascal Benoit. Correlation Electromagnetic Analysis on an FPGA Implementation of CRYSTALS-Kyber. In 2023 18th Conference on Ph.D Research in Microelectronics and Electronics (PRIME), pages 217–220, Valencia, Spain. June 2023. IEEE. DOI: 10.1109/PRIME58259.2023.10161764

Google Scholar ePrint

[CRR03]

Suresh Chari, Josyula R. Rao, and Pankaj Rohatgi. Template Attacks. Cryptographic Hardware and Embedded Systems - CHES 2002, 2003. DOI: 10.1007/3-540-36400-5_3

Google Scholar ePrint

[CRVBB24]

Rafael Carrera Rodriguez, Emanuele Valea, Florent Bruguier, and Pascal Benoit. Hardware Implementation and Security Analysis of Local-Masked NTT for CRYSTALS-Kyber. Publication info: Preprint.. 2024.

Google Scholar ePrint

[CT65]

James W. Cooley and John W. Tukey. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 19(90):297–301, 1965. DOI: 10.1090/S0025-5718-1965-0178586-1

Google Scholar ePrint

[FO99]

Eiichiro Fujisaki and Tatsuaki Okamoto. Secure Integration of Asymmetric and Symmetric Encryption Schemes. In Michael Wiener, editor, Advances in Cryptology — CRYPTO' 99, pages 537–554. 1999. Springer Berlin Heidelberg. DOI: 10.1007/s00145-011-9114-1

Google Scholar ePrint

[GS66]

W. M. Gentleman and G. Sande. Fast Fourier Transforms: for fun and profit. In Proceedings of the November 7-10, 1966, fall joint computer conference on XX - AFIPS '66 (Fall), pages 563, San Francisco, California. 1966. ACM Press. DOI: 10.1145/1464291.1464352

Google Scholar ePrint

[GT03]

Jovan D. Golić and Christophe Tymen. Multiplicative Masking and Power Analysis of AES. In Burton S. Kaliski, Cetin K. Koç, and Christof Paar, editors, Cryptographic Hardware and Embedded Systems - CHES 2002, pages 198–212, Berlin, Heidelberg. 2003. Springer. DOI: 10.1007/3-540-36400-5_16

Google Scholar ePrint

[HHP⁺21]

Mike Hamburg, Julius Hermelink, Robert Primas, Simona Samardjiska, Thomas Schamberger, Silvan Streit, Emanuele Strieder, and Christine Van Vredendaal. Chosen Ciphertext k-Trace Attacks on Masked CCA2 Secure Kyber. IACR Transactions on Cryptographic Hardware and Embedded Systems, August 2021. DOI: 10.46586/tches.v2021.i4.88-113

Google Scholar ePrint

[HSST23]

Julius Hermelink, Silvan Streit, Emanuele Strieder, and Katharina Thieme. Adapting belief propagation to counter shuffling of NTTs. IACR Transactions on Cryptographic Hardware and Embedded Systems, October 2023. DOI: 10.46586/tches.v2023.i1.60-88

Google Scholar ePrint

[KPP20]

Matthias J. Kannwischer, Peter Pessl, and Robert Primas. Single-Trace Attacks on Keccak. IACR Transactions on Cryptographic Hardware and Embedded Systems, June 2020. DOI: 10.46586/tches.v2020.i3.243-268

Google Scholar ePrint

[LPR10]

Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On Ideal Lattices and Learning with Errors over Rings. In Henri Gilbert, editor, Advances in Cryptology – EUROCRYPT 2010, pages 1–23, Berlin, Heidelberg. 2010. Springer. DOI: 10.1007/978-3-642-13190-5_1

Google Scholar ePrint

[LS15]

Adeline Langlois and Damien Stehlé. Worst-Case to Average-Case Reductions for Module Lattices. Des. Codes Cryptography, 75(3):565–599, June 2015. DOI: 10.1007/s10623-014-9938-4

Google Scholar ePrint

[LS19]

Vadim Lyubashevsky and Gregor Seiler. NTTRU: Truly Fast NTRU Using NTT. IACR Transactions on Cryptographic Hardware and Embedded Systems, May 2019. DOI: 10.46586/tches.v2019.i3.180-201

Google Scholar ePrint

[MWK⁺22]

Catinca Mujdei, Lennert Wouters, Angshuman Karmakar, Arthur Beckers, Jose Maria Bermudo Mera, and Ingrid Verbauwhede. Side-Channel Analysis of Lattice-Based Post-Quantum Cryptography: Exploiting Polynomial Multiplication. ACM Transactions on Embedded Computing Systems, November 2022. DOI: 10.1145/3569420

Google Scholar ePrint

[Nat]

National Institute of Standards and Technology. Post-Quantum Cryptography Standardization Process.

Google Scholar ePrint

[{Nat}24]

National Institute of Standards and Technology. Module-Lattice-Based Key-Encapsulation Mechanism Standard. August 2024.

Google Scholar ePrint

[PP19]

Peter Pessl and Robert Primas. More Practical Single-Trace Attacks on the Number Theoretic Transform. In Progress in Cryptology – LATINCRYPT 2019, pages 130–149. Springer International Publishing 2019. DOI: 10.1007/978-3-030-30530-7_7

Google Scholar ePrint

[PPM17]

Robert Primas, Peter Pessl, and Stefan Mangard. Single-Trace Side-Channel Attacks on Masked Lattice-Based Encryption. In Lecture Notes in Computer Science, pages 513–533. Springer International Publishing 2017. DOI: 10.1007/978-3-319-66787-4_25

Google Scholar ePrint

[RBRC22]

Prasanna Ravi, Shivam Bhasin, Sujoy Sinha Roy, and Anupam Chattopadhyay. On Exploiting Message Leakage in (Few) NIST PQC Candidates for Practical Message Recovery Attacks. IEEE Transactions on Information Forensics and Security, 17:684–699, 2022. DOI: 10.1109/TIFS.2021.3139268

Google Scholar ePrint

[Reg05]

Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05. 2005. ACM Press. DOI: 10.1145/1060590.1060603

Google Scholar ePrint

[RPBC20]

Prasanna Ravi, Romain Poussier, Shivam Bhasin, and Anupam Chattopadhyay. On Configurable SCA Countermeasures Against Single Trace Attacks for the NTT. In Security, Privacy, and Applied Cryptography Engineering, pages 123–146. Springer International Publishing 2020. DOI: 10.1007/978-3-030-66626-2_7

Google Scholar ePrint

[RSRCB20]

Prasanna Ravi, Sujoy Sinha Roy, Anupam Chattopadhyay, and Shivam Bhasin. Generic Side-channel attacks on CCA-secure lattice-based PKE and KEMs. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020. DOI: 10.46586/tches.v2020.i3.307-335

Google Scholar ePrint

[Saa17]

Markku-Juhani O. Saarinen. Arithmetic coding and blinding countermeasures for lattice signatures. Journal of Cryptographic Engineering, 8(1):71–84, January 2017. Publisher: Springer Science and Business Media LLC DOI: 10.1007/s13389-017-0149-6

Google Scholar ePrint

[UXT⁺21]

Rei Ueno, Keita Xagawa, Yutaro Tanaka, Akira Ito, Junko Takahashi, and Naofumi Homma. Curse of Re-encryption: A Generic Power/EM Analysis on Post-Quantum KEMs. IACR Transactions on Cryptographic Hardware and Embedded Systems, November 2021. Publisher: Universitatsbibliothek der Ruhr-Universitat Bochum DOI: 10.46586/tches.v2022.i1.296-322

Google Scholar ePrint

[VCGS14]

Nicolas Veyrat-Charvillon, Benoît Gérard, and François-Xavier Standaert. Soft Analytical Side-Channel Attacks. In Lecture Notes in Computer Science, pages 282–296. Springer Berlin Heidelberg 2014. DOI: 10.1007/978-3-662-45611-8_15

Google Scholar ePrint

[Wil27]

Edwin B Wilson. Probable inference, the law of succession, and statistical inference. Journal of the American Statistical Association, 22(158):209–212, 1927. Publisher: Taylor & Francis DOI: 10.1080/01621459.1927.10502953

Google Scholar ePrint

[ZBT19]

Timo Zijlstra, Karim Bigou, and Arnaud Tisserand. FPGA Implementation and Comparison of Protections Against SCAs for RLWE. In Lecture Notes in Computer Science, pages 535–555. Springer International Publishing 2019. DOI: 10.1007/978-3-030-35423-7_27

Google Scholar ePrint

[ZPM⁺23]

Yiqiang Zhao, Shijian Pan, Haocheng Ma, Ya Gao, Xintong Song, Jiaji He, and Yier Jin. Side Channel Security Oriented Evaluation and Protection on Hardware Implementations of Kyber. IEEE Transactions on Circuits and Systems I: Regular Papers, 70(12):5025–5035, December 2023. Conference Name: IEEE Transactions on Circuits and Systems I: Regular Papers DOI: 10.1109/TCSI.2023.3288600

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/aesgbnja5

History

Submitted: 2025-04-07
Accepted: 2025-06-02
Published: 2025-07-07

How to cite

Rafael Carrera Rodriguez, Florent Bruguier, Emanuele Valea, and Pascal Benoit, Cracking the Mask: SASCA Against Local-Masked NTT for CRYSTALS-Kyber. IACR Communications in Cryptology, vol. 2, no. 2, Jul 07, 2025, doi: 10.62056/aesgbnja5.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{10.62056/aesgbnja5,
         author={Rafael Carrera Rodriguez and Florent Bruguier and Emanuele Valea and Pascal Benoit},
         title={Cracking the Mask: {SASCA} Against Local-Masked {NTT} for {CRYSTALS}-Kyber},
         volume={2},
         number={2},
         year={2025},
         date={2025-07-07},
         issn={3006-5496},
         doi={10.62056/aesgbnja5},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}

TY  - JOUR
AU  - Rafael Carrera Rodriguez
AU  - Florent Bruguier
AU  - Emanuele Valea
AU  - Pascal Benoit
PY  - 2025
TI  - Cracking the Mask: SASCA Against Local-Masked NTT for CRYSTALS-Kyber
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 2
IS  - 2
DO  - 10.62056/aesgbnja5
UR  - https://doi.org/10.62056/aesgbnja5
AB  - <p>        Soft-Analytical Side-Channel Attacks (SASCAs) on lattice-based cryptography implementations have become a prominent vector of attack in the recent years, specially against the Number-Theoretic Transform (NTT).         To address this issue, local masking with twiddle factors has been proposed as a countermeasure to protect the NTT against such attacks.         In this paper we propose an adaptation of SASCA to local-masked NTT implementations, by modifying the factor graph representation to include the masking nodes.         We evaluate the success rate of the attack with respect to the level of noise of simulated traces and the number of masks $u$ per layer.         We show that the attack proves very successful in the lower values of $u$, by even outperforming the attack on the unmasked case.         When $u$ is increased there is a gradual augmentation of security, which comes with an important overhead on performance.         Thus, we question the practicality of this countermeasure when compared to other analyzed countermeasures in the state of the art, such as shuffling. </p>
ER  -

Rafael Carrera Rodriguez, Florent Bruguier, Emanuele Valea, and Pascal Benoit, Cracking the Mask: SASCA Against Local-Masked NTT for CRYSTALS-Kyber. IACR Communications in Cryptology, vol. 2, no. 2, Jul 07, 2025, doi: 10.62056/aesgbnja5.