crypto/rsa: RSA key generation is non-deterministic while RSA is deterministic in design

[norbertvannobelen]

What version of Go are you using (go version)?

go version go1.13.4 darwin/amd64

Does this issue reproduce with the latest release?

Yes

What did you do?

Provide non-random input to rsa.GenerateKey (ie: A passkey phrase repeatable generated key algorithm)

		salt := "ABCDEF" + userEnteredCredential
		b := []byte(salt)
// Dummy key stretch
		maxLen := 4096
		b = append(b, make([]byte, maxLen-len(b))...)
		for i := len(salt); i < maxLen; i++ {
			b[i] = []byte(strconv.Itoa(i % maxLen))[0]
		}
		sr := bytes.NewReader(b)
		privateKey, err := rsa.GenerateKey(sr, 128)

What did you expect to see?

Based on the rsa algorithm definition and the input: The same key for the same input.

What did you see instead?

2 different keys.

Root cause analysis:

The package https://golang.org/src/crypto/rsa/rsa.go contains the following lines:

func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (*PrivateKey, error) {
	randutil.MaybeReadByte(random)

The line

randutil.MaybeReadByte(random)

actually flips a coin (bit) and can result in a 0 or 1.
When combined with random input, this behaviour would random (but the input is already random),
When combined with deterministic input, the algorithm becomes useless.

Suggestion is to remove the line randutil.MaybeReadByte(random) and leave the randomness to the input only.

Related issue #29290 mentions the reason in release 1.11.2 where tests were the root issue to change this (the here proposed to be removed line, was added). However a standard behaviour for the algorithm is I think better, and fixing the test to be such that it can rely on deterministic behaviour is probably better.

Also this "fix" is such that a test still has a 50% chance of just getting the same key on the second request, thus making the test reliability not per definition better (just more confusing).

[andybons]

@katiehockman @FiloSottile

[FiloSottile]

This was intentional because we don't want to commit to the specific algorithm, and we want to reserve the flexibility to change it from one release to the next, without applications coming to rely on it.

Is there a widespread interoperable specification (with, like, test vectors) that goes from a stream of random bytes to RSA keys? If so, we could consider implementing it, otherwise we don't want to establish a de-facto spec of "what Go does right now".

[norbertvannobelen]

To give more background by the request:

use case:

• Do not have a (rsa) key store which has to be secured by backups, is forever growing, and is harder to protect against hackers. Instead have a key (re-)generation algorithm which provides a secure deterministic key generation with a deterministic salt (for example: signup date+ email +secure salt), thus having to secure only 1 value (the secure salt).

In this context the current line randutil.MaybeReadByte(random) IMO now does two things:

1. In case of non random input, it flips the coin (0/1), and removes usability for the algorithm to have crypt keys per user/record (as sample use case above)
2. The randutil.MaybeReadByte(random) can give a false sense of security in case the developer did not provide a correct random seeded set: A too cursory inspection could just lead to the 0/1 case (so you see two different results) and assume your randomness was actually there, while in reality it was not => An actual test should show the lack of randomness as a problem

As with regards to the intention of the function:

• If the golang goal is that the developer can not rely on algorithm to be deterministic, then probably the rand.Reader should not be exposed (ie: the package fulfills all the functionalities and the interface is more limited). If the rand.Reader is made private, and managed by the package, the expectation of the developer is possibly more clear.

As for committing to the algorithm:

The produced key sets have to be compatible with rsa. The here requested rollback and different approach to the tests is with regards to the output. How the algorithm actually factors the rsa public/private key set is I think not influenced by this request

[FiloSottile]

Unfortunately the use case you describe is exactly what we don't want to support. If tomorrow we need to change the GenerateKey implementation, we don't want to cause your database of keys to become invalid.

For that use case, you should copy the GenerateKey source, so your copy will always be the same (and of course drop the MaybeReadByte).

Most randomness failures are not of the kind that cause outputs to always be the same. That would not even have detected the terribly broken Debian OpenSSL RNG.

I don't disagree that it would be even better if we did not accept a Reader for the randomness, but unfortunately some applications have opinions on their CSPRNGs.