Skip to content

crypto/rsa: reimplement GenerateKey per FIPS 186-5 with bigmod [freeze exception] #69799

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.

Sign up for GitHub

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
Closed
FiloSottile opened this issue Oct 7, 2024 · 10 comments
Closed

crypto/rsa: reimplement GenerateKey per FIPS 186-5 with bigmod [freeze exception] #69799

FiloSottile opened this issue Oct 7, 2024 · 10 comments
Labels
FixPending Issues that have a fix which has not yet been reviewed or submitted. NeedsFix The path to resolution is known, but the work has not been done.
Milestone
Go1.24

Comments

@FiloSottile
Copy link
Contributor

For #69536, we'll need rsa.GenerateKey to comply with FIPS 140-3 requirements. Moreover, we don't want to include math/big in the module boundary, so we'll need to reimplement it on top of crypto/internal/bigmod.

  • Need to comply with IG C.E, IG C.F, and FIPS 186-5
  • Should use the process in FIPS 186-5 A.1.1, A.1.3, B.3, B.3.2, and B.3.3
    • That is, we should run at least two (see IG C.F) Enhanced Miller-Rabin tests followed by a Lucas test
  • Key generation runs only once, so it's ok for it not to be constant time, if it significantly reduces complexity
  • For it to be testable, the process should draw non-determinism only from the DRBG io.Reader
    • Every reachable condition should have a test vector, unreachable conditions should be marked by a comment
  • GenerateMultiPrimeKey is deprecated and doesn't need to be supported
@FiloSottile FiloSottile added the NeedsFix The path to resolution is known, but the work has not been done. label Oct 7, 2024
@FiloSottile FiloSottile added this to the Go1.24 milestone Oct 7, 2024
derekparker pushed a commit to derekparker/go that referenced this issue Nov 20, 2024
@archanaravindar @derekparker
crypto/rsa: reimplement GenerateKey per FIPS 186-5
82d3139 
Submitting on behalf of @archanaravindar.

This patch implements RSA Key Generation per FIPS 186-5.
The implementation uses math/big despite eventually needing
to port to bigmod in order to not have to validate the
math/big package in the FIPS certification. The port to
bigmod will be committed as a follow-up patch.

For golang#69799
derekparker pushed a commit to derekparker/go that referenced this issue Nov 20, 2024
@archanaravindar @derekparker
crypto/rsa: reimplement GenerateKey per FIPS 186-5
431a8a6 
Submitting on behalf of @archanaravindar.

This patch implements RSA Key Generation per FIPS 186-5.
The implementation uses math/big despite eventually needing
to port to bigmod in order to not have to validate the
math/big package in the FIPS certification. The port to
bigmod will be committed as a follow-up patch.

For golang#69799

cleanup tests
derekparker added a commit to derekparker/go that referenced this issue Nov 20, 2024
@derekparker
crypto/rsa: reimplement GenerateKey per FIPS 186-5
24d31ef 
Submitting on behalf of @archanaravindar.

This patch implements RSA Key Generation per FIPS 186-5. The
implementation uses math/big despite eventually needing to port to
bigmod in order to not have to validate the math/big package in the FIPS
certification. The port to bigmod will be committed as a follow-up
patch.

For golang#69799
derekparker added a commit to derekparker/go that referenced this issue Nov 20, 2024
@derekparker
crypto/rsa: reimplement GenerateKey per FIPS 186-5
13933ef 
Submitting on behalf of @archanaravindar.

This patch implements RSA Key Generation per FIPS 186-5. The
implementation uses math/big despite eventually needing to port to
bigmod in order to not have to validate the math/big package in the FIPS
certification. The port to bigmod will be committed as a follow-up
patch.

For golang#69799

refactor
@derekparker derekparker mentioned this issue Nov 20, 2024
Closed
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/630336 mentions this issue: crypto/rsa: reimplement GenerateKey per FIPS 186-5

@FiloSottile FiloSottile changed the title crypto/rsa: reimplement GenerateKey per FIPS 186-5 with bigmod crypto/rsa: reimplement GenerateKey per FIPS 186-5 with bigmod [freeze exception] Nov 21, 2024
@FiloSottile
Copy link
Contributor Author

@golang/release I'd like to request a freeze exception to land this by Friday, November 29th.

