bartossh / Computantis

The Computantis is a backbone service for creating secure, reliable and performant solutions for transaction exchange and Byzantine fault-tolerant systems.
https://bartossh.github.io/Computantis/
GNU General Public License v3.0
0 stars 0 forks source link

Asymmetric cryptography signatures divergence issue. #219

Closed bartossh closed 1 year ago

bartossh commented 1 year ago

@kubagruszka @kmroz @dmatusiewicz-consult-red The use of edward25519 elliptic curve asymmetric key cryptography has pros and cons.

I need to state that I do not fully understand the details of different implementations, but at my current level of understanding, I see that keeping to C and Go implementation using ed25519 we are safe, but we cannot accept implementations of that cryptographic algorithm from outside of the Go (standard library) and C (OpenSSL). What we already do.

Let's elaborate a bit more...

PROS: Full: https://cr.yp.to/ecdh/curve25519-20060209.pdf In short:

But nothing is free this day nor without downsides. CONS: Full: https://archive.ph/scZ3T Fairly in short:

Fixing the problem: Ed25519 signatures are widely used in consensus-critical contexts (e.g., blockchains), where different nodes must agree on whether or not a given signature is valid. In these contexts, incompatible validation criteria create the risk of consensus divergence, such as a chain fork. Mitigating this risk can require an enormous amount of effort. For instance, the initial implementation of Zcash consensus in zcashd inherited validation criteria from the then-current version of libsodium 1.0.15. Due to a bug in libsodium, the actual behavior was different from the intended criteria, which had been documented in the Zcash protocol specification, so the specification had to be corrected to match. Because libsodium never guaranteed stable validation criteria, and changed behavior in a later point release, zcashd was forced to use an older version before eventually patching a newer version. This meant that Zebra, the Zcash Foundation’s Zcash implementation had to implement ed25519-zebra, a library attempting to match libsodium 1.0.15 exactly. And the initial implementation of ed25519-zebra was also incompatible because it precisely matched the wrong compile-time configuration of libsodium. Instead of attempting to replicate implementation-defined behavior, a better solution would be to select a precise set of validation criteria. There are two basic choices which determine the resulting validation criteria. Selecting precise criteria Should the validation criteria allow batch verification, or not? In order to allow batch verification, batch and single verification must always agree, which means that single verification must use the batch equation, rather than the unbatched equation. The only downside of using the batch equation for single verification is that it requires an additional 3 doublings to compute the multiplication by 8. This costs a bit more than 1000 Skylake cycles, or about 1-2% of the total cost of a single verification. The upside is that batch verification can provide a speedup of 2x or more. Should the validation criteria be backwards-compatible, or not? Most existing implementations don’t require canonically-encoded points. If every signature that was considered valid by an existing implementation is considered valid under the new rules, an implementation of the new rules can be used in place of an existing implementation. On the other hand, if the new rules are more strict than the previous ones, it might be possible for someone to insert a signature valid under the old rules and not the new ones, which could cause unexpected breakage. There’s no downside and no security impact to allowing non-canonical point encodings because this choice only affects signatures created with specially crafted verification keys. Honest participants generate their signing and verification keys according to the protocol and are unaffected either way. The ZIP215 rules To fix this problem in Zcash, we chose to support both batch verification and backwards compatibility. The resulting rules are specified in ZIP215, scheduled to activate as part of the Zcash Heartwood network upgrade, implemented in Rust in ed25519-zebra’s 2.x series, and implemented in Go in a new ed25519consensus library. Although this work was motivated by the problem in Zcash, the same risk exists in other projects. For instance, Tendermint uses Go’s crypto/ed25519, which means that any future consensus implementations, such as tendermint-rs need to carefully consider and mitigate the risk of consensus incompatibilities, and interoperability mechanisms like IBC that are likely to have multiple implementations need to specify precise validation criteria. In either case, upgrading to the ZIP215 rules may be helpful.

To consider.

  1. Keep ed25519: ed25519 is used in Go https://docs.tendermint.com/v0.34/ and Rust https://archive.ph/o/o1xh6/https://github.com/informalsystems/tendermint-rs/issues/355
  2. Move to ECDH - While Curve25519 supports Diffie-Helman–which you will find called X25519–it is not specified to support signatures.
  3. Move to ed448 (I am not sure it may have the same signature validity consensus inconsistency as ed25519)

Discussion is required.

bartossh commented 1 year ago

Batched signature verification: Will leave it here: https://link.springer.com/chapter/10.1007/978-3-642-37682-5_30

bartossh commented 1 year ago

https://eprint.iacr.org/2020/823

bartossh commented 1 year ago

https://eprint.iacr.org/2016/191

bartossh commented 1 year ago

https://c.cdyn.dev/dQqu_IJ3 <- The Provable Security of Ed25519: Theory and Practice

bartossh commented 1 year ago

Long story short:

bartossh commented 1 year ago

Based on the current findings there are no vulnerabilities of edDSA that are not present in ecDSA. Usage of ed25519 improves the speed and security of key size in comparison with ecDSA. So I am closing this investigation. We shall stick to the ed25519 as we are from the production release and wallet offers signing and validation as a facade abstraction that can be refactored later.