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

GenerateSecp256k1 doesn't use the provided random reader source. #2791

Open
jsimnz opened this issue May 15, 2024 · 15 comments
Open

GenerateSecp256k1 doesn't use the provided random reader source. #2791

jsimnz opened this issue May 15, 2024 · 15 comments

Comments

@jsimnz
Copy link

jsimnz commented May 15, 2024

Based on the latest version (33.2).

Currently the GenerateSecp256k1Key(src io.Reader) accepts a io.Reader parameter to use as its source of random ness to generate the new key, however it doesn't actually use the provided reader, and instead uses the default random reader within the secp256k1 package.

However, the underlying cryptographic package does support using a provided source of randomness as seen here.

@Stebalien
Copy link
Member

This should probably be documented, but likely isn't going to be fixed.

@jsimnz
Copy link
Author

jsimnz commented May 23, 2024

Why do you feel it shouldn't be fixed? The function takes in an argument that doesn't do anything.

Additionally, the equivalent function in the crypto package for generating Ed25519 keys which has the same io.Reader argument which is actually used if supplied.

So it's inconsistent behavior between equivalent functions?

@MarcoPolo
Copy link
Collaborator

Seems like a reasonable request. feel free to open a PR and I can review.

@Stebalien am I missing some reason for why we shouldn't fix this?

@Stebalien
Copy link
Member

Ah, I didn't realize decred actually provided a way to do this.

My response comes from the fact that:

  1. While the go standard library takes a random source when generating private keys, it intentionally (and randomly) reads a few bytes from the source before generating the key to prevent users from relying on this for deterministic key generation (turned out to be a compatibility footgun).
  2. The library we just switched to in Filecoin doesn't even provide a way to specify a random source.

I agree that taking an argument that doesn't do anything isn't great, but I expect it's that way for historical reasons (i.e., from before the switch to decred). But... we probably shouldn't have taken a random source in the first place.

  • If you don't trust crypto.Rand, any crypto you do will likely be broken.
  • As noted above, it's a compatibility footgun.

@jsimnz
Copy link
Author

jsimnz commented May 23, 2024

I can certainly open a PR as I have a branch I'm using for this.

@Stebalien at least from my POV it's not about trusting crypto.Rand, but intentionally wanting deterministic keys for certain testing scenarios.

It should be also noted that some of the standard lib crypto libs (eg ecdsa) has specific behavior for supplied io.Reader for Generate functions.

Specifically

This does not affect tests that pass a stream of fixed bytes as the random source (e.g. a zeroReader).

My only preference for the libp2p crypto pkg is to be consistent with itself. If that means support the supplied io.Reader for the secp256k1 funcs, awesome, and I'll open a PR ASAP.

Lmk

@Stebalien
Copy link
Member

but intentionally wanting deterministic keys for certain testing scenarios.

My point is that this behavior, unfortunately, is hard to rely on. E.g., see the comment on GenerateKey in https://pkg.go.dev/crypto/ecdh#Curve.

There's no reason not to fix it in go-libp2p given that it's easy, but you'll likely feel the pain somewhere down the line when this breaks.

@MarcoPolo
Copy link
Collaborator

I'm fine doing the same thing as the Go stdlib's practice of maybeReadByte

@jsimnz
Copy link
Author

jsimnz commented May 27, 2024

Just want to add that currently the libp2p crypto generation of Ed25519 keys, which uses crypto/ed25519 under the hood. However, the crypto/ed25519.GenerateKey which also takes in a rand io.Reader and does a raw full 32 byte read, without any of the maybeReadByte semantics from the other go standard lib crypto packages.

It has the following note:

// The output of this function is deterministic, and equivalent to reading
// [SeedSize] bytes from rand, and passing them to [NewKeyFromSeed].

So the question becomes, do we want equivalent behavior for both libp2p generate ed25519 & secp256k1 keys, or make the change now only for secp256k1 to use maybeReadByte as @MarcoPolo suggested, and leave the ed25519 unchanged?

@MarcoPolo
Copy link
Collaborator

Thinking about this a bit more, I don't think we should be deciding what to do with the reader. We aren't the crypto library and don't have the context on whether it makes sense to use the reader as is or not. I think we should just forward the call to the underlying library.

@Stebalien
Copy link
Member

We don't have to read the extra byte, but I also don't want to make any guarantees. Otherwise, it becomes hard to change the underlying secp256k1 library.

E.g., in Filecoin we're looking into switching to https://gitlab.com/yawning/secp256k1-voi which doesn't even support reading from a user-specified random source.

@jsimnz
Copy link
Author

jsimnz commented May 29, 2024

https://gitlab.com/yawning/secp256k1-voi which doesn't even support reading from a user-specified random source

In this example, the library doesn't specify it because its a lower level utility, the dcrec/secp256k1 and the crypto/ed25519 provide higher level functions that take in a io.Reader, but the outcome is the same. The private key is a function of a point on a curve multiplied by some scalar, where the point is the "generator" and the scalar is the "seed", and the seed is some random slice of bytes clamped with a hashing func.

