Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

#264 restircted fuzz coverage due to conversion to real private -> public key conversion #271

Closed
TheBlueMatt opened this issue Jan 15, 2021 · 6 comments · Fixed by #282
Closed

Comments

@TheBlueMatt
Copy link
Member

Sorry for the late comments on this one, but #264 is somewhat less appealing than the previous version at least in rust-lightning. Specifically, in our "lol just shove the whole library into the fuzzer" target, we want to be able to do state revocation by revealing the private key corresponding to a previously-provided public key. Obviously this would imply a real cryptographic operation on 32 bytes for the fuzzer to guess, which isn't possible. How important is it that all the tests pass in fuzz mode, and can we swap the private->public conversion to something more dummy, eg xor or simply map them 1:1?

@apoelstra
Copy link
Member

So, the issue is that these unit tests reflect assumptions that are needed in real code. In particular, that if I do a BIP32 derivation on a series of secret keys, and sign with the result, that it will be verifiable by somebody who did the "same" derivation using the public keys.

I think we were able to get away with having an inconsistent pubkey derivation scheme for so long because

  • rust-bitcoin had no fuzztests that depended on this
  • rust-lighting had no fuzztests
  • nobody but you and I had a clear idea of what the "fuzztest" target was for, so if anyone else was fuzzing at all, they were doing so using the real crypto

Now that we are using the fuzzing config flag rather than doing our own custom cargo-flag thing, I expect other people who depend on this lib, and who fuzz their stuff, to run into problems.

