From ee5ccc9d4a41df1a1c6d339fa2624b0ee8e26045 Mon Sep 17 00:00:00 2001 From: Filippo Valsorda Date: Sun, 23 Oct 2022 14:22:22 +0200 Subject: [PATCH] crypto/rsa: deprecate and de-optimize multi-prime RSA I have never encountered multi-prime RSA in the wild. A GitHub-wide search reveals exactly two explicit uses of it (and a couple of tools that leave the number configurable but defaulting to two). https://github.com/decred/tumblebit/blob/31898baea/puzzle/puzzlekey.go#L38 https://github.com/carl-mastrangelo/pixur/blob/95d4a4208/tools/genkeys/genkeys.go#L13 Multi-prime RSA has a slight performance advantage, but has limited compatibility and the number of primes must be chosen carefully based on the key size to avoid security issues. It also requires a completely separate and rarely used private key operation code path, which if buggy or incorrect would leak the private key. Mark it as deprecated, and remove the dedicated CRT optimization, falling back instead to the slower but safer non-CRT fallback. Change-Id: Iba95edc044fcf9b37bc1f4bb59c6ea273975837f Reviewed-on: https://go-review.googlesource.com/c/go/+/445017 Reviewed-by: Roland Shoemaker Reviewed-by: Michael Knyszek TryBot-Result: Gopher Robot Run-TryBot: Filippo Valsorda --- src/crypto/rsa/rsa.go | 46 +++++++++++++++++++++---------------------- 1 file changed, 22 insertions(+), 24 deletions(-) diff --git a/src/crypto/rsa/rsa.go b/src/crypto/rsa/rsa.go index 237d745b39..1450032652 100644 --- a/src/crypto/rsa/rsa.go +++ b/src/crypto/rsa/rsa.go @@ -201,6 +201,11 @@ type PrecomputedValues struct { // historical accident, the CRT for the first two primes is handled // differently in PKCS #1 and interoperability is sufficiently // important that we mirror this. + // + // Deprecated: these values are still filled in by Precompute for + // backwards compatibility, but are not used. Multi-prime RSA is very rare, + // and is implemented by this package without CRT optimizations to limit + // complexity. CRTValues []CRTValue } @@ -256,16 +261,24 @@ func GenerateKey(random io.Reader, bits int) (*PrivateKey, error) { } // GenerateMultiPrimeKey generates a multi-prime RSA keypair of the given bit -// size and the given random source, as suggested in [1]. Although the public -// keys are compatible (actually, indistinguishable) from the 2-prime case, -// the private keys are not. Thus it may not be possible to export multi-prime -// private keys in certain formats or to subsequently import them into other -// code. +// size and the given random source. // -// Table 1 in [2] suggests maximum numbers of primes for a given size. +// Table 1 in "[On the Security of Multi-prime RSA]" suggests maximum numbers of +// primes for a given bit size. // -// [1] US patent 4405829 (1972, expired) -// [2] http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf +// Although the public keys are compatible (actually, indistinguishable) from +// the 2-prime case, the private keys are not. Thus it may not be possible to +// export multi-prime private keys in certain formats or to subsequently import +// them into other code. +// +// This package does not implement CRT optimizations for multi-prime RSA, so the +// keys with more than two primes will have worse performance. +// +// Deprecated: The use of this function with a number of primes different from +// two is not recommended for the above security, compatibility, and performance +// reasons. Use GenerateKey instead. +// +// [On the Security of Multi-prime RSA]: http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (*PrivateKey, error) { randutil.MaybeReadByte(random) @@ -573,7 +586,7 @@ func decrypt(priv *PrivateKey, ciphertext []byte) ([]byte, error) { // Note that because our private decryption exponents are stored as big.Int, // we potentially leak the exact number of bits of these exponents. This // isn't great, but should be fine. - if priv.Precomputed.Dp == nil { + if priv.Precomputed.Dp == nil || len(priv.Primes) > 2 { out := make([]byte, modulusSize(N)) return new(nat).exp(c, priv.D.Bytes(), N).fillBytes(out), nil } @@ -594,21 +607,6 @@ func decrypt(priv *PrivateKey, ciphertext []byte) ([]byte, error) { // m = m + m2 mod N m.modAdd(m2.expandFor(N), N) - for i, values := range priv.Precomputed.CRTValues { - p := modulusFromNat(natFromBig(priv.Primes[2+i])) - // m2 = c ^ Exp mod p - m2.exp(t0.mod(c, p), values.Exp.Bytes(), p) - // m2 = m2 - m mod p - m2.modSub(t0.mod(m, p), p) - // m2 = m2 * Coeff mod p - m2.modMul(natFromBig(values.Coeff).expandFor(p), p) - // m2 = m2 * R mod N - R := natFromBig(values.R).expandFor(N) - m2.expandFor(N).modMul(R, N) - // m = m + m2 mod N - m.modAdd(m2, N) - } - out := make([]byte, modulusSize(N)) return m.fillBytes(out), nil } -- 2.50.0