A Deep dive into Ed25519 Signatures Mon Mar 07 2022 Signatures enable phone calls, emails, operating system updates, and payments to process securely. Ed25519 is one such algorithm, here's how to use it. -------------------------------------------------------------------------------- A Deep dive into Ed25519 Signatures =================================== Published Mar 7, 2022 - 31 min read /------------------ Table of contents -----------------\ | Table of contents | | * A Deep dive into Ed25519 Signatures | | * Meet Ed25519 | | * A Deep Dive into Ed25519 in practice | | * Ed25519 Signatures in QR Date | | * Generating our own Ed25519 key | | * What's really inside an Ed25519 private key file | | * What's inside an Ed25519 public key file | | * What's really inside an Ed25519 public key file | | * How to create a signature with Ed25519 | | * Let's verify our own signature | | * Verifying we did it right | \------------------------------------------------------/ 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 [L1], 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. /[cendyne: talk-w-bubble]------------------------------------------------------\ | 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. | \------------------------------------------------------------------------------/ /[cendyne: you-got-it]---------------------------------------------------------\ | For attacks on Ed25519, check out the addendum to this article: Ed25519 Deep | | Dive Addendum [L2]. 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 [L3] (see A Public Key Cryptosystem and a | | Signature Scheme Based on Discrete Logarithms [L4]) - July 1985 | | | | 2. RSASSA-PKCS1-v1_5 (see PKCS#1 v1.5 [L5]) - March 1998 | | | | 3. ECDSA (see X9.62-1998 The Elliptic Curve Digital Signature Algorithm | | (ECDSA) [L6]) - September 20, 1998 | | | | 4. RSASSA-PSS (see PKCS#1 v2.2 [L7]) - October 1998 | | | | 5. "The Digital Signature Algorithm" (see Federal Information Processing | | Standards Publication 186-1 [L8]) - December 1998 | | | | There was a lot of activity in 1998, during the dot-com bubble [L9] 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 [L10], side channel attacks | | [L11], clever mathematical solutions, and more [L12]. Each reduction makes | | brute force more feasible. | | | | /[cendyne: access-granted]-------------------------------------------------\ | | | Computational improvements and security reductions make breaking [L13] | | | | keys [L14] accessible [L15] 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. [I1: weierstrass curves] By Deirdre Connolly [L16] in State of the Curve [L17] (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 [L18], Daniel J. Bernstein [L19] (DJB), a cryptographer that has contributed so much to the field such as the Salsa20 [L20] symmetric cipher and the Poly1305 [L21] message authentication code [L22], developed Curve25519 [L23] . /[cendyne: owo]----------------------------------------------------------------\ | 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 [L24]) the | | ChaCha20-Poly1305 AEAD [L25] cipher, based upon Salsa20 and Poly1305. | \------------------------------------------------------------------------------/ [I2: curve25519 graphic] By Deirdre Connolly [L16] in State of the Curve [L17] (2016) DJB found that Curve25519 came with so many benefits [L18] : 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 [L26] –which you will find called X25519–it is not specified to support signatures. /[cendyne: talk-w-bubble]------------------------------------------------------\ | 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 [L27] supports fast multiplications | | in the way signature algorithms use them, unlike the Montgomery Curve [L28] | | 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 [L29] 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 [L29]. | | "EdDSA is a twisted Edwards curve birationally equivalent to the curve –" | | the publication reads [L29]. "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. | | | | /[cendyne: math]-----------------------------------------------------------\ | | | Later on, Curve448 [L30] was discovered in 2015 [L31] by Mike Hamburg | | | | [L32], 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. | | | \--------------------------------------------------------------------------/ | | | | /[cendyne: loading]--------------------------------------------------------\ | | | Now (2017) Ed25519 and Ed448 have an RFC standard, see RFC8032 [L33]. | | | | This lag of nearly a decade means that widely applied tools like OpenSSL | | | | did not get Ed25519 in until 2019. | | | \--------------------------------------------------------------------------/ | | | | /-----------------------------------------------[cendyne: you-got-me-there]\ | | | One new feature of the IETF RFC version of Ed25519 over the original | | | | Ed25519 as published is its resistance to signature forgeries. | | | | Similarly, libsodium [L34] includes a defense by remaining within the | | | | group order (L), see Scalar arithmetic over L [L35] See The Provable | | | | Security of Ed25519: Theory and Practice (2020) [L36] section 5.2 and | | | | RFC8032 [L33] section 8.4. | | | \--------------------------------------------------------------------------/ | | | | /[cendyne: stonks]---------------------------------------------------------\ | | | The new tech to look forward to is Ristretto [L37], by Mike Hamburg | | | | [L32] —the same who came up with Ed448 and then Decaf [L38]. Decaf | | | | operates on the same curve as Ed448, and has been extended to support | | | | Curve25519 as "Ristretto". | | | \--------------------------------------------------------------------------/ | | | | /----------------------------------------------[cendyne: peeking-from-door]\ | | | 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 [L39] 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 [L40] | | | | (such as crypto currency). | | | \--------------------------------------------------------------------------/ | | | | /------------------------------------------------------------[cendyne: nod]\ | | | 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? [L41]) 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 [L42]. | | | \--------------------------------------------------------------------------/ | | | | /[cendyne: jittery-excited]------------------------------------------------\ | | | As of February 2022, ristretto255 and decaf448 are going through the RFC | | | | standardization process. See The ristretto255 and decaf448 Groups [L43]. | | | \--------------------------------------------------------------------------/ | \------------------------------------------------------------------------------/ 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. [I3: Edwards curve graphic] By Deirdre Connolly [L16] in State of the Curve [L17] (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 [L44] 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 [L45] and the authentication scheme is elaborated in the Edwards digital signature algorithm [L46]. /[cendyne: excited]------------------------------------------------------------\ | Hey! A reminder that this is a continuation of QR Date, an trusted timestamp | | for real-time media [L47]. 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 [L48]. /[cendyne: increase]-----------------------------------------------------------\ | This post is quite long! If you find the next section too intimidating, that | | 's alright. You can skip on to the end [L49]. 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 [L50] uses Ed25519 [L51], an EdDSA [L46] signature using SHA-512 [L45] and an edwards curve equivalent to Curve25519 [L23]. Curve25519 has been documented as RFC7748 [L52] and Ed25519 standardized as RFC8032 [L33]. 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 [L53] 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 [L54] URL Encoded [L55] 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. /-----------------------------------------------------------[cendyne: facepalm]\ | 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') | | '-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. /------------------------------------------------------------------------------\ | This is a rant, feel free to skip | |------------------------------------------------------------------------------| | /[cendyne: frustrated2]----------------------------------------------------\ | | | 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! | | | \--------------------------------------------------------------------------/ | | | | /-----------------------------------------------------[cendyne: table-flip]\ | | | Why does Mac OS ship with such old versions of everything!? Ed25519 was | | | | added in Mar 7, 2019 [L56] ! | | | \--------------------------------------------------------------------------/ | \------------------------------------------------------------------------------/ # 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' /[cendyne: derp]---------------------------------------------------------------\ | If you try X25519 instead of ED25519 you'll get an unsupported error later | | on. As mentioned before, the two are different [L57], but are mathematically | | related. | \------------------------------------------------------------------------------/ Now that the key file is ready, let's peek inside. The pkey module provides a few commands [L58] 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. /[cendyne: hmm]----------------------------------------------------------------\ | 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 -----BEGIN PRIVATE KEY----- MC4CAQAwBQYDK2VwBCIEINomRwzzBTahF5PSKP7Kp8NUr5s8uvW/m2GIHqEd/GR2 -----END PRIVATE KEY----- /------------------------------------------------------------------------------\ | This section is highly technical, feel free to skip over | |------------------------------------------------------------------------------| | What's really inside an Ed25519 private key file | | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ | | | | /[cendyne: looking]--------------------------------------------------------\ | | | 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 "1.3.101.112" | | })} | | {: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. | | | | /[cendyne: angel]----------------------------------------------------------\ | | | If you'd like to see more examples, check out What's in a private key? | | | | [L59] where I dissect a NIST P-256 key. | | | \--------------------------------------------------------------------------/ | | | | /[cendyne: talk-w-bubble]--------------------------------------------------\ | | | The structure you see above is a "OneAsymmetricKey" defined in RFC5958 | | | | [L60]. Within it identifies its algorithm with an object identifier | | | | (OID): 1.3.101.112 [L61]. The OID is officially registered to RFC8410 | | | | [L62] and for OneAsymmetricKey, the details are clarified in section 7. | | | \--------------------------------------------------------------------------/ | | | | /[cendyne: peeking-from-door]----------------------------------------------\ | | | Like a file system where folders are stored in folders, OID's represent | | | | nested relationships of ownership. 1.3.101.112 expands to iso, | | | | identified-organization, thawte, id-Ed25519. | | | \--------------------------------------------------------------------------/ | | | | /--------------------------------------------------------[cendyne: ill-say]\ | | | 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. | | | \--------------------------------------------------------------------------/ | | | | /[cendyne: ssssh]----------------------------------------------------------\ | | | Ultimately, that value inside | | | | da26470cf30536a11793d228fecaa7c354af9b3cbaf5bf9b61881ea11dfc6476 is just | | | | a big number! Ed25519 uses little-endian, this turns out to be... | | | | 535513408781889562295430469596380784265422974461786431318435222892562889 | | | | 54074. 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:f1 /[cendyne: peeking-from-door]--------------------------------------------------\ | 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. | \------------------------------------------------------------------------------/ /------------------------------------------------------------[cendyne: looking]\ | 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 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" | | }) | | } | | | | /[cendyne: looking-ych]----------------------------------------------------\ | | | 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) "1.3.101.112". This key will not successfully load in a | | | | function that expects private keys, its format is actually quite | | | | different. | | | \--------------------------------------------------------------------------/ | | | | /--------------------------------------------------------[cendyne: reading]\ | | | In fact, this is a SubjectPublicKeyInfo (or SPKI) as defined in its | | | | respective RFC8410 [L62] section 4 for this key type. For other key | | | | types, look for the definition of SubjectPublicKeyInfo in their | | | | respective specifications. | | | \--------------------------------------------------------------------------/ | | | | /-----------------------------------------------------------[cendyne: blep]\ | | | If you ever try exporting a public key in node crypto [L63], you'll see | | | | 'spki' as one of the key types, 'spki' refers to SubjectPublicKeyInfo! | | | \--------------------------------------------------------------------------/ | | | | /[cendyne: peeking-from-door]----------------------------------------------\ | | | 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. | | | \--------------------------------------------------------------------------/ | | | | /-------------------------------------------------------[cendyne: surprise]\ | | | 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. | | | \--------------------------------------------------------------------------/ | | | | /---------------------------------------------------------[cendyne: judges]\ | | | 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) [L36] and It’s 255:19AM. | | | | Do you know what your validation criteria are? [L41]. | | | \--------------------------------------------------------------------------/ | \------------------------------------------------------------------------------/ 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. /[cendyne: glassy-tears]-------------------------------------------------------\ | 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 | |------------------------------------------------------------------------------| | /[cendyne: crossmark]------------------------------------------------------\ | | | 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@.. | | | | /[cendyne: notes]----------------------------------------------------------\ | | | 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 | | | | [L64], you will have to do this step yourself. | | | \--------------------------------------------------------------------------/ | \------------------------------------------------------------------------------/ /------------------------------------------------------------------------------\ | This is a rant, feel free to skip | |------------------------------------------------------------------------------| | /[cendyne: dying-at-computer]----------------------------------------------\ | | | 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. | | | \--------------------------------------------------------------------------/ | | | | /[cendyne: guess-i-will-die]-----------------------------------------------\ | | | 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. | | | \--------------------------------------------------------------------------/ | | | | /-----------------------------------------------------[cendyne: table-flip]\ | | | 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. | | | \--------------------------------------------------------------------------/ | \------------------------------------------------------------------------------/ /--------------------------------------------------------------[cendyne: ssssh]\ | 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 /--------------------------------------------------------------[cendyne: ughhh]\ | 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 [L65]. | \------------------------------------------------------------------------------/ $ 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 | |------------------------------------------------------------------------------| | /[cendyne: math]-----------------------------------------------------------\ | | | This signature actually two 256 bit numbers, R and S. You can read more | | | | about it in RFC8032 [L33] section 3.3 and section 5.1.6 | | | \--------------------------------------------------------------------------/ | | | | /[cendyne: mad-science]----------------------------------------------------\ | | | 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. | | | \--------------------------------------------------------------------------/ | | | | /-----------------------------------------------------------[cendyne: derp]\ | | | 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 [L66] ", | | | | such that no other key can produce the same signature for the same data. | | | | RSA and ECDSA do not offer exclusive ownership as is. | | | \--------------------------------------------------------------------------/ | | | | /[cendyne: ssssh]----------------------------------------------------------\ | | | 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 [L33]. Again, do not share | | | | the private key. | | | \--------------------------------------------------------------------------/ | | | | /[cendyne: hello]----------------------------------------------------------\ | | | 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 [L67]. | | | \--------------------------------------------------------------------------/ | \------------------------------------------------------------------------------/ 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 /[cendyne: this]---------------------------------------------------------------\ | 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. /---------------------------------------------------[cendyne: guess-i-will-die]\ | 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 /[cendyne: hooray]-------------------------------------------------------------\ | Hooray! The signature matched the private key. That means we should be able | | to hand out this signature to all our friends! | \------------------------------------------------------------------------------/ /----------------------------------------------------------[cendyne: crossmark]\ | 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. | \------------------------------------------------------------------------------/ /[cendyne: notes]--------------------------------------------------------------\ | 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. | \------------------------------------------------------------------------------/ /------------------------------------------------------------[cendyne: nervous]\ | 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. /[cendyne: spray-bottle]-------------------------------------------------------\ | 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 /[cendyne: coffee]-------------------------------------------------------------\ | Phew. I'm glad that's over and checks out. I've gone through so much | | caffeine to produce this article. | \------------------------------------------------------------------------------/ -------------------------------------------------------------------------------- /[cendyne: heart]--------------------------------------------------------------\ | 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 [L47]. 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 [L44]. | \------------------------------------------------------------------------------/ /[cendyne: hi]-----------------------------------------------------------------\ | Hey, you should check out the next article Ed25519 Deep Dive Addendum [L2]. | | 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 | | [L33] and what you will learn if you read it; what deterministic signatures | | are; and a misuse vulnerability that is in many implementations today. | \------------------------------------------------------------------------------/ /[cendyne: i-sleep]------------------------------------------------------------\ | 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 [L68] | | , Telegram [L69], and through my RSS feed here. | \------------------------------------------------------------------------------/ -------------------------------------------------------------------------------- Digital Signature Algorithm (DSA): A digital signature algorithm produces and verifies signatures on a message and authenticates to a verifier that the sender signed the message. The minimum security property requirement for a DSA is EUF-CMA. See Why Digital Signature Algorithms [L44]. Elliptic Curve Digital Signature Algorithm (ECDSA): A DSA which uses elliptic curve operations to sign a message. See /topics/ ecdsa.html [L70] for how it works. [L1]: https://en.wikipedia.org/wiki/One-way_function [L2]: /posts/2022-09-11-ed25519-deep-dive-addendum.html [L3]: https://en.wikipedia.org/wiki/ElGamal_signature_scheme [L4]: https://caislab.kaist.ac.kr/lecture/2010/spring/cs548/basic/B02.pdf [L5]: https://tools.ietf.org/html/rfc2313 [L6]: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.202.2977&rep= rep1&type=pdf [L7]: https://tools.ietf.org/html/rfc8017 [L8]: https://web.archive.org/web/20131226115544/http://csrc.nist.gov/ publications/fips/fips1861.pdf [L9]: https://en.wikipedia.org/wiki/Dot-com_bubble [L10]: https://archive.ph/zvJ9R [L11]: https://en.wikipedia.org/wiki/Side-channel_attack [L12]: https://archive.ph/o5Xio [L13]: https://archive.ph/uqDSD [L14]: https://archive.ph/WSbLN [L15]: https://archive.ph/qZvJI [L16]: https://twitter.com/durumcrustulum [L17]: https://dconnolly.github.io/talks/defcon-2016/state-of-the-curve-defcon- 2016.pdf [L18]: https://cr.yp.to/ecdh/curve25519-20060209.pdf [L19]: https://en.wikipedia.org/wiki/Daniel_J._Bernstein [L20]: https://en.wikipedia.org/wiki/Salsa20 [L21]: https://en.wikipedia.org/wiki/Poly1305 [L22]: https://en.wikipedia.org/wiki/Message_authentication_code [L23]: https://en.wikipedia.org/wiki/Curve25519 [L24]: https://tools.ietf.org/html/rfc7905 [L25]: https://en.wikipedia.org/wiki/Authenticated_encryption [L26]: https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange [L27]: https://en.wikipedia.org/wiki/Twisted_Edwards_curve [L28]: https://en.wikipedia.org/wiki/Montgomery_curve [L29]: https://ed25519.cr.yp.to/ed25519-20110926.pdf [L30]: https://en.wikipedia.org/wiki/Curve448 [L31]: https://eprint.iacr.org/2015/625.pdf [L32]: https://www.shiftleft.org/about/ [L33]: https://tools.ietf.org/html/rfc8032 [L34]: https://doc.libsodium.org/ [L35]: https://libsodium.gitbook.io/doc/advanced/point-arithmetic#scalar- arithmetic-over-l [L36]: https://eprint.iacr.org/2020/823.pdf [L37]: https://ristretto.group/ [L38]: https://www.shiftleft.org/papers/decaf/decaf.pdf [L39]: /posts/2022-02-18-user-provided-primary-keys.html [L40]: https://archive.ph/jX2xF [L41]: https://archive.ph/o1xh6 [L42]: https://ristretto.group/why_ristretto.html#why-ristretto [L43]: https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-ristretto255- decaf448 [L44]: /posts/2022-03-05-why-dsa.html [L45]: https://en.wikipedia.org/wiki/SHA-2 [L46]: https://en.wikipedia.org/wiki/EdDSA [L47]: /posts/2022-03-03-qr-date-for-real-time-media.html [L48]: https://www.openssl.org/ [L49]: #verifying-we-did-it-right [L50]: https://qrdate.org/ [L51]: https://ed25519.cr.yp.to/ [L52]: https://tools.ietf.org/html/rfc7748 [L53]: https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number [L54]: https://developer.mozilla.org/en-US/docs/Glossary/Base64 [L55]: https://archive.ph/qu9ZZ [L56]: https://github.com/openssl/openssl/pull/8431 [L57]: https://archive.ph/BdZcu [L58]: https://www.openssl.org/docs/man3.0/man1/openssl-pkey.html [L59]: /posts/2021-04-16-private-key.html [L60]: https://tools.ietf.org/html/rfc5958 [L61]: https://oid-rep.orange-labs.fr/get/1.3.101.112 [L62]: https://tools.ietf.org/html/rfc8410 [L63]: https://nodejs.org/docs/latest-v14.x/api/crypto.html#crypto_keyobject_ export_options [L64]: https://tls.mbed.org/ [L65]: https://www.openssl.org/docs/man3.0/man1/openssl-pkeyutl.html [L66]: https://link.springer.com/content/pdf/10.1007%2F11496137_10.pdf [L67]: https://en.wikipedia.org/wiki/Non-repudiation [L68]: https://twitter.com/CendyneNaga [L69]: https://t.me/s/cendynedev [L70]: /topics/ecdsa.html