This change will have no application-visible impact, and is necessary to keep math/big out of the FIPS 140 module boundary.

Apologies for not landing this by the deadline.

@dmitshur
Copy link
Member

Thanks for letting us know ahead of the freeze. We discussed this and will approve the freeze exception bit here. Please be ready to update your plan if there turn out to be more complications than originally anticipated. Thanks.

@dmitshur dmitshur moved this from In Review to Approved in Release: Freeze Exceptions Nov 21, 2024
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/632215 mentions this issue: crypto/internal/fips140/rsa: add Miller-Rabin test

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/632415 mentions this issue: crypto/internal/fips140/bigmod: add Inverse and gcd

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/632479 mentions this issue: crypto/internal/fips140/rsa: do trial divisions in key generation

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/632478 mentions this issue: crypto/x509: keep RSA CRT values in ParsePKCS1PrivateKey

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/632476 mentions this issue: crypto/rsa: move precomputation to crypto/internal/fips140/rsa

@gopherbot
Copy link
Contributor

Change https://go.dev/cl/632477 mentions this issue: crypto/rsa: move key generation to crypto/internal/fips140/rsa

gopherbot pushed a commit that referenced this issue Nov 30, 2024
@FiloSottile @gopherbot
crypto/internal/fips140/rsa: add Miller-Rabin test
22b5c14 
A following CL will move key generation to crypto/internal/fips140/rsa.

Updates #69799
For #69536

Change-Id: Icdf9b8424da20453939c6587af7dc922aad9e0ca
Reviewed-on: https://go-review.googlesource.com/c/go/+/632215
Auto-Submit: Filippo Valsorda <[email protected]>
Reviewed-by: Roland Shoemaker <[email protected]>
LUCI-TryBot-Result: Go LUCI <[email protected]>
Reviewed-by: Russ Cox <[email protected]>
Reviewed-by: Daniel McCarney <[email protected]>
gopherbot pushed a commit that referenced this issue Nov 30, 2024
@FiloSottile @gopherbot
crypto/internal/fips140/bigmod: add Nat.InverseVarTime
f7475a0 
Will be needed for RSA key generation.

We now require Modulus to be > 1 because we don't want to worry about 1
being out of range. There is no use for a Modulus of 1 anyway, and we
already return an error from NewModulus.

Ported from https://cs.opensource.google/boringssl/boringssl/+/master:crypto/fipsmodule/bn/gcd_extra.cc.inc;drc=5813c2c10c73d800f1b0d890a7d74ff973abbffc.

Updates #69799
For #69536

Change-Id: I9850bcc461565b23fa7186a09c65355f7da3e5ba
Reviewed-on: https://go-review.googlesource.com/c/go/+/632415
Auto-Submit: Filippo Valsorda <[email protected]>
Reviewed-by: Daniel McCarney <[email protected]>
LUCI-TryBot-Result: Go LUCI <[email protected]>
Reviewed-by: Roland Shoemaker <[email protected]>
Reviewed-by: Russ Cox <[email protected]>
gopherbot pushed a commit that referenced this issue Nov 30, 2024
@FiloSottile @gopherbot
crypto/rsa: move precomputation to crypto/internal/fips140/rsa
7d7192e 
We are severely limited by the crypto/rsa API in a few ways:

 - Precompute doesn't return an error, but is the only function allowed
   to modify a PrivateKey.

 - Clients presumably expect the PrecomputedValues big.Ints to be
   populated after Precompute.

 - MarshalPKCS1PrivateKey requires the precomputed values, and doesn't
   have an error return.

 - PrivateKeys with only N, e, and D have worked so far, so they might
   have to keep working.

To move precomputation to the FIPS module, we focus on the happy path of
a PrivateKey with two primes where Precompute is called before anything
else, which match ParsePKCS1PrivateKey and GenerateKey.

There is a significant slowdown in the Parse benchmark due to the
constant-time inversion of qInv. This will be addressed in a follow-up
CL that will use (and check) the value in the ASN.1.

Note that the prime product check now moved to checkPrivateKey is broken
(Π should start at 1 not 0) and fixed in CL 632478.

Updates #69799
For #69536

