Ed25519 Deep Dive Addendum
Sun Sep 11 2022
Ed25519 signature algorithm implementations, inner details, signature
malleability, misuse vulnerabilities, and deterministic signatures in
cryptography.
--------------------------------------------------------------------------------
Ed25519 Deep Dive Addendum
==========================
Published Sep 11, 2022 - 70 min read
/------------------------ Table of contents -----------------------\
| Table of contents |
| * What's in this article? |
| * When I wrote the deep dive |
| * It's 255:19 AM. Do you know what your validation criteria are? |
| * Batched verification? |
| * Signature malleability? |
| * Multiple incompatible implementations |
| * The original paper |
| * Provable security of Ed25519 |
| * Reading RFC8032 |
| * Deterministic signatures and their weaknesses |
| * What problem do deterministic signatures solve? |
| * How are deterministic signatures implemented? |
| * Deterministic signatures in practice |
| * Public Key Confusion |
| * Conclusion |
| * Final Words |
| * Acknowledgements |
\------------------------------------------------------------------/
As an application developer, you have likely connected to GitHub or an SSH
server with an SSH Key [L1]. To do this successfully without anyone else
impersonating you, a Digital Signature Algorithm [L2] (DSA) is used to
authenticate you. Several DSAs can be used to authenticate over SSH [L3] ;
Ed25519 is a great option and not only for SSH keys. In A Deep dive into Ed25519
Signatures [L4], I suggest the Ed25519 algorithm is modern, fast, small, misuse-
resistant, and secure option for signing data; I also included an exercise in
creating Ed25519 keys, signing data and verifying signatures.
What's in this article?
-----------------------
While my last article (A Deep dive into Ed25519 Signatures [L4]) aimed to give
developers a detailed practical introduction to Ed25519, I have since learned
there are several fine details that ought to be considered when working with
Ed25519 and selecting an implementation.
1. First, I look into a post I saw on the đźŤŠ site in 2020, it describes how
there are different validation criteria across implementations.
* Within, I learned that batch verification is a thing and briefly
investigate what it means.
* I found out that signature malleability is a problem which I later
learn is tied to exclusive ownership.
* Then I learn that there are important differences between
implementations which make them incompatible, especially in the face
of maliciously signed signatures.
2. Second, I research what "exclusive ownership" means and find a paper. I
double take when I learn that Ed25519 was not formally proven to be secure
for nearly nine years.
3. Third, I review a technical specification for Ed25519: RFC8032 [L5].
4. Fourth, I discuss deterministic signatures.
* To set a baseline, I cover how ECDSA signatures work, which Ed25519
improves upon.
* Then I elaborate on deterministic signatures and how it is
implemented.
* But there are faults with deterministic signatures too, which I cover.
5. And lastly, I wrap up by covering how Ed25519's reference implementation
promotes a misuse vulnerability widely promoted this year.
/[cendyne: hi]-----------------------------------------------------------------\
| Hey there! This article is quite long and detailed. Cryptography often ends |
| up being difficult to grok, especially for those add to this world with |
| technology. I have written this content for those who wish to improve their |
| application security with applied cryptography. |
\------------------------------------------------------------------------------/
/------------------------------------------------------------------[jacobi: hi]\
| You will see me throughout this post too. My words are by the same author |
| but with an emphasis on the mathematical side of cryptography. If you come |
| out with a greater understanding of cryptography at the end, then let me |
| know! |
\------------------------------------------------------------------------------/
When I wrote the deep dive
--------------------------
I did my best with my knowledge at the time to write that deep dive and I shared
what I knew about Ed25519 with the world. Or more accurately, the internet,
where the best way to get the right answer on the internet is not to ask a
question; it's to post the wrong answer. [L6] Several corrections were applied
to A Deep dive into Ed25519 Signatures [L4]. However, that experience left me
feeling less informed than when I started.
So, I scraped even my vaguest memories for any leads.
It's 255:19 AM. Do you know what your validation criteria are?
--------------------------------------------------------------
/[cendyne: weary]--------------------------------------------------------------\
| I remember this graphic of a bunch of invalid curve point or key or |
| something, where several different implementations were being compared |
| (Dalek, LibSodium); it mentioned incompatibility between several and patchy |
| coverage of rejecting certain inputs. Do you happen to remember anything |
| like that? |
\------------------------------------------------------------------------------/
/---------------------------------------------------------------[soatok: smile]\
| https://hdevalence.ca/blog/2020-10-04-its-25519am [L7] |
\------------------------------------------------------------------------------/
/[cendyne: mood]---------------------------------------------------------------\
| I spent an hour searching for that. Thank you. |
\------------------------------------------------------------------------------/
[I1: Image from 255:19AM]
/[cendyne: reading]------------------------------------------------------------\
| Finally finished reading it. That was dense. Some of it stuck. |
\------------------------------------------------------------------------------/
/-------------------------------------------------------------------[mara: hmm]\
| That diagram, what do all those squares mean? I'd think it would be related |
| to tests passing and failing but I'm not sure which is which and what that |
| means in practice. |
\------------------------------------------------------------------------------/
/[cendyne: sword]--------------------------------------------------------------\
| For each implementation, a 14x14 matrix of maliciously crafted signatures is |
| tested. A dark pixel means that a test case was rejected. A light pixel |
| means the test case was accepted and a malicious signature will be accepted |
| by that implementation. |
\------------------------------------------------------------------------------/
/-----------------------------------------------------------------[mara: happy]\
| Ah! I see. That's... concerning though. This algorithm is so core to the |
| internet but implementations disagree that much? That's... about what I |
| expected really. |
\------------------------------------------------------------------------------/
It's 255:19AM. Do you know what your validation criteria are? [L8] helped me
understand that additional verification of public keys (contrary to Ed25519's
proposed claims) is necessary. The original paper (which I read later) suggests
that all public keys are valid. While the math does not divide by zero, it also
does not satisfy certain security properties.
I learned a new concept: unbatched and batch signature verification. Most
applications authenticate requests or transactions one at a time in real-time.
However, some use cases (e.g., blockchain consensus) benefit more from a batched
verification technique where a sufficient number of messages and signatures can
be verified together with less computation.
Batched verification?
^^^^^^^^^^^^^^^^^^^^^
/-------------------------------------------------------[ibzan: puppy-confused]\
| Outside of the blockchain, where is batch signature verification useful? |
\------------------------------------------------------------------------------/
/[cendyne: looking]------------------------------------------------------------\
| In the paywalled paper Batch Verification Suitable for Efficiently Verifying |
| a Limited Number of Signatures [L9], the authors present a use case for |
| camera and sensor data verification in realtime. Many sensor readings and |
| surveillance images are verified to be authentic with digital signature |
| algorithms by using batch verification. |
\------------------------------------------------------------------------------/
/[cendyne: grump]--------------------------------------------------------------\
| I do not support paywalls for cryptographic research. By limiting access to |
| this material, publishers are constraining the security of our past, |
| present, and future. Please support The International Association for |
| Cryptologic Research [L10] (IACR) instead. |
\------------------------------------------------------------------------------/
[I2: Networked IP Cameras which sign their images]
A reproduction of a figure in the paper titled "Batch Verification Suitable for
Efficiently Verifying a Limited Number of Signatures."
/[cendyne: go-on]--------------------------------------------------------------\
| If your threat model includes tampered data at scale, which can be |
| authenticated in a batch-basis, then batched verification may be a good |
| choice for you. Unfortunately, the behavior of batched equations and |
| unbatched equations are different for Ed25519 for dishonest signatures. |
\------------------------------------------------------------------------------/
Signature malleability?
^^^^^^^^^^^^^^^^^^^^^^^
/-------------------------------------------------------------------[ibzan: oh]\
| It briefly mentions signature malleability. |
| |
| > ... which chose to write a paragraph arguing that signature malleability |
| > is never a problem instead of performing the check. |
\------------------------------------------------------------------------------/
/[cendyne: anime-glasses]------------------------------------------------------\
| It might be similar to Base64 malleability [L11], where the meaning of the |
| message is the same but either the author or an adversary can tweak the |
| bytes without the application realizing it has been tampered. |
\------------------------------------------------------------------------------/
Multiple incompatible implementations
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
As you might guess from that graphic above, the RFC8032 [L5] specification,
OpenSSL [L12], dalek [L13], LibSodium [L14], zebra [L15], donna [L16], and even
the Go crypto library [L17] all behave differently. Not only that, but the same
library can differ over time between versions, such as LibSodium.
/-------------------------------------------------------------[ibzan: thinking]\
| What ramifications does that have? |
\------------------------------------------------------------------------------/
/[cendyne: dot-dot-dot-surprised]----------------------------------------------\
| Differences in individual and batch verification can lead to denial-of- |
| service within an application or across distributed consensus applications. |
| This can be triggered by maliciously crafted signatures, either by a |
| dishonest signer, or a dishonest participant with an existing honest |
| signature. |
\------------------------------------------------------------------------------/
/----------------------------------------------------------------[ibzan: notes]\
| Could you give some examples? |
\------------------------------------------------------------------------------/
/[cendyne: bonk]---------------------------------------------------------------\
| Tor [L18] could be crashed [L19] by sending multiple signatures that fail |
| batch verification with the batched verification equation but succeed in |
| individual verification with the unbatched verification equation. It could |
| not determine which signature to remove. |
\------------------------------------------------------------------------------/
/[cendyne: heck]---------------------------------------------------------------\
| ZCash was taken by surprise when LibSodium updated its validation rules |
| [L20] to reject more signatures. This lead to the development of ed25519- |
| zebra [L15], which replicated LibSodium's older implementation bug for bug |
| so ZCash agents would not inadvertently disagree. This disagreement posed an |
| existential risk to the operation of the ZCash blockchain; in other words |
| the chain could be halted by denial-of-service. |
\------------------------------------------------------------------------------/
/[cendyne: checkmark]----------------------------------------------------------\
| Then, ZIP-215: Explicitly Defining and Modifying Ed25519 Validation Rules |
| [L21] was then proposed to formally change the Ed25519 implementation to |
| behave consistently with batch and individual verification. This provided a |
| successful evolution to Ed25519 in ZCash's history. |
\------------------------------------------------------------------------------/
Note: I have no ties to ZCash the currency or the foundation at this time. I
just find this use case interesting and concerning.
The original paper
------------------
With the malleability comment from "It's 255:19AM..." in mind, I checked the
original paper "High-speed high-security signatures" [L22]. Indeed, there is a
paragraph for Malleability which starts with:
> We also see no relevance of "malleability" to the standard definition of
> signature security.
/[cendyne: social-credit-20]---------------------------------------------------\
| That's how you respond to a known issue? |
\------------------------------------------------------------------------------/
/[cendyne: say-disappointed]---------------------------------------------------\
| Malleability took me by surprise with Base64 [L11], and I found it |
| concerning. Distinguished Encoding Rules [L23], which is used in the very |
| certificate used to secure this website over HTTPS, was designed |
| specifically to remove malleability. This is an important problem in |
| cryptography, and it should not be hand-waved away. |
\------------------------------------------------------------------------------/
/-----------------------------------------------------------------[ibzan: blep]\
| What about the rest of the paper? |
\------------------------------------------------------------------------------/
/[cendyne: math]---------------------------------------------------------------\
| It was mostly math and benchmark comparison. |
\------------------------------------------------------------------------------/
/[cendyne: cooking]------------------------------------------------------------\
| He mentions that other Pseudorandom functions [L24] (PRFs) may be used by |
| Ed25519, like SHA3 (which was not finalized at the time). |
\------------------------------------------------------------------------------/
/---------------------------------------------------------------[ibzan: wizard]\
| I might try mixing and matching my own choices in this, though I understand |
| it will not be compatible with other implementations. |
\------------------------------------------------------------------------------/
/[cendyne: boi]----------------------------------------------------------------\
| In practice, application developers and cryptography engineers do not go out |
| of their way to change the reference behavior. Doing so creates a |
| compatibility nightmare and introduces risk. |
\------------------------------------------------------------------------------/
/[cendyne: guess-i-will-die]---------------------------------------------------\
| In Dalek, isis specifically notes that they are not willing to change |
| behavior for something that is nearly a decade old, even if it is poorly |
| designed. Compatibility matters to cryptographers too. |
\------------------------------------------------------------------------------/
> isis agora lovecruft (they/them)
>
> ... one doesn't simply get to change the definition of a cryptographic
> primitive ten years after-the-fact with zero consideration for backwards
> compatibility in hardware and protocols which have it already have the older
> definition baked in.
>
> Dalek keypair.rs line 388-392 [L25]
/[cendyne: dumb-math2]---------------------------------------------------------\
| Also, the mod L detail during verification only appears in the batched |
| equation but not the unbatched equation. I'll refer to this as the "L bound |
| check" later. |
\------------------------------------------------------------------------------/
/-------------------------------------------------------------[ibzan: surprise]\
| That's such a little detail though! |
\------------------------------------------------------------------------------/
/[cendyne: humph]--------------------------------------------------------------\
| In cryptography, these small details really matter. Thousands of people |
| hours have been sunk in discovering and working around rough edges in |
| Ed25519 specifically. Maybe this is why NIST hesitates to include DJB's |
| cryptography? |
\------------------------------------------------------------------------------/
I left this paper knowing it lacked due diligence, but just how much? Also, this
paper was incredibly difficult to read. This was easily the worst paper I have
read in months. I do not recommend you put your time towards it.
Provable security of Ed25519
----------------------------
After publishing my deep dive, I asked Soatok for feedback. In response to one
of the trivia points, he mentioned:
/---------------------------------------------------------[soatok: finger-guns]\
| The inclusion of the public key in R provides a property called "Exclusive |
| Ownership" :3 |
| |
| ECDSA lacks it |
| |
| Lightning Round - Commitments [L26] has a write-up on it |
\------------------------------------------------------------------------------/
To find out a definition "Exclusive Ownership", I searched around and found a
comprehensive paper with relevant material to cite.
I found the paper The Provable Security of Ed25519: Theory and Practice [L27] on
IACR's ePrint archive when looking for more details. I did a double take when I
started reading.
/[cendyne: maybe-you]----------------------------------------------------------\
| You're telling me there's a paper saying we have a signature scheme in |
| something as important as TLS 1.3 and it quotes: |
| |
| > No detailed proofs have ever been given for these security properties for |
| > EdDSA, and in particular its Ed25519 instantiations. |
\------------------------------------------------------------------------------/
/[cendyne: maybe-you-should-not]-----------------------------------------------\
| I cannot believe we have gotten this far without a formal analysis of such |
| an important and now widespread technology. |
\------------------------------------------------------------------------------/
This paper holds nothing back, at the start the authors address one of my
significant concerns:
> The papers do refer to malleability and argue that is not relevant for the
> standard definitions of signature scheme security, but their definition of
> malleability does not agree with the common usage of the term.
Without even a moment to breath, the next line mentions that the source code
does not even match the paper.
> It also transpires that, whilst the source code presented alongside the paper
> accepts mangled signatures (hence is not SUF-CMA), the additional check
> included in the paperâ€™s description but not the source code, is actually
> sufficient to prove SUF-CMA.
/------------------------------------------------------[glitch: puppy-confused]\
| What's SUF-CMA? |
\------------------------------------------------------------------------------/
/[cendyne: you-got-it]---------------------------------------------------------\
| That one means they can't tweak your signature and it still work. |
\------------------------------------------------------------------------------/
/[cendyne: hmm]----------------------------------------------------------------\
| Also, the paper only described the L bound check on the batched equation, |
| and the source code implemented the unbatched equation with single |
| verification. |
\------------------------------------------------------------------------------/
/-------------------------------------------------------------[glitch: pick-me]\
| Why is SUF-CMA important? |
\------------------------------------------------------------------------------/
/[cendyne: laptop]-------------------------------------------------------------\
| In a use case where the message and signature should be unique, you must |
| have the SUF-CMA property in your system. Otherwise, mangling the signature |
| will yield more valid message and signature combinations which are seen as |
| unique. This is particularly important in blockchain applications. |
\------------------------------------------------------------------------------/
This paper was highly educational for me. I finally started to understand the
design decisions behind Ed25519. For example, why is the public key mixed into
the signature? The method is called Key-Prefixing and it defends against key
substitution attacks. Mixing in the key may not be required for this defense.
This paper references another, Optimal Security Proofs for Signatures from
Identification Schemes [L28], but I have not reviewed it yet.
Thankfully the proof this paper prepares is far more accessible than the mathy
benchmark paper [L22] that DJB et al published. I came out with a better
understanding of what's going on and why. Like "It's 255:19 AM...", this paper
also compares variants of Ed25519.
> Another variant is the use of Ristretto encodings for Ed25519. Whilst this
> appears promising, the draft RFC is still under active development and we do
> not analyze it here.
/------------------------------------------------------------[glitch: surprise]\
| Will we see any Ristretto in any new standards? |
\------------------------------------------------------------------------------/
/[cendyne: faceplant]----------------------------------------------------------\
| I asked about this. It is unlikely. The IETF process has been blocking the |
| draft for Ristretto [L29] for years and it is unclear if they want it. As of |
| now, it is expired and archived. |
\------------------------------------------------------------------------------/
I specifically learned about "pre-hashing" and that while it is supported in the
IETF standard, it is not often employed.
/-----------------------------------------------------------[glitch: satisfied]\
| ECDSA and RSA signatures do that! But not Ed25519? |
\------------------------------------------------------------------------------/
/[cendyne: 01010101]-----------------------------------------------------------\
| It hashes the public key point and the full message at once to create the |
| signature, so no it does not take a raw hash. That explains my confusion |
| when I wrote the deep dive. |
\------------------------------------------------------------------------------/
The paper finally gets to comparing the original reference implementation, the
IETF specification, and the latest LibSodium implementation.
[I3: comparison chart of Ed25519 implementations]
The reference implementation was almost SUF-CMA but lacked the essential L bound
check, which the IETF specification required. But what are these other checks
that LibSodium added? And what are these other security properties?
/------------------------------------------------------------------------------\
| A few security properties defined in straightforward language |
|------------------------------------------------------------------------------|
| Existential Unforgeability Under Chosen Message attacks (EUF-CMA): |
| An attacker cannot forge a signature for a new message that has never been |
| signed before. |
| |
| Strong Unforgeability Under Chosen Message Attacks (SUF-CMA): |
| An attacker cannot forge a different signature for an already signed |
| message that also verifies for the original public key. |
| |
| Strong Universal Exclusive Ownership (S-UEO): |
| An attacker that knows another honest public key cannot create their own |
| public key and message which verifies with an existing signature from an |
| honest public key. |
| |
| Malicious Strong Universal Exclusive Ownership (M-S-UEO): |
| An attacker that can create two malicious public keys and two messages |
| cannot create a single signature that verifies for both messages and |
| public keys. Also, if you have the M-S-UEO property, you also have the S- |
| UEO property. |
| |
| Message Bound Signature (MBS): |
| An attacker cannot create a single signature that verifies two distinct |
| messages with the same public key. |
\------------------------------------------------------------------------------/
The original release of Ed25519 achieves the minimum requirement of EUF-CMA but
not SUF-CMA.
/------------------------------------------------------[glitch: puppy-confused]\
| What's EUF-CMA? |
\------------------------------------------------------------------------------/
/[cendyne: the-more-you-know]--------------------------------------------------\
| That one says others cannot forge signatures and say you signed them. |
\------------------------------------------------------------------------------/
/---------------------------------------------------[glitch: surprised-pikachu]\
| Oh! That is essential to a digital signature! If someone could sign things |
| for me without my key, then what is the point of my secret key? |
\------------------------------------------------------------------------------/
/[cendyne: ceiling-watching]---------------------------------------------------\
| Exactly! That said, it is still possible to create alternative signatures |
| which can disrupt systems that expect one message - one public key - one and |
| only one signature. |
\------------------------------------------------------------------------------/
The IETF specification achieves SUF-CMA by ensuring that the signature S is
within a proper bound. On top of the signature bound, LibSodium achieved M-S-UEO
and MBS by checking:
* that the signature's commitment R is within a proper bound;
* and that the public key A is within a proper bound.
/---------------------------------------------------------------[glitch: ughhh]\
| So the original idea was sound but they dropped the ball on mandating some |
| bounds checks? |
\------------------------------------------------------------------------------/
/[cendyne: ughhh]--------------------------------------------------------------\
| Exactly, while saying malleability isn't a problem in the original paper. |
| History begs to differ; malleability is a problem. |
\------------------------------------------------------------------------------/
/-------------------------------------------------------------[glitch: popcorn]\
| What about that old RSA that everything still uses? Is it EUF-CMA? |
\------------------------------------------------------------------------------/
/[cendyne: looking-ych]--------------------------------------------------------\
| According to On the Security of the PKCS#1 v1.5 Signature Scheme [L30], it |
| meets EUF-CMA, though it calls it "UF-CMA." |
\------------------------------------------------------------------------------/
/--------------------------------------------------------[glitch: tech-support]\
| What about small curve group and invalid point attacks, is that a thing for |
| Ed25519? |
\------------------------------------------------------------------------------/
/[cendyne: derpy]--------------------------------------------------------------\
| That's an attack that exposes a victim's secret to the attacker through key |
| agreement! Key agreement is different from digital signature algorithms, |
| DSAs like Ed25519 only share whether a message, signature, and public key |
| were accepted or rejected. |
\------------------------------------------------------------------------------/
/[cendyne: fist-bump-ych]------------------------------------------------------\
| That said, maliciously crafted public keys and signatures can be used to |
| create malleable signatures. LibSodium rejects these signatures by checking |
| the public key, the signature, and the commitment R. |
\------------------------------------------------------------------------------/
For those wishing to read the same paper, check out my annotated version of The
Provable Security of Ed25519: Theory and Practice [L31]
/----------------------------------------------------------------[glitch: poof]\
| What about clamping? You highlight that a few times in this paper. |
\------------------------------------------------------------------------------/
/[cendyne: exasperated]--------------------------------------------------------\
| Clamping is actually a touchy subject. Clamping made the security proof very |
| difficult according to this paper. It has caused problems for hierarchical |
| keys generation with Tor and wallet key derivation too. |
\------------------------------------------------------------------------------/
/------------------------------------------------------------[glitch: cucumber]\
| Could you elaborate? |
\------------------------------------------------------------------------------/
/[cendyne: dumb-math]----------------------------------------------------------\
| Clamping is mathematically unsound; some even regard it as offensive. The |
| lower bits can be clamped with a mathematically acrobatic operation, but the |
| upper bit cannot be set so soundly. It is argued that the upper bit is set |
| to enforce constant time computation for everybody. The lower bits |
| supposedly make the cofactor go away. |
\------------------------------------------------------------------------------/
/[cendyne: objection]----------------------------------------------------------\
| Implementations do not use the mathematical technique that the high bit |
| would affect with regard to timing attacks. Adding the high bit only makes |
| this construction harder to extend in practice to interesting applications. |
| The original goal may have been a misuse-resistant implementation but in |
| practice it has been a waste of people's time. |
\------------------------------------------------------------------------------/
/[cendyne: you-dense]----------------------------------------------------------\
| This is not key agreement! The lower bits do not mitigate the cofactor in |
| any way for signatures. Instead other bound checks have been found and |
| applied to libraries like LibSodium. |
\------------------------------------------------------------------------------/
/-----------------------------------------------------------------[glitch: shy]\
| So should I add clamping or not? |
\------------------------------------------------------------------------------/
/[cendyne: bullshit2]----------------------------------------------------------\
| If you are developing an Ed25519 implementation from scratch for educational |
| purposes, to remain compatible with existing implementations you should |
| apply clamping. You'll find out that the secret key itself is not clamped. |
| The secret key is hashed and the hash is clamped before use with elliptic |
| curve mathematics. |
\------------------------------------------------------------------------------/
Now that I am aware of how this algorithm works and the theory behind its
security and how it is realized in practice: I was ready to review a proper
specification. If you are interested in reading this paper, check out my
annotated copy of The Provable Security of Ed25519 [L32].
Reading RFC8032
---------------
If you thought the original Ed25519 paper was a specification, it really is not.
It describes an idea and then fills every page with benchmark bragging,
mathematical transformations, and comparing to competing research. It is a
scientific paper and an accompanying implementation called "ref10" that
demonstrates the performance it touted on every page.
Unlike the original paper, the IETF's RFC8032 [L5] is actually useful. IETF
documents are written for engineers tasked with implementing a solution to a
known problem on the internet. A good RFC has an appendix with a reference
implementation and/ or "test vectors" to verify a successful implementation.
/------------------------------------------------------------------[jacobi: hi]\
| What is RFC and IETF? |
\------------------------------------------------------------------------------/
/[cendyne: talk-w-bubble]------------------------------------------------------\
| A "Request for Comments" or RFC is an accessible document made by the |
| "internet community" for the community to advance industry standards for |
| connected software. The "Internet Engineering Task Force" or IETF is one |
| such community. Other communities exist too, but the IETF uses "RFC" as a |
| name for their informational, best practice, and specification documents. |
| |
| This is my definition. Others may disagree. |
\------------------------------------------------------------------------------/
/-----------------------------------------------------------------[jacobi: hmm]\
| What does it take for something to become an RFC? |
\------------------------------------------------------------------------------/
/[cendyne: maybe-you]----------------------------------------------------------\
| Several things make for a successful RFC! Here's my opinion on what it takes |
| : |
| |
| * The internet community has tried to solve a complex problem involving |
| internet communication and that community has come up with several |
| similar solutions. |
| * Those creating solutions are likely making incompatible implementations |
| for the problem in question. |
| * These solutions may be entirely proprietary and the internet community |
| would benefit by having a freely available standard that others could |
| implement. |
| * A committee of volunteers with industry clout deem an idea worth |
| standardizing and support or refuse to support a standardization |
| effort. |
| * Those submitting the standard draft have the patience to trudge through |
| political mud and mailing lists for years. |
\------------------------------------------------------------------------------/
/-----------------------------------------------------------------[jacobi: nah]\
| That last half sounds very discouraging. Maybe that is why Google ditched |
| the standards process for JWT. |
\------------------------------------------------------------------------------/
/-------------------------------------------------------------[jacobi: peeking]\
| What do you recommend referencing while reading RFC8032 [L5] ? |
\------------------------------------------------------------------------------/
/[cendyne: thumbs-up]----------------------------------------------------------\
| Read the source code for ed25519-dalek [L13]. isis agora lovecruft [L33] is |
| the primary author of Dalek cryptography. It is very well written, easy to |
| explore, and straightforward to read. |
| |
| As far as I can tell, isis's name is intentionally lowercase. |
\------------------------------------------------------------------------------/
/[cendyne: concern]------------------------------------------------------------\
| However, there is a known misuse vulnerability that has not been addressed |
| and the library has not had a new version published in two years. Some are |
| reporting it as no longer maintained [L34] in the Rust community. While the |
| source is easy to read, consider another implementation if you are using |
| Rust. |
\------------------------------------------------------------------------------/
[I4: ed25519-dalek is deprecated]
Libraries that included Dalek now consider it deprecated and are replacing its
usage.
A list of unsafe libraries [L35] is available on GitHub.
/[cendyne: todays-interesting-thing]-------------------------------------------\
| But back to RFCs: once a technology component (like Ed25519) is |
| standardized, extending other IETF specs to support those components is |
| relatively easy and the documents are quite short. For example, soon after |
| RFC8032 [L5] (Ed25519) was finalized, RFC8037 [L36] was accepted which |
| specified how to use Ed25519 signatures with JWTs. |
\------------------------------------------------------------------------------/
/-------------------------------------------------------------[jacobi: reading]\
| Enough about the IETF, what did you actually learn from reading RFC8032 [L5] |
| ? |
\------------------------------------------------------------------------------/
[I5: RFC 8032 Annotations]
If you are interested, read my annotated copy of RFC 8032 [L37].
If you go into a specification, you should understand that you will learn how to
make the thing, not necessarily how to use it effectively or correctly. There
are "best practice" documents on using a technology, but unless it is a living
draft, the knowledge documented will be out of date in months or years.
/[cendyne: deus-ex-new]--------------------------------------------------------\
| The community may submit errata, but the RFC text itself is not updated. I |
| consider this aspect of RFCs to be unfortunate. It should not be upon a |
| reader 5 years later to patch the document in their head. This is a |
| usability defect. Implementors will not always review the errata. |
\------------------------------------------------------------------------------/
As I read RFC8032 [L5] and referenced Dalek and LibSodium source code, I learned
how Ed25519 was constructed and implemented. If you should read this, and re-
read it five times, you should develop a better understanding of the following:
* How Ed25519 secret keys (the "k") are prepared for elliptic curve
operations (the secret scalar "s")
* How Ed25519 secret scalars are converted to public keys (the "A")
* How Ed25519 signature commitments (the "R") are deterministically generated
* How Ed25519 signature verifiers (the "S") are created
* How to verify a signature with a public key, the message, the signature
commitment, and the signature verifier
* That implementations may differ by having different contexts in the hashing
process (which creates incompatible signatures)
* Develop a better intuition of elliptic curve math in practice
/-------------------------------------------------------------[jacobi: excited]\
| Oh! That's some useful information, but will this help me as an application |
| developer? |
\------------------------------------------------------------------------------/
/[cendyne: i-dunno-man-im-just-a]----------------------------------------------\
| No, not really. It will remind a developer about the basic interface of key |
| generation, signing, and verifying. But a library that implements it should |
| too. Reading RFC8032 [L5] will not help you secure your application. |
\------------------------------------------------------------------------------/
/[cendyne: ych-chomp]----------------------------------------------------------\
| Though it does hint that not every Ed25519 signature will be compatible with |
| the same message and key due to contexts. This is different from |
| compatibility by rejecting malicious signatures and malicious keys. |
\------------------------------------------------------------------------------/
/[cendyne: yeee]---------------------------------------------------------------\
| As a developing cryptographer, it was incredibly informative to me. If you |
| would like to learn about how cryptographic constructions are assembled then |
| do check out RFC8032 [L5] as functioning example. |
\------------------------------------------------------------------------------/
After finishing up my review of RFC8032 [L5] and the other papers, I felt
Ed25519 is a quirky design. It works, but it is clear that DJB et al were racing
to make something so performant on Intel chips that it would compel adoption.
I'm not saying don't use it. Just that whatever we use next [L38] should face a
fair number of questions on design and implementation.
Note that RFC8032 [L5] does not have the safety checks that LibSodium has. The
RFC will never be updated to give caution for malicious keys that have small or
malicious points [L39]. A future informational RFC might be published but by the
time it comes out, it will be far too late.
While RFCs may describe how a technology should be implemented or behave, it
does not specify how it should be used or how it should be exposed to a
developer. RFCs are also not a reliable source for guidance on preventing misuse
of a technology.
Sure, RFCs come with a section called "security considerations", but the content
is intended for the implementers and not the developers. The only thing in
RFC8032 [L5] that extends to developers says "don't sign large amounts of data
at once." Well thanks but what if I need to? No advice is given here.
Deterministic signatures and their weaknesses
---------------------------------------------
First an introduction to signatures based upon elliptic curve technology. This
knowledge is necessary to understand why deterministic signatures are
advantageous.
What problem do deterministic signatures solve?
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
The following describes how ECDSA works, consider reading the weaknesses at the
end before skipping back to deterministic signatures.
An Elliptic Curve Digital Signature Algorithm (ECDSA) is based on a commitment
and verifier. With ECDSA, the commitment is typically a random point on the
elliptic curve, and the verifier is an unguessable number which satisfies a
verification equation that also takes a public key and message. Corruption to
either the commitment or the verifier will result in an unverifiable signature.
Creating a signature involves both a probabilistic process and a few
deterministic processes.
/[cendyne: puppy-confused]-----------------------------------------------------\
| Could you explain what probabilistic and deterministic mean? |
\------------------------------------------------------------------------------/
/-----------------------------------------------------------[jacobi: thumbs-up]\
| A probabilistic process is a computation that produces something that |
| appears random, inputs may be given that tweak the properties of what comes |
| out. |
| |
| A deterministic process is a sequence of steps that always results in the |
| same thing given the exact same inputs. |
\------------------------------------------------------------------------------/
/--------------------------------------------------------------[jacobi: typing]\
| Also, I will refer to the private key, what you might see in a PEM file, as |
| a "signing secret" or "signing secret key". Other created and forgotten |
| secrets are involved as you will see next. |
\------------------------------------------------------------------------------/
A commitment secret is chosen randomly and is a large number. This secret should
be less than the prime number the curve is based on and it should be greater
than zero. This commitment secret will be used in the signature equation later
and, as named, should be kept secret. It is generated with a probabilistic
process.
Then, the commitment secret is transformed into a public format called the
commitment. This generally involves math where the "base point" or "generator"
of the curve is multiplied by itself many times. If the commitment secret were
500 then the base point would be multiplied by itself 500 times. This is also
referred to as exponentiation.
/---------------------------------------------------------------[jacobi: heart]\
| "Base point" and "generator" are terms used to refer to a point value |
| defined by the curve. Points are defined as having an x and y coordinate. If |
| you apply a whole number (called a "scalar") as an exponent to the |
| coordinate, an elliptic curve operation is executed to compute a new point |
| on the elliptic curve. |
\------------------------------------------------------------------------------/
/[cendyne: gendo]--------------------------------------------------------------\
| What about this mathematical operation makes it important? |
\------------------------------------------------------------------------------/
/------------------------------------------------------------[jacobi: teaching]\
| Reversing this exponentiation operation is considered a computationally-hard |
| problem. It is also sometimes called a "trap door function", where it is |
| easy to fall in, but not to climb out. Often this problem is referred as |
| "The Discrete Log Problem", or "DLog." Computationally-hard problems |
| underpin all of modern practical cryptography. |
\------------------------------------------------------------------------------/
We often call the commitment in specifications and papers "R", as it is a random
point. The verifying application cannot confirm how the commitment was
constructed. It may be maliciously constructed or unsafely constructed if the
commitment secret were 0 or greater than the prime-order of the curve.
/[cendyne: peeking-from-door]--------------------------------------------------\
| What's this about a prime-order? |
\------------------------------------------------------------------------------/
/-----------------------------------------------------------[jacobi: crossmark]\
| ECDSA is based upon elliptic curves which involve a high-bit prime number in |
| its definition. When the "base point" is multiplied to itself more times |
| than the prime number, this reduces the security of the curve by introducing |
| bias or malleability. So it is important that scalars used in exponentiation |
| do not equal or exceed the prime number in honest implementations. |
\------------------------------------------------------------------------------/
Before creating the verifier, the message is hashed (along with any other
contextual information) and the hash is treated as a big number, in other words
a "scalar." This hash is something the verifying application must recreate when
using a verification equation. It is generated with a deterministic process.
The verifier is constructed with an equation which takes the secret signing key,
the message hash, the public key, the commitment, and the curve parameters as
inputs. Unlike the commitment which is a point, the verifier is just a large
number.
A signature is the commitment and the verifier bundled together. Additional info
like what curve, what hash algorithm, the public key identifier, etc. may also
be included.
To verify a signature, an application must reconstruct the hash from the message
and have the public key of the signer. A signature is verified with the
signature components (the commitment and verifier, and contextual components
like the message hash, the public key, and the curve parameters. It is verified
by using an equation which if satisfied strongly indicates that the private key
tied to the public key was used to sign the message hash.
/---------------------------------------------------------------[jacobi: notes]\
| To see more on how ECDSA is implemented, check out RFC6979 [L40] section |
| 2.3.5 and section 2.4. RFC6979 [L40] describes a deterministic |
| implementation, to read a non-deterministic implementation consider step 2 |
| of section 2.4 to only contain: |
| |
| > A random value modulo q, dubbed k, is generated [with a cryptographic |
| > number generator]. |
| |
| And ignore section 3 entirely for a probabilistic ECDSA implementation. |
\------------------------------------------------------------------------------/
ECDSA comes with a few weaknesses:
* If the same commitment is signed with two verifiers using the same public
key, the private key can be trivially recovered;
* Insufficient randomness or broken randomness for commitment generation will
allow private keys to be recovered;
* Libraries may allow the application to set the commitment, which may let
the attacker influence or set the commitment and therefore allow private
keys to be recovered;
* And if the public key is maliciously constructed, its signatures might be
accepted for any or several messages.
/----------------------------------------------------------[jacobi: point-left]\
| You can find out more how ECDSA was poorly implemented in Sony PlayStation 3 |
| ECDSA random number reuse [L41] (archived [L42]). |
\------------------------------------------------------------------------------/
Feel free to share this topic: Elliptic Curve Digital Signature Algorithms [L43]
.
How are deterministic signatures implemented?
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
In practice we see a need for caution and care around the commitment part of a
signature. If the commitment secret is duplicated for different messages, then
the signing key secret for that key can be recovered. When an attacker holds the
key, they may impersonate the honest key holder and defeat the security of the
scheme that relies upon that authenticity.
/[cendyne: tell-me-more]-------------------------------------------------------\
| If you are unfamiliar with some of the vocabulary in this section, see |
| Elliptic Curve Digital Signature Algorithms [L43]. When I mention "recovered |
| ", consider it equal to "leaked" or "stolen." |
\------------------------------------------------------------------------------/
The security of a signature scheme requires that all commitment secrets be
unique (at least as far as distinct messages go). One way to do this is to
record information that changes over time, called state. It could be a counter
or a collection of all previously issued commitments. Unfortunately, state in
this scenario requires consistency for any application that holds the private
key. Also, maintaining a set of all commitments that can be efficiently searched
is difficult at scale. An alternative is to partition counters such that each
signer has a reserved counter space, so other signers will not accidentally
duplicate commitment secrets that will collide.
/----------------------------------------------------------------[jacobi: yuck]\
| If this is starting to sound over engineered, that is because it is. |
\------------------------------------------------------------------------------/
Instead, we have a cryptographic tool which is collision-resistant.
Cryptographic hashes or message digests exist to fill the role of what is called
a "random oracle." In computer science theory, an oracle is something that gives
an answer, and a random oracle gives a random answer which has never been seen
before. Replying with a pre-existing signature does not reveal more information
about the secret key. By definition something that has never been seen before
cannot collide with previous answers.
We deem a hash function as broken when a collision is found. MD5 is easily
broken, and SHA-1 (see shattered [L44]) can be broken with sufficient money and
server time.
/------------------------------------------------------------------[jacobi: ok]\
| One more computer science thing to mention: we generally do not care if a |
| message is verified twice. The verifier will not be able to determine if a |
| signer had signed the same message again or replied with a saved signature |
| when the message is the same. Because of that, it is safe to use |
| deterministic signatures which use deterministic commitments. |
\------------------------------------------------------------------------------/
To create a deterministic commitment secret with a hash function, we need to
maintain one important requirement: the hash digest used to create the
commitment secret must be unguessable. Also, the public form of the commitment
which goes into the signature should not reveal the commitment secret.
/------------------------------------------------------------[jacobi: surprise]\
| If you see that the commitment for any signature repeat for a different |
| message or key: that is a strong sign that something is wrong! Examples of |
| this are on the blockchain [L45]. |
\------------------------------------------------------------------------------/
Ed25519 uses the message and part of a SHA-512 hash of the signing secret key to
create a deterministic commitment secret and then the commitment is made from
that commitment secret. Because secret bits of sufficient entropy were added to
the hash of the message, it is too difficult to guess or reverse what the
commitment secret is.
Deterministic ECDSA (RFC6979 [L40]) uses a unique approach to probe for safe
commitment secrets using HMACs. The message and signing secret key are mixed
together with HMACs to create a possible commitment secret. If the commitment
secret is unsatisfactory, it probes for another value with a deterministic
algorithm. For example, a commitment secret of all 0â€™s is unsatisfactory.
A deterministic commitment secret protects the secret signing key from being
recovered. This protection relies on the collision resistance property we get
from cryptographic hashes. Besides key generation, the commitment secret
generation part of digital signatures is the only probabilistic part of creating
a signature. By replacing the commitment secret probabilistic process with a
deterministic process, the complete signature process for a pre-existing key
becomes deterministic.
Deterministic signatures remove the risk of exposing a secret signing key when
commitment secrets could be misused. This provides a defense against application
developer ignorance (like Sony) and poor randomness from the environment (like
some transactions on the blockchain).
/------------------------------------------------------------[jacobi: standard]\
| An interesting consequence of Ed25519â€™s design: since the secret scalar is |
| derived from the first 256 bits of the SHA-512 hash and the secret |
| commitments are made from the other 256 bits, if the secret scalar were |
| leaked but not the private key then signatures made with a stolen secret |
| scalar must be different from honest signatures for messages that have not |
| been honestly signed before. |
\------------------------------------------------------------------------------/
/---------------------------------------------------------------[jacobi: dizzy]\
| However, a verifier cannot tell the difference between the impersonator and |
| the honest signer since the commitment is made from secret information. |
\------------------------------------------------------------------------------/
Feel free to share this topic: Deterministic Digital Signature Algorithms [L46].
Deterministic signatures in practice
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
/---------------------------------------------------------------[jacobi: angel]\
| Ed25519 removed the biggest landmine that traditional ECDSA still has to |
| this day. By removing user choice and randomness from this signature |
| algorithm, we can feel safer in using it. |
\------------------------------------------------------------------------------/
/[cendyne: puking]-------------------------------------------------------------\
| Yep! It is not all rainbows however. |
\------------------------------------------------------------------------------/
/-----------------------------------------------------------------[jacobi: beg]\
| Did I miss something? |
\------------------------------------------------------------------------------/
/[cendyne: wrench]-------------------------------------------------------------\
| The theory is good! However, the real world has a few more tricks for |
| deterministic algorithms. |
\------------------------------------------------------------------------------/
/------------------------------------------------------------[jacobi: standard]\
| Do tell. |
\------------------------------------------------------------------------------/
Assuming your deterministic algorithm runs in constant time, a remote attacker
should not be able to use side channels (e.g., timing analysis) to discover
information about the secret key.
However, the story is quite different for a local attacker. Power analysis is a
technique that samples power consumption or monitors radio frequency noise for
indications of computation.
/------------------------------------------------------------------------------\
| Real World Crypto |
|------------------------------------------------------------------------------|
| Youtube Video [L47] |
| Side channel attacks on implementations of Curve25519 | Yuval Yarom and |
| Daniel Genkin | RWC 2018 [L48] 1/9/2023 |
\------------------------------------------------------------------------------/
Yarom and Genkin show on stage that they could recover an Ed25519 key with a
cheap software-defined radio by getting the device to sign a variety of data on
the primary CPU.
In the same line as power analysis, an attacker might try to use a fault attack
to corrupt the commitment secret. A fault attack involves tampering with the
deviceâ€™s power for a short duration of time. Instead of a full computer, fault
attacks generally target smart cards or dedicated chips that perform
cryptographic operations. These trusted devices are important for identity
between machines.
/---------------------------------------------------------[jacobi: jaw-dropped]\
| What devices should I keep secure if fault attacks are a threat to me? |
\------------------------------------------------------------------------------/
/[cendyne: access-granted]-----------------------------------------------------\
| If you have a hardware security module (HSM), a hardware wallet, or even a |
| WebAuthN key, you should keep it secure. There are devices that self- |
| destruct when tampered. This is also a choice, but make a plan if the device |
| is lost or destroyed. |
\------------------------------------------------------------------------------/
Often fault attacks are performed by tapping into the processorâ€™s power and then
intentionally manipulating the power when the device performs a computation. As
an example, if a fault is introduced when the process should have hashed the
message but it did not, then the hash that is signed may be predictable. That
is, the commitment secret has been coerced to a predictable value and the
signing code may proceed without realizing anything is wrong. The signature that
comes out of the device may then be examined to recover the private key.
/--------------------------------------------------------------[jacobi: flails]\
| Suppose I wanted to defend against fault attacks and power analysis, what |
| can I do? |
\------------------------------------------------------------------------------/
/[cendyne: heh-heh]------------------------------------------------------------\
| I have heard a few things. For applications, a developer may try to use |
| blinded keys. This does make it slower but if youâ€™re only signing something |
| once a minute you will not notice. An example of how to do this is included |
| in "Draft: Key Blinding for Signature Schemes." [L49] |
\------------------------------------------------------------------------------/
/[cendyne: ready]--------------------------------------------------------------\
| For hardware developers, I have heard a suggestion where a power source like |
| a capacitor is charged, the main power is disconnected, and the capacitor is |
| used as a power source for the computation. See Protecting smart cards from |
| passive power analysis with detached power supplies [L50]. The patent for |
| this idea [L51] has expired so try it out! |
\------------------------------------------------------------------------------/
/---------------------------------------------------------------[jacobi: angel]\
| I was just interested. Turns out local attackers are not part of my threat |
| model. Is there anything else? |
\------------------------------------------------------------------------------/
/[cendyne: yes]----------------------------------------------------------------\
| There is! Keep reading! |
\------------------------------------------------------------------------------/
Public Key Confusion
--------------------
If you take a look at RFC8032 [L5], you will find that the signing function
takes the public key as part of the hash which is signed. Also, you will see
that the public key is the same in both the signing hash and the verifying hash.
/[cendyne: thumbs-up]----------------------------------------------------------\
| By including the public key in the hash, assuming other checks are in place |
| like LibSodium, this signature scheme produces message bound signatures. |
| Soatok called this exclusive ownership. |
\------------------------------------------------------------------------------/
Now what do developers do when they see duplicate domain specific code? It is
refactored into its own function.
And what do developers do when they see something is deterministic and
effectively static? It is memoized and cached.
In the original implementation, we see the following code. If it looks hard to
read, you are not alone. This is why I recommend reading Dalek instead. The Rust
compiler can do so much more than the C compiler to make an optimized
executable.
int crypto_sign(
unsigned char *sm,
unsigned long long *smlen,
const unsigned char *m,
unsigned long long mlen,
const unsigned char *sk
)
{
unsigned char pk[32];
unsigned char az[64];
unsigned char nonce[64];
unsigned char hram[64];
ge_p3 R;
memmove(pk,sk + 32,32);
crypto_hash_sha512(az,sk,32);
az[0] &= 248;
az[31] &= 63;
az[31] |= 64;
*smlen = mlen + 64;
memmove(sm + 64,m,mlen);
memmove(sm + 32,az + 32,32);
crypto_hash_sha512(nonce,sm + 32,mlen + 32);
memmove(sm + 32,pk,32);
sc_reduce(nonce);
ge_scalarmult_base(&R,nonce);
ge_p3_tobytes(sm,&R);
crypto_hash_sha512(hram,sm,mlen + 64);
sc_reduce(hram);
sc_muladd(sm + 32,hram,az,nonce);
return 0;
}
Source for the above code snippet [L52]
In the incredibly inaccessible code above, we see that the public key "pk" is
created on the fly and that it sneaks into the signing buffer which is hashed at
the end.
/------------------------------------------------------------[jacobi: teaching]\
| As a reminder, RFC8032 [L5] helpfully describes that this hash takes in the |
| following order: |
| |
| * The commitment "R" |
| * The public key "A" in RFC, "pk" in the above |
| * The message "M" in the RFC, "m" in the above |
\------------------------------------------------------------------------------/
/------------------------------------------------------------------------------\
| Cendyne @CendyneNaga@twitter.com |
|------------------------------------------------------------------------------|
| I am getting heartburn trying to read and explain ed25519 ref10 |
| [L53] 9/10/2022 |
\------------------------------------------------------------------------------/
/---------------------------------------------------------------[jacobi: dizzy]\
| It'll be over soon. No wonder everyone wanted to rewrite it. This is |
| absolutely terrible code. |
\------------------------------------------------------------------------------/
A small but impactful change is often introduced. I have found multiple
instances of this change being independently introduced into this function by
multiple developers in their commit history.
Here is the most readable change I have seen.
void ed25519_sign(
unsigned char *signature,
const unsigned char *message,
size_t message_len,
const unsigned char *public_key,
const unsigned char *private_key) {
sha512_context hash;
unsigned char hram[64];
unsigned char r[64];
ge_p3 R;
sha512_init(&hash);
sha512_update(&hash, private_key + 32, 32);
sha512_update(&hash, message, message_len);
sha512_final(&hash, r);
sc_reduce(r);
ge_scalarmult_base(&R, r);
ge_p3_tobytes(signature, &R);
sha512_init(&hash);
sha512_update(&hash, signature, 32);
sha512_update(&hash, public_key, 32);
sha512_update(&hash, message, message_len);
sha512_final(&hash, hram);
sc_reduce(hram);
sc_muladd(signature + 32, hram, private_key, r);
}
Source code for the above snippet [L54]
This code made several changes:
* The secret signing key is no longer an input. Instead, a private_key is
given as input.
* The secret scalar that is derived from the secret signing key is preserved.
It is the first 32 bytes of the private_key variable
* The key tag is preserved. It is another 32 bytes (after the secret scalar)
from the private_key variable.
* The public key is now supplied as another variable to this function.
Previously, the public key was calculated from the private key each time
the signature function executed.
* The hash function switches from a single call to a stateful call using the
initialize, update, and finalize pattern.
Unfortunately, these changes have introduced a misuse vulnerability.
/[cendyne: glare]--------------------------------------------------------------\
| Remember, the problem is accidentally signing the commitment twice with |
| different signatures. The last thing that can be tweaked in the signing |
| function is the public key! |
\------------------------------------------------------------------------------/
/-----------------------------------------------[jacobi: dot-dot-dot-surprised]\
| But I can pass in the public key that comes from my private key, what is the |
| problem? |
\------------------------------------------------------------------------------/
/[cendyne: smug]---------------------------------------------------------------\
| What if you donâ€™t pass the public key that you specifically derived from the |
| secret key? |
\------------------------------------------------------------------------------/
/-----------------------------------------------------[jacobi: laptop-thinking]\
| Then the hash, which takes the public key comes out differently. |
\------------------------------------------------------------------------------/
/[cendyne: panic2]-------------------------------------------------------------\
| And so, the verifier changes in the signature, but not the commitment! |
\------------------------------------------------------------------------------/
/----------------------------------------------------------------[jacobi: idea]\
| Which creates two different signatures by the same public key on the same |
| commitment. |
\------------------------------------------------------------------------------/
/[cendyne: failure]------------------------------------------------------------\
| That means the secret scalar (which is effectively the secret signing key to |
| any verifying application) may be recovered with some math. |
\------------------------------------------------------------------------------/
This misuse is demonstrated in ed25519-unsafe-libs/ed25519-chalkias-exploit
[L55].
/----------------------------------------------------[jacobi: screaming-inside]\
| What can we learn from this issue? Besides "donâ€™t do that." |
\------------------------------------------------------------------------------/
/[cendyne: flails2]------------------------------------------------------------\
| The public key is bound to the secret key in the signing process. This |
| change unbinds the public key to the secret key. |
\------------------------------------------------------------------------------/
/------------------------------------------------------------[jacobi: thinking]\
| The secret scalar and key tag appear bound together. |
\------------------------------------------------------------------------------/
/[cendyne: shades]-------------------------------------------------------------\
| Indeed. If the public key were a part of the signing key variable, then it |
| would be bound to the signing key and this issue would be avoided. |
\------------------------------------------------------------------------------/
/-----------------------------------------------------[jacobi: wtfdidijustread]\
| That would require more offsets and then Iâ€™d have to keep that consistent |
| across all the call points. |
\------------------------------------------------------------------------------/
/[cendyne: ych-doot]-----------------------------------------------------------\
| There is a better way... C has structures as does practically every |
| language. You should leave behind these dangerous techniques that use byte |
| pointers and offsets and just use structs. All the data in this scenario has |
| fixed sizes. It can be passed by value or reference with ease. |
\------------------------------------------------------------------------------/
/--------------------------------------------------------------[ibzan: excited]\
| Also try Rust! Rust is designed to prevent misuse involving bytes and |
| pointers. As long as you do not use unsafe. Why use buffers in Rust when you |
| could use structures that pass around slices? |
\------------------------------------------------------------------------------/
/[cendyne: proud]--------------------------------------------------------------\
| By composing related and bound data together in a structure, we can be more |
| confident that it would not be misused over the alternative, which is that |
| the programming language is used as the source of structure. |
\------------------------------------------------------------------------------/
/-----------------------------------------------------------------[jacobi: beg]\
| Could you elaborate more? |
\------------------------------------------------------------------------------/
/[cendyne: looking-ych]--------------------------------------------------------\
| If you have ever heard of static application security testing (SAST), it |
| works by discovering the structures of how data flows in a program. While |
| some structures are technically safe at one point in time, the program |
| structure may be changed with new code to be unsafe later. |
\------------------------------------------------------------------------------/
/[cendyne: galaxy-brain]-------------------------------------------------------\
| Data structures can be understood and reasoned about more easily, while |
| program structures require a holistic analysis â€” which is often beyond the |
| scope of what a developer can do in their head. |
\------------------------------------------------------------------------------/
/--------------------------------------------------------------[jacobi: typing]\
| All that said, what can application developers take away from this |
| experience? |
\------------------------------------------------------------------------------/
/[cendyne: sneeze]-------------------------------------------------------------\
| If you are supplying a public key to a signing (not verifying) operation, |
| then this is an area prone to mistakes and misuse. Insulate this code from |
| the outside with a few changes! |
\------------------------------------------------------------------------------/
/[cendyne: laptop2]------------------------------------------------------------\
| Immediately wrap the signing function from a misuse-prone library with your |
| own function which derives the public key from the secret signing key. Then, |
| look for alternative implementations which do not include this misuse prone |
| function design. |
\------------------------------------------------------------------------------/
/[cendyne: corporate-drone]----------------------------------------------------\
| You could go further and wrap the signing key to memoize the public key next |
| to it so it is never separated. |
\------------------------------------------------------------------------------/
Conclusion
----------
The Ed25519 digital signature algorithm raised the bar for signature key safety
by introducing reliable and efficient deterministic signatures. Unfortunately,
the original authors hand-waved away important security guarantees in the name
of efficiency. These authors produced an inaccessible scientific document
focused entirely on performance. The community had to review, adopt, and
integrate an inaccessible implementation from Daniel J. Bernstein's SUPERCOP
[L56] codebase because the paper did such a poor job on describing its
implementation. Daniel J. Bernstein et al were so close to providing message
bound signatures but failed to add trivial checks to the reference
implementation, likely in the name of performance. The paper also proposed two
equations, one that was fast for individual verification and one that was
acceptable for batch verification. However, these equations behave differently
for maliciously crafted signatures. This difference in behavior has led to a
denial-of-service problem for batch verification use cases. Also, the paper did
not provide proofs for its security properties.
A combination of no formal specification, no human friendly framework of how
Ed25519 is made, and a completely inaccessible codebase has lead to misuse as
Ed25519's adoption has proliferated. RFC8032 [L5] helped formalize what an
Ed25519 implementation should look like but lacked several safety features
required to complete the message bound signature security property. Those
security features included: checking the commitment was within an acceptable
range, checking that the public key was within an acceptable range, and
verifying that the public key was not maliciously constructed with known points
that break the mathematical properties of the elliptic curve. Again, LibSodium
provides these protections now.
Without a reliable baseline, several diverse implementations came to be. Each
implementation had its own validation criteria on signatures and hardly any of
them actually implemented RFC8032 [L5] faithfully. Some of these
implementations, such as LibSodium, changed over time to restrict signatures to
those signed only by honest signers. In distributed consensus environments,
changes in verification behavior must be versioned and coordinated. Because
verification behavior changed in LibSodium, a denial-of-service attack was a
threat if some contributors to consensus accepted maliciously crafted
signatures.
The reference code was also so inaccessible that developers would introduce a
misuse vulnerability when trying to improve their application while minimizing
impact to the API. A developer looking to improve the accessibility of their
code, minimize impact to usage of that code, and improve performance by
memoizing the public key would unknowingly introduce risk into their
application.
I believe that the next generation of digital signature algorithms, including
post-quantum algorithms, should:
* Be resistant to timing attacks
* Be efficient for signing and verification
* Prevent misuse which can reveal the private key
* Prevent misuse on signing and verifying large messages, including partial
signing and partial verification of messages
* Prevent misuse on signing content by correctly binding all key specific
material to the signing key up front
* Include an accessible implementation with clear documentation for both API
usage and the internal code in how it functions
* Supply a reference implementation with the knowledge that it will
proliferate for a decade instead of being rewritten by another competent
patient cryptographer
* Provide a draft specification for the digital signature algorithm
* Ensure the draft specification and the reference implementation are
consistent
* Minimize acrobatic math for odd behavior like clamping and instead rely
upon mathematically sound approaches when required
* Actually provide formal proofs for security properties and how the security
properties are realized in the specification
* Include security properties such as M-S-UEO and MBS and Non Re-Signability
/----------------------------------------------------------[jacobi: point-left]\
| Non Re-signability is a newly proposed security property in BUFFing |
| signature schemes beyond unforgeability and the case of post-quantum |
| signatures [L57]. In short it means that without the message, there should |
| be no way for someone else to come up with their own signature for their own |
| public key. |
\------------------------------------------------------------------------------/
/[cendyne: cupcake]------------------------------------------------------------\
| I might write about this later! |
\------------------------------------------------------------------------------/
/[cendyne: i-sleep]------------------------------------------------------------\
| This article is part of the series Creating Authenticated QR Codes. The next |
| article has not been published yet! When it is, I will post it on Twitter |
| [L58], Telegram [L59], and through my RSS feed here. |
\------------------------------------------------------------------------------/
Final Words
-----------
My goal was to really understand Ed25519 so that I could explain it here in a
way where you, the reader, do not have to dive into the depths that I had to in
order to understand the content and its qualities.
My journey continually confirmed that cryptography resources remain inaccessible
to many audiences. I had to reach out to experts (see acknowledgement below) to
clarify or confirm my understanding. Some of my expert interactions required a
significant mathematical understanding of what goes into a cryptographic tool
like a digital signature algorithm. I would not have been able to follow along
three years ago.
After publishing A Deep dive into Ed25519 Signatures [L4], I received enough
feedback to convince me that I had much more to learn. While investigating that
feedback, I made small corrections and added hints to the original article and
put larger items onto a backlog which led to this addendum. However while
preparing the pre-draft to this article, I burned out [L60] and could not write
for months.
Once I had regained my writing capability in August, I resumed my education on
Ed25519 to write this addendum. This article took nearly a month to research and
write. I hope that my language is more accessible than what I had to read and
that it is correct enough to inform application developers that make decisions
on what cryptographic tools to employ in their applications.
/[cendyne: hi]-----------------------------------------------------------------\
| Hey, if you think something is inaccurate, please contact me over email. See |
| my contact page [L61] for details. I would appreciate feedback that includes |
| references that support your views and knowledge. |
\------------------------------------------------------------------------------/
Thank you for taking the time to get this far, I wish you the best in securing
the future of your teams and customers.
Acknowledgements
^^^^^^^^^^^^^^^^
Thank you to Thomas Pornin [L62], author of RFC6979 [L40] and BearSSL [L63] for
taking the time to connect everything together for signature schemes and the
math involved. Thank you to Filippo Valsorda [L64], author of age encryption
[L65] which uses Ed25519 keys, for recommending what content to include. Thank
you to Nadim Kobeissi [L66], who is invested in raising the baseline for
cryptography education [L67] in neat and fun ways, for recommending what content
to include. Thank you to Soatok [L68], another furry blogger who seeks to make
cryptography accessible, for leads and feedback while researching Ed25519 and
for final proof reading of this article. Thank you to Ibzan [L69] for content
and editing review. Thank you to Xe Iaso [L70] for reviewing this article before
publication. Thank you to Glitch [L71] for permission to use his character in
dialog, Ibzan and Soatok and Xe also have characters depicted above with
permission.
--------------------------------------------------------------------------------
Request For Comments (RFC):
A "Request for Comments" or RFC is an accessible document made by the
"internet community" for the community to advance industry standards for
connected software.
Existential Unforgeability Under Chosen Message attacks (EUF-CMA):
An attacker cannot forge a signature for a new message that has never been
signed before.
Elliptic Curve Digital Signature Algorithm (ECDSA):
A DSA which uses elliptic curve operations to sign a message. See /topics/
ecdsa.html [L43] for how it works.
Message Bound Signature (MBS):
An attacker cannot create a single signature that verifies two distinct
messages with the same public key.
Malicious Strong Universal Exclusive Ownership (M-S-UEO):
An attacker that can create two malicious public keys and two messages cannot
create a single signature that verifies for both messages and public keys.
Also, if you have the M-S-UEO property, you also have the S-UEO property.
Internet Engineering Task Force (IETF):
The IETF is a standards organization for the internet composed of volunteers.
IETF working groups collaborate to produce RFCs that standardize internet
technologies.
Strong Universal Exclusive Ownership (S-UEO):
An attacker that knows another honest public key cannot create their own
public key and message which verifies with an existing signature from an
honest public key.
Strong Unforgeability Under Chosen Message Attacks (SUF-CMA):
An attacker cannot forge a different signature for an already signed message
that also verifies for the original public key.
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 [L2].
Hash based Message Authentication Code (HMAC):
An HMAC is a MAC which uses hashes or message digests to authenticate a
message. It is resistant to length extension attacks, which the underlying
hash function may be susceptible to. You will find that common instatiations
of HMAC are also PRFs.
[L1]: https://archive.ph/Wbyos
[L2]: /posts/2022-03-05-why-dsa.html
[L3]: https://archive.ph/pn4HS
[L4]: /posts/2022-03-06-ed25519-signatures.html
[L5]: https://tools.ietf.org/html/rfc8032
[L6]: https://meta.wikimedia.org/wiki/Cunningham%27s_Law
[L7]: https://hdevalence.ca/blog/2020-10-04-its-25519am
[L8]: https://archive.ph/o1xh6
[L9]: https://link.springer.com/chapter/10.1007/978-3-642-37682-5_30
[L10]: https://iacr.org/
[L11]: /posts/2022-01-23-base64.html
[L12]: https://www.openssl.org/docs/man1.1.1/man7/Ed25519.html
[L13]: https://github.com/dalek-cryptography/ed25519-dalek
[L14]: https://doc.libsodium.org/
[L15]: https://github.com/ZcashFoundation/ed25519-zebra
[L16]: https://github.com/floodyberry/ed25519-donna
[L17]: https://pkg.go.dev/crypto/ed25519@go1.19
[L18]: https://en.wikipedia.org/wiki/Tor_(network)
[L19]: https://archive.ph/4sJpo
[L20]: https://github.com/jedisct1/libsodium/commit/
5808b830924b137d6332314edb2f654da7702f2b
[L21]: https://zips.z.cash/zip-0215
[L22]: https://ed25519.cr.yp.to/ed25519-20110926.pdf
[L23]: https://en.wikipedia.org/wiki/X.690
[L24]: https://csrc.nist.gov/glossary/term/pseudorandom_function
[L25]: https://github.com/dalek-cryptography/ed25519-dalek/blob/main/src/
keypair.rs#L388-L392
[L26]: https://soatok.blog/2021/08/16/lightning-round/#commitments
[L27]: https://eprint.iacr.org/2020/823
[L28]: https://eprint.iacr.org/2016/191
[L29]: https://datatracker.ietf.org/doc/draft-irtf-cfrg-ristretto255-decaf448/03
/
[L30]: https://eprint.iacr.org/2018/855
[L31]: https://c.cdyn.dev/bbrasE9M
[L32]: https://c.cdyn.dev/dQqu_IJ3
[L33]: https://blog.patternsinthevoid.net/index.html
[L34]: https://github.com/rustsec/advisory-db/issues/1360
[L35]: https://github.com/MystenLabs/ed25519-unsafe-libs
[L36]: https://tools.ietf.org/html/rfc8037
[L37]: https://c.cdyn.dev/rlnW1ohb
[L38]: https://doubleodd.group/
[L39]: https://archive.ph/WU8MW
[L40]: https://tools.ietf.org/html/rfc6979
[L41]: https://yingtongli.me/blog/2019/01/28/crypto-failures.html
[L42]: https://archive.ph/sS4HI
[L43]: /topics/ecdsa.html
[L44]: https://shattered.io/
[L45]: https://bitcoin.stackexchange.com/questions/97094/what-does-this-variable
-r-mean
[L46]: /topics/deterministic-dsa.html
[L47]: https://youtu.be/mcEHVvcqUzU
[L48]: https://www.youtube.com/watch?v=mcEHVvcqUzU
[L49]: https://datatracker.ietf.org/doc/html/draft-dew-cfrg-signature-key-
blinding-02
[L50]: https://patents.google.com/scholar/17297821962695206839
[L51]: https://patents.google.com/patent/US6507913B1/en
[L52]: https://github.com/jedisct1/supercop/blob/master/crypto_sign/ed25519/
ref10/sign.c
[L53]: https://twitter.com/CendyneNaga/status/1568410604875956224
[L54]: https://github.com/orlp/ed25519/blob/
b0de745a0c1d92d2e5ec8bd2169d149056aeac1f/src/sign.c
[L55]: https://github.com/MystenLabs/ed25519-unsafe-libs/tree/main/ed25519-
chalkias-exploit
[L56]: https://bench.cr.yp.to/supercop.html
[L57]: https://eprint.iacr.org/2020/1525
[L58]: https://twitter.com/CendyneNaga
[L59]: https://t.me/s/cendynedev
[L60]: /posts/2022-06-20-burnout-again.html
[L61]: /contact.html
[L62]: https://twitter.com/bearsslnews
[L63]: https://www.bearssl.org/
[L64]: https://filippo.io/
[L65]: https://age-encryption.org/
[L66]: https://nadim.computer/
[L67]: https://twitter.com/kaepora/status/1529080567458938880
[L68]: https://soatok.blog/
[L69]: https://twitter.com/ibzanhyena
[L70]: https://xeiaso.net/
[L71]: https://www.glitchfur.net/
[I1]: https://c.cdyn.dev/8hAa457l
[I3]: https://c.cdyn.dev/Q7C7V2jz