Ed25519 Deep Dive Addendum  20220911
As an application developer, you have likely connected to GitHub or an SSH server with an SSH Key. To do this successfully without anyone else impersonating you, a Digital Signature Algorithm (DSA) is used to authenticate you. Several DSAs can be used to authenticate over SSH; Ed25519 is a great option and not only for SSH keys. In A Deep dive into Ed25519 Signatures, I suggest the Ed25519 algorithm is modern, fast, small, misuseresistant, and secure option for signing data; I also included an exercise in creating Ed25519 keys, signing data and verifying signatures.
What's in this article?
While my last article (A Deep dive into Ed25519 Signatures) aimed to give developers a detailed practical introduction to Ed25519, I have since learned there are several fine details that ought to be considered when working with Ed25519 and selecting an implementation.

First, I look into a post I saw on the đźŤŠ site in 2020, it describes how there are different validation criteria across implementations.
 Within, I learned that batch verification is a thing and briefly investigate what it means.
 I found out that signature malleability is a problem which I later learn is tied to exclusive ownership.
 Then I learn that there are important differences between implementations which make them incompatible, especially in the face of maliciously signed signatures.
 Second, I research what "exclusive ownership" means and find a paper. I double take when I learn that Ed25519 was not formally proven to be secure for nearly nine years.
 Third, I review a technical specification for Ed25519: RFC8032.

Fourth, I discuss deterministic signatures.
 To set a baseline, I cover how ECDSA signatures work, which Ed25519 improves upon.
 Then I elaborate on deterministic signatures and how it is implemented.
 But there are faults with deterministic signatures too, which I cover.
 And lastly, I wrap up by covering how Ed25519's reference implementation promotes a misuse vulnerability widely promoted this year.
When I wrote the deep dive
I did my best with my knowledge at the time to write that deep dive and I shared what I knew about Ed25519 with the world. Or more accurately, the internet, where the best way to get the right answer on the internet is not to ask a question; it's to post the wrong answer. Several corrections were applied to A Deep dive into Ed25519 Signatures. However, that experience left me feeling less informed than when I started.
So, I scraped even my vaguest memories for any leads.
It's 255:19 AM. Do you know what your validation criteria are?
It's 255:19AM. Do you know what your validation criteria are? helped me understand that additional verification of public keys (contrary to Ed25519's proposed claims) is necessary. The original paper (which I read later) suggests that all public keys are valid. While the math does not divide by zero, it also does not satisfy certain security properties.
I learned a new concept: unbatched and batch signature verification. Most applications authenticate requests or transactions one at a time in realtime. However, some use cases (e.g., blockchain consensus) benefit more from a batched verification technique where a sufficient number of messages and signatures can be verified together with less computation.
Batched verification?
Signature malleability?
Multiple incompatible implementations
As you might guess from that graphic above, the RFC8032 specification, OpenSSL, dalek, LibSodium, zebra, donna, and even the Go crypto library all behave differently. Not only that, but the same library can differ over time between versions, such as LibSodium.
Note:I have no ties to ZCash the currency or the foundation at this time. I just find this use case interesting and concerning.
The original paper
With the malleability comment from "It's 255:19AM..." in mind, I checked the original paper "Highspeed highsecurity signatures". Indeed, there is a paragraph for Malleability which starts with:
We also see no relevance of "malleability" to the standard definition of signature security.
I left this paper knowing it lacked due diligence, but just how much? Also, this paper was incredibly difficult to read. This was easily the worst paper I have read in months. I do not recommend you put your time towards it.
Provable security of Ed25519
After publishing my deep dive, I asked Soatok for feedback. In response to one of the trivia points, he mentioned:
To find out a definition "Exclusive Ownership", I searched around and found a comprehensive paper with relevant material to cite.
I found the paper The Provable Security of Ed25519: Theory and Practice on IACR's ePrint archive when looking for more details. I did a double take when I started reading.
This paper holds nothing back, at the start the authors address one of my significant concerns:
The papers do refer to malleability and argue that is not relevant for the standard definitions of signature scheme security, but their definition of malleability does not agree with the common usage of the term.
Without even a moment to breath, the next line mentions that the source code does not even match the paper.
It also transpires that, whilst the source code presented alongside the paper accepts mangled signatures (hence is not SUFCMA), the additional check included in the paperâ€™s description but not the source code, is actually sufficient to prove SUFCMA.
This paper was highly educational for me. I finally started to understand the design decisions behind Ed25519. For example, why is the public key mixed into the signature? The method is called KeyPrefixing and it defends against key substitution attacks. Mixing in the key may not be required for this defense. This paper references another, Optimal Security Proofs for Signatures from Identification Schemes, but I have not reviewed it yet.
Thankfully the proof this paper prepares is far more accessible than the mathy benchmark paper that DJB et al published. I came out with a better understanding of what's going on and why. Like "It's 255:19 AM...", this paper also compares variants of Ed25519.
Another variant is the use of Ristretto encodings for Ed25519. Whilst this appears promising, the draft RFC is still under active development and we do not analyze it here.
I specifically learned about "prehashing" and that while it is supported in the IETF standard, it is not often employed.
The paper finally gets to comparing the original reference implementation, the IETF specification, and the latest LibSodium implementation.
The reference implementation was almost SUFCMA but lacked the essential L bound check, which the IETF specification required. But what are these other checks that LibSodium added? And what are these other security properties?
 Existential Unforgeability Under Chosen Message attacks EUFCMA
 An attacker cannot forge a signature for a new message that has never been signed before.
 Strong Unforgeability Under Chosen Message Attacks SUFCMA
 An attacker cannot forge a different signature for an already signed message that also verifies for the original public key.
 Strong Universal Exclusive Ownership SUEO
 An attacker that knows another honest public key cannot create their own public key and message which verifies with an existing signature from an honest public key.
 Malicious Strong Universal Exclusive Ownership MSUEO
 An attacker that can create two malicious public keys and two messages cannot create a single signature that verifies for both messages and public keys. Also, if you have the MSUEO property, you also have the SUEO property.
 Message Bound Signature MBS
 An attacker cannot create a single signature that verifies two distinct messages with the same public key.
