Neil Madden recently wrote a blog post titled, Digital Signatures and How to Avoid Them. One of the major points he raised is:
Another way that signatures cause issues is that they are too powerful for the job they are used for. You just wanted to authenticate that an email came from a legitimate server, but now you are providing irrefutable proof of the provenance of leaked private communications. Oops!Signatures are very much the hammer of cryptographic primitives. As well as authenticating a message, they also provide third-party verifiability and (part of) non-repudiation.
Neil Madden
Later, he goes on to make recommendations for alternatives. Namely HMAC, possibly with a KEM. His recommendations are sensible and straightforward.
Where’s the fun in that, though?
Let’s design a type of digital signature algorithm that can only be verified by the intended recipients.
Standard Crypto Disclaimer
Don’t use any of this.
I’m rolling my own crypto, which is almost always a bad idea, for my own amusement.
Absolutely none of this has been peer-reviewed or audited.
Even if there’s no immediately obvious fatal flaw in this design, it’s always possible that I screwed something up.
If anything of value ever comes of this post, it will be serious cryptographers writing their own protocol that accomplishes the goals set out in this furry blog post, but with a machine verifiable security proof.
X3MAC
Let’s start with a somewhat simple building block (using libsodium), which I call X3MAC.
Why? Because it’s partly inspired by X3DH.
The idea is pretty straightforward, and basically in line with what Neil recommended:
- Generate an ephemeral keypair.
- Do two ECDHs. One between the sender and the recipient, the other between the ephemeral keypair and the recipient.
- Use a domain-separated hash with both ECDH outputs and all three public keys to obtain a symmetric key.
- Calculate a MAC over the message, using the symmetric key.
- Return the ephemeral public key and MAC.
Verification is basically deriving the same symmetric key from the recipient’s perspective, recalculating the MAC, and comparing the two in constant-time.
This should be pretty easy to understand.
Why bother with ephemeral keypairs?
It doesn’t buy us much for the MAC use-case (since we aren’t encrypting so forward secrecy isn’t a consideration), but we will use it when we turn the X3MAC into X3SIG.
What are people saying about X3MAC?
When I showed X3MAC to some friends, some recoiled in horror and others said, “Oh, I think I have a use case!”
I really hope they’re joking. But out of caution, this is where I will cease to provide sample code.
Sarah Jamie Lewis said, “thank you i hate this.” That’s probably the correct response.
Turning X3MAC into a Signature
X3MAC isn’t actually very useful.
If Alice and Bob use X3MAC, it’s true that only the two of them can verify the authentication tag for a message… but both parties can also create authentication tags.
To turn this into a signature algorithm, we need to work with the Ristretto group and build a non-interactive variant of Schnorr’s identification protocol.
My modified protocol, X3SIG, uses Ristretto255 scalars and points instead of X25519 keypairs.
“What does any of that even mean?“Ristretto255 is a prime-order group (imagine a clock, but instead of numbers going from 1 to 12, it’s between 0 and a very large prime number), built from Curve25519.
Scalars are analogous to secret keys.
Points are analogous to public keys.
You can do point arithmetic. You can do scalar arithmetic. You don’t have to worry about the cofactor (like you would with Ed25519 or X25519).
Schnorr’s identification protocol (explained above) is essentially the basis of elliptic curve signatures; i.e., you can construct EdDSA out of it with minor (yet important) tweaks.
That’s exactly what we’re doing here: Turning X3MAC into a signature by building Schnorr out of it.
The protocol begins the same way as X3MAC: Generate a random scalar, multiply it by the base point to get a point. Do some point-scalar multiplications and a domain-separated hash to derive a symmetric key. Hash the message with the symmetric key.
But this time, we don’t stop there. We use the X3MAC-alike hash in place of the Hash() step in non-interactive Schnorr.
Important: We can eschew some data from the hashing step because certain parameters are fixed by virtue of using Ristretto255.If anyone ever builds something on another group, especially one where these parameters can change, you MUST also include all of them in the hash.
If you fail to do this, you will find yourself vulnerable to weak Fiat-Shamir attacks (e.g., Frozen Heart). If you’re writing Rust, check out Decree for transcript hashing.
(As stated before: No sample code will be provided, due to not wanting people to ship it to production.)
What does this give us?
Alice can sign a message that only she and Bob can verify. Bob cannot generate a new signature. Third parties cannot perform either action.
Thus, we still have a digital signature, but not one that provides third-party verifiability.
X3INU – Cryptographic Innuendos
If we had stopped the train at X3SIG, that’d be pretty neat.
However, X3SIG is limited to one sender and one recipient. This is kind of a bummer that doesn’t scale very well.
Fortunately, this is a solvable problem.
If you recall from my idea for multicast support in Noise-based protocols, I’m no stranger to reusing the TreeKEM abstraction from the MLS RFC to nerd-snipe my friends in the cryptography community.
So let’s do that here.
X3INU.Pack
Inputs:
- 1 keypair (sk, pk)
- A finite number of other public keys (
pk_ifor many values ofi)
Output:
- Group public key
gpk
Here, we use a Ratchet Tree (per RFC 9420) where each step is a scalar multiplication over the Ristretto group (since that’s what everyone’s public key is) and a Key Derivation Function.
The important property is that each participant in the Pack can asynchronously derive the group secret key, and it’s computationally infeasible to do so without one of the pack members’ secret keys.
This step must be performed ahead of time to establish the Pack (quorum of recipients that can verify a signature).
X3INU.Howl
Inputs:
- The message being signed.
- The secret key for the entity sending the message.
- The pack public key for all of the recipients.
Outputs:
- A signature that only pack members can validate.
Here, we just perform an X3SIG signature with the pack public key.
X3INU.Hear
Inputs:
- The message being signed.
- The signature.
- The public key for the entity sending the message.
- The secret key for a pack member.
- The pack public key for all other recipients.
Outputs:
- Boolean (is the signature valid?)
Here, we just perform an X3SIG validation.
If you’re a member of the pack that can validate the signature, you can derive the group secret key and perform X3SIG as usual.
If you’re not, you can’t tell if the signature is valid or not. To you, it should be indistinguishable from random.
X3INU Questions and Answers
Why “X3INU”?
It’s short for “innuendo”, but also “inu” is the Japanese word for “dog”, and I like to make furry puns.
Why “Pack”, “Howl”, and “Hear”?
See above! Furry puns!
Why are you like this?
I dunno.
You fool, this already exists in the cryptographic literature under a different name! What do you have to say for yourself?
Okay, yeah, probably.
I’m not an academic, so if I reinvented something that someone else made (except worse, because this is being published on a furry blog for fun), that’s kind of cool but not surprising.
It also shouldn’t be surprising that I haven’t heard of it before, due to me not being an academic.
(The closest I’ve heard of are designated verifier signatures, as Neil Madden alluded to at the bottom of his blog post.)
What if I think this might actually be useful?
Normally, I would say, “Talk to a cryptographer before writing any code,” especially if you’re writing your own protocol that uses a Fiat-Shamir transform like I did here.
However, if it turns out that X3INU is in any way novel or valuable, you should instead consult the entire cryptographic community and wait for their verdict on whether this idea is totally bonkers or not.
Why not just public-key-encrypt a digital signature?
Why not just use the existing digital signature algorithms, but encrypt it under the recipients’ public keys?
Because after decryption, the recipient possesses a signature that a third-party could still use to verify the contents of a communication.
If you transmit the signatures produced by X3INU, only the audience can tell if they’re genuine or not.
(This assumes your audience’s secret keys all remain secret, of course.)
Under what conditions do the security guarantees fall apart?
If the signer reveals their secret key, messages can be forged.
If one of the Pack members reveals their secret key, anyone can verify signatures again.
If one of the Pack members leaks the internal hash used for a given message, anyone who knows this hash can verify the signature. Pack members can do this without compromising their own signing key.
This leakage is possible because the signature is computed over a keyed hash, and the key used by the hash is a shared secret between the signer and the recipients.
Thanks to Thad for inquiring about this:
could Bob not reveal the shared symmetric key from the X3MAC to a third party? His private key is still protected by mixing the ephemeral key and the KDF, while having the shared key allows the third party to verify the message hash and prove it with Alice’s public signing key(?)
Additionally, nothing about this protocol is post-quantum secure.
Couldn’t you extend X3MAC instead of X3SIG for the Innuendo protocol?
Yes. It may even be desirable to do so. After all, designated-verifier proofs already exist, and the recipients must be able to forge signatures.
The only downside is: Anyone in the quorum can forge messages, so there is no special “signer” role, really.
With that in mind, you’re probably better off just using a Ratchet Tree to get a shared secret, and then using that with HMAC.
Can we make it even more wild?
Here’s a fun one: Combine the idea behind innuendos (as outlined above) with ring signatures.
Now Alice is one indeterminate member of a discrete set of potential signers, rather than just one, who can sign a message such that only a designated group of recipients can verify (provided nobody’s secret key is leaked).
Header art by Harubaki and CMYKat.
https://soatok.blog/2024/09/20/cryptographic-innuendos/
#asymmetricCryptography #cryptographicInnuendos #RatchetTrees
Wikipedia’s definition of a digital signature is:A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature on a message gives a recipient confidence that the message came from a sender known to the recipient.—Wikipedia
They also have a handy diagram of the process by which digital signatures are created and verified:Source: https://commons.m.wikimedia.org/wiki/File😛rivate_key_signing.svg#mw-jump-to-license (CC-BY-SA)
Alice signs a message using her private key and Bob can then verify that the message came from Alice, and hasn’t been tampered with, using her public key. This all seems straightforward and uncomplicated and is probably most developers’ view of what signatures are for and how they should be used. This has led to the widespread use of signatures for all kinds of things: validating software updates, authenticating SSL connections, and so on.But cryptographers have a different way of looking at digital signatures that has some surprising aspects. This more advanced way of thinking about digital signatures can tell us a lot about what are appropriate, and inappropriate, use-cases.
Identification protocols
There are several ways to build secure signature schemes. Although you might immediately think of RSA, the scheme perhaps most beloved by cryptographers is Schnorr signatures. These form the basis of modern EdDSA signatures, and also (in heavily altered form) DSA/ECDSA.The story of Schnorr signatures starts not with a signature scheme, but instead with an interactive identification protocol. An identification protocol is a way to prove who you are (the “prover”) to some verification service (the “verifier”). Think logging into a website. But note that the protocol is only concerned with proving who you are, not in establishing a secure session or anything like that.
There are a whole load of different ways to do this, like sending a username and password or something like WebAuthn/passkeys (an ironic mention that we’ll come back to later). One particularly elegant protocol is known as Schnorr’s protocol. It’s elegant because it is simple and only relies on basic security conjectures that are widely accepted, and it also has some nice properties that we’ll mention shortly.
The basic structure of the protocol involves three phases: Commit-Challenge-Response. If you are familiar with challenge-response authentication protocols this just adds an additional commitment message at the start.
Alice (for it is she!) wants to prove to Bob who she is. Alice already has a long-term private key, a, and Bob already has the corresponding public key, A. These keys are in a Diffie-Hellman-like finite field or elliptic curve group, so we can say A = g^a mod p where g is a generator and p is the prime modulus of the group. The protocol then works like this:
- Alice generates a random ephemeral key, r, and the corresponding public key R = g^r mod p. She sends R to Bob as the commitment.
- Bob stores R and generates a random challenge, c and sends that to Alice.
- Alice computes s = ac + r and sends that back to Bob as the response.
- Finally, Bob checks if g^s = A^c * R (mod p). If it is then Alice has successfully authenticated, otherwise it’s an imposter. The reason this works is that g^s = g^(ac + r) and A^c * R = (g^a)^c * g^r = g^(ac + r) too. Why it’s secure is another topic for another day.
Don’t worry if you don’t understand all this. I’ll probably do a blog post about Schnorr identification at some point, but there are plenty of explainers online if you want to understand it. For now, just accept that this is indeed a secure identification scheme. It has some nice properties too.
One is that it is a (honest-verifier) zero knowledge proof of knowledge (of the private key). That means that an observer watching Alice authenticate, and the verifier themselves, learn nothing at all about Alice’s private key from watching those runs, but the verifier is nonetheless convinced that Alice knows it.
This is because it is easy to create valid runs of the protocol for any private key by simply working backwards rather than forwards, starting with a response and calculating the challenge and commitment that fit that response. Anyone can do this without needing to know anything about the private key. That is, for any given challenge you can find a commitment for which it is easy to compute the correct response. (What they cannot do is correctly answer a random challenge after they’ve already sent a commitment). So they learn no information from observing a genuine interaction.
Fiat-Shamir
So what does this identification protocol have to do with digital signatures? The answer is that there is a process known as the Fiat-Shamir heuristic by which you can automatically transform certain interactive identification protocols into a non-interactive signature scheme. You can’t do this for every protocol, only ones that have a certain structure, but Schnorr identification meets the criteria. The resulting signature scheme is known, amazingly, as the Schnorr signature scheme.You may be relieved to hear that the Fiat-Shamir transformation is incredibly simple. We basically just replace the challenge part of the protocol with a cryptographic hash function, computed over the message we want to sign and the commitment public key: c = H(R, m).
That’s it. The signature is then just the pair (R, s).
Note that Bob is now not needed in the process at all and Alice can compute this all herself. To validate the signature, Bob (or anyone else) recomputes c by hashing the message and R and then performs the verification step just as in the identification protocol.
Schnorr signatures built this way are secure (so long as you add some critical security checks!) and efficient. The EdDSA signature scheme is essentially just a modern incarnation of Schnorr with a few tweaks.
What does this tell us about appropriate uses of signatures
The way I’ve just presented Schnorr signatures and Fiat-Shamir is the way they are usually presented in cryptography textbooks. We start with an identification protocol, performed a simple transformation and ended with a secure signature scheme. Happy days! These textbooks then usually move on to all the ways you can use signatures and never mention identification protocols again. But the transformation isn’t an entirely positive process: a lot was lost in translation!There are many useful aspects of interactive identification protocols that are lost by signature schemes:
- A protocol run is only meaningful for the two parties involved in the interaction (Alice and Bob). By contrast a signature is equally valid for everyone.
- A protocol run is specific to a given point in time. Alice’s response is to a specific challenge issued by Bob just prior. A signature can be verified at any time.
These points may sound like bonuses for signature schemes, but they are actually drawbacks in many cases. Signatures are often used for authentication, where we actually want things to be tied to a specific interaction. This lack of context in signatures is why standards like JWT have to add lots of explicit statements such as audience and issuer checks to ensure the JWT came from the expected source and arrived at the intended destination, and expiry information or unique identifiers (that have to be remembered) to prevent replay attacks. A significant proportion of JWT vulnerabilities in the wild are caused by developers forgetting to perform these checks.
WebAuthn is another example of this phenomenon. On paper it is a textbook case of an identification protocol. But because it is built on top of digital signatures it requires adding a whole load of “contextual bindings” for similar reasons to JWTs. Ironically, the most widely used WebAuthn signature algorithm, ECDSA, is itself a Schnorr-ish scheme.
TLS also uses signatures for what is essentially an identification protocol, and similarly has had a range of bugs due to insufficient context binding information being included in the signed data. (SSL also uses signatures for verifying certificates, which is IMO a perfectly good use of the technology. Certificates are exactly a case of where you want to convert an interactive protocol into a non-interactive one. But then again we also do an interactive protocol (DNS) in that case anyway 🤷).
In short, an awful lot of uses of digital signatures are actually identification schemes of one form or another and would be better off using an actual identification scheme. But that doesn’t mean using something like Schnorr’s protocol! There are actually better alternatives that I’ll come back to at the end.
Special Soundness: fragility by design
Before I look at alternatives, I want to point out that pretty much all in-use signature schemes are extremely fragile in practice. The zero-knowledge security of Schnorr identification is based on it having a property called special soundness. Special soundness essentially says that if Alice accidentally reuses the same commitment (R) for two runs of the protocol, then any observer can recover her private key.This sounds like an incredibly fragile notion to build into your security protocol! If I accidentally reuse this random value then I leak my entire private key??! And in fact it is: such nonce-reuse bugs are extremely common in deployed signature systems, and have led to compromise of lots of private keys (eg Playstation 3, various Bitcoin wallets etc).
But despite its fragility, this notion of special soundness is crucial to the security of many signature systems. They are truly a cursed technology!
To solve this problem, some implementations and newer standards like EdDSA use deterministic commitments, which are based on a hash of the private key and the message. This ensures that the commitment will only ever be the same if the message is identical: preventing the private key from being recovered. Unfortunately, such schemes turned out to be more susceptible to fault injection attacks (a much less scalable or general attack vector), and so now there are “hedged” schemes that inject a bit of randomness back into the hash. It’s cursed turtles all the way down.
If your answer to this is to go back to good old RSA signatures, don’t be fooled. There are plenty of ways to blow your foot off using old faithful, but that’s for another post.
Did you want non-repudiation with that?
Another way that signatures cause issues is that they are too powerful for the job they are used for. You just wanted to authenticate that an email came from a legitimate server, but now you are providing irrefutable proof of the provenance of leaked private communications. Oops!Signatures are very much the hammer of cryptographic primitives. As well as authenticating a message, they also provide third-party verifiability and (part of) non-repudiation.
You don’t need to explicitly want anonymity or deniability to understand that these strong security properties can have damaging and unforeseen side-effects. Non-repudiation should never be the default in open systems.
I could go on. From the fact that there are basically zero acceptable post-quantum signature schemes (all way too large or too risky), to issues with non-canonical signatures and cofactors and on and on. The problems of signature schemes never seem to end.
What to use instead?
Ok, so if signatures are so bad, what can I use instead?Firstly, if you can get away with using a simple shared secret scheme like HMAC, then do so. In contrast to public key crypto, HMAC is possibly the most robust crypto primitive ever invented. You’d have to go really far out of your way to screw up HMAC. (I mean, there are timing attacks and that time that Bouncy Castle confused bits and bytes and used 16-bit HMAC keys, so still do pay attention a little bit…)
If you need public key crypto, then… still use HMAC. Use an authenticated KEM with X25519 to generate a shared secret and use that with HMAC to authenticate your message. This is essentially public key authenticated encryption without the actual encryption. (Some people mistakenly refer to such schemes as designated verifier signatures, but they are not).
Signatures are good for software/firmware updates and pretty terrible for everything else.
https://neilmadden.blog/2024/09/18/digital-signatures-and-how-to-avoid-them/
#authenticatedEncryption #cryptography #misuseResistance #signatures
