A Deep dive into Ed25519 Signatures
- 32 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.
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.
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.
# 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'
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:f1
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.
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"
})
})
}
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:f1
What'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"
})
}
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.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"))
.
# 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@..
# 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
$ 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.
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-Hx8TGsCw
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.
# 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 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.
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