search

lithdew / ed25519-donna-zig

Minimal Zig bindings to ed25519-donna.
1 stars 0 forks source link

ed25519-donna's batch verification is unsafe #1

Open Yawning opened 3 years ago

Yawning commented 3 years ago

This is an issue that this package is inheriting from donna, but:

The simple solution to get correct and consistent behavior is to alter donna's single and batch verification routines to use the equations that include the cofactor multiply(s), but depending on how well you want your library to interoperate exactly with other implementations, this may not be feasible.

See section 3.2 of https://eprint.iacr.org/2020/1244.pdf for a more detailed explanation of the problem.

lithdew commented 3 years ago

Thanks for the report! Just finished reading Section 3.2 of the paper carefully, looked up issues related to signature malleability online, and concluded that it certainly is an issue to be worried about. For the time being, I'll look into putting up a warning on the readme of this repository.

Got a few questions out of curiosity though.

It seems that in Section 3.2, the paper states that the combined use of cofactored signature verification + cofactorless signature batch verification is plausible. Would you know if this implies that we can make use of the cofactorless signature batch verification implementation in ed25519-donna, and proceed to iteratively run all signatures in the input batch through the cofactored signature verification implementation in Zig's standard library if the batch verification algorithm reports a failure?

Another question I had is, might you have recommendations for other ed25519 implementations to write C bindings against that are performant and provide both cofactored and cofactorless signature verification and signature batch verification?

Yawning commented 3 years ago

Thanks for the report! Just finished reading Section 3.2 of the paper carefully, looked up issues related to signature malleability online, and concluded that it certainly is an issue to be worried about. For the time being, I'll look into putting up a warning on the readme of this repository.

No worries, I got burned by this a while ago when I was maintaining a fork of donna converted to Go). I fixed my fork, then got annoyed at everything and started the curve25519-voi project to solve the issue once and for all. The whole situation is a huge mess, especially if you need 100% consistent interoperability between different implementations.

Got a few questions out of curiosity though.

It seems that in Section 3.2, the paper states that the combined use of cofactored signature verification + cofactorless signature batch verification is plausible. Would you know if this implies that we can make use of the cofactorless signature batch verification implementation in ed25519-donna, and proceed to iteratively run all signatures in the input batch through the cofactored signature verification implementation in Zig's standard library if the batch verification algorithm reports a failure?

Assuming what you use as ground truth is cofactored single verification, and you're 100% sure that Zig's standard library is cofactored, then ~sure~ maybe.

EDIT: You need to patch donna because it accepts s > L, while I assume/hope the Zig standard library rejects such things. Alternatively, you could do the scalar canonicity check for each signature before calling the batch verification routine.

That said because donna's batch verification routine single-verifies (cofactorless) on failure already, both false negatives and actual verification failures will be extra expensive since you are stuck doing 2 signature verifications across the entire batch, which isn't great.

If you're wiling to patch donna anyway, I personally would (and have, before I gave up and wrote curve25519-voi) do something like:

This still leaves some inter-implementation incompatibility edge cases with how each implementation handles small-order A/R and non-canonical A/R, but I'm not sure how much those things matter for your use case.

Another question I had is, might you have recommendations for other ed25519 implementations to write C bindings against that are performant and provide both cofactored and cofactorless signature verification and signature batch verification?

In C? Not that I am aware of.

Personally (like many others), my view on the actual solution to this rat's nest of problems is "Just use Ristretto". But since that isn't an option for a lot of people, each project should standardize on one concrete project wide definition of ed25519 (out of say ZIP-215, FIPS 186-5 or Algorithm 2), but unfortunately ecosystem support is poor and language dependent.

lithdew commented 3 years ago

Personally (like many others), my view on the actual solution to this rat's nest of problems is "Just use Ristretto". But since that isn't an option for a lot of people, each project should standardize on one concrete project wide definition of ed25519 (out of say ZIP-215, FIPS 186-5 or Algorithm 2), but unfortunately ecosystem support is poor and language dependent.

Interesting :open_mouth:. In my case, using Ristretto definitely seems like a viable option as these ed25519-donna bindings were originally for a new project that I'm doing completely from scratch.

Looks like I can get started with Ristretto by writing Zig bindings to ristretto-donna which appears to be a patched-up version of ed25519-donna that uses the Ristretto curve, and releasing them in a separate repository. What do you think?

Yawning commented 3 years ago

It looks like Zig has support for the Ristretto255 group already (std::crypto::ecc::Ristretto255), though performance will approximately be the same as the standard library's ed25519 implementation.

The library you linked looks kind of old (though likely correct). However, the "defacto" algorithm for signing using Ristretto is w3f's schorrkel (aka sr25519), which is a bit more involved to implement if you just have curve operations because you need STROBE (based on keccac-f[1600]) and Merlin to do domain separation and delinearization.

See:

Unfortunately sr25519 is also under-documented/specified as well, so the path of least resistance would probably be to impose the semantics you want on ed25519-donna, unless calling code written in rust is easy and you can just use the w3f code.

Yawning commented 3 years ago

As a lightly tested example of how to make ed25519-donna behave correctly, see https://github.com/Yawning/ed25519-donna-cofactored

Verification semantics are probably still different from what the Zig stdlib does with respect to non-canonical/small-order points, but at least batch verification will be consistent with single verification, and S >= L will be rejected.