crypto: document that GenerateKey functions are not deterministic

[FiloSottile]

In Go 1.20 we finally made crypto/ecdsa.GenerateKey call MaybeReadByte, so that now all GenerateKey implementation are non-deterministic, avoiding applications relying on the internals of our implementation, which would stop us from ever changing them. We should document this.

[n2vi]

This change seems to have broken user recovery of lost keys in Upspin (https://upspin.io/doc/faq.md#lost-key) and I'm trying to figure out the best way to keep our app's promise. Any suggestions?

By the way, I'm not the only developer that misunderstood the intent of
func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error)
having the caller supply rand for determinism; for example, see https://www.reddit.com/r/golang/comments/12ynmw2/why_did_ecdsageneratekey_stopped_being/
so making this documentation change will be well worthwhile. Also, I'm not against changing future apps or rewriting current apps that aren't committed to already archived seeds, but at first look I don't see a way out of calling ecdsa_legacy.go's generateLegacy() for Upspin key recovery.

Upspin's design and implementation did pass review by Google's AppSec and ISE teams at the time and this key recovery design was not a buried detail, so I conjecture other applications may discover a similar catastrophic problem in the future. I'd like to document the best solution here to save their app users from panic. It doesn't need to be high performance or constant-time, just a rarely used standalone compatibility tool, ideally fitting into the rest of your work as well as possible.

(By the way, thanks very much for your Go 1.20 cryptography changes!)

[n2vi]

A few more points not evident from the quoted Upspin doc:

1. My thinking when designing this lost key recovery back in 2014 was that we would soon move to post-quantum-cryptography and the expected longer key lengths would preclude ordinary users being willing to copy a full key to and from paper. But a 128-bit-entropy seed for a DRNG is feasible, so if we had deterministic key generation we'd still be good.
2. No Upspin user has yet complained "OMG all my data is lost!", perhaps because lost key recovery is only one of several layers of backup. I imagine most users have the full binary *.upspinkey files on several devices and might also have used the upsync command to save their data even if Upspin goes away entirely. One never knows when a project may get cancelled at the whim of executives current or retired.
3. It is somewhat premature for me to comment here because I have not finished researching the issue myself. For all I know, the non-determinism is not only due to recent crypto changes but also affected by something else. But given the "Go 1.21 Milestone" label, I wanted to point out these extra considerations before an irrevocable decision is made.

[FiloSottile]

Thank you for the feedback and sorry for the churn.

Deterministic key generation absolutely has its place, and is a reasonable design to adopt in your case. However, relying on Hyrum's Law and the unspecified behavior exposed by an implementation is problematic. If you need the same input to always produce the same output, you want a precise specification and test vectors. Kinda surprisingly, the cryptography community has not produced that yet for deterministic key generation. (I do plan to try to fix that at some point.)

Still, this was not a change made out of ideological purity. The other issue with relying on the implementation details of GenerateKey is that it ties our hands in making GenerateKey and its backend better. What happened in Go 1.20 (so that ship has sailed, we're just talking about documentation here) is that we rewrote the backend to be constant time and safer, and a different key generation strategy became a much better choice. (Rejection sampling doesn't require a wide reduction, which we didn't have to implement in the new backend. There are alternatives but they add complexity.)

By the way, I regret GenerateKey taking an io.Reader at all. There is no correct answer for what to pass to it except crypto/rand.Reader.

It doesn't need to be high performance or constant-time, just a rarely used standalone compatibility tool, ideally fitting into the rest of your work as well as possible.

I do have that for you though! https://pkg.go.dev/filippo.io/keygen#ECDSALegacy is Go 1.19's GenerateKey, implemented in non-constant time, just like it was in Go 1.19. (Note that timing side channels rarely matter for key generation, as a single observation is not enough to leak significant parts of the key, except when doing deterministic key generation. For your use case you should be fine, because it's a recovery path, but it was important to make GenerateKey constant time especially if it was being used deterministically.)

I am always reticent to point to my own third-party package in official docs, but is there some place I could have linked that which would have helped you find it?

[n2vi]

Thank you, excellent answer!

I would have voted to remove the io.Reader parameter as the clearest fix, but I understand why you were reluctant.

Happy to use your ECDSALegacy while waiting for an eventual deterministic key generation in the standard library. Also, thanks for linking here from the reddit discussion.

[gopherbot]

Change https://go.dev/cl/505155 mentions this issue: crypto: document non-determinism of GenerateKey

[n2vi]

in case it helps anyone else coming here in the future:
For my application, it turned out ECDSALegacy wasn't compatible but copying a few lines from Go 1.19 did the job.
https://upspin-review.googlesource.com/c/upspin/+/19841
I'm not advocating that as secure, just that it maintains compatibility and is not too insecure as used in my application.

[FiloSottile]

For my application, it turned out ECDSALegacy wasn't compatible

Can I ask you for any details on this? I have tests comparing it to Go 1.19's GenerateKey and they are passing, but there could definitely be a bug somewhere.

[n2vi]

Sure, the difference is in randFieldElement. The "compatible one" that I'm using is:

> // randFieldElement returns a random element of the order of the given
> // curve using the procedure given in FIPS 186-4, Appendix B.5.1.
> func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) {
> 	params := c.Params()
> 	// Note that for P-521 this will actually be 63 bits more than the order, as
> 	// division rounds down, but the extra bit is inconsequential.
> 	b := make([]byte, params.N.BitLen()/8+8)
> 	_, err = io.ReadFull(rand, b)
> 	if err != nil {
> 		return
> 	}
> 
> 	k = new(big.Int).SetBytes(b)
> 	n := new(big.Int).Sub(params.N, one)
> 	k.Mod(k, n)
> 	k.Add(k, one)
> 	return
> }
> 

whereas the one you're perhaps checking against from ecdsa_legacy.go is:

> // randFieldElement returns a random element of the order of the given
> // curve using the procedure given in FIPS 186-4, Appendix B.5.2.
> func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) {
> 	// See randomPoint for notes on the algorithm. This has to match, or s390x
> 	// signatures will come out different from other architectures, which will
> 	// break TLS recorded tests.
> 	for {
> 		N := c.Params().N
> 		b := make([]byte, (N.BitLen()+7)/8)
> 		if _, err = io.ReadFull(rand, b); err != nil {
> 			return
> 		}
> 		if excess := len(b)*8 - N.BitLen(); excess > 0 {
> 			b[0] >>= excess
> 		}
> 		k = new(big.Int).SetBytes(b)
> 		if k.Sign() != 0 && k.Cmp(N) < 0 {
> 			return
> 		}
> 	}
> }
> 

There are various things one could be "compatible" with, so I'm not asking for any changes in ECDSALegacy but only recording for anyone else in my situation that this is what I needed to do so that Upspin's keygen_test.go would pass, and users' old secretseeds would continue to create the same keys as from years ago.

[FiloSottile]

Hmm, no, ECDSALegacy implements the first algorithm you excerpted

https://github.com/FiloSottile/keygen/blob/5201437acf8ef20c6d0f118780cdd79847bae520/ecdsa.go#L88-L92

and it's tested against Go 1.19 in GitHub Actions

https://github.com/FiloSottile/keygen/blob/5201437acf8ef20c6d0f118780cdd79847bae520/ecdsa_test.go#L34-L39

ECDSALegacy is meant to and documented to be compatible with Go 1.19, that's what it's for, so if it didn't work for you I'd like to know more about how.

[n2vi]

I'm traveling and don't have all my notes with me, but have rewritten the test and confirm ECDSALegacy is working fine for me now. Not sure what I got wrong before, sorry.