The Edwards-curve Digital Signature Algorithm (EdDSA)
You've heard of EdDSA right? The shiny and new signature scheme (well new, it's been here since 2008, wake up).
Since its inception, EdDSA has evolved quite a lot, and some amount of standardization process has happened to it. It's even doomed to be adopted by the NIST in FIPS 186-5!
First, some definition:
- EdDSA stands for Edwards-curve Digital Signature Algorithm. As its name indicates, it is supposed to be used with twisted Edwards curves (a type of elliptic curve). Its name can be deceiving though, as it is not based on the Digital Signature Algorithm (DSA) but on Schnorr signatures!
- Ed25519 is the name given to the algorithm combining EdDSA and the Edwards25519 curve (a curve somewhat equivalent to Curve25519 but discovered later, and much more performant).
EdDSA, Ed25519, and the more secure Ed448 are all specified in RFC 8032.
RFC 8032: Edwards-Curve Digital Signature Algorithm (EdDSA)
RFC 8032 takes some new direction from the original paper:
- It specifies a malleability check during verification, which prevents ill-intentioned people to forge an additional valid signature from an existing signature of yours. Whenever someone talks about Ed25519-IETF, they probably mean "the algorithm with the malleability check".
- It specifies a number of Ed25519 variants, which is the reason of this post.
- Maybe some other stuff I'm missing.
To sign with Ed25519, the original algorithm defined in the paper, here is what you're supposed to do:
- compute the nonce as
HASH(nonce_key || message) - compute the commitment
R = [nonce]GwithGthe generator of the group. - compute the challenge as
HASH(commitment || public_key || message) - compute the proof
S = nonce + challenge × signing_key - the signature is
(R, S)
where HASH is just the SHA-512 hash function.
At a high-level this is similar to Schnorr signatures, except for the following differences:
- The nonce is generated deterministically (as opposed to probabilistically) using a fixed
nonce_key(derived from your private key, and the messageM. This is one of the cool feature of Ed25519: it prevents you from re-using the same nonce twice. - The challenge is computed not only with the commitment and the message to sign, but with the public key of the signer as well. Do you know why?
Important: notice that the message here does not need to be hashed before being passed to the algorithm, as it is already hashed as part of the algorithm.
Anyway, we still don't know WTF all the variants specified are.
PureEdDSA, ContextEdDSA and HashEdDSA
Here are the variants that the RFC actually specifies:
- PureEdDSA, shortened as Ed25519 when coupled with Edwards25519.
- HashEdDSA, shortened as Ed25519ph when coupled with Edwards25519 (and where
phstands for "prehash"). - Something with no name we'll call ContextEdDSA, defined as Ed25519ctx when coupled with Edwards25519.
All three variants can share the same keys. They differ only in their signing and verification algorithms.
By the way Ed448 is a bit different, so from now on I'll focus on EdDSA with the Edwards25519 curve.
Ed25519 (or pureEd25519) is the algorithm I described in the previous section.
Easy!
Ed25519ctx (or ContextEd25519) is pureEd25519 with some additional modification: the HASH(.) function used in the signing protocol I described above is re-defined as HASH(x) = SHA-512(some_encoding(flag, context) || x) where:
flagis set to 0contextis a context string (mandatory only for Ed25519ctx)
In other words, the two instances of hashing in the signing algorithm now include some prefix.(Intuitively, you can also see that these variants are totally incompatible with each other.)
Right out of the bat, you can see that ContextEd25519 big difference is just that it mandates some domain separation to Ed25519.
Ed25519ph (or HashEd25519), finally, builds on top of ContextEd25519 with the following modifications:
flagis set to 1contextis now optional, but advised- the message is replaced with a hash of the message (the specification says that the hash has to be SHA-512, but I'm guessing that it can be anything in reality)
OK. So the big difference now seems that we are doubly-hashing.
Why HashEdDSA and why double hashing?
First, pre-hashing sucks, this is because it kills the collision resistance of the signature algorithm.In PureEdDSA we assume that we take the original message and not a hash.(Although this is not always true, the caller of the function can do whatever they want.)Then a collision on the hash function wouldn't matter (to make you create a signature that validates two different messages) because you would have to find a collision on the nonce which is computed using a secret (the nonce key).
But if you pre-hash the message, then finding a collision there is enough to obtain a signature that validates two messages.
Thus, you should use PureEdDSA if possible. And use it correctly (pass it the correct message.)
Why is HashEdDSA a thing then?
The EdDSA for more curves paper which was the first to introduce the algorithm has this to say:
The main motivation for HashEdDSA is the following storage issue (which is irrelevant to most well-designed signature applications). Computing the PureEdDSA signature of M requires reading through M twice from a buffer as long as M, and therefore does not support a small-memory “InitUpdate-Final” interface for long messages. Every common hash function H0 supports a smallmemory “Init-Update-Final” interface for long messages, so H0 -EdDSA signing also supports a small-memory “Init-Update-Final” interface for long messages. Beware, however, that analogous streaming of verification for long messages means that verifiers pass along forged packets from attackers, so it is safest for protocol designers to split long messages into short messages to be signed; this splitting also eliminates the storage issue.
Why am I even looking at this rabbit hole?
Because I'm writing a book, and it'd be nice to explain what the hell is going on with Ed25519.
Well done! You've reached the end of my post. Now you can leave a comment or read something else.
