We know hash-based signatures (Winternitz signature, HORS(T) signature) that are quantum-safe and efficient. They can be stateful or stateless, one-time or multiple-time. But why are they not widely used in practice? Or maybe they are, please tell me some applications, advantages and disadvantages.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
This table—of Ed25519 vs. the lattice-based post-quantum candidate Dilithium vs. SPHINCS+ variants at a comparable post-quantum security level, with a tradeoff between signature size and signing time—may help explain:
\begin{equation*} \begin{array}{r|rr|rr|rr} \text{sig scheme} && \text{sig bytes} && \text{cycles to sign} \\ \hline \text{ed25519} & \times1= & 64 & \times1= & 45\,400 \\ \text{dilithium3} & \times42= & 2\,701 & \times101= & 4\,600\,060 \\ \text{sphincss192sha256simple} & \times266= & 17\,064 & \times46\,000= & 2\,105\,269\,820 \\ \text{sphincsf192sha256simple} & \times557= & 35\,664 & \times1\,850= & 84\,025\,740 \end{array} \end{equation*}
Median cycle counts taken from SUPERCOP measurements on a 2019 AMD EPYC 7702 with 64 x 2000MHz cores; see the full results https://bench.cr.yp.to/results-sign.html for more details, comparisons on different machines, and additional signature schemes.
Although hash-based signatures are reasonably well-understood and based on conservative design principles, they are thousands of times costlier than the modern standard for signatures secure against a classical adversary, the elliptic-curve signature scheme Ed25519, and hundreds of times larger. (That said, the verification costs of SPHINCS+ aren't quite so bad.)
The stateful signature scheme XMSS has been deployed in OpenSSH, which is a little silly because (a) stateful signatures are a serious foot-gun for operators, and (b) there's no need to deploy post-quantum online authentication mechanisms for a long time—it is only important to deploy them once quantum computers are becoming a serious threat so that future sessions cannot be forged by a quantum adversary.
(In contrast, post-quantum encryption and post-quantum key agreement are important to deploy as soon as possible—and OpenSSH is experimenting with that too—to prevent a future quantum computer from retroactively decrypting past sessions.)
answered Oct 28, 2019 at 2:34
-
$\begingroup$ The foot-gun issues with stateful signatures are probably worth expanding a little. I came here to upvote whoever had covered them. $\endgroup$ Oct 28, 2019 at 12:00
-
1$\begingroup$ @James_pic In that case, consider poncho's answer, which elaborates on that so I don't have to! $\endgroup$ Oct 28, 2019 at 14:41
$\begingroup$
$\endgroup$
As for the "foot-gun" issues with stateful hash-based signatures, it comes down to repeating state.
Stateful hash-based signatures (XMSS, LMS) are moderately interesting (can be implemented with competitive signature generation time, and have a sum of public key and signature size which compares fairly well with other postquantum signature algorithms, based on fewer hard problems than, say, the lattice or the multivariate signature methods [1]), however they do have a kryptonite, the state.
Stateful hash-based signatures are based on a collection of one-time signatures; for each signed message, we use one of the one-time signatures on sign the actual message. If we (for whatever reason) use the same one-time signature to sign two different messages, then it is possible that an adversary could use the two signatures to sign a third message (which obviously violates the guarantees that a signature method is supposed to give).
Most typically, we keep around an index of the next one-time signature to use, and we keep that index around in some sort of permanent storage (so that, should we rerun the program, we continue where we left of).
Possible problems:
If we keep the permanent storage in a disk file, what happens if we back up and then later restore the disk file; would the restore process reset the current index to one we previously used?
If we're on a virtual machine, what happens if it gets cloned? If so, does the permanent storage also get cloned (and so the two virtual machines might use the same index to sign two different messages)?
What if we generate a signature, output it, but then restart before the updated state is actually written to disk?
If we need to generate signatures rapidly (e.g. with multiple concurrent signers), how do we make sure that two different signers don't accidentally use the same state (actually, this one isn't that hard to solve)
On the other hand, there are possible solutions. One possibility would be to keep the state on a Hardware Security Module (which cannot be restored or cloned).
As for why someone would go through the bother, one scenario where hash-based signatures look attractive is image signing. That is, we generate a public key, which we might embed into a hard-to-update device (for example, an IOT device); when we attempt to download an update to the device, the device validates the signature on the image. Such devices might live for a long time (hence we are interested in postquantum), and we (or, at least, I) trust the hard problem that hash-based signatures rely on (we don't know how to find second preimages to a specific hash function) to remain hard longer than the corresponding hard problems to other signature methods.
BTW: these "foot-gun" issues do not apply to stateless hash-based signatures (such as Sphincs+), which avoid these state management issues.
[1]: Every signature method that performs an initial hash of the message (and then signs the hash) needs to assume that the hash they use is strong. The point is that hash-based signatures makes that the only assumption; which (say) Lattice based signature methods also need to assume that the Lattice problem they are based on is also hard...
