Side-channel attacks on CRYSTALS-KYBER, countermeasures and comparison with SKELYA (DSTU 8961-2019)
DOI:
https://doi.org/10.30837/rt.2023.1.212.02Keywords:
post-quantum algorithm, side channels, Skelya algorithm, Crystals-Kyber, NISTAbstract
Although the mathematical problems used in post-quantum cryptography algorithms appear to be mathematically secure, a class of attacks known as side-channel attacks may prove to be a threat to the security of such algorithms. Side-channel attacks affect the hardware on which the cryptographic algorithm runs, they are not attacks on the algorithm itself.
The good news is that side-channel analysis on new post-quantum cryptographic algorithms started early, even before the algorithms were standardized, given that older algorithms still face side-channel problems.
Kyber is a lattice-based post-quantum algorithm based on the complexity of the M-LWE problem. Kyber offers a secure public key encryption (PKE) scheme against a chosen plaintext attack (CPA) and a secure key encapsulation mechanism against a chosen ciphertext attack (CCA).
This paper provides a study of side-channel and fault-injection attacks on lattice-based schemes, with focus on the Kyber (KEM).
Considering the wide range of known attacks, the protection of the algorithm requires the implementation of individual countermeasures. The paper presents and tests a number of countermeasures capable of providing/improving protection against existing SCA/FIA for Kyber KEM.
The obtained results show that the presented countermeasures incur a reasonable performance cost. Therefore, the use of special countermeasures in real implementations of lattice-based schemes, either alone or as an augmentation of general countermeasures, is necessary.
References
Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, Damien Stehlé. CRYSTALS-Kyber Algorithm Specifications And Supporting Documentation (version 3.02). URL: https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf.
PRASANNA RAVI, ANUPAM CHATTOPADHYAY, ANUBHAB BAKSI. Side-channel and Fault-injection attacks over Lattice-based Post-quantum Schemes (Kyber, Dilithium): Survey and New Results. 2022. URL: https://eprint.iacr.org/2022/737.pdf.
Robert Primas, Peter Pessl, and Stefan Mangard. Single-Trace Side-Channel Attacks on Masked Lattice-Based Encryption. 2017. URL: https://eprint.iacr.org/2017/594.pdf.
Nicolas Veyrat-Charvillon, Benoît Gérard, and François-Xavier Standaert. Soft Analytical Side-Channel Attacks. 2014. URL: https://eprint.iacr.org/2014/410.pdf.
Judea Pearl. Fusion, propagation, and structuring in belief networks. 1986. URL: https://ftp.cs.ucla.edu/pub/stat_ser/r42-reprint.pdf.
Jan-Pieter D'Anvers, Marcel Tiepelt, Frederik Vercauteren, and Ingrid Verbauwhede. Timing attacks on Error Correcting Codes in Post-Quantum Schemes. 2019. URL: https://eprint.iacr.org/2019/292.pdf.
Prasanna Ravi, Sujoy Sinha Roy, Anupam Chattopadhyay, and Shivam Bhasin. Generic Side-channel attacks on CCA-secure lattice-based PKE and KEM schemes. 2019. URL: https://eprint.iacr.org/2019/948.pdf.
Qian Guo, Thomas Johansson, and Alexander Nilsson. A key-recovery timing attack on post-quantum primitives using the Fujisaki-Okamoto transformation and its application on FrodoKEM. 2020. URL: https://eprint.iacr.org/2020/743.pdf.
Shivam Bhasin, Jan-Pieter D'Anvers, Daniel Heinz, Thomas Pöppelmann, and Michiel Van Beirendonck. Attacking and Defending Masked Polynomial Comparison for Lattice-Based Cryptography. 2021. URL: https://eprint.iacr.org/2021/104.pdf.
Jan-Pieter D'Anvers, Daniel Heinz, Peter Pessl, Michiel van Beirendonck, and Ingrid Verbauwhede. Higher-Order Masked Ciphertext Comparison for Lattice-Based Cryptography. 2021. URL: https://eprint.iacr.org/2021/1422.pdf.
Julius Hermelink, Peter Pessl, and Thomas Pöppelmann. Fault-enabled chosen-ciphertext attacks on Kyber. 2021. URL: https://eprint.iacr.org/2021/1222.pdf.
Zhuang Xu, Owen Pemberton, Sujoy Sinha Roy, David Oswald, Wang Yao, and Zhiming Zheng. Magnifying Side-Channel Leakage of Lattice-Based Cryptosystems with Chosen Ciphertexts: The Case Study of Kyber. 2020. URL: https://eprint.iacr.org/2020/912.pdf.
Zhuang Xu et al. Magnifying Side-Channel Leakage of Lattice-Based Cryptosystems With Chosen Ciphertexts. 2021. URL: https://ieeexplore.ieee.org/document/9591340.
Prasanna Ravi, Shivam Bhasin, Sujoy Sinha Roy, and Anupam Chattopadhyay. On Exploiting Message Leakage in (few) NIST PQC Candidates for Practical Message Recovery and Key Recovery Attacks. 2020. URL: https://eprint.iacr.org/2020/1559.pdf.
Kalle Ngo, Elena Dubrova, Qian Guo, Thomas Johansson. A Side-Channel Attack on a Masked IND-CCA Secure Saber KEM Implementation. 2021. URL: https://tches.iacr.org/index.php/TCHES/article/view/9079/8666.
Kalle Ngo, Elena Dubrova, and Thomas Johansson. Breaking Masked and Shuffled CCA Secure Saber KEM by Power Analysis. 2021. URL: https://eprint.iacr.org/2021/902.pdf.
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. 2021. URL: https://eprint.iacr.org/2021/956.pdf.
Dorian Amiet, Andreas Curiger, Lukas Leuenberger, and Paul Zbinden. Defeating NewHope with a Single Trace. 2020. URL: https://eprint.iacr.org/2020/368.pdf.
Peter Pessl and Robert Primas. More Practical Single-Trace Attacks on the Number Theoretic Transform. 2019. URL: https://eprint.iacr.org/2019/795.pdf.
Prasanna Ravi, Debapriya Basu Roy, Shivam Bhasin, Anupam Chattopadhyay, and Debdeep Mukhopadhyay. Number "Not Used" Once - Practical fault attack on pqm4 implementations of NIST candidates. 2018. URL: https://eprint.iacr.org/2018/211.pdf.
Felipe Valencia, Tobias Oder, Tim Güneysu, and Francesco Regazzoni. Exploring the Vulnerability of R-LWE Encryption to Fault Attacks. 2018. URL: https://dl.acm.org/doi/10.1145/3178291.3178294.
Keita Xagawa, Akira Ito, Rei Ueno, Junko Takahashi, and Naofumi Homma. Fault-Injection Attacks against NIST's Post-Quantum Cryptography Round 3 KEM Candidates. 2021. URL: https://eprint.iacr.org/2021/840.pdf.
Matthias J. Kannwischer, Joost Rijneveld, Peter Schwabe, and Ko Stoffelen. PQM4: Post-quantum cryptolibrary for the ARM Cortex-M4. 2019. URL: https://github.com/mupq/pqm4.
Peter Pessl and Lukas Prokop. Fault Attacks on CCA-secure Lattice KEMs. 2021. URL: https://eprint.iacr.org/2021/064.pdf.
Jeroen Delvaux. Roulette: Breaking Kyber with Diverse Fault Injection Setups. 2021. URL: https://eprint.iacr.org/2021/1622.pdf.
Prasanna Ravi, Romain Poussier, Shivam Bhasin, and Anupam Chattopadhyay. On Configurable SCA Countermeasures Against Single Trace Attacks for the NTT - A Performance Evaluation Study over Kyber and Dilithium on the ARM Cortex-M4. 2020. URL: https://eprint.iacr.org/2020/1038.pdf.
Leon Botros, Matthias J. Kannwischer, and Peter Schwabe. Memory-Efficient High-Speed Implementation of Kyber on Cortex-M4. 2019. URL: https://eprint.iacr.org/2019/489.pdf.
ДСТУ 8961:2019 Інформаційні технології. Криптографічний захист інформації. Алгоритми асиметричного шифрування та інкапсуляції ключів. URL: http://online.budstandart.com/ua/catalog/doc-page.html?id_doc=88056.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
