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!"
Sarah Jamie Lewis said, "thank you i hate this."
I really hope they're joking. But out of caution, this is where I will cease to provide sample code.
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 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.)
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_i for many values of i)
Output:
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.
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.
Header art by Harubaki and CMYKat.
No comments:
Post a Comment