As a secondary thing, the more tests we can get to pass with the fuzztarget on, the more assuredness we have that we haven't badly broken it. For example, before the recent fuzz changes, elichai and I had totally broken context creation with fuzztarget on with our alignment-munging stuff, and we didn't notice (though we would've noticed immediately as soon as there was a release and you came down on us :)).

@apoelstra
Copy link
Member

There are a few options for how to move forward:

  1. Do some dumb xor thing that isn't really consistent (but which we can make consistent with signing at least), and wait for people to file bugs because they hit "impossible" assertions when fuzzing.
  2. Rewrite the whole fuzz harness to use a broken xor-y group, but make it actually be a group
  3. Revisit using the order-17 group -- I have some ideas here which are a bit of a PITA but not nearly as much as creating a whole new group.

@TheBlueMatt
Copy link
Member Author

TheBlueMatt commented Jan 15, 2021 via email

@apoelstra
Copy link
Member

As for (2), I want the following things to hold:

  • if you use seckey_tweak_mul then pubkey_create, or pubkey_create then pubkey_tweak_mul, you get the same result
  • ditto for the _add functions
  • ditto for the xonly variants of the above two
  • if you ECDSA sign with a seckey, then use pubkey_create and verify the resulting sig, it should pass
  • ditto for schnorr signatures
  • ditto for recoverable signatures
  • if you start with two secret keys, and turn either one of them into a pubkey with pubkey_create, then do ECDH with the resulting (secret, public) pair, you get the same result

Unfortunately this is a really long list now.

@TheBlueMatt
Copy link
Member Author

TheBlueMatt commented Jan 15, 2021 via email

@apoelstra
Copy link
Member

You can, though it has the minor drawback of eliminating the "half of all pubkeys are invalid even though almost no secret keys are invalid" property. But you still have to re-implement basically the entire library in terms of that.

TheBlueMatt added a commit to TheBlueMatt/rust-secp256k1 that referenced this issue Feb 18, 2021
This reduces the usage of real cryptography in --cfg=fuzzing,
specifically replacing the secret->public key derivation with a
simple copy and ECDH with XOR of the public and private parts
(plus a stream of 1s to make a test pass that expected non-0
output).

It leaves secret tweak addition/multiplication as-is.

It also changes the context creation to over-allocate and store
the context flags at the end of the context buffer, allowing us
to easily test context flags in each function.

While it would be nice to have something fancier (eg XOR-based),
its not immediately obvious how to accomplish this, and better to
fix the issues I have than spend too much time on it.

Fixes rust-bitcoin#271.

This partially reverts b811ec1
TheBlueMatt added a commit to TheBlueMatt/rust-secp256k1 that referenced this issue Feb 18, 2021
This reduces the usage of real cryptography in --cfg=fuzzing,
specifically replacing the secret->public key derivation with a
simple copy and ECDH with XOR of the public and private parts
(plus a stream of 1s to make a test pass that expected non-0
output).

It leaves secret tweak addition/multiplication as-is.

It also changes the context creation to over-allocate and store
the context flags at the end of the context buffer, allowing us
to easily test context flags in each function.

While it would be nice to have something fancier (eg XOR-based),
its not immediately obvious how to accomplish this, and better to
fix the issues I have than spend too much time on it.

Fixes rust-bitcoin#271.

This partially reverts b811ec1
TheBlueMatt added a commit to TheBlueMatt/rust-secp256k1 that referenced this issue Feb 18, 2021
This reduces the usage of real cryptography in --cfg=fuzzing,
specifically replacing the secret->public key derivation with a
simple copy and ECDH with XOR of the public and private parts
(plus a stream of 1s to make a test pass that expected non-0
output).

It leaves secret tweak addition/multiplication as-is.

It also changes the context creation to over-allocate and store
the context flags at the end of the context buffer, allowing us
to easily test context flags in each function.

While it would be nice to have something fancier (eg XOR-based),
its not immediately obvious how to accomplish this, and better to
fix the issues I have than spend too much time on it.

Fixes rust-bitcoin#271.

This partially reverts b811ec1
TheBlueMatt added a commit to TheBlueMatt/rust-secp256k1 that referenced this issue Mar 9, 2021
This reduces the usage of real cryptography in --cfg=fuzzing,
specifically replacing the secret->public key derivation with a
simple copy and ECDH with XOR of the public and private parts
(plus a stream of 1s to make a test pass that expected non-0
output).

It leaves secret tweak addition/multiplication as-is.

It also changes the context creation to over-allocate and store
the context flags at the end of the context buffer, allowing us
to easily test context flags in each function.

While it would be nice to have something fancier (eg XOR-based),
its not immediately obvious how to accomplish this, and better to
fix the issues I have than spend too much time on it.

Fixes rust-bitcoin#271.

This partially reverts b811ec1
TheBlueMatt added a commit to TheBlueMatt/rust-secp256k1 that referenced this issue Mar 18, 2021
This reduces the usage of real cryptography in --cfg=fuzzing,
specifically replacing the secret->public key derivation with a
simple copy and ECDH with XOR of the public and private parts
(plus a stream of 1s to make a test pass that expected non-0
output).

It leaves secret tweak addition/multiplication as-is.

It also changes the context creation to over-allocate and store
the context flags at the end of the context buffer, allowing us
to easily test context flags in each function.

While it would be nice to have something fancier (eg XOR-based),
its not immediately obvious how to accomplish this, and better to
fix the issues I have than spend too much time on it.

Fixes rust-bitcoin#271.

This partially reverts b811ec1
TheBlueMatt added a commit to TheBlueMatt/rust-secp256k1 that referenced this issue Apr 7, 2021
This reduces the usage of real cryptography in --cfg=fuzzing,
specifically replacing the secret->public key derivation with a
simple copy and ECDH with XOR of the public and private parts
(plus a stream of 1s to make a test pass that expected non-0
output).

It leaves secret tweak addition/multiplication as-is.

It also changes the context creation to over-allocate and store
the context flags at the end of the context buffer, allowing us
to easily test context flags in each function.

While it would be nice to have something fancier (eg XOR-based),
its not immediately obvious how to accomplish this, and better to
fix the issues I have than spend too much time on it.

Fixes rust-bitcoin#271.

This partially reverts b811ec1
TheBlueMatt added a commit to TheBlueMatt/rust-secp256k1 that referenced this issue Apr 28, 2021
This reduces the usage of real cryptography in --cfg=fuzzing,
specifically replacing the secret->public key derivation with a
simple copy and ECDH with XOR of the public and private parts
(plus a stream of 1s to make a test pass that expected non-0
output).

It leaves secret tweak addition/multiplication as-is.

It also changes the context creation to over-allocate and store
the context flags at the end of the context buffer, allowing us
to easily test context flags in each function.

While it would be nice to have something fancier (eg XOR-based),
its not immediately obvious how to accomplish this, and better to
fix the issues I have than spend too much time on it.

Fixes rust-bitcoin#271.

This partially reverts b811ec1
TheBlueMatt added a commit to TheBlueMatt/rust-secp256k1 that referenced this issue May 3, 2021
This reduces the usage of real cryptography in --cfg=fuzzing,
specifically replacing the secret->public key derivation with a
simple copy and ECDH with XOR of the public and private parts
(plus a stream of 1s to make a test pass that expected non-0
output).

It leaves secret tweak addition/multiplication as-is.

It also changes the context creation to over-allocate and store
the context flags at the end of the context buffer, allowing us
to easily test context flags in each function.

While it would be nice to have something fancier (eg XOR-based),
its not immediately obvious how to accomplish this, and better to
fix the issues I have than spend too much time on it.

Fixes rust-bitcoin#271.

This partially reverts b811ec1
TheBlueMatt added a commit to TheBlueMatt/rust-secp256k1 that referenced this issue Jun 8, 2021
This reduces the usage of real cryptography in --cfg=fuzzing,
specifically replacing the secret->public key derivation with a
simple copy and ECDH with XOR of the public and private parts
(plus a stream of 1s to make a test pass that expected non-0
output).

It leaves secret tweak addition/multiplication as-is.

It also changes the context creation to over-allocate and store
the context flags at the end of the context buffer, allowing us
to easily test context flags in each function.

While it would be nice to have something fancier (eg XOR-based),
its not immediately obvious how to accomplish this, and better to
fix the issues I have than spend too much time on it.

Fixes rust-bitcoin#271.

This partially reverts b811ec1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants