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.
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.
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:
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.
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.
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.
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 Ristretto scalars and points instead of X25519 keypairs.
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.)
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.
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.
Inputs:
pk_i
for many values of i
)Output:
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).
Inputs:
Outputs:
Here, we just perform an X3SIG signature with the pack public key.
Inputs:
Outputs:
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.
It’s short for “innuendo”, but also “inu” is the Japanese word for “dog”, and I like to make furry puns.
See above! Furry puns!
I dunno.
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.)
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 use the existing digital signature algorithms, but encrypt it under the recipients’ public keys?
Tursiae
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.)
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).