Change-Id: I95a8bc1244755c6d15d7c4eb179135a15608ddd6
Reviewed-on: https://go-review.googlesource.com/c/go/+/632476
LUCI-TryBot-Result: Go LUCI <[email protected]>
Auto-Submit: Filippo Valsorda <[email protected]>
Reviewed-by: Roland Shoemaker <[email protected]>
Reviewed-by: Russ Cox <[email protected]>
gopherbot pushed a commit that referenced this issue Nov 30, 2024
@FiloSottile @gopherbot
crypto/rsa: move key generation to crypto/internal/fips140/rsa
acd54c9 
It's about 2x slower, but we'll recover that by implementing trial
divisions in a follow-up CL.

Updates #69799
For #69536

Change-Id: Icc02f5a268b658d629bbe7fdaf2a42ad3b259e2c
Reviewed-on: https://go-review.googlesource.com/c/go/+/632477
Auto-Submit: Filippo Valsorda <[email protected]>
Reviewed-by: Russ Cox <[email protected]>
Reviewed-by: Roland Shoemaker <[email protected]>
LUCI-TryBot-Result: Go LUCI <[email protected]>
gopherbot pushed a commit that referenced this issue Nov 30, 2024
@FiloSottile @gopherbot
crypto/x509: keep RSA CRT values in ParsePKCS1PrivateKey
c5c4f3d 
Turns out that recomputing them (and qInv in particular) in constant
time is expensive, so let's not throw them away when they are available.
They are much faster to check, so we now do that on precompute.

Also, thanks to the opaque crypto/internal/fips140/rsa.PrivateKey type,
we now have some assurance that the values we use are always ones we
checked.

Recovers most of the performance loss since CL 630516 in the happy path.
Also, since now we always use the CRT, if necessary by running a
throwaway Precompute, which is now cheap if PrecomputedValues is filled
out, we effectively fixed the JSON round-trip slowdown (#59695).

goos: darwin
goarch: arm64
pkg: crypto/rsa
cpu: Apple M2
                            │ 3b42687  │          f017604bc6-dirty           │
                            │   sec/op    │   sec/op     vs base                │
ParsePKCS8PrivateKey/2048-8   26.76µ ± 1%   65.99µ ± 1%  +146.64% (p=0.002 n=6)

Fixes #59695
Updates #69799
For #69536

Change-Id: I507f8c5a32e69ab28990a3bf78959836b9b08cc9
Reviewed-on: https://go-review.googlesource.com/c/go/+/632478
Auto-Submit: Filippo Valsorda <[email protected]>
Reviewed-by: Russ Cox <[email protected]>
LUCI-TryBot-Result: Go LUCI <[email protected]>
Reviewed-by: Roland Shoemaker <[email protected]>
gopherbot pushed a commit that referenced this issue Nov 30, 2024
@FiloSottile @gopherbot
crypto/internal/fips140/rsa: do trial divisions in key generation
dd7ab5e 
This is optimized to be cheap in terms of extra code and complexity,
rather than performance, so we reuse the GCD we have for inverting d.

Recovers most of the performance loss since CL 630516, although
benchmarking key generation is by nature extremely noisy.

goos: darwin
goarch: arm64
pkg: crypto/rsa
cpu: Apple M2
                   │ 3b42687  │           b3d018a1e8-dirty           │
                   │   sec/op    │    sec/op     vs base                │
GenerateKey/2048-8   104.1m ± 7%   139.7m ± 20%  +34.10% (p=0.000 n=20)

Updates #69799
For #69536

Change-Id: I00347610935db8feb0597529a301ad7ace5b2f22
Reviewed-on: https://go-review.googlesource.com/c/go/+/632479
Reviewed-by: Roland Shoemaker <[email protected]>
Auto-Submit: Filippo Valsorda <[email protected]>
Reviewed-by: Daniel McCarney <[email protected]>
Reviewed-by: Russ Cox <[email protected]>
LUCI-TryBot-Result: Go LUCI <[email protected]>
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/632535 mentions this issue: crypto/rsa: minor FIPS 186-5 compliance fixes

@dmitshur dmitshur added the FixPending Issues that have a fix which has not yet been reviewed or submitted. label Dec 2, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
FixPending Issues that have a fix which has not yet been reviewed or submitted. NeedsFix The path to resolution is known, but the work has not been done.
Projects
Release: Freeze Exceptions
Archived in project
Milestone
Go1.24
Development

No branches or pull requests
3 participants
@FiloSottile @dmitshur @gopherbot