Ed25519 signature usage prone to inconsistent peer views between LibP2p implementations

[kayabaNerve]

Ed25519 signatures are defined in the spec as per the RFC: https://github.com/libp2p/specs/blob/87c684e2451684445e8ae8073c90add9645b3b26/peer-ids/peer-ids.md?plain=1#L166

Unfortunately, the RFC is incomplete with regards to edge cases. Please see https://hdevalence.ca/blog/2020-10-04-its-25519am for more info.

While additional rules have been created (ZIP-0215, further adopted by IOTA), and implemented into a variety of libraries becoming the defacto standard (ed25519consensus, ed25519-zebra), they are not employed by LibP2p.

To reduce the risk of some peers finding some peers valid which others do not, LibP2p should explicitly standardize its signature rules to ZIP-0215 or an equivalent spec.

Please note this an active possibility. rust-libp2p uses curve25519-dalek's verify (banning torsioned Rs, distinct from clearing their cofactor) and depending on the features used, may accept some unreduced s values (which rust-libp2p cannot prevent due to the way features work in Rust). go-libp2p uses Go's crypto/ed25519 bans torsioned Rs and doesn't accept unreduced s values. js-libp2p does already use ZIP-215 rules as a side effect of it being the default for Noble.

[lidel]

Thank you for flagging @kayabaNerve

It will be important to improve libp2p/ipns specifications to include details for this because it potentially impacts the ongoing work to add Curve25519 (Ed25519 X25519) support to Web Cryptographic APIs in browsers (https://github.com/ipfs/in-web-browsers/issues/204).

@javifernandez are you able to confirm if ED25519 implementation in browsers will follow additional rules from ZIP-215 or something else? Writing it down would be the first step towards agreeing what to do here.

[javifernandez]

I'd need more time to do a deeper investigation, but when it comes to an standardized implementation in browsers of a web API, the Secure Curves spec is where we should look at.

As you can see, the section about the Verify operation includes 2 steps to check for invalid points. These checks have been added recently to the spec and they are not implemented in either the WebKit (Safari) or Blink (Chrome) engines. There is a bug in chrome that I plan to start working on in the following weeks.

Additionally, regarding the divergence derived fro the choice of verification equations, there is an issue filed 1 year ago precisely about that, which has not been discussed extensively. I know from private conversations that the spec editor is considering the issue, but it's definitively not a priority for now.

[kayabaNerve]

Without having the read the specification/implementations, my guess is Ed25519 as standardized in the RFC will be implemented. As the RFC says, clients may (should?) use the formula which clears the cofactor which is a notable part of ZIP-215. That'd leave it up to browsers in what they actually do.

I'd like to chime in there's two distinct design criteria here. The RFC's original underspecified implementation has created a variety of fragmented rule sets. Any single one of them will enjoy wide compatibility. All of them will be able to be forced into a disagreement by targeted signatures.

The ZIP simply creates a very clear rule set. The problem with using it in a web spec is that it explicitly prevents usage of any other rule set in web browsers. Certain web browsers may want to enable wider support OR may want to pick a specific rule set due to ecosystem reasons. Explicitly picking any, while resolving conflicts, would reduce applicability.

However, for LibP2p and distributed systems in general where conflicts are explicitly undesirable, the ZIP specifically is desirable.

While I support having the context of web specs applied, I don't believe the decision from their design criteria should be the decision applied here.

---

Actually reading the spec, https://wicg.github.io/webcrypto-secure-curves/#ed25519, it's explicitly incompatible.

1) They reject small order points. 2) They don't require usage of the cofactor-agnostic formula. Browsers have the choice to use sG == R + cA or 8sG == 8R + 8cA. 3) They don't define encode/decode. Assuming the RFC is also followed for this, the RFC does ban unreduced points (distinct from the ZIP. I'm unsure why the ZIP allows this but believe it's likely due to unreduced points existing in signatures in the wild due to libraries which had improperly implemented the RFC) and unreduced scalars.

The biggest issue is point 2. Because of point 2, browsers will also be fragmented and disagree, with their spec incapable for use in consensus-critical systems.

EDIT: Having read the above comment, if that issue is resolved, the spec will be properly defined and I'd be fine with it being adopted instead of ZIP-0215. Whichever is considered better as a standard should be used.

[javifernandez]

EDIT: Having read the above comment, if that issue is resolved, the spec will be properly defined and I'd be fine with it being adopted instead of ZIP-0215. Whichever is considered better as a standard should be used.

When you said "issue is resolved" do you mean changing the spec to remove the possibility of choice in the cofactor formula ?

[kayabaNerve]

Correct. If resolution of the GH issue is by explicitly allowing either formula, then it would not be valid here.

[javifernandez]

The problem is that we are limited by the cryptographic libraries that each browser use. While chrome's implementation is based on BoringSSL, WebKit relies on the mac's platform Apple CryptoKit and Firefox depends on libNSS. As it's mentioned in the issue, it might be worth to investigate if these components have a common behavior that could be the base of a standard for the Secure Curve spec.

[kayabaNerve]

BoringSSL: 1) Uses the non-cofactor formula. 2) Doesn't reject small-order points and is incompatible with the web spec, meaning Chrome is unless Chrome added additional checks (which I'd assume).

CryptoKit is a closed-source impl (I believe?) or OpenSSL. OpenSSL matches BoringSSL.

libNSS doesn't appear to offer Ed25519 verification, solely curve operations.

[javifernandez]

BoringSSL:

1. Uses the non-cofactor formula.

2. Doesn't reject small-order points and is incompatible with the web spec, meaning Chrome is unless Chrome added additional checks (which I'd assume).

There are WPT to verify the X25519 implementation, based also on BoringSSL, rejects small-order points, so I wonder why it's not the case of the Ed25519 curve. In any case, the idea of the bug is to add additional checks if necessary.

CryptoKit is a closed-source impl (I believe?) or OpenSSL. OpenSSL matches BoringSSL.

CryptoKit is closed-source, indeed, so it complicates the investigation, but I could ask some contacts at Apple.

libNSS doesn't appear to offer Ed25519 verification, solely curve operations.

Yes, libNSS doesn't implement the Ed25519 algorithm, but it's currently under development , so probably we can influence on their decision about this issue.

[kayabaNerve]

My guess would be something along the lines of because because using a small order public key doesn't impact your authenticity (you setting it to effectively none) yet using a small order point in a handshake does effect the effective entropy of the handshake result. Reading the linked-to code, it seems because the x25519 RFC rejects small-order points yet the Ed25519 RFC does not.

You could also write a few basic tests, but yes, either would work.

Regarding libNSS, if it wants to impl the web spec, that's one thing. If that's not an explicit goal, I'd personally encourage it to implement the RFC however, with the non-cofactor formula.

[lidel]

Related Chromium bug: Ensure Ed25519 and X25519 implementations matches the spec regarding small-order keys

[javifernandez]

There is a PR for the Secure Curves specification to require the cofactorless verification.