New ECDSA API without prehashed messages

[paulmillr]

Hey folks,

ECDSA verify

secp256k1/src/ecdsa_impl.h

Line 207 in 1e5d50f

static int secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context *ctx, const secp256k1_scalar *sigr, const secp256k1_scalar *sigs, const secp256k1_ge *pubkey, const secp256k1_scalar *message) {

secp256k1/src/scalar_4x64_impl.h

Line 559 in 1e5d50f

static void secp256k1_scalar_mul_512(uint64_t l[8], const secp256k1_scalar *a, const secp256k1_scalar *b) {

accepts all-zero hash aka (0, 0, 0 ....). Is this a valid behavior? Seems like it could enable fault attacks. The algorithm is as follows, as per https://www.secg.org/sec1-v2.pdf 4.1.4:

1. u1 = es^−1 mod n and u2 = rs^−1 mod n
2. R = (xR, yR) = u1 * G + u2 * Q * U
3. e == 0, then u1 == 0, then u1 * G is invalid because you cannot multiply G by 0

[real-or-random]

3. `e == 0`, then `u1 == 0`, then `u1 * G` is invalid because you cannot multiply G by 0

Sure you can multiply G by 0.
0*G is the point at infinity.

[paulmillr]

Which is invalid point.

[elichai]

Upstream allows it because in Bitcoin Core's use there is no way to get an all-0s hash (though there almost was, and this would've made coins trivial to steal), and preventing this would greatly complicate the C API.

by @apoelstra from rust-bitcoin/rust-secp256k1#207 (comment) ("upstream" refers to this library)

[paulmillr]

@elichai

As for "no way to get 0": libsecp is used everywhere. Someone will pass all-0 forged hashes which were not generated with sha256.

As for "complicate": just check if the scalar is 0 and early-return false.

[real-or-random]

Which is invalid point.

"invalid" according to what definition? It's a perfectly valid secp256k1_ge. What's the attack you have in mind?

[sipa]

No, we're not going to change this.

1. It violates the spec. It says nothing about rejecting hash=0, or why the point at infinity would be invalid as an intermediary result. It is invalid as a public key, but that doesn't apply here.
2. It shouldn't matter. The hash has to be a hash in correct usage, and thus it won't ever be 0 (as that implies mounting a succesful preimage attack first).

[paulmillr]

@sipa so, do all ed25519 libraries violate its spec? By being more strict on signature malleability?

[sipa]

ed25519 is not ECDSA. I also don't see what this has to do with malleability. The libsecp256k1 API requires passing in the hash of the message. The probability that that hash is 0, is negligible.

You could argue that this is unsafe API design, and that libsecp256k1 should do the hashing for you, if you're concerned about someone using the API incorrectly. That'd be a reasonable point, but the solution isn't deviating from the spec.

You can also argue that the ECDSA spec is unsafe by permitting 0 (though I still don't see the actual attack). If that's the case, I'm afraid it is too late, as that's a discussion you should have had with the SECG when they wrote the spec.

[paulmillr]

@sipa I was talking about ed25519 as an example. See this blog post: https://hdevalence.ca/blog/2020-10-04-its-25519am
RFC8032 is not strict enough and it's pretty bad. Different implementations of ed25519 have different behavior in regard to strictness. So they all deviate from spec? But it's fine for ed25519, why it isn't ok for secp?

Yes, your thinking here matches mine -- it's unsafe API design, and since libsecp is embedded everywhere, in every language, someone will use the api incorrectly.

My point here is that it's probably the only public api part that allows user input to produce point at infinity. Has there been extensive testing done for this case? What about timing discrepancies?

[sipa]

So they all deviate from spec? But it's fine for ed25519, why it isn't ok for secp?

This library is explicitly designed for consensus-critical applications, where exact behavior is paramount. Deviations can cause forks. I don't think that this change in particular would risk that, but still - I see absolutely no reason for deviating from (a) existing behavior and (b) the specification. The fact that ed25519 implementations differ in their behavior around edge cases is a problem for some of its use cases too.

and it's pretty bad.

Yes indeed. No reason to taking a bad approach because others do it too.

Yes, your thinking here matches mine -- it's unsafe API design, and since libsecp is embedded everywhere, in every language, someone will use the api incorrectly.

Then the solution is changing the API to accept the full unhashed message, and performing the hashing inside the API. Not changing behavior by deviating from the spec.

My point here is that it's probably the only public api part that allows user input to produce point at infinity.

There are definitely other ways, like secp256k1_ec_combine with two complementary public keys, will cause a point at infinity to be computed internally.

Also, in the actual implementation, the msghash=0 case won't actually construct the point at infinity in general. The u1G + u2Q sum of multiplications is computed in a single operation, which doesn't actually evaluate both multiplications individually.

Has there been extensive testing done for this case?

Adding the condition you suggest (failing verification if msghash=0) will cause our current tests to fail.

What about timing discrepancies?

This is a verification operation, where constant-timeness isn't a concern (there is no secret data involved that could be leaked).

[real-or-random]

Yes, your thinking here matches mine -- it's unsafe API design, and since libsecp is embedded everywhere, in every language, someone will use the api incorrectly.

Yeah, the API is not optimal. I don't think we'll change the API but we could add another cleaner API for ECDSA. I think that's a good idea. But we'll need someone to work on it.

My point here is that it's probably the only public api part that allows user input to produce point at infinity.

That's not true. A lot of computations start with accumulator initialized with the point at infinity, just because it's zero in the group.

Has there been extensive testing done for this case?

Yes.

What about timing discrepancies?

Verification does not involve secrets, so this is not an issue. For secret computations, we have constant-time code that protect secrets.

Of course there can be bugs, but shooting random questions in the dark here isn't really helpful.

[paulmillr]

Ed25519 is also used in consensus-critical applications, but I see your point. We can close this if you don't see the value I guess 🤷‍♂️

[real-or-random]

Ed25519 is also used in consensus-critical applications, but I see your point. We can close this if you don't see the value I guess man_shrugging

Let's leave it open as a reminder that we should change the API. (Allow me to update the title.) For historical context, one goal of the library was not to depend on SHA256 explicitly, so that's why an API with prehashed messages was chosen. Now we support two primitives that anyway depend on SHA256 (Schnorr sigs with a better API, no prehashed message) and ECDH with SHA256 in the code. So we're anyway committed to having SHA256 in the repo, and then we can design a better ECDSA API.

[sipa]

Note that Bitcoin's consensus rules rely on being able to set msghash=1 for pre-segwit transactions with SIGHASH_SINGLE set, for a txin index that doesn't have a corresponding txout index. That's dumb, and makes it insecure to use, but for better or worse it's part of the consensus rules, so at least that code path requires that an API with prehashed messages remains available.

[paulmillr]

After the api is live, I suggest to add a simple source code comment for all future maintainers and implementers who will want to rewrite the library in a different language; that signifies the need for the old api& risks.