Side-channel-assisted key recovery attacks on IND-CCA transformations
Joost Renes
Dear PQC forum,
In response to NIST's request for comments on the implementation, cryptanalysis, etc. of submissions, we would like to raise awareness on a (possibly non-exhaustive) series of papers describing side-channel attacks on IND-CCA secure NIST submissions [1, 2, 3, 4].
*TLDR*: We want to emphasize the role that (variants of) the Fujisaki-Okamoto transform play in side-channel attacks. Although the re-encryption step enables a decapsulater to reject malicious ciphertexts without leaking information about their secret key in a *black box* setting, the results from [1, 2, 3, 4] show that with very few side-channel traces the full secret/session key can be easily recovered. As the target is the transformation rather than the underlying scheme, such attacks apply to many families of post-quantum schemes. As a result, we believe that without other advances, the increase in complexity that their protection against side-channel attacks requires (compared to current PKC algorithms) might seriously prohibit their use, especially on resource-constrained platforms.
We believe there is an inherent difficulty with the Fujisaki-Okamoto transform as also demonstrated in [4]: for a full key recovery it suffices to construct a plaintext checking (PC) oracle with the help of side channels. In the simplest case, this plaintext checking oracle outputs whether the plaintext was decrypted correctly or not (i.e., a single bit of information). As the plaintext is used as input for the re-encryption, which is fully deterministic, throughout this whole (often lengthy) computation one has to avoid the leakage of this single bit. In other words, an attacker can generate as many traces with respect to a proper ciphertext as she desires, as decapsulation is deterministic. Similarly, she can generate as many traces as she wants for a (cleverly) modified ciphertext. The only goal is to distinguish whether at *any* point in the re-encryption the modified ciphertext resulted in a different intermediate value than the original ciphertext did. There can be hundreds/thousands/millions of such intermediate bytes/words.
We stress that this attack path gives adversaries very strong capabilities compared to standard attacks against symmetric encryption schemes. For example, when attacking the AES the first/last rounds'
leakage is much easier to exploit and targeting the leakage of inner rounds requires either large key guesses, which is only possible before diffusion gets complete [5], or performing advanced analytical attacks, the efficiency of which vanishes when digging within the cipher [6].
Here, all the (hundreds/thousands/millions) intermediate computations are equally easy to exploit and their information will essentially add up. At high-level, it corresponds to the strongest (state comparison) attack in the taxonomy of [7] (slide 1.7). The profiling of these computations' leakage is also very simple, whether being via standard techniques (e.g., template attacks + dimensionality reduction) or machine learning based side-channel cryptanalysis.
The leading countermeasure against such attacks is masking, which has especially received attention in the case of Saber and Kyber where first and higher-order implementations have been proposed [8, 9, 10, 11]. However, due to the large amount of intermediate computations of which the leakage can be exploited, secure implementations of FO-based NIST proposals will likely require relatively high-order masked implementations, which significantly impacts performance (both size and latency/throughput). Note that it has already been shown in [3] that a (first-order) masked implementation can be broken with very few traces (though they do not target the FO transform directly).
We are currently quantifying these attacks in a more systematic manner and plan to communicate our results in an upcoming report. But the high-level conclusions should remain that while secure implementations are never impossible, FO-based NIST proposals offer the simplest possible attack path for side-channel adversaries. As a result, we believe that without other advances, the increase in complexity that their protection against side-channel attacks requires (compared to current PKC algorithms) might seriously prohibit their use, especially on resource-constrained platforms.
Finally, and although it is of course too early to make general claims about the possible improvements, first discussions indicate that minor modifications of the schemes such as rejecting certain (easy to exploit) ciphertext structures (e.g., with low Hamming weight) or adding redundancy in the plaintext or the key are unlikely to solve the problem in a generic manner. We are unaware of a CPA to CCA FO-like transform that would avoid the aforementioned (or a similar) issue. We also note that the generic solution used to obtain CCA security with leakage in symmetric cryptography (i.e., to MAC the ciphertext with a careful verification mechanism [12]) is not applicable in the public-key setting. A generic replacement of this symmetric solution would be to rely on zero knowledge proof techniques on top of the CPA encryption, in order to avoid using the secret key before verifying the validity of the resulting ciphertext during its decapsulation. Standard solutions (e.g., generic à la Naor-Yung) or any other asymmetric techniques leveraging the group structure could be applied. But while such an addition should become more efficient than the direct masking approach for large enough security levels, evaluating the exact security level for which it is the case would require additional work to assess the security parameters required by the zero knowledge proof.
In the mid/long term, looking for solutions to this problem which can eventually lead to secure and efficient implementations of FO-based NIST proposals, while also considering how other post-quantum cryptographic schemes behave against leakage, are interesting open problems for the wider academic community. In the shorter term, we urge the NIST to consider the severity of this threat in their evaluations.
Kind regards,
Björn, Christine, Clement, Francois-Xavier, Joppe, Joost, Melissa, Olivier B, Olivier P, Thomas, Tobias
(NXP Semiconductors & UCLouvain)
PS. There are of course also side-channel attacks that do not target the
re-encryption: since they are often specific to a single scheme they are not as generally applicable, but are also a serious concern.
[1] Ravi, Roy, Chattopadhyay, Bhasin; Generic Side-channel attacks on CCA-secure lattice-based PKE and KEMs; https://tches.iacr.org/index.php/TCHES/article/view/8592/8159
[2] Ravi, Ezerman, Bhasin, Chattopadhyay, Roy; Generic Side-Channel Assisted Chosen-Ciphertext Attacks on Streamlined NTRU Prime; https://eprint.iacr.org/2021/718.pdf
[3] Ngo, Dubrova, Guo, Johansson; A Side-Channel Attack on a Masked IND-CCA Secure Saber KEM; https://eprint.iacr.org/2021/079.pdf
[4] Ueno, Xagawa, Tanaka, Ito,Takahashi, Homma; Curse of Re-encryption: A Generic Power/EM Analysis on Post-Quantum KEMs; https://eprint.iacr.org/2021/849 [5] Luke Mather, Elisabeth Oswald, Carolyn Whitnall; Multi-target DPA Attacks: Pushing DPA Beyond the Limits of a Desktop Computer; https://eprint.iacr.org/2014/365 [6] Nicolas Veyrat-Charvillon, Benoît Gérard, François-Xavier Standaert; Soft Analytical Side-Channel Attacks; https://eprint.iacr.org/2014/410 [7] F.-X. Standaert; Towards and Open Approach to Secure Cryptographic Implementations (Invited Talk); https://perso.uclouvain.be/fstandae/PUBLIS/217_slides.pdf
[8] Van Beirendonck, D'Anvers, Karmakar, Balasch, Verbauwhede; A Side-Channel Resistant Implementation of SABER; https://eprint.iacr.org/2020/733 [9] Bos, Gourjon, Renes, Schneider, Van Vredendaal; Masking Kyber: First- and Higher-Order Implementations; https://eprint.iacr.org/2021/483 [10] Heinz, Kannwischer, Land, Pöppelmann, Schwabe, Sprenkels; First-Order Masked Kyber on ARM Cortex-M4 (work in progress); https://csrc.nist.gov/CSRC/media/Presentations/first-order-masked-kyber-on-arm-cortex-m4/images-media/session-4-heinz-first-order-masked-kyber.pdf
[11] Fritzmann, Van Beirendonck, Roy, Karl, Schamberger, Verbauwhede, Sigl; Masked Accelerators and Instruction Set Extensions for Post-Quantum Cryptography; https://eprint.iacr.org/2021/479
[12] Davide Bellizia, Olivier Bronchain, Gaëtan Cassiers, Vincent Grosso, Chun Guo, Charles Momin, Olivier Pereira, Thomas Peters, François-Xavier Standaert; Mode-Level vs. Implementation-Level Physical Security in Symmetric Cryptography - A Practical Guide Through the Leakage-Resistance Jungle; https://eprint.iacr.org/2020/211
Chi Cheng
I strongly agree with the comments of the NXP Semiconductors & UCLouvain team, especially the part on side-channel assisted attack against Fujisaki-Okamoto transform.
We also would like to introduce our paper "A Systematic Approach and Analysis of Key Mismatch Attacks on Lattice-Based NIST Candidate KEMs", available at https://eprint.iacr.org/2021/123. In this paper, we propose and develop a systematic approach to find the lower bounds on the minimum average number of queries needed for key mismatch attacks. The introduction of the optimal Binary Recovery Tree approach also enables us to propose a generic improvement method for these existing attacks, which are confirmed by our experiments.
What we want to emphasize is that Ravi et al.'s attack in [1] could be seen as budilding on the basis of key mismatch attacks, and our proposed method could be directly used to improve the side-channel assisted attacks against CCA-secure NIST candidate KEMs.
Best regards
Chi Cheng
--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/AM9PR04MB81610C66590C243F628ADD62FFCD9%40AM9PR04MB8161.eurprd04.prod.outlook.com.
School of Computer Science, China University of Geosciences
https://sites.google.com/site/chichengcug/
Rei Ueno
In [4] given in this email below, we initially claimed that our attack could break the FO transformation with masked hardware based on TI.
However, it was pointed out that the masked implementations in our experiment did not correctly correspond to practical masked KEM implementations; that is, the input to PRF/PRG should be initially masked, whereas our experimental implementation did not.
Accordingly, we further conducted the distinguish attack on masked implementations in which the input was initially masked (More precisely, we explicitly excluded the timing for initial masking from side-channel trace). As a result, whereas the attack on masked software was still feasible, we could not achieve a sufficiently successful result on masked hardware based on TI in our environment.
So, let us revise our claim such that our attack cannot break masked TI-based hardware so far, and it would be an effective countermeasure (although it is still likely that an advanced side-channel distinguish attack may break even the TI-based hardware).
Our ePrint paper has been updated.
Best regards,
Rei
--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/AM9PR04MB81610C66590C243F628ADD62FFCD9%40AM9PR04MB8161.eurprd04.prod.outlook.com.
-- ======================================= 上野 嶺 Rei Ueno 東北大学 電気通信研究所 本間研究室 E-mail: rei.u...@tohoku.ac.jp Tel: 022-217-5507（本間研究室） Mobile: 090-6229-4274 =======================================