A Deep dive into Ed25519 Signatures
- 31 min read - Text OnlyDigital 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.
We've gone through several digital signature algorithms. The list below is incomplete, but has the important ones.
- ElGamal Signature Scheme (see A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms) - July 1985
- RSASSA-PKCS1-v1_5 (see PKCS#1 v1.5) - March 1998
- ECDSA (see X9.62-1998 The Elliptic Curve Digital Signature Algorithm (ECDSA)) - September 20, 1998
- RSASSA-PSS (see PKCS#1 v2.2) - October 1998
- "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.
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.
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.
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.
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.
"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.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.(L), see Scalar arithmetic over L See The Provable Security of Ed25519: Theory and Practice (2020) section 5.2 and RFC8032 section 8.4.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.
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.
The remainder of this article will actually demonstrate Ed25519 with a common tool: OpenSSL.
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:
- Signatures fit into 64 bytes (when binary)
- One can sign with Ed25519 with relatively little computation
- One can verify an Ed25519 with relatively little computation
- Ed25519 provides a high security level of
2^128 - The public keys are incredibly small, only 32 bytes!
- 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.
== 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')
'-A'
> Buffer.from([248]).toString('base64')
'+A=='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.
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!# 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'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
-----BEGIN PRIVATE KEY-----
MC4CAQAwBQYDK2VwBCIEINomRwzzBTahF5PSKP7Kp8NUr5s8uvW/m2GIHqEd/GR2
-----END PRIVATE KEY-----
ED25519 Private-Key:
priv:
da:26:47:0c:f3:05:36:a1:17:93:d2:28:fe:ca:a7:
c3:54:af:9b:3c:ba:f5:bf:9b:61:88:1e:a1:1d:fc:
64:76
pub:
77:1c:ff:d8:8b:20:b3:6c:65:71:76:91:34:d6:4b:
f8:4b:ef:ac:d2:58:e6:25:98:40:33:df:78:92:08:
c7:f1You'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.
Just in case you want to check the contents yourself, it would look like this.
$ cat test.pem
-----BEGIN PRIVATE KEY-----
MC4CAQAwBQYDK2VwBCIEINomRwzzBTahF5PSKP7Kp8NUr5s8uvW/m2GIHqEd/GR2
-----END PRIVATE KEY-----What's really inside an Ed25519 private key file
{:type :sequence
:value (
{:type :integer
:value "0"}
{:type :sequence
:value (
{:type :object-identifier
:value "1.3.101.112"
})}
{:type :octet-string
:value (
{:type :octet-string
:encoding :hex
:value "da26470cf30536a11793d228fecaa7c354af9b3cbaf5bf9b61881ea11dfc6476"
})
})
}OneAsymmetricKey" defined in RFC5958. Within it identifies its algorithm with an object identifier (OID): 1.3.101.112. The OID is officially registered to RFC8410 and for OneAsymmetricKey, the details are clarified in section 7.1.3.101.112 expands to iso, identified-organization, thawte, id-Ed25519.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.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
-----BEGIN PUBLIC KEY-----
MCowBQYDK2VwAyEAdxz/2Isgs2xlcXaRNNZL+EvvrNJY5iWYQDPfeJIIx/E=
-----END PUBLIC KEY-----
ED25519 Public-Key:
pub:
77:1c:ff:d8:8b:20:b3:6c:65:71:76:91:34:d6:4b:
f8:4b:ef:ac:d2:58:e6:25:98:40:33:df:78:92:08:
c7:f1What's really inside an Ed25519 public key file
{:type :sequence
:value (
{:type :sequence
:value (
{:type :object-identifier
:value "1.3.101.112"
})
}
{:bits 256
:type :bit-string
:encoding :hex
:value "771cffd88b20b36c6571769134d64bf84befacd258e625984033df789208c7f1"
})
}ed25519 key type with the oid (object identifier) "1.3.101.112". This key will not successfully load in a function that expects private keys, its format is actually quite different.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.'spki' as one of the key types, 'spki' refers to SubjectPublicKeyInfo!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.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.
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.txtNote 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")).
# 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@..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.-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.# 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.binAdditionally 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.
R and S. You can read more about it in RFC8032 section 3.3 and section 5.1.6R (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.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.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.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;'
ZVpS_jCdSN4GArWnbUPJLSkpLiKzaAFYg6paOzDZxGmWx3fIUL6Sb3AoHfciFBQHiDPVg9ZEkkbzg-Hx8TGsCwqrdate.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.
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# 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 SuccessfullyFantastic! 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.
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