Introduction
It has come to my attention that people are wagering dinner invitations to anyone who can convince me to publicly state my opinions and reasonings on hybrid signatures. So in the interest of not having people starve, here is a blog post on this topic and the recent controversies surrounding it.
This is going to be a somewhat lengthy rant, so in case you want to check if you owe somebody dinner, here the takeaway upfront:
Using pure ML-DSA for keys that can be rotated (even if that rotation is under great pain), is perfectly fine. Using the ML-DSA44 parameter set for such keys is also fine. I won’t go as far as telling you that you should never use hybrid signatures, but I will say that hybrid signatures have a hidden cost that often makes them not worthwhile.
Why hybrid signatures are easy
The point of a hybrid construction (in this context, there are about 3 different things in cryptography called a hybrid) is to take two schemes and create a new scheme of the same type that is as secure as the more secure of the two schemes. In the case of KEMs, you need key derivation functions for this, and if you are not careful you run into weird edge cases with IND-CCA that make your combined scheme technically (although not practically) insecure. In the case of signatures, constructing a hybrid is dead simple: You simply concatenated the public keys and signatures of the component schemes, and add two ampersands between the two component verification calls. Done. You know have a EUF-CMA hybrid signature scheme.
Why hybrid signatures are difficult
It turns out that in practice, creating a hybrid signature scheme is surprisingly difficult, mostly because people cannot agree which color the two ampersands should have.
Part of this has to do with understanding what motivations people have to advocate for hybrid schemes. The first (and in my opinion only permissible) motivation is the one I outlined above, wanting to have a signature scheme that has the security of both component schemes. However, a second motivation that many people have is to use hybrids in the transition itself. The scheme level is in my opinion the wrong layer to switch schemes, but what people essentially are arguing for is to continue using their old classical keys, just now augmented with an additional PQC key.
The less harmful version of a similar motivation is to use two completely separate implementations of the schemes, for example using an HSM for the classical part and a software implementation for the PQC part. While this is less dangerous, it forces the implementation to be crossing several layers, again leading to the wish of being able to use the keys somewhat separably. And once keys are used separately, an attacker starts to be able to take a hybrid signature and rip it apart into a separate, valid signature, or take a non-hybrid signature and a broken secondary scheme and glue them together into a hybrid signature the signer has never signed.
This property is called separability, and our simple concatenation scheme is very much separable. So are pretty much all constructions, to varying degree. And that varying degree allows for discussion of the color of ampersands. For example, we could introduce a domain separator into our hybrid scheme, and hope that that would make component signatures unusable. However, domain separators need to be chosen from a prefix-free set. And if you are only adding the domain separator to the hybrid, and not the already existing classical use, you run into the problem that the empty string is a prefix of every string, and as such your set of domain separators is very much not prefix-free.
Next, we have the issue of the context. Both ML-DSA and SLH-DSA have a context parameter in their specification, and if you are trying to describe a hybrid, you have to define around that, resulting in even more possible shades for your ampersands. You either ignore it and upset some people, or you retrofit it into the classical signature scheme and upset a bunch of other people. In either case, you are dealing with far more cryptography than you originally thought.
Next, we have our old friend, prehashing. ML-DSA with external-µ uses external µ, and with it a very specific construction using SHAKE256 as its compressing hash function, while, say, ECDSA-P256-SHA256 uses SHA256. Now you could sign µ with ECDSA, inventing ECDSA-P256-external-µ in the process, but that would be a different signature scheme and now you’ve upset the people who wanted to reuse HSMs. You can add yet another compressing hash function into the mix, and now you have something that starts to resemble the current LAMPS draft, arriving at a scheme that everybody hates the least.
This still leaves probably the biggest issue with hybrids: The combinatorical explosion. Given that you can combine any two schemes, you can create a lot of potential combinations. And people have created a lot of combinations.
This is an except of the aforementioned IETF signature combiner draft. 18 different combinations. Various different variants of RSA, and ECDSA combined with various different variants of ML-DSA. Some people want to match security levels, some people wanted to use a higher pqc security level, so both options go in. Some people wanted PKCS1, some people wanted PSS versions of RSA. So they go in. Some people wanted Brainpool curves, some people wanted Curve25519, some people wanted NIST curves. So they all go in. Rainbow ampersands for everyone!
This means implementers will now have to choose: Support all of the schemes? Probably not feasible. Support only some of them? Now you risk incompatibilities. It also means that regulators don’t have to choose: Don’t like the NIST curves? Just mandate the use of Curve25519, or better yet, Brainpool after all, it’s in the standard so surely everyone will support all of them, and systems of various compliance regimens will never interact with each other anyways, right?
All in all, the thing that makes hybrid signatures difficult is pretty much entirely due to social coordination reasons, and not technical reasons, but social coordination is a cost that cannot be neglected when looking at cryptographic primitives, and it has become clear that the social coordination costs of hybrid signatures is very high, much higher than many other standardization efforts have.
Are hybrid signatures schemes actually useful?
This brings us to the second question: Are hybrid signatures actually all that useful? After all, while the social coordination problem might be annoying, it is something that can usually be resolved, eventually at least. But here comes the kicker: Hybrid constructions are, by design, a temporary measure. So if the resolving of the social problems takes to long, it can result in the stable equilibrium point just moving past them entirely.
This brings us to a few important differences between key agreement schemes and signature schemes in practical deployments.
When it comes to key agreement, or more generally encryption schemes, your vulnerability begins when you create a ciphertext, and ends, well, never really. At some point your plaintext might only be of interest to historians, but don’t underestimate the lengths historians will go to in order to recover it. (I try to exclude them from my threat models, they are too scary).
For signatures on the other hand, your vulnerability begins and ends with your verifier starting and stopping to trust the public key. The bad news is that you don’t even need to create a signature to be potentially vulnerable, the good news is that your window of vulnerability is extremely finite. And even better yet: We have some methods to end the window of vulnerability early, by revoking the public key in question. Revocation is of course not without its problems, but even its theoretical existence can make us relax a lot more when it comes to novel cryptographic algorithms.
There are some keys that live virtually forever and can neither be revoked in an emergency, nor rotated in a normal key lifecycle management. These are keys such as firmware signing keys which are baked into silicon. At least on this mitigation aspect, those keys behave more like encryption keys (maybe sans the historian threat actors), and they need a separate analysis.
For all other keys, though, the time limit and revocation options mean that, opposed to encryption keys, the breakage of a signing key can be actively mitigated.
Signing keys differ from encryption keys in another important way: They are long lived. Where encryption keys are often ephemeral, there is no use case that would require an ephemeral signing key, that would not be better served with a cryptographic hash instead. After all, conceptually a signature scheme moves authentic channels through time, by using an existing authentic channel to transfer a public key which then can be used in the future to create a new authentic channel. If the channels existed at the same time, transfering a hash in the authentic channel would serve the same purpose.
The longer lifetime already increases compromise risks by completely classical means, so having robust rotation and revocation procedures in place for signing keys is already best practice.
Taken together, this means we have a rather large difference in threat model between signing keys and encryption keys: Where encryption keys should be hybrid, since there is no action possible if a break in the newer algorithm becomes known, a signing key can remediate this scenario.
Additionally, while an encryption key’s breakage is completely silent, in order to use a compromised signing key the attacker has to convince some endpoint to interact with the forgery they produced. This means, while still difficult to detect, signature keys being broken is detectable, especially if this type of breakage happens at scale.
This only leaves the question of how likely a break of ML-DSA is, and whether this break would likely happen in public or not.
ML-DSA mythbusting
A few months ago, somewhat similar circumstances led to me writing a blog post on ML-KEM mythbusting. Most of the answers in that blog equally apply to ML-DSA. Like ML-KEM, ML-DSA was created by a group of European researchers, was standardized under strict scrutiny of the international cryptographic community, and has a parameter space that is way too small to hide a NOBUS backdoor. While the entropy of the parameters (the calculation of which I leave as an exercise to the reader) is higher than that of ML-KEM, it still does not reach cryptographical relevance. I have included the parameter set below:
There is one thing where ML-KEM and ML-DSA differ: While ML-KEM uses the Fujisaki-Okamoto transform to create its KEM, and the changes to that transform was the one change that sparked some debate that I referred to in my mythbusting blog post, ML-DSA uses a variant of the Fiat-Shamir transform to construct its signature scheme. Fiat-Shamir requires the use of a nonce and is extremely sensitive to reuse. The nonce is used to mask the private key, which is otherwise part of the signature, and reusing a nonce leads to the same mask being used twice, leaking the key. A similar problem also occurs with ECDSA, which is technically not a Fiat-Shamir transform, but somewhat related. ECDSA is usually used with random nonces, relying on the random number generator at signing time to prevent nonce reuse. This has led to key compromises in the past, when the random number generator had trouble being random. For EdDSA (and deterministic ECDSA), the random number generator is instead replaced with a PRF, which uses the private key and the message to deterministically compute a nonce for a given message. This makes those schemes robust against random number generator failures at signing time, but, at least in the case of EdDSA, comes at the cost of a higher risk for fault attacks. As the nonce is computed from the private key and the message, but the challenge hash is computed from the public key and the message, any fault in the public key can lead to two different signatures being computed for the same nonce.
For ML-DSA, the designers went all out and put every mitigation into the algorithm that we are aware of. ML-DSA has randomness in its private key that it always uses to compute the nonce, but it will additionally accept external randomness, which reduces the chance of faults occurring. Additionally when computing the nonce and the challenge hash µ is used instead of the raw message, making it so that both nonce and signature depend on the public key, eliminating the potential faults that can break EdDSA. As a result, ML-DSA is substantially more robust against Fiat-Shamir related attacks than ECDSA or EdDSA are. Of course, if you manage to introduce a fault deep in the algorithm that leads to a reused nonce, ML-DSA will still fail, but the attack surface is substantially smaller. I will leave it as an exercise to the reader to determine the motivations of anyone who drags up Fiat-Shamir related attacks on ML-DSA as an argument against the algorithm, but stays quiet on the same attacks on, say, EdDSA.