The original release of Ed25519 achieves the minimum requirement of EUFCMA but not SUFCMA.
The IETF specification achieves SUFCMA by ensuring that the signature S
is within a proper bound.
On top of the signature bound, LibSodium achieved MSUEO and MBS by checking:
 that the signature's commitment
R
is within a proper bound;  and that the public key
A
is within a proper bound.
For those wishing to read the same paper, check out my annotated version of The Provable Security of Ed25519: Theory and Practice
Now that I am aware of how this algorithm works and the theory behind its security and how it is realized in practice: I was ready to review a proper specification. If you are interested in reading this paper, check out my annotated copy of The Provable Security of Ed25519.
Reading RFC8032
If you thought the original Ed25519 paper was a specification, it really is not. It describes an idea and then fills every page with benchmark bragging, mathematical transformations, and comparing to competing research. It is a scientific paper and an accompanying implementation called "ref10" that demonstrates the performance it touted on every page.
Unlike the original paper, the IETF's RFC8032 is actually useful. IETF documents are written for engineers tasked with implementing a solution to a known problem on the internet. A good RFC has an appendix with a reference implementation and/ or "test vectors" to verify a successful implementation.
If you go into a specification, you should understand that you will learn how to make the thing, not necessarily how to use it effectively or correctly. There are "best practice" documents on using a technology, but unless it is a living draft, the knowledge documented will be out of date in months or years.
As I read RFC8032 and referenced Dalek and LibSodium source code, I learned how Ed25519 was constructed and implemented. If you should read this, and reread it five times, you should develop a better understanding of the following:
 How Ed25519 secret keys (the
"k"
) are prepared for elliptic curve operations (the secret scalar"s"
)  How Ed25519 secret scalars are converted to public keys (the
"A"
)  How Ed25519 signature commitments (the
"R"
) are deterministically generated  How Ed25519 signature verifiers (the
"S"
) are created  How to verify a signature with a public key, the message, the signature commitment, and the signature verifier
 That implementations may differ by having different contexts in the hashing process (which creates incompatible signatures)
 Develop a better intuition of elliptic curve math in practice
