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

Jump to bottom

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

Closed
norbertvannobelen opened this issue Apr 20, 2020 · 4 comments
Closed

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

norbertvannobelen opened this issue Apr 20, 2020 · 4 comments
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone
Unplanned

Comments

@norbertvannobelen
Copy link

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 andybons changed the title RSA key generation is non-deterministic while RSA is deterministic in design crypto/rsa: RSA key generation is non-deterministic while RSA is deterministic in design Apr 21, 2020
@andybons
Copy link
Member

@katiehockman @FiloSottile

@andybons andybons added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Apr 21, 2020
@andybons andybons added this to the Unplanned milestone Apr 21, 2020
@FiloSottile
Copy link
Contributor

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
Copy link
Author

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
Copy link
Contributor

FiloSottile commented Apr 21, 2020 •
edited

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.

@acalatrava acalatrava mentioned this issue Sep 28, 2020
Closed
@golang golang locked and limited conversation to collaborators Apr 21, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
4 participants
@andybons @FiloSottile @gopherbot @norbertvannobelen