2
$\begingroup$

All these post quantum signature schemes are claimed by the authors to be naturally resistant to side channel attacks. My question is, why or how?

$\endgroup$
3
$\begingroup$

All these post quantum signature schemes are claimed by the authors to be naturally resistant to side channel attacks. My question is, why or how?

Well, lets break this down:

  • In terms of timing and cache-based side channels, the obvious implementation is fairly good (exception: the Haraka-based parameter sets of Sphincs+)

Here's why: the natural implementation of SHA-256 and SHAKE functions rely on instructions that are constant time on modern processors (logical ops, modular addition, shifts/rotates by constant amounts), and don't make data-dependent memory accesses or data-dependent branches (except for ones based on message length - the only variable length message involved is the initial message hash, and we don't consider the message being signed to be secret). In addition, the natural implementation of the HBS infrastructure (e.g. the Winternitz chaining or the Merkle tree computations) also doesn't have secret-based memory accesses or branches (it does involve conditional branches, however those conditions are always functions of either the message or values we place into the signature; that is, values that the adversary would know anyways).

Hence, timing and cache-based side channels don't yield any value that the attacker didn't already know (assuming, of course, that the implementation doesn't deliberately try to leak).

  • In terms of power or EMF-style side channel attacks, the story isn't quite as clear.

Most of the internal values (e.g. the internal nodes to the Merkle tree) are not actually secret. In addition, a power/EMF attack (assuming the signature isn't so strong that a single trace suffices - with the symmetric operations we're talking about, they generally aren't) requires using the same secret value in a number of different contexts; hence the previous values in a Winternitz chain is also hard to attack (because those values are used only once).

What could be attacked is the function used to generate the initial values for the Winternitz chains (and for Sphincs+ the FORS leaves). What is typically done in all three (and is formally mandated by Sphincs+) is to use the same static seed (with different additional parameters) to directly generate these values - that is precisely what a DPA attack would need (and of course, once the attacker recovers that, well, it's game over). The round 3 Sphincs+ document suggests you could use a DPA-resistant hash function implementation in that case.

Now, it is possible to rework the initial value generation logic so that it can't be attacked in this way (e.g. by generating those values as leaves from a large binary tree, so that any internal node value is used in only two contexts). However, no such method has been formally suggested for any of the three.

$\endgroup$
7
  • $\begingroup$ so generally the hash function has to yield constant power results. how about the CPA attack or fault injections that could manipulate the signature index(make it sign with the same key twice)? $\endgroup$
    – hooujki
    Oct 5 '21 at 17:07
  • $\begingroup$ @hooujki: No, hash functions don't generally yield constant power results - actually translating the recorded power draw into secrets typically requires multiple traces in different contexts. As for CPA ("Chosen Plaintext Attacks") there's nothing there that's useful (however those aren't generally considered side channel attacks). $\endgroup$
    – poncho
    Oct 5 '21 at 17:28
  • $\begingroup$ @hooujki: As for fault attacks, for LMS and XMSS, those are dependent on the Merkle tree walk logic (not all that difficult, but not trivial, and also not specified in the docs); with Sphincs+, fault attacks are quite strong, and the only countermeasure I know is "compute twice, hope the attacker can't inject same fault twice. $\endgroup$
    – poncho
    Oct 5 '21 at 17:29
  • $\begingroup$ by CPA I mean "Correlation Power Analysis". Well injecting the same fault (changes in MSB/LSB) may not be that challenging. By walk logic do you mean the optimization algorithms used to generate the root value as the signer? $\endgroup$
    – hooujki
    Oct 5 '21 at 17:46
  • $\begingroup$ @hooujki: would "Correlation Power Analysis" have the same constraints (needs to be run multiple times on related by not identical operations) that DPA has? If so, it has the same answer. As for "walk logic", well, actually a full answer would take up more space than what's allowed in a comment - brief answer is that you can do a one-way function to generate the Winternitz leaves (so once you sign, you can no longer re-sign with that leaf - you forgot how to do so), and you also (in a hierarchical model) you cache the intermediate signatures. Again, nontrivial, but doable. $\endgroup$
    – poncho
    Oct 5 '21 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.