After finishing up my review of RFC8032 and the other papers, I felt Ed25519 is a quirky design. It works, but it is clear that DJB et al were racing to make something so performant on Intel chips that it would compel adoption. I'm not saying don't use it. Just that whatever we use next should face a fair number of questions on design and implementation.
Note that RFC8032 does not have the safety checks that LibSodium has. The RFC will never be updated to give caution for malicious keys that have small or malicious points. A future informational RFC might be published but by the time it comes out, it will be far too late.
While RFCs may describe how a technology should be implemented or behave, it does not specify how it should be used or how it should be exposed to a developer. RFCs are also not a reliable source for guidance on preventing misuse of a technology.
Sure, RFCs come with a section called "security considerations", but the content is intended for the implementers and not the developers. The only thing in RFC8032 that extends to developers says "don't sign large amounts of data at once." Well thanks but what if I need to? No advice is given here.
Deterministic signatures and their weaknesses
First an introduction to signatures based upon elliptic curve technology. This knowledge is necessary to understand why deterministic signatures are advantageous.
What problem do deterministic signatures solve?
The following describes how ECDSA works, consider reading the weaknesses at the end before skipping back to deterministic signatures.
An Elliptic Curve Digital Signature Algorithm (ECDSA) is based on a commitment and verifier. With ECDSA, the commitment is typically a random point on the elliptic curve, and the verifier is an unguessable number which satisfies a verification equation that also takes a public key and message. Corruption to either the commitment or the verifier will result in an unverifiable signature.
Creating a signature involves both a probabilistic process and a few deterministic processes.
A commitment secret is chosen randomly and is a large number. This secret should be less than the prime number the curve is based on and it should be greater than zero. This commitment secret will be used in the signature equation later and, as named, should be kept secret. It is generated with a probabilistic process.
Then, the commitment secret is transformed into a public format called the commitment.
This generally involves math where the "base point" or "generator" of the curve is multiplied by itself many times.
If the commitment secret were 500
then the base point would be multiplied by itself 500
times.
This is also referred to as exponentiation.
We often call the commitment in specifications and papers "R"
, as it is a random point.
The verifying application cannot confirm how the commitment was constructed.
It may be maliciously constructed or unsafely constructed if the commitment secret were 0 or greater than the primeorder of the curve.
Before creating the verifier, the message is hashed (along with any other contextual information) and the hash is treated as a big number, in other words a "scalar." This hash is something the verifying application must recreate when using a verification equation. It is generated with a deterministic process.
The verifier is constructed with an equation which takes the secret signing key, the message hash, the public key, the commitment, and the curve parameters as inputs. Unlike the commitment which is a point, the verifier is just a large number.
A signature is the commitment and the verifier bundled together. Additional info like what curve, what hash algorithm, the public key identifier, etc. may also be included.
To verify a signature, an application must reconstruct the hash from the message and have the public key of the signer. A signature is verified with the signature components (the commitment and verifier, and contextual components like the message hash, the public key, and the curve parameters. It is verified by using an equation which if satisfied strongly indicates that the private key tied to the public key was used to sign the message hash.
ECDSA comes with a few weaknesses:
 If the same commitment is signed with two verifiers using the same public key, the private key can be trivially recovered;
 Insufficient randomness or broken randomness for commitment generation will allow private keys to be recovered;
 Libraries may allow the application to set the commitment, which may let the attacker influence or set the commitment and therefore allow private keys to be recovered;
 And if the public key is maliciously constructed, its signatures might be accepted for any or several messages.
Feel free to share this topic: Elliptic Curve Digital Signature Algorithms.
How are deterministic signatures implemented?
In practice we see a need for caution and care around the commitment part of a signature. If the commitment secret is duplicated for different messages, then the signing key secret for that key can be recovered. When an attacker holds the key, they may impersonate the honest key holder and defeat the security of the scheme that relies upon that authenticity.
The security of a signature scheme requires that all commitment secrets be unique (at least as far as distinct messages go). One way to do this is to record information that changes over time, called state. It could be a counter or a collection of all previously issued commitments. Unfortunately, state in this scenario requires consistency for any application that holds the private key. Also, maintaining a set of all commitments that can be efficiently searched is difficult at scale. An alternative is to partition counters such that each signer has a reserved counter space, so other signers will not accidentally duplicate commitment secrets that will collide.
Instead, we have a cryptographic tool which is collisionresistant. Cryptographic hashes or message digests exist to fill the role of what is called a "random oracle." In computer science theory, an oracle is something that gives an answer, and a random oracle gives a random answer which has never been seen before. Replying with a preexisting signature does not reveal more information about the secret key. By definition something that has never been seen before cannot collide with previous answers.
We deem a hash function as broken when a collision is found. MD5 is easily broken, and SHA1 (see shattered) can be broken with sufficient money and server time.
To create a deterministic commitment secret with a hash function, we need to maintain one important requirement: the hash digest used to create the commitment secret must be unguessable. Also, the public form of the commitment which goes into the signature should not reveal the commitment secret.
Ed25519 uses the message and part of a SHA512 hash of the signing secret key to create a deterministic commitment secret and then the commitment is made from that commitment secret. Because secret bits of sufficient entropy were added to the hash of the message, it is too difficult to guess or reverse what the commitment secret is.
Deterministic ECDSA (RFC6979) uses a unique approach to probe for safe commitment secrets using HMACs. The message and signing secret key are mixed together with HMACs to create a possible commitment secret. If the commitment secret is unsatisfactory, it probes for another value with a deterministic algorithm. For example, a commitment secret of all 0â€™s is unsatisfactory.
A deterministic commitment secret protects the secret signing key from being recovered. This protection relies on the collision resistance property we get from cryptographic hashes. Besides key generation, the commitment secret generation part of digital signatures is the only probabilistic part of creating a signature. By replacing the commitment secret probabilistic process with a deterministic process, the complete signature process for a preexisting key becomes deterministic.
Deterministic signatures remove the risk of exposing a secret signing key when commitment secrets could be misused. This provides a defense against application developer ignorance (like Sony) and poor randomness from the environment (like some transactions on the blockchain).
Feel free to share this topic: Deterministic Digital Signature Algorithms.
Deterministic signatures in practice
Assuming your deterministic algorithm runs in constant time, a remote attacker should not be able to use side channels (e.g., timing analysis) to discover information about the secret key.
However, the story is quite different for a local attacker. Power analysis is a technique that samples power consumption or monitors radio frequency noise for indications of computation.
Side channel attacks on implementations of Curve25519  Yuval Yarom and Daniel Genkin  RWC 2018 by Real World Crypto
Yarom and Genkin show on stage that they could recover an Ed25519 key with a cheap softwaredefined radio by getting the device to sign a variety of data on the primary CPU.
In the same line as power analysis, an attacker might try to use a fault attack to corrupt the commitment secret. A fault attack involves tampering with the deviceâ€™s power for a short duration of time. Instead of a full computer, fault attacks generally target smart cards or dedicated chips that perform cryptographic operations. These trusted devices are important for identity between machines.
Often fault attacks are performed by tapping into the processorâ€™s power and then intentionally manipulating the power when the device performs a computation. As an example, if a fault is introduced when the process should have hashed the message but it did not, then the hash that is signed may be predictable. That is, the commitment secret has been coerced to a predictable value and the signing code may proceed without realizing anything is wrong. The signature that comes out of the device may then be examined to recover the private key.
Public Key Confusion
If you take a look at RFC8032, you will find that the signing function takes the public key as part of the hash which is signed. Also, you will see that the public key is the same in both the signing hash and the verifying hash.
Now what do developers do when they see duplicate domain specific code? It is refactored into its own function.
And what do developers do when they see something is deterministic and effectively static? It is memoized and cached.
In the original implementation, we see the following code. If it looks hard to read, you are not alone. This is why I recommend reading Dalek instead. The Rust compiler can do so much more than the C compiler to make an optimized executable.
int crypto_sign(
unsigned char *sm,
unsigned long long *smlen,
const unsigned char *m,
unsigned long long mlen,
const unsigned char *sk
)
{
unsigned char pk[32];
unsigned char az[64];
unsigned char nonce[64];
unsigned char hram[64];
ge_p3 R;
memmove(pk,sk + 32,32);
crypto_hash_sha512(az,sk,32);
az[0] &= 248;
az[31] &= 63;
az[31] = 64;
*smlen = mlen + 64;
memmove(sm + 64,m,mlen);
memmove(sm + 32,az + 32,32);
crypto_hash_sha512(nonce,sm + 32,mlen + 32);
memmove(sm + 32,pk,32);
sc_reduce(nonce);
ge_scalarmult_base(&R,nonce);
ge_p3_tobytes(sm,&R);
crypto_hash_sha512(hram,sm,mlen + 64);
sc_reduce(hram);
sc_muladd(sm + 32,hram,az,nonce);
return 0;
}
Source for the above code snippet
In the incredibly inaccessible code
above, we see that the public key "pk"
is created on the fly and that it sneaks into the signing buffer which is hashed at the end.
A small but impactful change is often introduced. I have found multiple instances of this change being independently introduced into this function by multiple developers in their commit history.
Here is the most readable change I have seen.
void ed25519_sign(
unsigned char *signature,
const unsigned char *message,
size_t message_len,
const unsigned char *public_key,
const unsigned char *private_key) {
sha512_context hash;
unsigned char hram[64];
unsigned char r[64];
ge_p3 R;
sha512_init(&hash);
sha512_update(&hash, private_key + 32, 32);
sha512_update(&hash, message, message_len);
sha512_final(&hash, r);
sc_reduce(r);
ge_scalarmult_base(&R, r);
ge_p3_tobytes(signature, &R);
sha512_init(&hash);
sha512_update(&hash, signature, 32);
sha512_update(&hash, public_key, 32);
sha512_update(&hash, message, message_len);
sha512_final(&hash, hram);
sc_reduce(hram);
sc_muladd(signature + 32, hram, private_key, r);
}
Source code for the above snippet
This code made several changes:

The secret signing key is no longer an input.
Instead, a
private_key
is given as input. 
The secret scalar that is derived from the secret signing key is preserved.
It is the first 32 bytes of the
private_key
variable 
The key tag is preserved.
It is another 32 bytes (after the secret scalar) from the
private_key
variable.  The public key is now supplied as another variable to this function. Previously, the public key was calculated from the private key each time the signature function executed.
 The hash function switches from a single call to a stateful call using the initialize, update, and finalize pattern.
Unfortunately, these changes have introduced a misuse vulnerability.
This misuse is demonstrated in ed25519unsafelibs/ed25519chalkiasexploit.
Conclusion
The Ed25519 digital signature algorithm raised the bar for signature key safety by introducing reliable and efficient deterministic signatures. Unfortunately, the original authors handwaved away important security guarantees in the name of efficiency. These authors produced an inaccessible scientific document focused entirely on performance. The community had to review, adopt, and integrate an inaccessible implementation from Daniel J. Bernstein's SUPERCOP codebase because the paper did such a poor job on describing its implementation. Daniel J. Bernstein et al were so close to providing message bound signatures but failed to add trivial checks to the reference implementation, likely in the name of performance. The paper also proposed two equations, one that was fast for individual verification and one that was acceptable for batch verification. However, these equations behave differently for maliciously crafted signatures. This difference in behavior has led to a denialofservice problem for batch verification use cases. Also, the paper did not provide proofs for its security properties.
A combination of no formal specification, no human friendly framework of how Ed25519 is made, and a completely inaccessible codebase has lead to misuse as Ed25519's adoption has proliferated. RFC8032 helped formalize what an Ed25519 implementation should look like but lacked several safety features required to complete the message bound signature security property. Those security features included: checking the commitment was within an acceptable range, checking that the public key was within an acceptable range, and verifying that the public key was not maliciously constructed with known points that break the mathematical properties of the elliptic curve. Again, LibSodium provides these protections now.
Without a reliable baseline, several diverse implementations came to be. Each implementation had its own validation criteria on signatures and hardly any of them actually implemented RFC8032 faithfully. Some of these implementations, such as LibSodium, changed over time to restrict signatures to those signed only by honest signers. In distributed consensus environments, changes in verification behavior must be versioned and coordinated. Because verification behavior changed in LibSodium, a denialofservice attack was a threat if some contributors to consensus accepted maliciously crafted signatures.
The reference code was also so inaccessible that developers would introduce a misuse vulnerability when trying to improve their application while minimizing impact to the API. A developer looking to improve the accessibility of their code, minimize impact to usage of that code, and improve performance by memoizing the public key would unknowingly introduce risk into their application.
I believe that the next generation of digital signature algorithms, including postquantum algorithms, should:
 Be resistant to timing attacks
 Be efficient for signing and verification
 Prevent misuse which can reveal the private key
 Prevent misuse on signing and verifying large messages, including partial signing and partial verification of messages
 Prevent misuse on signing content by correctly binding all key specific material to the signing key up front
 Include an accessible implementation with clear documentation for both API usage and the internal code in how it functions
 Supply a reference implementation with the knowledge that it will proliferate for a decade instead of being rewritten by another competent patient cryptographer
 Provide a draft specification for the digital signature algorithm
 Ensure the draft specification and the reference implementation are consistent
 Minimize acrobatic math for odd behavior like clamping and instead rely upon mathematically sound approaches when required
 Actually provide formal proofs for security properties and how the security properties are realized in the specification
 Include security properties such as MSUEO and MBS and Non ReSignability
Final Words
My goal was to really understand Ed25519 so that I could explain it here in a way where you, the reader, do not have to dive into the depths that I had to in order to understand the content and its qualities.
My journey continually confirmed that cryptography resources remain inaccessible to many audiences. I had to reach out to experts (see acknowledgement below) to clarify or confirm my understanding. Some of my expert interactions required a significant mathematical understanding of what goes into a cryptographic tool like a digital signature algorithm. I would not have been able to follow along three years ago.
After publishing A Deep dive into Ed25519 Signatures, I received enough feedback to convince me that I had much more to learn. While investigating that feedback, I made small corrections and added hints to the original article and put larger items onto a backlog which led to this addendum. However while preparing the predraft to this article, I burned out and could not write for months.
Once I had regained my writing capability in August, I resumed my education on Ed25519 to write this addendum. This article took nearly a month to research and write. I hope that my language is more accessible than what I had to read and that it is correct enough to inform application developers that make decisions on what cryptographic tools to employ in their applications.
Thank you for taking the time to get this far, I wish you the best in securing the future of your teams and customers.
Acknowledgements
Thank you to Thomas Pornin, author of RFC6979 and BearSSL for taking the time to connect everything together for signature schemes and the math involved. Thank you to Filippo Valsorda, author of age encryption which uses Ed25519 keys, for recommending what content to include. Thank you to Nadim Kobeissi, who is invested in raising the baseline for cryptography education in neat and fun ways, for recommending what content to include. Thank you to Soatok, another furry blogger who seeks to make cryptography accessible, for leads and feedback while researching Ed25519 and for final proof reading of this article. Thank you to Ibzan for content and editing review. Thank you to Xe Iaso for reviewing this article before publication. Thank you to Glitch for permission to use his character in dialog, Ibzan and Soatok and Xe also have characters depicted above with permission.