Score:5

Post-quantum algorithms and side channel attacks

us flag

I am studying finalist algorithms of NIST Post-Quantum Cryptography Standardization. I noticed that almost all third party cryptanalysis papers consist of side-channel attacks. Why are classical cryptanalysis methods -algebraic, mathematical attacks etc.- more effective on classical algorithms than post-quantum algorithms?

In addition, I know that mathematical problems behind post-quantum algorithms are relatively new - at least for cryptography- but domination of side channel attacks in literature forced me to consider that "Is there any characteristical property of post-quantum algorithms that makes them more vulnerable to side-channel attacks?"

Finally, I am open to any advice for beginning side-channel resistant implementation techniques -especially for post quantum algorithms-.

Score:6
ru flag

Why are classical cryptanalysis methods -algebraic, mathematical attacks etc.- more effective on classical algorithms than post-quantum algorithms?

I feel that this is a little unfair on some excellent mathematical work. The recent developments in lattice algorithms such as saturation and sieving (see Alberecht et al "The General Sieve Kernel and New Records in Lattice Reduction" for example); using non-linear equation solving to recover Goppa structure (see Faugere et al "Structural Cryptanalysis of McEliece Schemes with Compact Keys") and recent work on UOV MVQ systems (see Buellens "Improved Cryptanalysis of UOV and Rainbow") show that "classical" cryptanalysis has a very strong role to play in the analysis of these algorithms.

Is there any characteristical property of post-quantum algorithms that makes them more vulnerable to side-channel attacks?

Certain post-quantum algorithms (particularly lattice-based learning with errors problems) are inherently noisy. This leads to designs incorporating a certain tolerable failure rate in the decryption process for which one must ensure does not lead to leakage of key information. In particular if an active attacker can induce a decryption failure, this might lead to key leakage (see Proos "Imperfect Decryption and an Attack on the NTRU Encryption Scheme" for early work). Similarly for lattice signatures, much care must be exercised in the selection of ephemeral "noise" lest the aggregated signatures leak signing key information (see Ducas "Lattice Signatures and Bimodal Gaussians" for example). The code-based BIKE proposal also has a decryption process which can fail and similar care needs to be taken there. These features can tie in strongly with side-channel methods.

Score:5
my flag

I noticed that almost all third party cryptanalysis papers consist of side-channel attacks.

Well, there certainly are papers examining the strength of these postquantum algorithms and the hardness of the hard problems they are based on - they may be a minority at this point.

Part of the issue is the publishability; at the moment, most of the cryptanalytic results would be negative, and people generally don't write papers that go "I tried this attack, and it failed big time". On the other hand, if you attempt a side channel attack against an implementation that wasn't built to protect against side channels, you will generally find something.

Is there any characteristical property of post-quantum algorithms that makes them more vulnerable to side-channel attacks?

You have a bit of recency bias - if you look at the literature 20 years ago, there were lots of papers talking about side-channel attacks against RSA and AES.

Maarten Bodewes avatar
in flag
Although I know of them, I think that ECC implementations have actually been a bit under-exposed to side channel analysis. One of the problems is that people that understand computers w.r.t. side channel analysis may not be mathematicians, and you need to understand the crypto-system before mounting the side channel. In that sense I'm very happy that implementations have already been exposed to them.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.