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.