So from the libp2p/crypto POV it would just do the higher level "read bytes from io.Reader and produce a clamped seed".

I think for the sake of compatibility it makes more sense to provide guarantees so that you can swap the underlying crypto package and not break things, regardless of what that guarantee is (either deterministic or not). Any low level elliptic curve package that deals with points and scalars behave the same, since its just (elliptic) arithmetic. Its up to you guys to determine how to "generate private keys" from said arithmetic.

Again, happy to implement and open a PR for either direction.

@MarcoPolo
Copy link
Collaborator

We don't have to read the extra byte, but I also don't want to make any guarantees. Otherwise, it becomes hard to change the underlying secp256k1 library.

Agreed on not making any future guarantees on determinism. We may decide to switch to a library that doesn't even take a reader and that should be fine.

For tests, maybe it makes sense to use a fixed key rather than a fixed seed? It's not as elegant, but we can and will guarantee a key will always behave the same for a given cipher.

My suggestion would be for us to simply forward the arguments and not add our opinion to what the underlying crypto library does. As well as update the doc comment to assert that we make no guarantees on determinism of the key generation between go-libp2p versions.

That might mean it doesn't server your use case @jsimnz of using a seed to deterministically generate keys, but that would break if we ever switch to a library that doesn't support an io.Reader or doesn't support deterministic generation of keys (which some do in an attempt to be foolproof). Would using a fixed key instead (as suggested earlier in my comment) help?

@Yawning
Copy link

Yawning commented Jun 29, 2024

In this example, the library doesn't specify it because its a lower level utility

It does not provide such a method because the absolutely overwhelming majority of the time, the system cryptographic entropy source is the right answer and the API is intentionally opinionated to try to minimize foot+guns.

There are escape hatches in the secec API so that if such a thing is desired, something like this (nb: dry-coded) is possible (which is what GenerateKey does, but with a fixed reader):

const MaxRetries = 3 // nb: Generate key uses 8.  Any small number is fine.

var ErrMaxRetries = errors.New("secp256k1: retries exhausted, broken rng?")

func PrivateKeyFromRand(rng io.Reader) (*secec.PrivateKey, error) {
  var (
    sc secp256k1.Scalar
    buf [secp256k1.ScalarSize]byte
  )

  // Note: In theory it is possible that multiple attempts are required.  In practice, the probability
  // is insignificant enough to be "will probably never happen".
  for i := 0; i < MaxRetries; i++ {
    // Sample random bytes from the provided entropy source.
    if _, err := io.ReadFull(rng, buf[:]); err != nil {
     return nil, fmt.Errorf("secp256k1: rng failure: %w", err)
    }

    // Ensure that the scalar is in the range [1, n).
    _, didReduce := sc.SetBytes(&buf)
    if didReduce == 0 && sc.IsZero() == 0 {
      // sc is a secp256k1 scalar in the range `[1, n)`.
      return secec.NewPrivateKeyFromScalar(&sc)
    }
  }
  return nil, ErrMaxRetries
}

The output (from skimming the other implementation) will be identical to the dcrd package, except in the "unlikely but theoretically possible" case where more than MaxRetries samples are required to produce a valid key, since the other library does not give up.

ps: "clamping" is Ed25519 specific.

@jsimnz
Copy link
Author

jsimnz commented Jun 29, 2024

It does not provide such a method because the absolutely overwhelming majority of the time, the system cryptographic entropy source is the right answer and the API is intentionally opinionated to try to minimize foot+guns.

Apologies, was only referencing the root package there, which only contained the EC arithmetic code. Didn't realize @Stebalien may have been referencing the high-level API in the sub package. Which as you point out doesn't accept a reader on the Generate func.

@Yawning
Copy link

Yawning commented Jun 29, 2024

It does not provide such a method because the absolutely overwhelming majority of the time, the system cryptographic entropy source is the right answer and the API is intentionally opinionated to try to minimize foot+guns.

Apologies, was only referencing the root package there, which only contained the EC arithmetic code. Didn't realize @Stebalien may have been referencing the high-level API in the sub package. Which as you point out doesn't accept a reader on the Generate func.

No worries, the secp256k1-voi API is rather opinionated throughout.

I currently do not currently provide a wide-reduction method for a scalar (though it would be easy to add, or implement on top of the existing Scalar API). Given such a routine, for a Ed25519-esque seed, it would be possible to do something like:

  • Generate a 512-bit scalar, s (eg: SHA-512(seed) (or better yet, something domain separated))
  • Reduce s, modulo the curve order
  • FAIL if s == 0 (or rehash etc)
  • NewPrivateKeyFromScalar(s)

However the algorithm would be non-standard (eg: BIP-32 opts for rejection sampling of a 256-bit scalar instead of doing a wide-reduction).

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

No branches or pull requests

4 participants