A Deep dive into Ed25519 Signatures - 2022-03-06

Digital Signature Algorithms (DSAs) underpin modern technology enabling phone calls, emails, operating system updates, and payments to process securely. Every DSA is built upon one way functions, which is easy to perform one way but hard to reverse. Ed25519 is one such DSA and in this article I'll show how to use it.

How hard to reverse? Enough that brute force seems to be the only option with current known techniques against correct and safe implementations. For nearly every solution introduced and adopted, techniques or attacks are discovered and published that show a reduction in security.
For attacks on Ed25519, check out the addendum to this article: Ed25519 Deep Dive Addendum. This article will focus on what you will see while using Ed25519 in your application. The addendum will describe how Ed25519 works and a real risk to mitigate when using it.
This section is highly technical, feel free to skip over

We've gone through several digital signature algorithms. The list below is incomplete, but has the important ones.

  1. ElGamal Signature Scheme (see A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms) - July 1985
  2. RSASSA-PKCS1-v1_5 (see PKCS#1 v1.5) - March 1998
  3. ECDSA (see X9.62-1998 The Elliptic Curve Digital Signature Algorithm (ECDSA)) - September 20, 1998
  4. RSASSA-PSS (see PKCS#1 v2.2) - October 1998
  5. "The Digital Signature Algorithm" (see Federal Information Processing Standards Publication 186-1) - December 1998

There was a lot of activity in 1998, during the dot-com bubble and for a while not much innovation occurred. It wasn't all that necessary to either. Computation capacity steadily grew and RSA keys changed from 1024 to 2048 or 4096 bits–to be a step ahead of brute force capacity of course.

Nearly each year, some reduction in security is published. Often these reductions are found through misuses in practice, side channel attacks, clever mathematical solutions, and more. Each reduction makes brute force more feasible.

Computational improvements and security reductions make breaking keys accessible to anyone with money, all it takes is money to throw brute force resources at a problem.

The previous state of the art for Elliptic Curve cryptography from NIST comes with high complexity that makes it vulnerable to poor implementations and side channel attacks.

weierstrass curves
By Deirdre Connolly in State of the Curve (2016)

All of those edge cases on the right side of the above image make it slow to do safely, and dangerous to implement in the first place.

In 2006, Daniel J. Bernstein (DJB), a cryptographer that has contributed so much to the field such as the Salsa20 symmetric cipher and the Poly1305 message authentication code, developed Curve25519.

I'm really impressed by Daniel's breadth of contributions. TLS 1.3, which you may be using to visit my website, includes (see RFC7905) the ChaCha20-Poly1305 AEAD cipher, based upon Salsa20 and Poly1305.
curve25519 graphic
By Deirdre Connolly in State of the Curve (2016)

DJB found that Curve25519 came with so many benefits: high speed, resistant to timing attacks, small secret keys, small public keys, all private key values are acceptable, and simpler to apply in applications. While Curve25519 supports Diffie-Helman–which you will find called X25519–it is not specified to support signatures.

Key Agreement is one of the several cryptographic problems. Like digital signature algorithms, there are several approaches. Some methods use "exchange" in name like the original Diffie-Helman key exchange, but I think "agreement" is more generally true across approaches.
This section is highly technical, feel free to skip over

It turns out the Twisted Edwards Curve supports fast multiplications in the way signature algorithms use them, unlike the Montgomery Curve which Curve25519 is specified upon.

Further, there is an equivalence proof from Edwards Curves to Montgomery Curves which means that DJB's findings can be extended to Twisted Edward Curves. That equivalence proof generally uses the words "birationally equivalent".

With this discovery in hand, DJB and others proposed EdDSA in 2011. "EdDSA is a twisted Edwards curve birationally equivalent to the curve –" the publication reads. "Ed" for Edwards curve by the way. And like ECDSA, it operates over elliptic curves but due to the mathematical properties of the specified curve, can skip so many of the pitfall detections required for Weierstrass curves like NIST P-256.

Later on, Curve448 was discovered in 2015 by Mike Hamburg, which also can be adapted for EdDSA in a similar manner. EdDSA with Curve448 is known as "Ed448". Curve448 permits larger signatures and likewise a higher security rating of 224 bits, whereas Curve25519 offers a security rating of 128 bits. Unlike Curve25519, Curve448 is an untwisted edwards curve.
Now (2017) Ed25519 and Ed448 have an RFC standard, see RFC8032. This lag of nearly a decade means that widely applied tools like OpenSSL did not get Ed25519 in until 2019.
One new feature of the IETF RFC version of Ed25519 over the original Ed25519 as published is its resistance to signature forgeries. Similarly, libsodium includes a defense by remaining within the group order (L), see Scalar arithmetic over L See The Provable Security of Ed25519: Theory and Practice (2020) section 5.2 and RFC8032 section 8.4.
The new tech to look forward to is Ristretto, by Mike Hamburg—the same who came up with Ed448 and then Decaf. Decaf operates on the same curve as Ed448, and has been extended to support Curve25519 as "Ristretto".
Ristretto is an approach to provide non-malleable signatures, to see why that is a problem, check out Do not recommend: User Provided Primary Keys where I describe the perils of canonicalization and malleability. While having 4 (Ed448) or 8 (Ed25519) possible signatures for a DSA does not make a DSA weaker, the non-uniqueness of a signature for a key and data can bite anyone relying on unique signatures (such as crypto currency).
Detecting and rejecting invalid values (as input to an application) will lead to inconsistent, vulnerable, or even incompatible implementations over time. (See It’s 255:19AM. Do you know what your validation criteria are?) Curve25519 removed the need to do validation in many places ultimately making it easier for developers to do the right thing simply by reducing the complexity of use. Likewise Ristretto and Decaf remove another landmine for developers by removing that complexity.
As of February 2022, ristretto255 and decaf448 are going through the RFC standardization process. See The ristretto255 and decaf448 Groups.

The Edwards Curve has known computational solutions for operations needed to safely compute values like digital signatures. With a method to translate – (in short: safe, secure, fast, easy) onto a twisted edwards curve, we have Ed25519.

Edwards curve graphic
By Deirdre Connolly in State of the Curve (2016)

Meet Ed25519

Ed25519 is favored for its small key size, small signature size, fast computation, and it is designed to be immune to many common attacks that make ECDSA insecure or vulnerable. Recall in Why Digital Signature Algorithms that digital signature algorithms involve a cryptographic hash function to protect against intentional tampering, and a means to authenticate the cryptographic hash value. For Ed25519, the cryptographic hash is SHA-512 and the authentication scheme is elaborated in the Edwards digital signature algorithm.

Hey! A reminder that this is a continuation of QR Date, an trusted timestamp for real-time media. To see how Ed25519 signatures can be used in context, be sure to read about QR Date!

The remainder of this article will actually demonstrate Ed25519 with a common tool: OpenSSL.

This post is quite long! If you find the next section too intimidating, that's alright. You can skip on to the end. Keep reading the next section if you want to learn the motions of a modern digital signature algorithm. There is a lot of detail.

A Deep Dive into Ed25519 in practice

QR Date uses Ed25519, an EdDSA signature using SHA-512 and an edwards curve equivalent to Curve25519. Curve25519 has been documented as RFC7748 and Ed25519 standardized as RFC8032.

Here's why Ed25519 is favorable to use:

  1. Signatures fit into 64 bytes (when binary)
  2. One can sign with Ed25519 with relatively little computation
  3. One can verify an Ed25519 with relatively little computation
  4. Ed25519 provides a high security level of 2^128
  5. The public keys are incredibly small, only 32 bytes!
  6. NIST P Curves face skepticism while Curve25519 is based on a nothing up my sleeve number 2^255 - 19.

First I'll cover what an existing signature looks like and then how we can make our own.

Ed25519 Signatures in QR Date

As I watch the requests from QR Date come by, I see the date endpoint return this.

  "timestamp": 1646615224327,
  "signature": "iPejYCq5-74u_Wx221SpApZxPiiOGcNuJoN9LBwcYWGYZSd-o5trViqqoC8OJmc5xMhTlJrL3hXOsPbxFbzLCg",
  "url": "https://qrdate.org/v?s=iPejYCq5-74u_Wx221SpApZxPiiOGcNuJoN9LBwcYWGYZSd-o5trViqqoC8OJmc5xMhTlJrL3hXOsPbxFbzLCg&t=1646615224327",
  "publicKey": "MCowBQYDK2VwAyEAdd1kV4qokPUtIhxmIBhMffjdUTzTDtHu39gwoP_kfEw"

In the above JSON, the "signature" field has a bunch of Base64 URL Encoded text, being "iPejYC...FbzLCg". This is one way of encoding a signature, they may be included in binary, in standard base64, hex, base32, base58, and so on.

Now that we know what we are looking at and how to decode it, let's see if it has any discernable meaning within.

$ echo "iPejYCq5-74u_Wx221SpApZxPiiOGcNuJoN9LBwcYWGYZSd-o5trViqqoC8OJmc5xMhTlJrL3hXOsPbxFbzLCg==" \
    | base64 -d \
    > sig.bin
$ cat sig.bin | xxd
00000000: 88f7 a360 2ab9 fbbe 2efd 6c76 db54 a902  ...`*.....lv.T..
00000010: 9671 3e28 8e19 c36e 2683 7d2c 1c1c 6161  .q>(...n&.},..aa
00000020: 9865 277e a39b 6b56 2aaa a02f 0e26 6739  .e'~..kV*../.&g9
00000030: c4c8 5394 9acb de15 ceb0 f6f1 15bc cb0a  ..S.............

Well, that has no human readable components.

I had to add == to the end of the base64 string in the above as "padding". The base64 utility included on Mac OS does not gracefully handle input where padding is removed. Typically URL Encoded data does not include padding, this is the default behavior of .toString('base64url') in node for example.
> Buffer.from([248]).toString('base64url')
> Buffer.from([248]).toString('base64')

For now, we will treat the signature as an opaque value which we will rely upon a verification function to understand. We can at least see that it is 64 bytes in size.

Generating our own Ed25519 key

To create a signature, we require a private key. I obviously do not have the private key of QR Date, the example we are examining. So we will create our own below. In the next post, we will use this key to create QR Codes with signed content.

OpenSSL is available pretty much everywhere, but what you have may be out of date. I will be using version 3.0.1 for this article's examples.

This is a rant, feel free to skip
Ed25519 is more recent than the openssl (which is LibreSSL) provided on modern Mac OS. So I had to bring in openssl from homebrew and then alias it for the duration of this writing. You may have a newer version in the future. If you find that it does not know what ED25519 is, you will need a newer version!
Why does Mac OS ship with such old versions of everything!? Ed25519 was added in Mar 7, 2019!
# My machine has an outdated openssl cli installed
# This command is for me, it may be completely different for you.
$ alias openssl=/opt/homebrew/Cellar/openssl@3/3.0.1/bin/openssl

# Now to actually create the key.
$ openssl genpkey -algorithm ED25519 -out test.pem
# No output will be made to the console, this is normal.
# It went to the file called 'test.pem'
If you try X25519 instead of ED25519 you'll get an unsupported error later on. As mentioned before, the two are different, but are mathematically related.

Now that the key file is ready, let's peek inside. The pkey module provides a few commands for working with private and public keys. To display and inspect the key file, the -text flag is provided in the command.

$ openssl pkey -in test.pem -text
ED25519 Private-Key:

You'll see first that the contents of the key file are printed, followed by an analysis. It describes the private key is 32 bytes and similarly the public key is 32 bytes.

Note that when reading the private key, OpenSSL prints out the public key. Below, I'll show that the public key is not inside this file, but is calculated on demand. This will be important later.

Just in case you want to check the contents yourself, it would look like this.

$ cat test.pem
This section is highly technical, feel free to skip over

What's inside an Ed25519 private key file

That sure is a short and small private key right? Let's look inside!
{:type :sequence
:value (
    {:type :integer
    :value "0"}
    {:type :sequence
    :value (
        {:type :object-identifier
        :value ""
    {:type :octet-string
    :value (
        {:type :octet-string
        :encoding :hex
        :value "da26470cf30536a11793d228fecaa7c354af9b3cbaf5bf9b61881ea11dfc6476"
First time seeing code like the above? It's lisp like dictionary / map constructed with a list of key value, key value. Read the words rather than focus on the syntax.
If you'd like to see more examples, check out What's in a private key? where I dissect a NIST P-256 key.
The structure you see above is a "OneAsymmetricKey" defined in RFC5958. Within it identifies its algorithm with an object identifier (OID): The OID is officially registered to RFC8410 and for OneAsymmetricKey, the details are clarified in section 7.
Like a file system where folders are stored in folders, OID's represent nested relationships of ownership. expands to iso, identified-organization, thawte, id-Ed25519.
While OneAsymmetricKey optionally specifies that a public key can be packaged next to the private key, in practice this is not performed with OpenSSL. You will find this to be the case in libsodium.
Ultimately, that value inside da26470cf30536a11793d228fecaa7c354af9b3cbaf5bf9b61881ea11dfc6476 is just a big number! Ed25519 uses little-endian, this turns out to be... 53551340878188956229543046959638078426542297446178643131843522289256288954074. And you get to keep it a secret. For public keys it is a bit different.

What's inside an Ed25519 public key file

For RSA, ECDSA, EdDSA, any private key can be used to create a public key. Below, I'll ask openssl to create a public key file from the private key.

$ openssl pkey -in test.pem -pubout -text
-----END PUBLIC KEY-----
ED25519 Public-Key:
If you compare to the above, the length of this key file is about the same. Ed25519 has both 32 byte private keys and 32 byte public keys. The rest of the bytes here are structures which distinguish the key type from others like NIST P-256 or RSA.
If you look closely, this time OpenSSL did not print any private bytes. Further if you compare the public section in this and the private key printout, you will see each byte is identical.
This section is highly technical, feel free to skip over

What's inside an Ed25519 public key file

{:type :sequence
 :value (
     {:type :sequence
      :value (
          {:type :object-identifier
           :value ""
     {:bits 256
      :type :bit-string
      :encoding :hex
      :value "771cffd88b20b36c6571769134d64bf84befacd258e625984033df789208c7f1"
The structure you see here is simpler than the private key format. Like the private key it says it is an ed25519 key type with the oid (object identifier) "". This key will not successfully load in a function that expects private keys, its format is actually quite different.
In fact, this is a SubjectPublicKeyInfo (or SPKI) as defined in its respective RFC8410 section 4 for this key type. For other key types, look for the definition of SubjectPublicKeyInfo in their respective specifications.
If you ever try exporting a public key in node crypto, you'll see 'spki' as one of the key types, 'spki' refers to SubjectPublicKeyInfo!
Now if you're wondering what 771cffd88b20b36c6571769134d64bf84befacd258e625984033df789208c7f1 is supposed to be, that's the public key! For Ed25519 this is a compressed coordinate point. What that means for you is that most of the Y coordinate (in a 2d plane) is there and a bit of math is used to figure out the X coordinate based on a negative or positive indicator. While the value is 256 bits long, 255 bits are used for the Y coordinate and 1 bit is used for the "sign" of the X coordinate. With some math, the X coordinate can be found again and selected depending on the "sign" bit.
Not all 256 bit values are valid public keys! The coordinate parsed has to be "on the curve" before it can be used in the Ed25519 equations.
Not all implementations actually check this though and that can lead to problems, especially around distributed consensus. See The Provable Security of Ed25519: Theory and Practice (2020) and It’s 255:19AM. Do you know what your validation criteria are?.

Now that we've examined the public key, let's preserve it for future use.

$ openssl pkey -in test.pem -pubout > test.pub.pem
# No output will be made to the console, this is normal.
# It went to the file called 'test.pub.pem'

How to create a signature with Ed25519

Exactly how will vary by whatever language you are using. What I will show below has nothing hidden, besides the mathematical operations specific to Ed25519.

Back in university I had to do textbook RSA on paper with every step of modular exponentiation written down on paper. It was so emotionally traumatizing that I still remember where I was in the library that day. I won't subject you to the raw math involved to do cryptography.

First we will go through some motions to show what's going on behind the scenes.

# Create an input file,
# the timestamp here is what's in the JSON referenced earlier.
$ echo -n "1646615224327" \
  > input.txt

Note that instead of sign("hello"), algorithms typically sign a fixed width input like a cryptographic hash function. Since Ed25519 uses SHA-512 specifically, it would look more like sign(sha512("hello")).

While this section is optional, I do advise reading it for a complete understanding of digital signature algorithms
Normally you will not use the hash function directly while signing. A good cryptography library will choose the right algorithm that goes with the key. If you write against OpenSSL in C, you may have to perform this step manually. For Ed25519, there is only one algorithm permitted: SHA-512.
# Save the digest of this input
# (what we are applying cryptographic integrity to)
$ openssl dgst -sha512 -binary input.txt \
  > digest.bin
# View the digest, a SHA-512
$ cat digest.bin | xxd
00000000: 36af 06b5 6d73 2d6c a193 937d e74b 3f40  6...ms-l...}.K?@
00000010: b897 7c1e c5e9 75e2 4847 ba31 cb53 1b7e  ..|...u.HG.1.S.~
00000020: 686c 0748 a76a cc24 c651 2f0b 12ce 952b  hl.H.j.$.Q/....+
00000030: e0f2 16dc aa8d d7da 038e 56dc 6b40 c404  ..........V.k@..
If you develop against other DSAs like ECDSA, they may take raw digests as input. In case you use a low level library like OpenSSL or mbedtls, you will have to do this step yourself.
This is a rant, feel free to skip
The UX for Ed25519 is pretty bad. The documentation for openssl dgst does not support Ed25519, so this alternative method was discovered by wait for it: reading the source code, which lead to reading some documentation and doing the wrong thing and then rewriting it a few times.
Well at least I double check my work so you can be sure what's here is right. This is well within the "rolling your own crypto" territory and it is easy to do the wrong thing.
While writing this I found out that the -rawin flag is only "raw" for other DSAs. For Ed25519 and Ed448, -rawin is a required flag that does not behave as documented! Ed25519 still hashes the raw content with SHA-512. I was in the middle of verifying my work with an alternate implementation when it of course failed to verify in node. The reason? OpenSSL's documentation and flag choices suck that badly.
With some trial and error, I present to you a functioning example for signing with Ed25519 in the command line. Good luck finding it on stackoverflow.
# the input will actually be the pre-hashed value
# not the digest we made above.
$ openssl pkeyutl \
  -in input.txt \
  -rawin \
  -sign \
  -inkey test.pem \
  > signature.bin
For technical reasons, we need the signature as a binary file for verification with openssl.
Additionally OpenSSL only supports "oneshot" operation with these algorithms. This means that the entire file to be signed/verified must be read into memory before processing it.
- Yours Truly, the OpenSSL pkeyutl Man Page.
$ cat signature.bin \
  | xxd
00000000: 655a 52fe 309d 48de 0602 b5a7 6d43 c92d  eZR.0.H.....mC.-
00000010: 2929 2e22 b368 0158 83aa 5a3b 30d9 c469  )).".h.X..Z;0..i
00000020: 96c7 77c8 50be 926f 7028 1df7 2214 1407  ..w.P..op(.."...
00000030: 8833 d583 d644 9246 f383 e1f1 f131 ac0b  .3...D.F.....1..

This signature file has the same length as the digest file, however the contents are quite different and both appear to have no human friendly data inside. Both the signature and the signing operations use one-way-functions to produce big numbers of a specific size.

This section is highly technical, feel free to skip over
This signature actually two 256 bit numbers, R and S. You can read more about it in RFC8032 section 3.3 and section 5.1.6
R (the first number) is something anyone can calculate, it is derived from the message hash and some context including the public key, which get hashed again. The result becomes little r, and then multiplied by the generator point. A generator point is part of any elliptic curve parameter and is public information.
If you try using another Ed25519 private key, it will not have the same R as the public key for the private key is part of the equation to calculate R. This property is known as "exclusive ownership", such that no other key can produce the same signature for the same data. RSA and ECDSA do not offer exclusive ownership as is.
The detail of how S is calculated is beyond the scope of this article, but safe to say S can only be calculated by one who holds the secret private key and the message. That calculation includes little r, R from before, the public key, the message, and s the secret private key. For those details, review section 3.3 of RFC8032. Again, do not share the private key.
The verification operation does a mathematical operation and equality check that can only be satisfied if the private key corresponded to the public key used to create S and R. There is no encryption or decryption performed here, merely a specialized mathematical operation to provide authenticity and non-repudiation.

Remember the JSON above from QR Date? It held a signature presented as Base64 URL encoded. What if we try that with our own signature now?

# read the signature, encode as base64, change it to url encoding
$ cat signature.bin \
  | base64 \
  | sed 's/+/-/g; s/=//g; s,/,_,g;'
It looks to be the same length as the qrdate.org service provides! We're getting much closer now to completing this deep dive.

Let's verify our own signature

Nothing is complete without verifying our own work right? Right? To do that, we can use the keys we have, the digest file, and the signature file we produced earlier.

Normally verifying signatures would be done with the openssl dgst commands, but since it does not support ED25519 keys, this method with pkeyutl has to be used instead.
# Here we use the binary signature file, as well as the digest
# (which was signed)
# This command verifies against the private key file
# (using the derived public component)
$ openssl pkeyutl \
  -verify \
  -sigfile signature.bin \
  -in input.txt \
  -rawin \
  -inkey test.pem
Signature Verified Successfully
Hooray! The signature matched the private key. That means we should be able to hand out this signature to all our friends!
Verifying is actually a public key operation, not a private key operation, I highly recommend that you do not verify contents using a private key.
OpenSSL had to derive the public key from the private key in order to do the verify operation. It is dangerous to handle private key material in contexts where public keys are expected and public operations are performed.
You wouldn't want to accidentally attach your private key on an email you signed, would you?
# This command does the same, but it uses the public
# key we made earlier, note the -pubin flag
$ openssl pkeyutl \
  -verify \
  -sigfile signature.bin \
  -in input.txt \
  -rawin \
  -pubin \
  -inkey test.pub.pem
Signature Verified Successfully

Fantastic! We're almost finished with this deep dive. There's one bit of practice I would recommend instilling. Always test an alternate implementation and compare.

Verifying we did it right

A troublesome part of rolling our own cryptography is that it can appear to work but it might not fit the standard, or we might be doing something accidentally wrong because documentation was unclear.

In fact, that is what has happened several times while writing this. You must always double check your work here. The documentation for OpenSSL is not always clear or consistent for specific use cases.

That's why you'll see things like testing vectors in good specifications. Bad specifications or publications about an approach do not provide a means to reproduce the work reliably.

Here's a small minimal node program that can verify the signatures with the files created above. It is running with node version v16.13.1.

const fs = require('fs');
const crypto = require('crypto');
const pub = crypto.createPublicKey(fs.readFileSync('test.pub.pem'));
const input = fs.readFileSync('input.txt');
const signature = fs.readFileSync('signature.bin');
console.log('verify?', crypto.verify(null, input, pub, signature));

And if I run it:

$ node verify.js
verify? true
Phew. I'm glad that's over and checks out. I've gone through so much caffeine to produce this article.

As usual there is a lot to write about to thoroughly introduce a technical subject like cryptography. This is the third post of a series starting with an introduction to QR Date. I started writing this series six days ago (February 28th), but so much of the detail and elaboration takes time to add in. If you made it here and don't quite know what makes a digital signature algorithm special, do check out Why Digital Signature Algorithms.
Hey, you should check out the next article Ed25519 Deep Dive Addendum. In that article I share: that implementations differ and there are factors to consider when choosing an implementation; the definition of "exclusive ownership" and how it relates to signature malleability; a review of RFC8032 and what you will learn if you read it; what deterministic signatures are; and a misuse vulnerability that is in many implementations today.
If you're reading for the Creating Authenticated QR Codes series, the next post has not been published yet! When it is, I will post it on Twitter, Telegram, and through my RSS feed here.