summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorVijay Anusuri <vanusuri@mvista.com>2024-01-06 11:19:31 +0530
committerSteve Sakoman <steve@sakoman.com>2024-01-21 08:33:18 -1000
commit5c5aa47adb05bb966711e5ead98333a53c07ab1d (patch)
tree103c69bad311467feaa3fb768e33b52eac9391f5
parentb418ede9942f8b31d66ce172ede35f55b423b0a2 (diff)
downloadpoky-5c5aa47adb05bb966711e5ead98333a53c07ab1d.tar.gz
go: Backport fix for CVE-2023-45287
Upstream-Status: Backport [https://github.com/golang/go/commit/9baafabac9a84813a336f068862207d2bb06d255 & https://github.com/golang/go/commit/c9d5f60eaa4450ccf1ce878d55b4c6a12843f2f3 & https://github.com/golang/go/commit/8f676144ad7b7c91adb0c6e1ec89aaa6283c6807 & https://github.com/golang/go/commit/8a81fdf165facdcefa06531de5af98a4db343035] (From OE-Core rev: 20e1d10a3ebefc8c5237c065c25eba4182d22efd) Signed-off-by: Vijay Anusuri <vanusuri@mvista.com> Signed-off-by: Steve Sakoman <steve@sakoman.com>
Diffstat
-rw-r--r--meta/recipes-devtools/go/go-1.14.inc4
-rw-r--r--meta/recipes-devtools/go/go-1.14/CVE-2023-45287-pre1.patch393
-rw-r--r--meta/recipes-devtools/go/go-1.14/CVE-2023-45287-pre2.patch401
-rw-r--r--meta/recipes-devtools/go/go-1.14/CVE-2023-45287-pre3.patch86
-rw-r--r--meta/recipes-devtools/go/go-1.14/CVE-2023-45287.patch1697
5 files changed, 2581 insertions, 0 deletions
diff --git a/meta/recipes-devtools/go/go-1.14.inc b/meta/recipes-devtools/go/go-1.14.inc
index b827a3606d..42a9ac8435 100644
--- a/meta/recipes-devtools/go/go-1.14.inc
+++ b/meta/recipes-devtools/go/go-1.14.inc
@@ -83,6 +83,10 @@ SRC_URI += "\
83 file://CVE-2023-39318.patch \ 83 file://CVE-2023-39318.patch \
84 file://CVE-2023-39319.patch \ 84 file://CVE-2023-39319.patch \
85 file://CVE-2023-39326.patch \ 85 file://CVE-2023-39326.patch \
86 file://CVE-2023-45287-pre1.patch \
87 file://CVE-2023-45287-pre2.patch \
88 file://CVE-2023-45287-pre3.patch \
89 file://CVE-2023-45287.patch \
86" 90"
87 91
88SRC_URI_append_libc-musl = " file://0009-ld-replace-glibc-dynamic-linker-with-musl.patch" 92SRC_URI_append_libc-musl = " file://0009-ld-replace-glibc-dynamic-linker-with-musl.patch"
diff --git a/meta/recipes-devtools/go/go-1.14/CVE-2023-45287-pre1.patch b/meta/recipes-devtools/go/go-1.14/CVE-2023-45287-pre1.patch
new file mode 100644
index 0000000000..4d65180253
--- /dev/null
+++ b/meta/recipes-devtools/go/go-1.14/CVE-2023-45287-pre1.patch
@@ -0,0 +1,393 @@
1From 9baafabac9a84813a336f068862207d2bb06d255 Mon Sep 17 00:00:00 2001
2From: Filippo Valsorda <filippo@golang.org>
3Date: Wed, 1 Apr 2020 17:25:40 -0400
4Subject: [PATCH] crypto/rsa: refactor RSA-PSS signing and verification
5
6Cleaned up for readability and consistency.
7
8There is one tiny behavioral change: when PSSSaltLengthEqualsHash is
9used and both hash and opts.Hash were set, hash.Size() was used for the
10salt length instead of opts.Hash.Size(). That's clearly wrong because
11opts.Hash is documented to override hash.
12
13Change-Id: I3e25dad933961eac827c6d2e3bbfe45fc5a6fb0e
14Reviewed-on: https://go-review.googlesource.com/c/go/+/226937
15Run-TryBot: Filippo Valsorda <filippo@golang.org>
16TryBot-Result: Gobot Gobot <gobot@golang.org>
17Reviewed-by: Katie Hockman <katie@golang.org>
18
19Upstream-Status: Backport [https://github.com/golang/go/commit/9baafabac9a84813a336f068862207d2bb06d255]
20CVE: CVE-2023-45287 #Dependency Patch1
21Signed-off-by: Vijay Anusuri <vanusuri@mvista.com>
22---
23 src/crypto/rsa/pss.go | 173 ++++++++++++++++++++++--------------------
24 src/crypto/rsa/rsa.go | 9 ++-
25 2 files changed, 96 insertions(+), 86 deletions(-)
26
27diff --git a/src/crypto/rsa/pss.go b/src/crypto/rsa/pss.go
28index 3ff0c2f4d0076..f9844d87329a8 100644
29--- a/src/crypto/rsa/pss.go
30+++ b/src/crypto/rsa/pss.go
31@@ -4,9 +4,7 @@
32
33 package rsa
34
35-// This file implements the PSS signature scheme [1].
36-//
37-// [1] https://www.emc.com/collateral/white-papers/h11300-pkcs-1v2-2-rsa-cryptography-standard-wp.pdf
38+// This file implements the RSASSA-PSS signature scheme according to RFC 8017.
39
40 import (
41 "bytes"
42@@ -17,8 +15,22 @@ import (
43 "math/big"
44 )
45
46+// Per RFC 8017, Section 9.1
47+//
48+// EM = MGF1 xor DB || H( 8*0x00 || mHash || salt ) || 0xbc
49+//
50+// where
51+//
52+// DB = PS || 0x01 || salt
53+//
54+// and PS can be empty so
55+//
56+// emLen = dbLen + hLen + 1 = psLen + sLen + hLen + 2
57+//
58+
59 func emsaPSSEncode(mHash []byte, emBits int, salt []byte, hash hash.Hash) ([]byte, error) {
60- // See [1], section 9.1.1
61+ // See RFC 8017, Section 9.1.1.
62+
63 hLen := hash.Size()
64 sLen := len(salt)
65 emLen := (emBits + 7) / 8
66@@ -30,7 +42,7 @@ func emsaPSSEncode(mHash []byte, emBits int, salt []byte, hash hash.Hash) ([]byt
67 // 2. Let mHash = Hash(M), an octet string of length hLen.
68
69 if len(mHash) != hLen {
70- return nil, errors.New("crypto/rsa: input must be hashed message")
71+ return nil, errors.New("crypto/rsa: input must be hashed with given hash")
72 }
73
74 // 3. If emLen < hLen + sLen + 2, output "encoding error" and stop.
75@@ -40,8 +52,9 @@ func emsaPSSEncode(mHash []byte, emBits int, salt []byte, hash hash.Hash) ([]byt
76 }
77
78 em := make([]byte, emLen)
79- db := em[:emLen-sLen-hLen-2+1+sLen]
80- h := em[emLen-sLen-hLen-2+1+sLen : emLen-1]
81+ psLen := emLen - sLen - hLen - 2
82+ db := em[:psLen+1+sLen]
83+ h := em[psLen+1+sLen : emLen-1]
84
85 // 4. Generate a random octet string salt of length sLen; if sLen = 0,
86 // then salt is the empty string.
87@@ -69,8 +82,8 @@ func emsaPSSEncode(mHash []byte, emBits int, salt []byte, hash hash.Hash) ([]byt
88 // 8. Let DB = PS || 0x01 || salt; DB is an octet string of length
89 // emLen - hLen - 1.
90
91- db[emLen-sLen-hLen-2] = 0x01
92- copy(db[emLen-sLen-hLen-1:], salt)
93+ db[psLen] = 0x01
94+ copy(db[psLen+1:], salt)
95
96 // 9. Let dbMask = MGF(H, emLen - hLen - 1).
97 //
98@@ -81,47 +94,57 @@ func emsaPSSEncode(mHash []byte, emBits int, salt []byte, hash hash.Hash) ([]byt
99 // 11. Set the leftmost 8 * emLen - emBits bits of the leftmost octet in
100 // maskedDB to zero.
101
102- db[0] &= (0xFF >> uint(8*emLen-emBits))
103+ db[0] &= 0xff >> (8*emLen - emBits)
104
105 // 12. Let EM = maskedDB || H || 0xbc.
106- em[emLen-1] = 0xBC
107+ em[emLen-1] = 0xbc
108
109 // 13. Output EM.
110 return em, nil
111 }
112
113 func emsaPSSVerify(mHash, em []byte, emBits, sLen int, hash hash.Hash) error {
114+ // See RFC 8017, Section 9.1.2.
115+
116+ hLen := hash.Size()
117+ if sLen == PSSSaltLengthEqualsHash {
118+ sLen = hLen
119+ }
120+ emLen := (emBits + 7) / 8
121+ if emLen != len(em) {
122+ return errors.New("rsa: internal error: inconsistent length")
123+ }
124+
125 // 1. If the length of M is greater than the input limitation for the
126 // hash function (2^61 - 1 octets for SHA-1), output "inconsistent"
127 // and stop.
128 //
129 // 2. Let mHash = Hash(M), an octet string of length hLen.
130- hLen := hash.Size()
131 if hLen != len(mHash) {
132 return ErrVerification
133 }
134
135 // 3. If emLen < hLen + sLen + 2, output "inconsistent" and stop.
136- emLen := (emBits + 7) / 8
137 if emLen < hLen+sLen+2 {
138 return ErrVerification
139 }
140
141 // 4. If the rightmost octet of EM does not have hexadecimal value
142 // 0xbc, output "inconsistent" and stop.
143- if em[len(em)-1] != 0xBC {
144+ if em[emLen-1] != 0xbc {
145 return ErrVerification
146 }
147
148 // 5. Let maskedDB be the leftmost emLen - hLen - 1 octets of EM, and
149 // let H be the next hLen octets.
150 db := em[:emLen-hLen-1]
151- h := em[emLen-hLen-1 : len(em)-1]
152+ h := em[emLen-hLen-1 : emLen-1]
153
154 // 6. If the leftmost 8 * emLen - emBits bits of the leftmost octet in
155 // maskedDB are not all equal to zero, output "inconsistent" and
156 // stop.
157- if em[0]&(0xFF<<uint(8-(8*emLen-emBits))) != 0 {
158+ var bitMask byte = 0xff >> (8*emLen - emBits)
159+ if em[0] & ^bitMask != 0 {
160 return ErrVerification
161 }
162
163@@ -132,37 +155,30 @@ func emsaPSSVerify(mHash, em []byte, emBits, sLen int, hash hash.Hash) error {
164
165 // 9. Set the leftmost 8 * emLen - emBits bits of the leftmost octet in DB
166 // to zero.
167- db[0] &= (0xFF >> uint(8*emLen-emBits))
168+ db[0] &= bitMask
169
170+ // If we don't know the salt length, look for the 0x01 delimiter.
171 if sLen == PSSSaltLengthAuto {
172- FindSaltLength:
173- for sLen = emLen - (hLen + 2); sLen >= 0; sLen-- {
174- switch db[emLen-hLen-sLen-2] {
175- case 1:
176- break FindSaltLength
177- case 0:
178- continue
179- default:
180- return ErrVerification
181- }
182- }
183- if sLen < 0 {
184+ psLen := bytes.IndexByte(db, 0x01)
185+ if psLen < 0 {
186 return ErrVerification
187 }
188- } else {
189- // 10. If the emLen - hLen - sLen - 2 leftmost octets of DB are not zero
190- // or if the octet at position emLen - hLen - sLen - 1 (the leftmost
191- // position is "position 1") does not have hexadecimal value 0x01,
192- // output "inconsistent" and stop.
193- for _, e := range db[:emLen-hLen-sLen-2] {
194- if e != 0x00 {
195- return ErrVerification
196- }
197- }
198- if db[emLen-hLen-sLen-2] != 0x01 {
199+ sLen = len(db) - psLen - 1
200+ }
201+
202+ // 10. If the emLen - hLen - sLen - 2 leftmost octets of DB are not zero
203+ // or if the octet at position emLen - hLen - sLen - 1 (the leftmost
204+ // position is "position 1") does not have hexadecimal value 0x01,
205+ // output "inconsistent" and stop.
206+ psLen := emLen - hLen - sLen - 2
207+ for _, e := range db[:psLen] {
208+ if e != 0x00 {
209 return ErrVerification
210 }
211 }
212+ if db[psLen] != 0x01 {
213+ return ErrVerification
214+ }
215
216 // 11. Let salt be the last sLen octets of DB.
217 salt := db[len(db)-sLen:]
218@@ -181,19 +197,19 @@ func emsaPSSVerify(mHash, em []byte, emBits, sLen int, hash hash.Hash) error {
219 h0 := hash.Sum(nil)
220
221 // 14. If H = H', output "consistent." Otherwise, output "inconsistent."
222- if !bytes.Equal(h0, h) {
223+ if !bytes.Equal(h0, h) { // TODO: constant time?
224 return ErrVerification
225 }
226 return nil
227 }
228
229-// signPSSWithSalt calculates the signature of hashed using PSS [1] with specified salt.
230+// signPSSWithSalt calculates the signature of hashed using PSS with specified salt.
231 // Note that hashed must be the result of hashing the input message using the
232 // given hash function. salt is a random sequence of bytes whose length will be
233 // later used to verify the signature.
234 func signPSSWithSalt(rand io.Reader, priv *PrivateKey, hash crypto.Hash, hashed, salt []byte) (s []byte, err error) {
235- nBits := priv.N.BitLen()
236- em, err := emsaPSSEncode(hashed, nBits-1, salt, hash.New())
237+ emBits := priv.N.BitLen() - 1
238+ em, err := emsaPSSEncode(hashed, emBits, salt, hash.New())
239 if err != nil {
240 return
241 }
242@@ -202,7 +218,7 @@ func signPSSWithSalt(rand io.Reader, priv *PrivateKey, hash crypto.Hash, hashed,
243 if err != nil {
244 return
245 }
246- s = make([]byte, (nBits+7)/8)
247+ s = make([]byte, priv.Size())
248 copyWithLeftPad(s, c.Bytes())
249 return
250 }
251@@ -223,16 +239,15 @@ type PSSOptions struct {
252 // PSSSaltLength constants.
253 SaltLength int
254
255- // Hash, if not zero, overrides the hash function passed to SignPSS.
256- // This is the only way to specify the hash function when using the
257- // crypto.Signer interface.
258+ // Hash is the hash function used to generate the message digest. If not
259+ // zero, it overrides the hash function passed to SignPSS. It's required
260+ // when using PrivateKey.Sign.
261 Hash crypto.Hash
262 }
263
264-// HashFunc returns pssOpts.Hash so that PSSOptions implements
265-// crypto.SignerOpts.
266-func (pssOpts *PSSOptions) HashFunc() crypto.Hash {
267- return pssOpts.Hash
268+// HashFunc returns opts.Hash so that PSSOptions implements crypto.SignerOpts.
269+func (opts *PSSOptions) HashFunc() crypto.Hash {
270+ return opts.Hash
271 }
272
273 func (opts *PSSOptions) saltLength() int {
274@@ -242,56 +257,50 @@ func (opts *PSSOptions) saltLength() int {
275 return opts.SaltLength
276 }
277
278-// SignPSS calculates the signature of hashed using RSASSA-PSS [1].
279-// Note that hashed must be the result of hashing the input message using the
280-// given hash function. The opts argument may be nil, in which case sensible
281-// defaults are used.
282-func SignPSS(rand io.Reader, priv *PrivateKey, hash crypto.Hash, hashed []byte, opts *PSSOptions) ([]byte, error) {
283+// SignPSS calculates the signature of digest using PSS.
284+//
285+// digest must be the result of hashing the input message using the given hash
286+// function. The opts argument may be nil, in which case sensible defaults are
287+// used. If opts.Hash is set, it overrides hash.
288+func SignPSS(rand io.Reader, priv *PrivateKey, hash crypto.Hash, digest []byte, opts *PSSOptions) ([]byte, error) {
289+ if opts != nil && opts.Hash != 0 {
290+ hash = opts.Hash
291+ }
292+
293 saltLength := opts.saltLength()
294 switch saltLength {
295 case PSSSaltLengthAuto:
296- saltLength = (priv.N.BitLen()+7)/8 - 2 - hash.Size()
297+ saltLength = priv.Size() - 2 - hash.Size()
298 case PSSSaltLengthEqualsHash:
299 saltLength = hash.Size()
300 }
301
302- if opts != nil && opts.Hash != 0 {
303- hash = opts.Hash
304- }
305-
306 salt := make([]byte, saltLength)
307 if _, err := io.ReadFull(rand, salt); err != nil {
308 return nil, err
309 }
310- return signPSSWithSalt(rand, priv, hash, hashed, salt)
311+ return signPSSWithSalt(rand, priv, hash, digest, salt)
312 }
313
314 // VerifyPSS verifies a PSS signature.
315-// hashed is the result of hashing the input message using the given hash
316-// function and sig is the signature. A valid signature is indicated by
317-// returning a nil error. The opts argument may be nil, in which case sensible
318-// defaults are used.
319-func VerifyPSS(pub *PublicKey, hash crypto.Hash, hashed []byte, sig []byte, opts *PSSOptions) error {
320- return verifyPSS(pub, hash, hashed, sig, opts.saltLength())
321-}
322-
323-// verifyPSS verifies a PSS signature with the given salt length.
324-func verifyPSS(pub *PublicKey, hash crypto.Hash, hashed []byte, sig []byte, saltLen int) error {
325- nBits := pub.N.BitLen()
326- if len(sig) != (nBits+7)/8 {
327+//
328+// A valid signature is indicated by returning a nil error. digest must be the
329+// result of hashing the input message using the given hash function. The opts
330+// argument may be nil, in which case sensible defaults are used. opts.Hash is
331+// ignored.
332+func VerifyPSS(pub *PublicKey, hash crypto.Hash, digest []byte, sig []byte, opts *PSSOptions) error {
333+ if len(sig) != pub.Size() {
334 return ErrVerification
335 }
336 s := new(big.Int).SetBytes(sig)
337 m := encrypt(new(big.Int), pub, s)
338- emBits := nBits - 1
339+ emBits := pub.N.BitLen() - 1
340 emLen := (emBits + 7) / 8
341- if emLen < len(m.Bytes()) {
342+ emBytes := m.Bytes()
343+ if emLen < len(emBytes) {
344 return ErrVerification
345 }
346 em := make([]byte, emLen)
347- copyWithLeftPad(em, m.Bytes())
348- if saltLen == PSSSaltLengthEqualsHash {
349- saltLen = hash.Size()
350- }
351- return emsaPSSVerify(hashed, em, emBits, saltLen, hash.New())
352+ copyWithLeftPad(em, emBytes)
353+ return emsaPSSVerify(digest, em, emBits, opts.saltLength(), hash.New())
354 }
355diff --git a/src/crypto/rsa/rsa.go b/src/crypto/rsa/rsa.go
356index 5a42990640164..b4bfa13defbdf 100644
357--- a/src/crypto/rsa/rsa.go
358+++ b/src/crypto/rsa/rsa.go
359@@ -2,7 +2,7 @@
360 // Use of this source code is governed by a BSD-style
361 // license that can be found in the LICENSE file.
362
363-// Package rsa implements RSA encryption as specified in PKCS#1.
364+// Package rsa implements RSA encryption as specified in PKCS#1 and RFC 8017.
365 //
366 // RSA is a single, fundamental operation that is used in this package to
367 // implement either public-key encryption or public-key signatures.
368@@ -10,13 +10,13 @@
369 // The original specification for encryption and signatures with RSA is PKCS#1
370 // and the terms "RSA encryption" and "RSA signatures" by default refer to
371 // PKCS#1 version 1.5. However, that specification has flaws and new designs
372-// should use version two, usually called by just OAEP and PSS, where
373+// should use version 2, usually called by just OAEP and PSS, where
374 // possible.
375 //
376 // Two sets of interfaces are included in this package. When a more abstract
377 // interface isn't necessary, there are functions for encrypting/decrypting
378 // with v1.5/OAEP and signing/verifying with v1.5/PSS. If one needs to abstract
379-// over the public-key primitive, the PrivateKey struct implements the
380+// over the public key primitive, the PrivateKey type implements the
381 // Decrypter and Signer interfaces from the crypto package.
382 //
383 // The RSA operations in this package are not implemented using constant-time algorithms.
384@@ -111,7 +111,8 @@ func (priv *PrivateKey) Public() crypto.PublicKey {
385
386 // Sign signs digest with priv, reading randomness from rand. If opts is a
387 // *PSSOptions then the PSS algorithm will be used, otherwise PKCS#1 v1.5 will
388-// be used.
389+// be used. digest must be the result of hashing the input message using
390+// opts.HashFunc().
391 //
392 // This method implements crypto.Signer, which is an interface to support keys
393 // where the private part is kept in, for example, a hardware module. Common
diff --git a/meta/recipes-devtools/go/go-1.14/CVE-2023-45287-pre2.patch b/meta/recipes-devtools/go/go-1.14/CVE-2023-45287-pre2.patch
new file mode 100644
index 0000000000..1327b44545
--- /dev/null
+++ b/meta/recipes-devtools/go/go-1.14/CVE-2023-45287-pre2.patch
@@ -0,0 +1,401 @@
1From c9d5f60eaa4450ccf1ce878d55b4c6a12843f2f3 Mon Sep 17 00:00:00 2001
2From: Filippo Valsorda <filippo@golang.org>
3Date: Mon, 27 Apr 2020 21:52:38 -0400
4Subject: [PATCH] math/big: add (*Int).FillBytes
5
6Replaced almost every use of Bytes with FillBytes.
7
8Note that the approved proposal was for
9
10 func (*Int) FillBytes(buf []byte)
11
12while this implements
13
14 func (*Int) FillBytes(buf []byte) []byte
15
16because the latter was far nicer to use in all callsites.
17
18Fixes #35833
19
20Change-Id: Ia912df123e5d79b763845312ea3d9a8051343c0a
21Reviewed-on: https://go-review.googlesource.com/c/go/+/230397
22Reviewed-by: Robert Griesemer <gri@golang.org>
23
24Upstream-Status: Backport [https://github.com/golang/go/commit/c9d5f60eaa4450ccf1ce878d55b4c6a12843f2f3]
25CVE: CVE-2023-45287 #Dependency Patch2
26Signed-off-by: Vijay Anusuri <vanusuri@mvista.com>
27---
28 src/crypto/elliptic/elliptic.go | 13 ++++----
29 src/crypto/rsa/pkcs1v15.go | 20 +++---------
30 src/crypto/rsa/pss.go | 17 +++++------
31 src/crypto/rsa/rsa.go | 32 +++----------------
32 src/crypto/tls/key_schedule.go | 7 ++---
33 src/crypto/x509/sec1.go | 7 ++---
34 src/math/big/int.go | 15 +++++++++
35 src/math/big/int_test.go | 54 +++++++++++++++++++++++++++++++++
36 src/math/big/nat.go | 15 ++++++---
37 9 files changed, 106 insertions(+), 74 deletions(-)
38
39diff --git a/src/crypto/elliptic/elliptic.go b/src/crypto/elliptic/elliptic.go
40index e2f71cdb63bab..bd5168c5fd842 100644
41--- a/src/crypto/elliptic/elliptic.go
42+++ b/src/crypto/elliptic/elliptic.go
43@@ -277,7 +277,7 @@ var mask = []byte{0xff, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f}
44 func GenerateKey(curve Curve, rand io.Reader) (priv []byte, x, y *big.Int, err error) {
45 N := curve.Params().N
46 bitSize := N.BitLen()
47- byteLen := (bitSize + 7) >> 3
48+ byteLen := (bitSize + 7) / 8
49 priv = make([]byte, byteLen)
50
51 for x == nil {
52@@ -304,15 +304,14 @@ func GenerateKey(curve Curve, rand io.Reader) (priv []byte, x, y *big.Int, err e
53
54 // Marshal converts a point into the uncompressed form specified in section 4.3.6 of ANSI X9.62.
55 func Marshal(curve Curve, x, y *big.Int) []byte {
56- byteLen := (curve.Params().BitSize + 7) >> 3
57+ byteLen := (curve.Params().BitSize + 7) / 8
58
59 ret := make([]byte, 1+2*byteLen)
60 ret[0] = 4 // uncompressed point
61
62- xBytes := x.Bytes()
63- copy(ret[1+byteLen-len(xBytes):], xBytes)
64- yBytes := y.Bytes()
65- copy(ret[1+2*byteLen-len(yBytes):], yBytes)
66+ x.FillBytes(ret[1 : 1+byteLen])
67+ y.FillBytes(ret[1+byteLen : 1+2*byteLen])
68+
69 return ret
70 }
71
72@@ -320,7 +319,7 @@ func Marshal(curve Curve, x, y *big.Int) []byte {
73 // It is an error if the point is not in uncompressed form or is not on the curve.
74 // On error, x = nil.
75 func Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
76- byteLen := (curve.Params().BitSize + 7) >> 3
77+ byteLen := (curve.Params().BitSize + 7) / 8
78 if len(data) != 1+2*byteLen {
79 return
80 }
81diff --git a/src/crypto/rsa/pkcs1v15.go b/src/crypto/rsa/pkcs1v15.go
82index 499242ffc5b57..3208119ae1ff4 100644
83--- a/src/crypto/rsa/pkcs1v15.go
84+++ b/src/crypto/rsa/pkcs1v15.go
85@@ -61,8 +61,7 @@ func EncryptPKCS1v15(rand io.Reader, pub *PublicKey, msg []byte) ([]byte, error)
86 m := new(big.Int).SetBytes(em)
87 c := encrypt(new(big.Int), pub, m)
88
89- copyWithLeftPad(em, c.Bytes())
90- return em, nil
91+ return c.FillBytes(em), nil
92 }
93
94 // DecryptPKCS1v15 decrypts a plaintext using RSA and the padding scheme from PKCS#1 v1.5.
95@@ -150,7 +149,7 @@ func decryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) (valid
96 return
97 }
98
99- em = leftPad(m.Bytes(), k)
100+ em = m.FillBytes(make([]byte, k))
101 firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
102 secondByteIsTwo := subtle.ConstantTimeByteEq(em[1], 2)
103
104@@ -256,8 +255,7 @@ func SignPKCS1v15(rand io.Reader, priv *PrivateKey, hash crypto.Hash, hashed []b
105 return nil, err
106 }
107
108- copyWithLeftPad(em, c.Bytes())
109- return em, nil
110+ return c.FillBytes(em), nil
111 }
112
113 // VerifyPKCS1v15 verifies an RSA PKCS#1 v1.5 signature.
114@@ -286,7 +284,7 @@ func VerifyPKCS1v15(pub *PublicKey, hash crypto.Hash, hashed []byte, sig []byte)
115
116 c := new(big.Int).SetBytes(sig)
117 m := encrypt(new(big.Int), pub, c)
118- em := leftPad(m.Bytes(), k)
119+ em := m.FillBytes(make([]byte, k))
120 // EM = 0x00 || 0x01 || PS || 0x00 || T
121
122 ok := subtle.ConstantTimeByteEq(em[0], 0)
123@@ -323,13 +321,3 @@ func pkcs1v15HashInfo(hash crypto.Hash, inLen int) (hashLen int, prefix []byte,
124 }
125 return
126 }
127-
128-// copyWithLeftPad copies src to the end of dest, padding with zero bytes as
129-// needed.
130-func copyWithLeftPad(dest, src []byte) {
131- numPaddingBytes := len(dest) - len(src)
132- for i := 0; i < numPaddingBytes; i++ {
133- dest[i] = 0
134- }
135- copy(dest[numPaddingBytes:], src)
136-}
137diff --git a/src/crypto/rsa/pss.go b/src/crypto/rsa/pss.go
138index f9844d87329a8..b2adbedb28fa8 100644
139--- a/src/crypto/rsa/pss.go
140+++ b/src/crypto/rsa/pss.go
141@@ -207,20 +207,19 @@ func emsaPSSVerify(mHash, em []byte, emBits, sLen int, hash hash.Hash) error {
142 // Note that hashed must be the result of hashing the input message using the
143 // given hash function. salt is a random sequence of bytes whose length will be
144 // later used to verify the signature.
145-func signPSSWithSalt(rand io.Reader, priv *PrivateKey, hash crypto.Hash, hashed, salt []byte) (s []byte, err error) {
146+func signPSSWithSalt(rand io.Reader, priv *PrivateKey, hash crypto.Hash, hashed, salt []byte) ([]byte, error) {
147 emBits := priv.N.BitLen() - 1
148 em, err := emsaPSSEncode(hashed, emBits, salt, hash.New())
149 if err != nil {
150- return
151+ return nil, err
152 }
153 m := new(big.Int).SetBytes(em)
154 c, err := decryptAndCheck(rand, priv, m)
155 if err != nil {
156- return
157+ return nil, err
158 }
159- s = make([]byte, priv.Size())
160- copyWithLeftPad(s, c.Bytes())
161- return
162+ s := make([]byte, priv.Size())
163+ return c.FillBytes(s), nil
164 }
165
166 const (
167@@ -296,11 +295,9 @@ func VerifyPSS(pub *PublicKey, hash crypto.Hash, digest []byte, sig []byte, opts
168 m := encrypt(new(big.Int), pub, s)
169 emBits := pub.N.BitLen() - 1
170 emLen := (emBits + 7) / 8
171- emBytes := m.Bytes()
172- if emLen < len(emBytes) {
173+ if m.BitLen() > emLen*8 {
174 return ErrVerification
175 }
176- em := make([]byte, emLen)
177- copyWithLeftPad(em, emBytes)
178+ em := m.FillBytes(make([]byte, emLen))
179 return emsaPSSVerify(digest, em, emBits, opts.saltLength(), hash.New())
180 }
181diff --git a/src/crypto/rsa/rsa.go b/src/crypto/rsa/rsa.go
182index b4bfa13defbdf..28eb5926c1a54 100644
183--- a/src/crypto/rsa/rsa.go
184+++ b/src/crypto/rsa/rsa.go
185@@ -416,16 +416,9 @@ func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, l
186 m := new(big.Int)
187 m.SetBytes(em)
188 c := encrypt(new(big.Int), pub, m)
189- out := c.Bytes()
190
191- if len(out) < k {
192- // If the output is too small, we need to left-pad with zeros.
193- t := make([]byte, k)
194- copy(t[k-len(out):], out)
195- out = t
196- }
197-
198- return out, nil
199+ out := make([]byte, k)
200+ return c.FillBytes(out), nil
201 }
202
203 // ErrDecryption represents a failure to decrypt a message.
204@@ -597,12 +590,9 @@ func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext
205 lHash := hash.Sum(nil)
206 hash.Reset()
207
208- // Converting the plaintext number to bytes will strip any
209- // leading zeros so we may have to left pad. We do this unconditionally
210- // to avoid leaking timing information. (Although we still probably
211- // leak the number of leading zeros. It's not clear that we can do
212- // anything about this.)
213- em := leftPad(m.Bytes(), k)
214+ // We probably leak the number of leading zeros.
215+ // It's not clear that we can do anything about this.
216+ em := m.FillBytes(make([]byte, k))
217
218 firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
219
220@@ -643,15 +633,3 @@ func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext
221
222 return rest[index+1:], nil
223 }
224-
225-// leftPad returns a new slice of length size. The contents of input are right
226-// aligned in the new slice.
227-func leftPad(input []byte, size int) (out []byte) {
228- n := len(input)
229- if n > size {
230- n = size
231- }
232- out = make([]byte, size)
233- copy(out[len(out)-n:], input)
234- return
235-}
236diff --git a/src/crypto/tls/key_schedule.go b/src/crypto/tls/key_schedule.go
237index 2aab323202f7d..314016979afb8 100644
238--- a/src/crypto/tls/key_schedule.go
239+++ b/src/crypto/tls/key_schedule.go
240@@ -173,11 +173,8 @@ func (p *nistParameters) SharedKey(peerPublicKey []byte) []byte {
241 }
242
243 xShared, _ := curve.ScalarMult(x, y, p.privateKey)
244- sharedKey := make([]byte, (curve.Params().BitSize+7)>>3)
245- xBytes := xShared.Bytes()
246- copy(sharedKey[len(sharedKey)-len(xBytes):], xBytes)
247-
248- return sharedKey
249+ sharedKey := make([]byte, (curve.Params().BitSize+7)/8)
250+ return xShared.FillBytes(sharedKey)
251 }
252
253 type x25519Parameters struct {
254diff --git a/src/crypto/x509/sec1.go b/src/crypto/x509/sec1.go
255index 0bfb90cd5464a..52c108ff1d624 100644
256--- a/src/crypto/x509/sec1.go
257+++ b/src/crypto/x509/sec1.go
258@@ -52,13 +52,10 @@ func MarshalECPrivateKey(key *ecdsa.PrivateKey) ([]byte, error) {
259 // marshalECPrivateKey marshals an EC private key into ASN.1, DER format and
260 // sets the curve ID to the given OID, or omits it if OID is nil.
261 func marshalECPrivateKeyWithOID(key *ecdsa.PrivateKey, oid asn1.ObjectIdentifier) ([]byte, error) {
262- privateKeyBytes := key.D.Bytes()
263- paddedPrivateKey := make([]byte, (key.Curve.Params().N.BitLen()+7)/8)
264- copy(paddedPrivateKey[len(paddedPrivateKey)-len(privateKeyBytes):], privateKeyBytes)
265-
266+ privateKey := make([]byte, (key.Curve.Params().N.BitLen()+7)/8)
267 return asn1.Marshal(ecPrivateKey{
268 Version: 1,
269- PrivateKey: paddedPrivateKey,
270+ PrivateKey: key.D.FillBytes(privateKey),
271 NamedCurveOID: oid,
272 PublicKey: asn1.BitString{Bytes: elliptic.Marshal(key.Curve, key.X, key.Y)},
273 })
274diff --git a/src/math/big/int.go b/src/math/big/int.go
275index 8816cf5266cc4..65f32487b58c0 100644
276--- a/src/math/big/int.go
277+++ b/src/math/big/int.go
278@@ -447,11 +447,26 @@ func (z *Int) SetBytes(buf []byte) *Int {
279 }
280
281 // Bytes returns the absolute value of x as a big-endian byte slice.
282+//
283+// To use a fixed length slice, or a preallocated one, use FillBytes.
284 func (x *Int) Bytes() []byte {
285 buf := make([]byte, len(x.abs)*_S)
286 return buf[x.abs.bytes(buf):]
287 }
288
289+// FillBytes sets buf to the absolute value of x, storing it as a zero-extended
290+// big-endian byte slice, and returns buf.
291+//
292+// If the absolute value of x doesn't fit in buf, FillBytes will panic.
293+func (x *Int) FillBytes(buf []byte) []byte {
294+ // Clear whole buffer. (This gets optimized into a memclr.)
295+ for i := range buf {
296+ buf[i] = 0
297+ }
298+ x.abs.bytes(buf)
299+ return buf
300+}
301+
302 // BitLen returns the length of the absolute value of x in bits.
303 // The bit length of 0 is 0.
304 func (x *Int) BitLen() int {
305diff --git a/src/math/big/int_test.go b/src/math/big/int_test.go
306index e3a1587b3f0ad..3c8557323a032 100644
307--- a/src/math/big/int_test.go
308+++ b/src/math/big/int_test.go
309@@ -1840,3 +1840,57 @@ func BenchmarkDiv(b *testing.B) {
310 })
311 }
312 }
313+
314+func TestFillBytes(t *testing.T) {
315+ checkResult := func(t *testing.T, buf []byte, want *Int) {
316+ t.Helper()
317+ got := new(Int).SetBytes(buf)
318+ if got.CmpAbs(want) != 0 {
319+ t.Errorf("got 0x%x, want 0x%x: %x", got, want, buf)
320+ }
321+ }
322+ panics := func(f func()) (panic bool) {
323+ defer func() { panic = recover() != nil }()
324+ f()
325+ return
326+ }
327+
328+ for _, n := range []string{
329+ "0",
330+ "1000",
331+ "0xffffffff",
332+ "-0xffffffff",
333+ "0xffffffffffffffff",
334+ "0x10000000000000000",
335+ "0xabababababababababababababababababababababababababa",
336+ "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
337+ } {
338+ t.Run(n, func(t *testing.T) {
339+ t.Logf(n)
340+ x, ok := new(Int).SetString(n, 0)
341+ if !ok {
342+ panic("invalid test entry")
343+ }
344+
345+ // Perfectly sized buffer.
346+ byteLen := (x.BitLen() + 7) / 8
347+ buf := make([]byte, byteLen)
348+ checkResult(t, x.FillBytes(buf), x)
349+
350+ // Way larger, checking all bytes get zeroed.
351+ buf = make([]byte, 100)
352+ for i := range buf {
353+ buf[i] = 0xff
354+ }
355+ checkResult(t, x.FillBytes(buf), x)
356+
357+ // Too small.
358+ if byteLen > 0 {
359+ buf = make([]byte, byteLen-1)
360+ if !panics(func() { x.FillBytes(buf) }) {
361+ t.Errorf("expected panic for small buffer and value %x", x)
362+ }
363+ }
364+ })
365+ }
366+}
367diff --git a/src/math/big/nat.go b/src/math/big/nat.go
368index c31ec5156b81d..6a3989bf9d82b 100644
369--- a/src/math/big/nat.go
370+++ b/src/math/big/nat.go
371@@ -1476,19 +1476,26 @@ func (z nat) expNNMontgomery(x, y, m nat) nat {
372 }
373
374 // bytes writes the value of z into buf using big-endian encoding.
375-// len(buf) must be >= len(z)*_S. The value of z is encoded in the
376-// slice buf[i:]. The number i of unused bytes at the beginning of
377-// buf is returned as result.
378+// The value of z is encoded in the slice buf[i:]. If the value of z
379+// cannot be represented in buf, bytes panics. The number i of unused
380+// bytes at the beginning of buf is returned as result.
381 func (z nat) bytes(buf []byte) (i int) {
382 i = len(buf)
383 for _, d := range z {
384 for j := 0; j < _S; j++ {
385 i--
386- buf[i] = byte(d)
387+ if i >= 0 {
388+ buf[i] = byte(d)
389+ } else if byte(d) != 0 {
390+ panic("math/big: buffer too small to fit value")
391+ }
392 d >>= 8
393 }
394 }
395
396+ if i < 0 {
397+ i = 0
398+ }
399 for i < len(buf) && buf[i] == 0 {
400 i++
401 }
diff --git a/meta/recipes-devtools/go/go-1.14/CVE-2023-45287-pre3.patch b/meta/recipes-devtools/go/go-1.14/CVE-2023-45287-pre3.patch
new file mode 100644
index 0000000000..ae9fcc170c
--- /dev/null
+++ b/meta/recipes-devtools/go/go-1.14/CVE-2023-45287-pre3.patch
@@ -0,0 +1,86 @@
1From 8f676144ad7b7c91adb0c6e1ec89aaa6283c6807 Mon Sep 17 00:00:00 2001
2From: Himanshu Kishna Srivastava <28himanshu@gmail.com>
3Date: Tue, 16 Mar 2021 22:37:46 +0530
4Subject: [PATCH] crypto/rsa: fix salt length calculation with
5 PSSSaltLengthAuto
6
7When PSSSaltLength is set, the maximum salt length must equal:
8
9 (modulus_key_size - 1 + 7)/8 - hash_length - 2
10and for example, with a 4096 bit modulus key, and a SHA-1 hash,
11it should be:
12
13 (4096 -1 + 7)/8 - 20 - 2 = 490
14Previously we'd encounter this error:
15
16 crypto/rsa: key size too small for PSS signature
17
18Fixes #42741
19
20Change-Id: I18bb82c41c511d564b3f4c443f4b3a38ab010ac5
21Reviewed-on: https://go-review.googlesource.com/c/go/+/302230
22Reviewed-by: Emmanuel Odeke <emmanuel@orijtech.com>
23Reviewed-by: Filippo Valsorda <filippo@golang.org>
24Trust: Emmanuel Odeke <emmanuel@orijtech.com>
25Run-TryBot: Emmanuel Odeke <emmanuel@orijtech.com>
26TryBot-Result: Go Bot <gobot@golang.org>
27
28Upstream-Status: Backport [https://github.com/golang/go/commit/8f676144ad7b7c91adb0c6e1ec89aaa6283c6807]
29CVE: CVE-2023-45287 #Dependency Patch3
30Signed-off-by: Vijay Anusuri <vanusuri@mvista.com>
31---
32 src/crypto/rsa/pss.go | 2 +-
33 src/crypto/rsa/pss_test.go | 20 +++++++++++++++++++-
34 2 files changed, 20 insertions(+), 2 deletions(-)
35
36diff --git a/src/crypto/rsa/pss.go b/src/crypto/rsa/pss.go
37index b2adbedb28fa8..814522de8181f 100644
38--- a/src/crypto/rsa/pss.go
39+++ b/src/crypto/rsa/pss.go
40@@ -269,7 +269,7 @@ func SignPSS(rand io.Reader, priv *PrivateKey, hash crypto.Hash, digest []byte,
41 saltLength := opts.saltLength()
42 switch saltLength {
43 case PSSSaltLengthAuto:
44- saltLength = priv.Size() - 2 - hash.Size()
45+ saltLength = (priv.N.BitLen()-1+7)/8 - 2 - hash.Size()
46 case PSSSaltLengthEqualsHash:
47 saltLength = hash.Size()
48 }
49diff --git a/src/crypto/rsa/pss_test.go b/src/crypto/rsa/pss_test.go
50index dfa8d8bb5ad02..c3a6d468497cd 100644
51--- a/src/crypto/rsa/pss_test.go
52+++ b/src/crypto/rsa/pss_test.go
53@@ -12,7 +12,7 @@ import (
54 _ "crypto/md5"
55 "crypto/rand"
56 "crypto/sha1"
57- _ "crypto/sha256"
58+ "crypto/sha256"
59 "encoding/hex"
60 "math/big"
61 "os"
62@@ -233,6 +233,24 @@ func TestPSSSigning(t *testing.T) {
63 }
64 }
65
66+func TestSignWithPSSSaltLengthAuto(t *testing.T) {
67+ key, err := GenerateKey(rand.Reader, 513)
68+ if err != nil {
69+ t.Fatal(err)
70+ }
71+ digest := sha256.Sum256([]byte("message"))
72+ signature, err := key.Sign(rand.Reader, digest[:], &PSSOptions{
73+ SaltLength: PSSSaltLengthAuto,
74+ Hash: crypto.SHA256,
75+ })
76+ if err != nil {
77+ t.Fatal(err)
78+ }
79+ if len(signature) == 0 {
80+ t.Fatal("empty signature returned")
81+ }
82+}
83+
84 func bigFromHex(hex string) *big.Int {
85 n, ok := new(big.Int).SetString(hex, 16)
86 if !ok {
diff --git a/meta/recipes-devtools/go/go-1.14/CVE-2023-45287.patch b/meta/recipes-devtools/go/go-1.14/CVE-2023-45287.patch
new file mode 100644
index 0000000000..90a74255db
--- /dev/null
+++ b/meta/recipes-devtools/go/go-1.14/CVE-2023-45287.patch
@@ -0,0 +1,1697 @@
1From 8a81fdf165facdcefa06531de5af98a4db343035 Mon Sep 17 00:00:00 2001
2From: =?UTF-8?q?L=C3=BAc=C3=A1s=20Meier?= <cronokirby@gmail.com>
3Date: Tue, 8 Jun 2021 21:36:06 +0200
4Subject: [PATCH] crypto/rsa: replace big.Int for encryption and decryption
5
6Infamously, big.Int does not provide constant-time arithmetic, making
7its use in cryptographic code quite tricky. RSA uses big.Int
8pervasively, in its public API, for key generation, precomputation, and
9for encryption and decryption. This is a known problem. One mitigation,
10blinding, is already in place during decryption. This helps mitigate the
11very leaky exponentiation operation. Because big.Int is fundamentally
12not constant-time, it's unfortunately difficult to guarantee that
13mitigations like these are completely effective.
14
15This patch removes the use of big.Int for encryption and decryption,
16replacing it with an internal nat type instead. Signing and verification
17are also affected, because they depend on encryption and decryption.
18
19Overall, this patch degrades performance by 55% for private key
20operations, and 4-5x for (much faster) public key operations.
21(Signatures do both, so the slowdown is worse than decryption.)
22
23name old time/op new time/op delta
24DecryptPKCS1v15/2048-8 1.50ms ± 0% 2.34ms ± 0% +56.44% (p=0.000 n=8+10)
25DecryptPKCS1v15/3072-8 4.40ms ± 0% 6.79ms ± 0% +54.33% (p=0.000 n=10+9)
26DecryptPKCS1v15/4096-8 9.31ms ± 0% 15.14ms ± 0% +62.60% (p=0.000 n=10+10)
27EncryptPKCS1v15/2048-8 8.16µs ± 0% 355.58µs ± 0% +4258.90% (p=0.000 n=10+9)
28DecryptOAEP/2048-8 1.50ms ± 0% 2.34ms ± 0% +55.68% (p=0.000 n=10+9)
29EncryptOAEP/2048-8 8.51µs ± 0% 355.95µs ± 0% +4082.75% (p=0.000 n=10+9)
30SignPKCS1v15/2048-8 1.51ms ± 0% 2.69ms ± 0% +77.94% (p=0.000 n=10+10)
31VerifyPKCS1v15/2048-8 7.25µs ± 0% 354.34µs ± 0% +4789.52% (p=0.000 n=9+9)
32SignPSS/2048-8 1.51ms ± 0% 2.70ms ± 0% +78.80% (p=0.000 n=9+10)
33VerifyPSS/2048-8 8.27µs ± 1% 355.65µs ± 0% +4199.39% (p=0.000 n=10+10)
34
35Keep in mind that this is without any assembly at all, and that further
36improvements are likely possible. I think having a review of the logic
37and the cryptography would be a good idea at this stage, before we
38complicate the code too much through optimization.
39
40The bulk of the work is in nat.go. This introduces two new types: nat,
41representing natural numbers, and modulus, representing moduli used in
42modular arithmetic.
43
44A nat has an "announced size", which may be larger than its "true size",
45the number of bits needed to represent this number. Operations on a nat
46will only ever leak its announced size, never its true size, or other
47information about its value. The size of a nat is always clear based on
48how its value is set. For example, x.mod(y, m) will make the announced
49size of x match that of m, since x is reduced modulo m.
50
51Operations assume that the announced size of the operands match what's
52expected (with a few exceptions). For example, x.modAdd(y, m) assumes
53that x and y have the same announced size as m, and that they're reduced
54modulo m.
55
56Nats are represented over unsatured bits.UintSize - 1 bit limbs. This
57means that we can't reuse the assembly routines for big.Int, which use
58saturated bits.UintSize limbs. The advantage of unsaturated limbs is
59that it makes Montgomery multiplication faster, by needing fewer
60registers in a hot loop. This makes exponentiation faster, which
61consists of many Montgomery multiplications.
62
63Moduli use nat internally. Unlike nat, the true size of a modulus always
64matches its announced size. When creating a modulus, any zero padding is
65removed. Moduli will also precompute constants when created, which is
66another reason why having a separate type is desirable.
67
68Updates #20654
69
70Co-authored-by: Filippo Valsorda <filippo@golang.org>
71Change-Id: I73b61f87d58ab912e80a9644e255d552cbadcced
72Reviewed-on: https://go-review.googlesource.com/c/go/+/326012
73Run-TryBot: Filippo Valsorda <filippo@golang.org>
74TryBot-Result: Gopher Robot <gobot@golang.org>
75Reviewed-by: Roland Shoemaker <roland@golang.org>
76Reviewed-by: Joedian Reid <joedian@golang.org>
77
78Upstream-Status: Backport [https://github.com/golang/go/commit/8a81fdf165facdcefa06531de5af98a4db343035]
79CVE: CVE-2023-45287
80Signed-off-by: Vijay Anusuri <vanusuri@mvista.com>
81---
82 src/crypto/rsa/example_test.go | 21 +-
83 src/crypto/rsa/nat.go | 626 +++++++++++++++++++++++++++++++++
84 src/crypto/rsa/nat_test.go | 384 ++++++++++++++++++++
85 src/crypto/rsa/pkcs1v15.go | 47 +--
86 src/crypto/rsa/pss.go | 50 ++-
87 src/crypto/rsa/pss_test.go | 10 +-
88 src/crypto/rsa/rsa.go | 174 ++++-----
89 7 files changed, 1143 insertions(+), 169 deletions(-)
90 create mode 100644 src/crypto/rsa/nat.go
91 create mode 100644 src/crypto/rsa/nat_test.go
92
93diff --git a/src/crypto/rsa/example_test.go b/src/crypto/rsa/example_test.go
94index 1435b70..1963609 100644
95--- a/src/crypto/rsa/example_test.go
96+++ b/src/crypto/rsa/example_test.go
97@@ -12,7 +12,6 @@ import (
98 "crypto/sha256"
99 "encoding/hex"
100 "fmt"
101- "io"
102 "os"
103 )
104
105@@ -36,21 +35,17 @@ import (
106 // a buffer that contains a random key. Thus, if the RSA result isn't
107 // well-formed, the implementation uses a random key in constant time.
108 func ExampleDecryptPKCS1v15SessionKey() {
109- // crypto/rand.Reader is a good source of entropy for blinding the RSA
110- // operation.
111- rng := rand.Reader
112-
113 // The hybrid scheme should use at least a 16-byte symmetric key. Here
114 // we read the random key that will be used if the RSA decryption isn't
115 // well-formed.
116 key := make([]byte, 32)
117- if _, err := io.ReadFull(rng, key); err != nil {
118+ if _, err := rand.Read(key); err != nil {
119 panic("RNG failure")
120 }
121
122 rsaCiphertext, _ := hex.DecodeString("aabbccddeeff")
123
124- if err := DecryptPKCS1v15SessionKey(rng, rsaPrivateKey, rsaCiphertext, key); err != nil {
125+ if err := DecryptPKCS1v15SessionKey(nil, rsaPrivateKey, rsaCiphertext, key); err != nil {
126 // Any errors that result will be “public” – meaning that they
127 // can be determined without any secret information. (For
128 // instance, if the length of key is impossible given the RSA
129@@ -86,10 +81,6 @@ func ExampleDecryptPKCS1v15SessionKey() {
130 }
131
132 func ExampleSignPKCS1v15() {
133- // crypto/rand.Reader is a good source of entropy for blinding the RSA
134- // operation.
135- rng := rand.Reader
136-
137 message := []byte("message to be signed")
138
139 // Only small messages can be signed directly; thus the hash of a
140@@ -99,7 +90,7 @@ func ExampleSignPKCS1v15() {
141 // of writing (2016).
142 hashed := sha256.Sum256(message)
143
144- signature, err := SignPKCS1v15(rng, rsaPrivateKey, crypto.SHA256, hashed[:])
145+ signature, err := SignPKCS1v15(nil, rsaPrivateKey, crypto.SHA256, hashed[:])
146 if err != nil {
147 fmt.Fprintf(os.Stderr, "Error from signing: %s\n", err)
148 return
149@@ -151,11 +142,7 @@ func ExampleDecryptOAEP() {
150 ciphertext, _ := hex.DecodeString("4d1ee10e8f286390258c51a5e80802844c3e6358ad6690b7285218a7c7ed7fc3a4c7b950fbd04d4b0239cc060dcc7065ca6f84c1756deb71ca5685cadbb82be025e16449b905c568a19c088a1abfad54bf7ecc67a7df39943ec511091a34c0f2348d04e058fcff4d55644de3cd1d580791d4524b92f3e91695582e6e340a1c50b6c6d78e80b4e42c5b4d45e479b492de42bbd39cc642ebb80226bb5200020d501b24a37bcc2ec7f34e596b4fd6b063de4858dbf5a4e3dd18e262eda0ec2d19dbd8e890d672b63d368768360b20c0b6b8592a438fa275e5fa7f60bef0dd39673fd3989cc54d2cb80c08fcd19dacbc265ee1c6014616b0e04ea0328c2a04e73460")
151 label := []byte("orders")
152
153- // crypto/rand.Reader is a good source of entropy for blinding the RSA
154- // operation.
155- rng := rand.Reader
156-
157- plaintext, err := DecryptOAEP(sha256.New(), rng, test2048Key, ciphertext, label)
158+ plaintext, err := DecryptOAEP(sha256.New(), nil, test2048Key, ciphertext, label)
159 if err != nil {
160 fmt.Fprintf(os.Stderr, "Error from decryption: %s\n", err)
161 return
162diff --git a/src/crypto/rsa/nat.go b/src/crypto/rsa/nat.go
163new file mode 100644
164index 0000000..da521c2
165--- /dev/null
166+++ b/src/crypto/rsa/nat.go
167@@ -0,0 +1,626 @@
168+// Copyright 2021 The Go Authors. All rights reserved.
169+// Use of this source code is governed by a BSD-style
170+// license that can be found in the LICENSE file.
171+
172+package rsa
173+
174+import (
175+ "math/big"
176+ "math/bits"
177+)
178+
179+const (
180+ // _W is the number of bits we use for our limbs.
181+ _W = bits.UintSize - 1
182+ // _MASK selects _W bits from a full machine word.
183+ _MASK = (1 << _W) - 1
184+)
185+
186+// choice represents a constant-time boolean. The value of choice is always
187+// either 1 or 0. We use an int instead of bool in order to make decisions in
188+// constant time by turning it into a mask.
189+type choice uint
190+
191+func not(c choice) choice { return 1 ^ c }
192+
193+const yes = choice(1)
194+const no = choice(0)
195+
196+// ctSelect returns x if on == 1, and y if on == 0. The execution time of this
197+// function does not depend on its inputs. If on is any value besides 1 or 0,
198+// the result is undefined.
199+func ctSelect(on choice, x, y uint) uint {
200+ // When on == 1, mask is 0b111..., otherwise mask is 0b000...
201+ mask := -uint(on)
202+ // When mask is all zeros, we just have y, otherwise, y cancels with itself.
203+ return y ^ (mask & (y ^ x))
204+}
205+
206+// ctEq returns 1 if x == y, and 0 otherwise. The execution time of this
207+// function does not depend on its inputs.
208+func ctEq(x, y uint) choice {
209+ // If x != y, then either x - y or y - x will generate a carry.
210+ _, c1 := bits.Sub(x, y, 0)
211+ _, c2 := bits.Sub(y, x, 0)
212+ return not(choice(c1 | c2))
213+}
214+
215+// ctGeq returns 1 if x >= y, and 0 otherwise. The execution time of this
216+// function does not depend on its inputs.
217+func ctGeq(x, y uint) choice {
218+ // If x < y, then x - y generates a carry.
219+ _, carry := bits.Sub(x, y, 0)
220+ return not(choice(carry))
221+}
222+
223+// nat represents an arbitrary natural number
224+//
225+// Each nat has an announced length, which is the number of limbs it has stored.
226+// Operations on this number are allowed to leak this length, but will not leak
227+// any information about the values contained in those limbs.
228+type nat struct {
229+ // limbs is a little-endian representation in base 2^W with
230+ // W = bits.UintSize - 1. The top bit is always unset between operations.
231+ //
232+ // The top bit is left unset to optimize Montgomery multiplication, in the
233+ // inner loop of exponentiation. Using fully saturated limbs would leave us
234+ // working with 129-bit numbers on 64-bit platforms, wasting a lot of space,
235+ // and thus time.
236+ limbs []uint
237+}
238+
239+// expand expands x to n limbs, leaving its value unchanged.
240+func (x *nat) expand(n int) *nat {
241+ for len(x.limbs) > n {
242+ if x.limbs[len(x.limbs)-1] != 0 {
243+ panic("rsa: internal error: shrinking nat")
244+ }
245+ x.limbs = x.limbs[:len(x.limbs)-1]
246+ }
247+ if cap(x.limbs) < n {
248+ newLimbs := make([]uint, n)
249+ copy(newLimbs, x.limbs)
250+ x.limbs = newLimbs
251+ return x
252+ }
253+ extraLimbs := x.limbs[len(x.limbs):n]
254+ for i := range extraLimbs {
255+ extraLimbs[i] = 0
256+ }
257+ x.limbs = x.limbs[:n]
258+ return x
259+}
260+
261+// reset returns a zero nat of n limbs, reusing x's storage if n <= cap(x.limbs).
262+func (x *nat) reset(n int) *nat {
263+ if cap(x.limbs) < n {
264+ x.limbs = make([]uint, n)
265+ return x
266+ }
267+ for i := range x.limbs {
268+ x.limbs[i] = 0
269+ }
270+ x.limbs = x.limbs[:n]
271+ return x
272+}
273+
274+// clone returns a new nat, with the same value and announced length as x.
275+func (x *nat) clone() *nat {
276+ out := &nat{make([]uint, len(x.limbs))}
277+ copy(out.limbs, x.limbs)
278+ return out
279+}
280+
281+// natFromBig creates a new natural number from a big.Int.
282+//
283+// The announced length of the resulting nat is based on the actual bit size of
284+// the input, ignoring leading zeroes.
285+func natFromBig(x *big.Int) *nat {
286+ xLimbs := x.Bits()
287+ bitSize := bigBitLen(x)
288+ requiredLimbs := (bitSize + _W - 1) / _W
289+
290+ out := &nat{make([]uint, requiredLimbs)}
291+ outI := 0
292+ shift := 0
293+ for i := range xLimbs {
294+ xi := uint(xLimbs[i])
295+ out.limbs[outI] |= (xi << shift) & _MASK
296+ outI++
297+ if outI == requiredLimbs {
298+ return out
299+ }
300+ out.limbs[outI] = xi >> (_W - shift)
301+ shift++ // this assumes bits.UintSize - _W = 1
302+ if shift == _W {
303+ shift = 0
304+ outI++
305+ }
306+ }
307+ return out
308+}
309+
310+// fillBytes sets bytes to x as a zero-extended big-endian byte slice.
311+//
312+// If bytes is not long enough to contain the number or at least len(x.limbs)-1
313+// limbs, or has zero length, fillBytes will panic.
314+func (x *nat) fillBytes(bytes []byte) []byte {
315+ if len(bytes) == 0 {
316+ panic("nat: fillBytes invoked with too small buffer")
317+ }
318+ for i := range bytes {
319+ bytes[i] = 0
320+ }
321+ shift := 0
322+ outI := len(bytes) - 1
323+ for i, limb := range x.limbs {
324+ remainingBits := _W
325+ for remainingBits >= 8 {
326+ bytes[outI] |= byte(limb) << shift
327+ consumed := 8 - shift
328+ limb >>= consumed
329+ remainingBits -= consumed
330+ shift = 0
331+ outI--
332+ if outI < 0 {
333+ if limb != 0 || i < len(x.limbs)-1 {
334+ panic("nat: fillBytes invoked with too small buffer")
335+ }
336+ return bytes
337+ }
338+ }
339+ bytes[outI] = byte(limb)
340+ shift = remainingBits
341+ }
342+ return bytes
343+}
344+
345+// natFromBytes converts a slice of big-endian bytes into a nat.
346+//
347+// The announced length of the output depends on the length of bytes. Unlike
348+// big.Int, creating a nat will not remove leading zeros.
349+func natFromBytes(bytes []byte) *nat {
350+ bitSize := len(bytes) * 8
351+ requiredLimbs := (bitSize + _W - 1) / _W
352+
353+ out := &nat{make([]uint, requiredLimbs)}
354+ outI := 0
355+ shift := 0
356+ for i := len(bytes) - 1; i >= 0; i-- {
357+ bi := bytes[i]
358+ out.limbs[outI] |= uint(bi) << shift
359+ shift += 8
360+ if shift >= _W {
361+ shift -= _W
362+ out.limbs[outI] &= _MASK
363+ outI++
364+ if shift > 0 {
365+ out.limbs[outI] = uint(bi) >> (8 - shift)
366+ }
367+ }
368+ }
369+ return out
370+}
371+
372+// cmpEq returns 1 if x == y, and 0 otherwise.
373+//
374+// Both operands must have the same announced length.
375+func (x *nat) cmpEq(y *nat) choice {
376+ // Eliminate bounds checks in the loop.
377+ size := len(x.limbs)
378+ xLimbs := x.limbs[:size]
379+ yLimbs := y.limbs[:size]
380+
381+ equal := yes
382+ for i := 0; i < size; i++ {
383+ equal &= ctEq(xLimbs[i], yLimbs[i])
384+ }
385+ return equal
386+}
387+
388+// cmpGeq returns 1 if x >= y, and 0 otherwise.
389+//
390+// Both operands must have the same announced length.
391+func (x *nat) cmpGeq(y *nat) choice {
392+ // Eliminate bounds checks in the loop.
393+ size := len(x.limbs)
394+ xLimbs := x.limbs[:size]
395+ yLimbs := y.limbs[:size]
396+
397+ var c uint
398+ for i := 0; i < size; i++ {
399+ c = (xLimbs[i] - yLimbs[i] - c) >> _W
400+ }
401+ // If there was a carry, then subtracting y underflowed, so
402+ // x is not greater than or equal to y.
403+ return not(choice(c))
404+}
405+
406+// assign sets x <- y if on == 1, and does nothing otherwise.
407+//
408+// Both operands must have the same announced length.
409+func (x *nat) assign(on choice, y *nat) *nat {
410+ // Eliminate bounds checks in the loop.
411+ size := len(x.limbs)
412+ xLimbs := x.limbs[:size]
413+ yLimbs := y.limbs[:size]
414+
415+ for i := 0; i < size; i++ {
416+ xLimbs[i] = ctSelect(on, yLimbs[i], xLimbs[i])
417+ }
418+ return x
419+}
420+
421+// add computes x += y if on == 1, and does nothing otherwise. It returns the
422+// carry of the addition regardless of on.
423+//
424+// Both operands must have the same announced length.
425+func (x *nat) add(on choice, y *nat) (c uint) {
426+ // Eliminate bounds checks in the loop.
427+ size := len(x.limbs)
428+ xLimbs := x.limbs[:size]
429+ yLimbs := y.limbs[:size]
430+
431+ for i := 0; i < size; i++ {
432+ res := xLimbs[i] + yLimbs[i] + c
433+ xLimbs[i] = ctSelect(on, res&_MASK, xLimbs[i])
434+ c = res >> _W
435+ }
436+ return
437+}
438+
439+// sub computes x -= y if on == 1, and does nothing otherwise. It returns the
440+// borrow of the subtraction regardless of on.
441+//
442+// Both operands must have the same announced length.
443+func (x *nat) sub(on choice, y *nat) (c uint) {
444+ // Eliminate bounds checks in the loop.
445+ size := len(x.limbs)
446+ xLimbs := x.limbs[:size]
447+ yLimbs := y.limbs[:size]
448+
449+ for i := 0; i < size; i++ {
450+ res := xLimbs[i] - yLimbs[i] - c
451+ xLimbs[i] = ctSelect(on, res&_MASK, xLimbs[i])
452+ c = res >> _W
453+ }
454+ return
455+}
456+
457+// modulus is used for modular arithmetic, precomputing relevant constants.
458+//
459+// Moduli are assumed to be odd numbers. Moduli can also leak the exact
460+// number of bits needed to store their value, and are stored without padding.
461+//
462+// Their actual value is still kept secret.
463+type modulus struct {
464+ // The underlying natural number for this modulus.
465+ //
466+ // This will be stored without any padding, and shouldn't alias with any
467+ // other natural number being used.
468+ nat *nat
469+ leading int // number of leading zeros in the modulus
470+ m0inv uint // -nat.limbs[0]⁻¹ mod _W
471+}
472+
473+// minusInverseModW computes -x⁻¹ mod _W with x odd.
474+//
475+// This operation is used to precompute a constant involved in Montgomery
476+// multiplication.
477+func minusInverseModW(x uint) uint {
478+ // Every iteration of this loop doubles the least-significant bits of
479+ // correct inverse in y. The first three bits are already correct (1⁻¹ = 1,
480+ // 3⁻¹ = 3, 5⁻¹ = 5, and 7⁻¹ = 7 mod 8), so doubling five times is enough
481+ // for 61 bits (and wastes only one iteration for 31 bits).
482+ //
483+ // See https://crypto.stackexchange.com/a/47496.
484+ y := x
485+ for i := 0; i < 5; i++ {
486+ y = y * (2 - x*y)
487+ }
488+ return (1 << _W) - (y & _MASK)
489+}
490+
491+// modulusFromNat creates a new modulus from a nat.
492+//
493+// The nat should be odd, nonzero, and the number of significant bits in the
494+// number should be leakable. The nat shouldn't be reused.
495+func modulusFromNat(nat *nat) *modulus {
496+ m := &modulus{}
497+ m.nat = nat
498+ size := len(m.nat.limbs)
499+ for m.nat.limbs[size-1] == 0 {
500+ size--
501+ }
502+ m.nat.limbs = m.nat.limbs[:size]
503+ m.leading = _W - bitLen(m.nat.limbs[size-1])
504+ m.m0inv = minusInverseModW(m.nat.limbs[0])
505+ return m
506+}
507+
508+// bitLen is a version of bits.Len that only leaks the bit length of n, but not
509+// its value. bits.Len and bits.LeadingZeros use a lookup table for the
510+// low-order bits on some architectures.
511+func bitLen(n uint) int {
512+ var len int
513+ // We assume, here and elsewhere, that comparison to zero is constant time
514+ // with respect to different non-zero values.
515+ for n != 0 {
516+ len++
517+ n >>= 1
518+ }
519+ return len
520+}
521+
522+// bigBitLen is a version of big.Int.BitLen that only leaks the bit length of x,
523+// but not its value. big.Int.BitLen uses bits.Len.
524+func bigBitLen(x *big.Int) int {
525+ xLimbs := x.Bits()
526+ fullLimbs := len(xLimbs) - 1
527+ topLimb := uint(xLimbs[len(xLimbs)-1])
528+ return fullLimbs*bits.UintSize + bitLen(topLimb)
529+}
530+
531+// modulusSize returns the size of m in bytes.
532+func modulusSize(m *modulus) int {
533+ bits := len(m.nat.limbs)*_W - int(m.leading)
534+ return (bits + 7) / 8
535+}
536+
537+// shiftIn calculates x = x << _W + y mod m.
538+//
539+// This assumes that x is already reduced mod m, and that y < 2^_W.
540+func (x *nat) shiftIn(y uint, m *modulus) *nat {
541+ d := new(nat).resetFor(m)
542+
543+ // Eliminate bounds checks in the loop.
544+ size := len(m.nat.limbs)
545+ xLimbs := x.limbs[:size]
546+ dLimbs := d.limbs[:size]
547+ mLimbs := m.nat.limbs[:size]
548+
549+ // Each iteration of this loop computes x = 2x + b mod m, where b is a bit
550+ // from y. Effectively, it left-shifts x and adds y one bit at a time,
551+ // reducing it every time.
552+ //
553+ // To do the reduction, each iteration computes both 2x + b and 2x + b - m.
554+ // The next iteration (and finally the return line) will use either result
555+ // based on whether the subtraction underflowed.
556+ needSubtraction := no
557+ for i := _W - 1; i >= 0; i-- {
558+ carry := (y >> i) & 1
559+ var borrow uint
560+ for i := 0; i < size; i++ {
561+ l := ctSelect(needSubtraction, dLimbs[i], xLimbs[i])
562+
563+ res := l<<1 + carry
564+ xLimbs[i] = res & _MASK
565+ carry = res >> _W
566+
567+ res = xLimbs[i] - mLimbs[i] - borrow
568+ dLimbs[i] = res & _MASK
569+ borrow = res >> _W
570+ }
571+ // See modAdd for how carry (aka overflow), borrow (aka underflow), and
572+ // needSubtraction relate.
573+ needSubtraction = ctEq(carry, borrow)
574+ }
575+ return x.assign(needSubtraction, d)
576+}
577+
578+// mod calculates out = x mod m.
579+//
580+// This works regardless how large the value of x is.
581+//
582+// The output will be resized to the size of m and overwritten.
583+func (out *nat) mod(x *nat, m *modulus) *nat {
584+ out.resetFor(m)
585+ // Working our way from the most significant to the least significant limb,
586+ // we can insert each limb at the least significant position, shifting all
587+ // previous limbs left by _W. This way each limb will get shifted by the
588+ // correct number of bits. We can insert at least N - 1 limbs without
589+ // overflowing m. After that, we need to reduce every time we shift.
590+ i := len(x.limbs) - 1
591+ // For the first N - 1 limbs we can skip the actual shifting and position
592+ // them at the shifted position, which starts at min(N - 2, i).
593+ start := len(m.nat.limbs) - 2
594+ if i < start {
595+ start = i
596+ }
597+ for j := start; j >= 0; j-- {
598+ out.limbs[j] = x.limbs[i]
599+ i--
600+ }
601+ // We shift in the remaining limbs, reducing modulo m each time.
602+ for i >= 0 {
603+ out.shiftIn(x.limbs[i], m)
604+ i--
605+ }
606+ return out
607+}
608+
609+// expandFor ensures out has the right size to work with operations modulo m.
610+//
611+// This assumes that out has as many or fewer limbs than m, or that the extra
612+// limbs are all zero (which may happen when decoding a value that has leading
613+// zeroes in its bytes representation that spill over the limb threshold).
614+func (out *nat) expandFor(m *modulus) *nat {
615+ return out.expand(len(m.nat.limbs))
616+}
617+
618+// resetFor ensures out has the right size to work with operations modulo m.
619+//
620+// out is zeroed and may start at any size.
621+func (out *nat) resetFor(m *modulus) *nat {
622+ return out.reset(len(m.nat.limbs))
623+}
624+
625+// modSub computes x = x - y mod m.
626+//
627+// The length of both operands must be the same as the modulus. Both operands
628+// must already be reduced modulo m.
629+func (x *nat) modSub(y *nat, m *modulus) *nat {
630+ underflow := x.sub(yes, y)
631+ // If the subtraction underflowed, add m.
632+ x.add(choice(underflow), m.nat)
633+ return x
634+}
635+
636+// modAdd computes x = x + y mod m.
637+//
638+// The length of both operands must be the same as the modulus. Both operands
639+// must already be reduced modulo m.
640+func (x *nat) modAdd(y *nat, m *modulus) *nat {
641+ overflow := x.add(yes, y)
642+ underflow := not(x.cmpGeq(m.nat)) // x < m
643+
644+ // Three cases are possible:
645+ //
646+ // - overflow = 0, underflow = 0
647+ //
648+ // In this case, addition fits in our limbs, but we can still subtract away
649+ // m without an underflow, so we need to perform the subtraction to reduce
650+ // our result.
651+ //
652+ // - overflow = 0, underflow = 1
653+ //
654+ // The addition fits in our limbs, but we can't subtract m without
655+ // underflowing. The result is already reduced.
656+ //
657+ // - overflow = 1, underflow = 1
658+ //
659+ // The addition does not fit in our limbs, and the subtraction's borrow
660+ // would cancel out with the addition's carry. We need to subtract m to
661+ // reduce our result.
662+ //
663+ // The overflow = 1, underflow = 0 case is not possible, because y is at
664+ // most m - 1, and if adding m - 1 overflows, then subtracting m must
665+ // necessarily underflow.
666+ needSubtraction := ctEq(overflow, uint(underflow))
667+
668+ x.sub(needSubtraction, m.nat)
669+ return x
670+}
671+
672+// montgomeryRepresentation calculates x = x * R mod m, with R = 2^(_W * n) and
673+// n = len(m.nat.limbs).
674+//
675+// Faster Montgomery multiplication replaces standard modular multiplication for
676+// numbers in this representation.
677+//
678+// This assumes that x is already reduced mod m.
679+func (x *nat) montgomeryRepresentation(m *modulus) *nat {
680+ for i := 0; i < len(m.nat.limbs); i++ {
681+ x.shiftIn(0, m) // x = x * 2^_W mod m
682+ }
683+ return x
684+}
685+
686+// montgomeryMul calculates d = a * b / R mod m, with R = 2^(_W * n) and
687+// n = len(m.nat.limbs), using the Montgomery Multiplication technique.
688+//
689+// All inputs should be the same length, not aliasing d, and already
690+// reduced modulo m. d will be resized to the size of m and overwritten.
691+func (d *nat) montgomeryMul(a *nat, b *nat, m *modulus) *nat {
692+ // See https://bearssl.org/bigint.html#montgomery-reduction-and-multiplication
693+ // for a description of the algorithm.
694+
695+ // Eliminate bounds checks in the loop.
696+ size := len(m.nat.limbs)
697+ aLimbs := a.limbs[:size]
698+ bLimbs := b.limbs[:size]
699+ dLimbs := d.resetFor(m).limbs[:size]
700+ mLimbs := m.nat.limbs[:size]
701+
702+ var overflow uint
703+ for i := 0; i < size; i++ {
704+ f := ((dLimbs[0] + aLimbs[i]*bLimbs[0]) * m.m0inv) & _MASK
705+ carry := uint(0)
706+ for j := 0; j < size; j++ {
707+ // z = d[j] + a[i] * b[j] + f * m[j] + carry <= 2^(2W+1) - 2^(W+1) + 2^W
708+ hi, lo := bits.Mul(aLimbs[i], bLimbs[j])
709+ z_lo, c := bits.Add(dLimbs[j], lo, 0)
710+ z_hi, _ := bits.Add(0, hi, c)
711+ hi, lo = bits.Mul(f, mLimbs[j])
712+ z_lo, c = bits.Add(z_lo, lo, 0)
713+ z_hi, _ = bits.Add(z_hi, hi, c)
714+ z_lo, c = bits.Add(z_lo, carry, 0)
715+ z_hi, _ = bits.Add(z_hi, 0, c)
716+ if j > 0 {
717+ dLimbs[j-1] = z_lo & _MASK
718+ }
719+ carry = z_hi<<1 | z_lo>>_W // carry <= 2^(W+1) - 2
720+ }
721+ z := overflow + carry // z <= 2^(W+1) - 1
722+ dLimbs[size-1] = z & _MASK
723+ overflow = z >> _W // overflow <= 1
724+ }
725+ // See modAdd for how overflow, underflow, and needSubtraction relate.
726+ underflow := not(d.cmpGeq(m.nat)) // d < m
727+ needSubtraction := ctEq(overflow, uint(underflow))
728+ d.sub(needSubtraction, m.nat)
729+
730+ return d
731+}
732+
733+// modMul calculates x *= y mod m.
734+//
735+// x and y must already be reduced modulo m, they must share its announced
736+// length, and they may not alias.
737+func (x *nat) modMul(y *nat, m *modulus) *nat {
738+ // A Montgomery multiplication by a value out of the Montgomery domain
739+ // takes the result out of Montgomery representation.
740+ xR := x.clone().montgomeryRepresentation(m) // xR = x * R mod m
741+ return x.montgomeryMul(xR, y, m) // x = xR * y / R mod m
742+}
743+
744+// exp calculates out = x^e mod m.
745+//
746+// The exponent e is represented in big-endian order. The output will be resized
747+// to the size of m and overwritten. x must already be reduced modulo m.
748+func (out *nat) exp(x *nat, e []byte, m *modulus) *nat {
749+ // We use a 4 bit window. For our RSA workload, 4 bit windows are faster
750+ // than 2 bit windows, but use an extra 12 nats worth of scratch space.
751+ // Using bit sizes that don't divide 8 are more complex to implement.
752+ table := make([]*nat, (1<<4)-1) // table[i] = x ^ (i+1)
753+ table[0] = x.clone().montgomeryRepresentation(m)
754+ for i := 1; i < len(table); i++ {
755+ table[i] = new(nat).expandFor(m)
756+ table[i].montgomeryMul(table[i-1], table[0], m)
757+ }
758+
759+ out.resetFor(m)
760+ out.limbs[0] = 1
761+ out.montgomeryRepresentation(m)
762+ t0 := new(nat).expandFor(m)
763+ t1 := new(nat).expandFor(m)
764+ for _, b := range e {
765+ for _, j := range []int{4, 0} {
766+ // Square four times.
767+ t1.montgomeryMul(out, out, m)
768+ out.montgomeryMul(t1, t1, m)
769+ t1.montgomeryMul(out, out, m)
770+ out.montgomeryMul(t1, t1, m)
771+
772+ // Select x^k in constant time from the table.
773+ k := uint((b >> j) & 0b1111)
774+ for i := range table {
775+ t0.assign(ctEq(k, uint(i+1)), table[i])
776+ }
777+
778+ // Multiply by x^k, discarding the result if k = 0.
779+ t1.montgomeryMul(out, t0, m)
780+ out.assign(not(ctEq(k, 0)), t1)
781+ }
782+ }
783+
784+ // By Montgomery multiplying with 1 not in Montgomery representation, we
785+ // convert out back from Montgomery representation, because it works out to
786+ // dividing by R.
787+ t0.assign(yes, out)
788+ t1.resetFor(m)
789+ t1.limbs[0] = 1
790+ out.montgomeryMul(t0, t1, m)
791+
792+ return out
793+}
794diff --git a/src/crypto/rsa/nat_test.go b/src/crypto/rsa/nat_test.go
795new file mode 100644
796index 0000000..3e6eb10
797--- /dev/null
798+++ b/src/crypto/rsa/nat_test.go
799@@ -0,0 +1,384 @@
800+// Copyright 2021 The Go Authors. All rights reserved.
801+// Use of this source code is governed by a BSD-style
802+// license that can be found in the LICENSE file.
803+
804+package rsa
805+
806+import (
807+ "bytes"
808+ "math/big"
809+ "math/bits"
810+ "math/rand"
811+ "reflect"
812+ "testing"
813+ "testing/quick"
814+)
815+
816+// Generate generates an even nat. It's used by testing/quick to produce random
817+// *nat values for quick.Check invocations.
818+func (*nat) Generate(r *rand.Rand, size int) reflect.Value {
819+ limbs := make([]uint, size)
820+ for i := 0; i < size; i++ {
821+ limbs[i] = uint(r.Uint64()) & ((1 << _W) - 2)
822+ }
823+ return reflect.ValueOf(&nat{limbs})
824+}
825+
826+func testModAddCommutative(a *nat, b *nat) bool {
827+ mLimbs := make([]uint, len(a.limbs))
828+ for i := 0; i < len(mLimbs); i++ {
829+ mLimbs[i] = _MASK
830+ }
831+ m := modulusFromNat(&nat{mLimbs})
832+ aPlusB := a.clone()
833+ aPlusB.modAdd(b, m)
834+ bPlusA := b.clone()
835+ bPlusA.modAdd(a, m)
836+ return aPlusB.cmpEq(bPlusA) == 1
837+}
838+
839+func TestModAddCommutative(t *testing.T) {
840+ err := quick.Check(testModAddCommutative, &quick.Config{})
841+ if err != nil {
842+ t.Error(err)
843+ }
844+}
845+
846+func testModSubThenAddIdentity(a *nat, b *nat) bool {
847+ mLimbs := make([]uint, len(a.limbs))
848+ for i := 0; i < len(mLimbs); i++ {
849+ mLimbs[i] = _MASK
850+ }
851+ m := modulusFromNat(&nat{mLimbs})
852+ original := a.clone()
853+ a.modSub(b, m)
854+ a.modAdd(b, m)
855+ return a.cmpEq(original) == 1
856+}
857+
858+func TestModSubThenAddIdentity(t *testing.T) {
859+ err := quick.Check(testModSubThenAddIdentity, &quick.Config{})
860+ if err != nil {
861+ t.Error(err)
862+ }
863+}
864+
865+func testMontgomeryRoundtrip(a *nat) bool {
866+ one := &nat{make([]uint, len(a.limbs))}
867+ one.limbs[0] = 1
868+ aPlusOne := a.clone()
869+ aPlusOne.add(1, one)
870+ m := modulusFromNat(aPlusOne)
871+ monty := a.clone()
872+ monty.montgomeryRepresentation(m)
873+ aAgain := monty.clone()
874+ aAgain.montgomeryMul(monty, one, m)
875+ return a.cmpEq(aAgain) == 1
876+}
877+
878+func TestMontgomeryRoundtrip(t *testing.T) {
879+ err := quick.Check(testMontgomeryRoundtrip, &quick.Config{})
880+ if err != nil {
881+ t.Error(err)
882+ }
883+}
884+
885+func TestFromBig(t *testing.T) {
886+ expected := []byte{0x01, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}
887+ theBig := new(big.Int).SetBytes(expected)
888+ actual := natFromBig(theBig).fillBytes(make([]byte, len(expected)))
889+ if !bytes.Equal(actual, expected) {
890+ t.Errorf("%+x != %+x", actual, expected)
891+ }
892+}
893+
894+func TestFillBytes(t *testing.T) {
895+ xBytes := []byte{0xAA, 0xFF, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, 0x88}
896+ x := natFromBytes(xBytes)
897+ for l := 20; l >= len(xBytes); l-- {
898+ buf := make([]byte, l)
899+ rand.Read(buf)
900+ actual := x.fillBytes(buf)
901+ expected := make([]byte, l)
902+ copy(expected[l-len(xBytes):], xBytes)
903+ if !bytes.Equal(actual, expected) {
904+ t.Errorf("%d: %+v != %+v", l, actual, expected)
905+ }
906+ }
907+ for l := len(xBytes) - 1; l >= 0; l-- {
908+ (func() {
909+ defer func() {
910+ if recover() == nil {
911+ t.Errorf("%d: expected panic", l)
912+ }
913+ }()
914+ x.fillBytes(make([]byte, l))
915+ })()
916+ }
917+}
918+
919+func TestFromBytes(t *testing.T) {
920+ f := func(xBytes []byte) bool {
921+ if len(xBytes) == 0 {
922+ return true
923+ }
924+ actual := natFromBytes(xBytes).fillBytes(make([]byte, len(xBytes)))
925+ if !bytes.Equal(actual, xBytes) {
926+ t.Errorf("%+x != %+x", actual, xBytes)
927+ return false
928+ }
929+ return true
930+ }
931+
932+ err := quick.Check(f, &quick.Config{})
933+ if err != nil {
934+ t.Error(err)
935+ }
936+
937+ f([]byte{0xFF, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, 0x88})
938+ f(bytes.Repeat([]byte{0xFF}, _W))
939+}
940+
941+func TestShiftIn(t *testing.T) {
942+ if bits.UintSize != 64 {
943+ t.Skip("examples are only valid in 64 bit")
944+ }
945+ examples := []struct {
946+ m, x, expected []byte
947+ y uint64
948+ }{{
949+ m: []byte{13},
950+ x: []byte{0},
951+ y: 0x7FFF_FFFF_FFFF_FFFF,
952+ expected: []byte{7},
953+ }, {
954+ m: []byte{13},
955+ x: []byte{7},
956+ y: 0x7FFF_FFFF_FFFF_FFFF,
957+ expected: []byte{11},
958+ }, {
959+ m: []byte{0x06, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0d},
960+ x: make([]byte, 9),
961+ y: 0x7FFF_FFFF_FFFF_FFFF,
962+ expected: []byte{0x00, 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff},
963+ }, {
964+ m: []byte{0x06, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0d},
965+ x: []byte{0x00, 0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff},
966+ y: 0,
967+ expected: []byte{0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x08},
968+ }}
969+
970+ for i, tt := range examples {
971+ m := modulusFromNat(natFromBytes(tt.m))
972+ got := natFromBytes(tt.x).expandFor(m).shiftIn(uint(tt.y), m)
973+ if got.cmpEq(natFromBytes(tt.expected).expandFor(m)) != 1 {
974+ t.Errorf("%d: got %x, expected %x", i, got, tt.expected)
975+ }
976+ }
977+}
978+
979+func TestModulusAndNatSizes(t *testing.T) {
980+ // These are 126 bit (2 * _W on 64-bit architectures) values, serialized as
981+ // 128 bits worth of bytes. If leading zeroes are stripped, they fit in two
982+ // limbs, if they are not, they fit in three. This can be a problem because
983+ // modulus strips leading zeroes and nat does not.
984+ m := modulusFromNat(natFromBytes([]byte{
985+ 0x3f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
986+ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff}))
987+ x := natFromBytes([]byte{
988+ 0x3f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
989+ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe})
990+ x.expandFor(m) // must not panic for shrinking
991+}
992+
993+func TestExpand(t *testing.T) {
994+ sliced := []uint{1, 2, 3, 4}
995+ examples := []struct {
996+ in []uint
997+ n int
998+ out []uint
999+ }{{
1000+ []uint{1, 2},
1001+ 4,
1002+ []uint{1, 2, 0, 0},
1003+ }, {
1004+ sliced[:2],
1005+ 4,
1006+ []uint{1, 2, 0, 0},
1007+ }, {
1008+ []uint{1, 2},
1009+ 2,
1010+ []uint{1, 2},
1011+ }, {
1012+ []uint{1, 2, 0},
1013+ 2,
1014+ []uint{1, 2},
1015+ }}
1016+
1017+ for i, tt := range examples {
1018+ got := (&nat{tt.in}).expand(tt.n)
1019+ if len(got.limbs) != len(tt.out) || got.cmpEq(&nat{tt.out}) != 1 {
1020+ t.Errorf("%d: got %x, expected %x", i, got, tt.out)
1021+ }
1022+ }
1023+}
1024+
1025+func TestMod(t *testing.T) {
1026+ m := modulusFromNat(natFromBytes([]byte{0x06, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0d}))
1027+ x := natFromBytes([]byte{0x40, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01})
1028+ out := new(nat)
1029+ out.mod(x, m)
1030+ expected := natFromBytes([]byte{0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x09})
1031+ if out.cmpEq(expected) != 1 {
1032+ t.Errorf("%+v != %+v", out, expected)
1033+ }
1034+}
1035+
1036+func TestModSub(t *testing.T) {
1037+ m := modulusFromNat(&nat{[]uint{13}})
1038+ x := &nat{[]uint{6}}
1039+ y := &nat{[]uint{7}}
1040+ x.modSub(y, m)
1041+ expected := &nat{[]uint{12}}
1042+ if x.cmpEq(expected) != 1 {
1043+ t.Errorf("%+v != %+v", x, expected)
1044+ }
1045+ x.modSub(y, m)
1046+ expected = &nat{[]uint{5}}
1047+ if x.cmpEq(expected) != 1 {
1048+ t.Errorf("%+v != %+v", x, expected)
1049+ }
1050+}
1051+
1052+func TestModAdd(t *testing.T) {
1053+ m := modulusFromNat(&nat{[]uint{13}})
1054+ x := &nat{[]uint{6}}
1055+ y := &nat{[]uint{7}}
1056+ x.modAdd(y, m)
1057+ expected := &nat{[]uint{0}}
1058+ if x.cmpEq(expected) != 1 {
1059+ t.Errorf("%+v != %+v", x, expected)
1060+ }
1061+ x.modAdd(y, m)
1062+ expected = &nat{[]uint{7}}
1063+ if x.cmpEq(expected) != 1 {
1064+ t.Errorf("%+v != %+v", x, expected)
1065+ }
1066+}
1067+
1068+func TestExp(t *testing.T) {
1069+ m := modulusFromNat(&nat{[]uint{13}})
1070+ x := &nat{[]uint{3}}
1071+ out := &nat{[]uint{0}}
1072+ out.exp(x, []byte{12}, m)
1073+ expected := &nat{[]uint{1}}
1074+ if out.cmpEq(expected) != 1 {
1075+ t.Errorf("%+v != %+v", out, expected)
1076+ }
1077+}
1078+
1079+func makeBenchmarkModulus() *modulus {
1080+ m := make([]uint, 32)
1081+ for i := 0; i < 32; i++ {
1082+ m[i] = _MASK
1083+ }
1084+ return modulusFromNat(&nat{limbs: m})
1085+}
1086+
1087+func makeBenchmarkValue() *nat {
1088+ x := make([]uint, 32)
1089+ for i := 0; i < 32; i++ {
1090+ x[i] = _MASK - 1
1091+ }
1092+ return &nat{limbs: x}
1093+}
1094+
1095+func makeBenchmarkExponent() []byte {
1096+ e := make([]byte, 256)
1097+ for i := 0; i < 32; i++ {
1098+ e[i] = 0xFF
1099+ }
1100+ return e
1101+}
1102+
1103+func BenchmarkModAdd(b *testing.B) {
1104+ x := makeBenchmarkValue()
1105+ y := makeBenchmarkValue()
1106+ m := makeBenchmarkModulus()
1107+
1108+ b.ResetTimer()
1109+ for i := 0; i < b.N; i++ {
1110+ x.modAdd(y, m)
1111+ }
1112+}
1113+
1114+func BenchmarkModSub(b *testing.B) {
1115+ x := makeBenchmarkValue()
1116+ y := makeBenchmarkValue()
1117+ m := makeBenchmarkModulus()
1118+
1119+ b.ResetTimer()
1120+ for i := 0; i < b.N; i++ {
1121+ x.modSub(y, m)
1122+ }
1123+}
1124+
1125+func BenchmarkMontgomeryRepr(b *testing.B) {
1126+ x := makeBenchmarkValue()
1127+ m := makeBenchmarkModulus()
1128+
1129+ b.ResetTimer()
1130+ for i := 0; i < b.N; i++ {
1131+ x.montgomeryRepresentation(m)
1132+ }
1133+}
1134+
1135+func BenchmarkMontgomeryMul(b *testing.B) {
1136+ x := makeBenchmarkValue()
1137+ y := makeBenchmarkValue()
1138+ out := makeBenchmarkValue()
1139+ m := makeBenchmarkModulus()
1140+
1141+ b.ResetTimer()
1142+ for i := 0; i < b.N; i++ {
1143+ out.montgomeryMul(x, y, m)
1144+ }
1145+}
1146+
1147+func BenchmarkModMul(b *testing.B) {
1148+ x := makeBenchmarkValue()
1149+ y := makeBenchmarkValue()
1150+ m := makeBenchmarkModulus()
1151+
1152+ b.ResetTimer()
1153+ for i := 0; i < b.N; i++ {
1154+ x.modMul(y, m)
1155+ }
1156+}
1157+
1158+func BenchmarkExpBig(b *testing.B) {
1159+ out := new(big.Int)
1160+ exponentBytes := makeBenchmarkExponent()
1161+ x := new(big.Int).SetBytes(exponentBytes)
1162+ e := new(big.Int).SetBytes(exponentBytes)
1163+ n := new(big.Int).SetBytes(exponentBytes)
1164+ one := new(big.Int).SetUint64(1)
1165+ n.Add(n, one)
1166+
1167+ b.ResetTimer()
1168+ for i := 0; i < b.N; i++ {
1169+ out.Exp(x, e, n)
1170+ }
1171+}
1172+
1173+func BenchmarkExp(b *testing.B) {
1174+ x := makeBenchmarkValue()
1175+ e := makeBenchmarkExponent()
1176+ out := makeBenchmarkValue()
1177+ m := makeBenchmarkModulus()
1178+
1179+ b.ResetTimer()
1180+ for i := 0; i < b.N; i++ {
1181+ out.exp(x, e, m)
1182+ }
1183+}
1184diff --git a/src/crypto/rsa/pkcs1v15.go b/src/crypto/rsa/pkcs1v15.go
1185index a216be3..ce89f92 100644
1186--- a/src/crypto/rsa/pkcs1v15.go
1187+++ b/src/crypto/rsa/pkcs1v15.go
1188@@ -9,7 +9,6 @@ import (
1189 "crypto/subtle"
1190 "errors"
1191 "io"
1192- "math/big"
1193
1194 "crypto/internal/randutil"
1195 )
1196@@ -58,14 +57,11 @@ func EncryptPKCS1v15(rand io.Reader, pub *PublicKey, msg []byte) ([]byte, error)
1197 em[len(em)-len(msg)-1] = 0
1198 copy(mm, msg)
1199
1200- m := new(big.Int).SetBytes(em)
1201- c := encrypt(new(big.Int), pub, m)
1202-
1203- return c.FillBytes(em), nil
1204+ return encrypt(pub, em), nil
1205 }
1206
1207 // DecryptPKCS1v15 decrypts a plaintext using RSA and the padding scheme from PKCS#1 v1.5.
1208-// If rand != nil, it uses RSA blinding to avoid timing side-channel attacks.
1209+// The rand parameter is legacy and ignored, and it can be as nil.
1210 //
1211 // Note that whether this function returns an error or not discloses secret
1212 // information. If an attacker can cause this function to run repeatedly and
1213@@ -76,7 +72,7 @@ func DecryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) ([]byt
1214 if err := checkPub(&priv.PublicKey); err != nil {
1215 return nil, err
1216 }
1217- valid, out, index, err := decryptPKCS1v15(rand, priv, ciphertext)
1218+ valid, out, index, err := decryptPKCS1v15(priv, ciphertext)
1219 if err != nil {
1220 return nil, err
1221 }
1222@@ -87,7 +83,7 @@ func DecryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) ([]byt
1223 }
1224
1225 // DecryptPKCS1v15SessionKey decrypts a session key using RSA and the padding scheme from PKCS#1 v1.5.
1226-// If rand != nil, it uses RSA blinding to avoid timing side-channel attacks.
1227+// The rand parameter is legacy and ignored, and it can be as nil.
1228 // It returns an error if the ciphertext is the wrong length or if the
1229 // ciphertext is greater than the public modulus. Otherwise, no error is
1230 // returned. If the padding is valid, the resulting plaintext message is copied
1231@@ -114,7 +110,7 @@ func DecryptPKCS1v15SessionKey(rand io.Reader, priv *PrivateKey, ciphertext []by
1232 return ErrDecryption
1233 }
1234
1235- valid, em, index, err := decryptPKCS1v15(rand, priv, ciphertext)
1236+ valid, em, index, err := decryptPKCS1v15(priv, ciphertext)
1237 if err != nil {
1238 return err
1239 }
1240@@ -130,26 +126,24 @@ func DecryptPKCS1v15SessionKey(rand io.Reader, priv *PrivateKey, ciphertext []by
1241 return nil
1242 }
1243
1244-// decryptPKCS1v15 decrypts ciphertext using priv and blinds the operation if
1245-// rand is not nil. It returns one or zero in valid that indicates whether the
1246-// plaintext was correctly structured. In either case, the plaintext is
1247-// returned in em so that it may be read independently of whether it was valid
1248-// in order to maintain constant memory access patterns. If the plaintext was
1249-// valid then index contains the index of the original message in em.
1250-func decryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) (valid int, em []byte, index int, err error) {
1251+// decryptPKCS1v15 decrypts ciphertext using priv. It returns one or zero in
1252+// valid that indicates whether the plaintext was correctly structured.
1253+// In either case, the plaintext is returned in em so that it may be read
1254+// independently of whether it was valid in order to maintain constant memory
1255+// access patterns. If the plaintext was valid then index contains the index of
1256+// the original message in em, to allow constant time padding removal.
1257+func decryptPKCS1v15(priv *PrivateKey, ciphertext []byte) (valid int, em []byte, index int, err error) {
1258 k := priv.Size()
1259 if k < 11 {
1260 err = ErrDecryption
1261 return
1262 }
1263
1264- c := new(big.Int).SetBytes(ciphertext)
1265- m, err := decrypt(rand, priv, c)
1266+ em, err = decrypt(priv, ciphertext)
1267 if err != nil {
1268 return
1269 }
1270
1271- em = m.FillBytes(make([]byte, k))
1272 firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
1273 secondByteIsTwo := subtle.ConstantTimeByteEq(em[1], 2)
1274
1275@@ -221,8 +215,7 @@ var hashPrefixes = map[crypto.Hash][]byte{
1276 // function. If hash is zero, hashed is signed directly. This isn't
1277 // advisable except for interoperability.
1278 //
1279-// If rand is not nil then RSA blinding will be used to avoid timing
1280-// side-channel attacks.
1281+// The rand parameter is legacy and ignored, and it can be as nil.
1282 //
1283 // This function is deterministic. Thus, if the set of possible
1284 // messages is small, an attacker may be able to build a map from
1285@@ -249,13 +242,7 @@ func SignPKCS1v15(rand io.Reader, priv *PrivateKey, hash crypto.Hash, hashed []b
1286 copy(em[k-tLen:k-hashLen], prefix)
1287 copy(em[k-hashLen:k], hashed)
1288
1289- m := new(big.Int).SetBytes(em)
1290- c, err := decryptAndCheck(rand, priv, m)
1291- if err != nil {
1292- return nil, err
1293- }
1294-
1295- return c.FillBytes(em), nil
1296+ return decryptAndCheck(priv, em)
1297 }
1298
1299 // VerifyPKCS1v15 verifies an RSA PKCS#1 v1.5 signature.
1300@@ -275,9 +262,7 @@ func VerifyPKCS1v15(pub *PublicKey, hash crypto.Hash, hashed []byte, sig []byte)
1301 return ErrVerification
1302 }
1303
1304- c := new(big.Int).SetBytes(sig)
1305- m := encrypt(new(big.Int), pub, c)
1306- em := m.FillBytes(make([]byte, k))
1307+ em := encrypt(pub, sig)
1308 // EM = 0x00 || 0x01 || PS || 0x00 || T
1309
1310 ok := subtle.ConstantTimeByteEq(em[0], 0)
1311diff --git a/src/crypto/rsa/pss.go b/src/crypto/rsa/pss.go
1312index 814522d..eaba4be 100644
1313--- a/src/crypto/rsa/pss.go
1314+++ b/src/crypto/rsa/pss.go
1315@@ -12,7 +12,6 @@ import (
1316 "errors"
1317 "hash"
1318 "io"
1319- "math/big"
1320 )
1321
1322 // Per RFC 8017, Section 9.1
1323@@ -207,19 +206,27 @@ func emsaPSSVerify(mHash, em []byte, emBits, sLen int, hash hash.Hash) error {
1324 // Note that hashed must be the result of hashing the input message using the
1325 // given hash function. salt is a random sequence of bytes whose length will be
1326 // later used to verify the signature.
1327-func signPSSWithSalt(rand io.Reader, priv *PrivateKey, hash crypto.Hash, hashed, salt []byte) ([]byte, error) {
1328- emBits := priv.N.BitLen() - 1
1329+func signPSSWithSalt(priv *PrivateKey, hash crypto.Hash, hashed, salt []byte) ([]byte, error) {
1330+ emBits := bigBitLen(priv.N) - 1
1331 em, err := emsaPSSEncode(hashed, emBits, salt, hash.New())
1332 if err != nil {
1333 return nil, err
1334 }
1335- m := new(big.Int).SetBytes(em)
1336- c, err := decryptAndCheck(rand, priv, m)
1337- if err != nil {
1338- return nil, err
1339+
1340+ // RFC 8017: "Note that the octet length of EM will be one less than k if
1341+ // modBits - 1 is divisible by 8 and equal to k otherwise, where k is the
1342+ // length in octets of the RSA modulus n."
1343+ //
1344+ // This is extremely annoying, as all other encrypt and decrypt inputs are
1345+ // always the exact same size as the modulus. Since it only happens for
1346+ // weird modulus sizes, fix it by padding inefficiently.
1347+ if emLen, k := len(em), priv.Size(); emLen < k {
1348+ emNew := make([]byte, k)
1349+ copy(emNew[k-emLen:], em)
1350+ em = emNew
1351 }
1352- s := make([]byte, priv.Size())
1353- return c.FillBytes(s), nil
1354+
1355+ return decryptAndCheck(priv, em)
1356 }
1357
1358 const (
1359@@ -269,7 +276,7 @@ func SignPSS(rand io.Reader, priv *PrivateKey, hash crypto.Hash, digest []byte,
1360 saltLength := opts.saltLength()
1361 switch saltLength {
1362 case PSSSaltLengthAuto:
1363- saltLength = (priv.N.BitLen()-1+7)/8 - 2 - hash.Size()
1364+ saltLength = (bigBitLen(priv.N)-1+7)/8 - 2 - hash.Size()
1365 case PSSSaltLengthEqualsHash:
1366 saltLength = hash.Size()
1367 }
1368@@ -278,7 +285,7 @@ func SignPSS(rand io.Reader, priv *PrivateKey, hash crypto.Hash, digest []byte,
1369 if _, err := io.ReadFull(rand, salt); err != nil {
1370 return nil, err
1371 }
1372- return signPSSWithSalt(rand, priv, hash, digest, salt)
1373+ return signPSSWithSalt(priv, hash, digest, salt)
1374 }
1375
1376 // VerifyPSS verifies a PSS signature.
1377@@ -291,13 +298,22 @@ func VerifyPSS(pub *PublicKey, hash crypto.Hash, digest []byte, sig []byte, opts
1378 if len(sig) != pub.Size() {
1379 return ErrVerification
1380 }
1381- s := new(big.Int).SetBytes(sig)
1382- m := encrypt(new(big.Int), pub, s)
1383- emBits := pub.N.BitLen() - 1
1384+
1385+ emBits := bigBitLen(pub.N) - 1
1386 emLen := (emBits + 7) / 8
1387- if m.BitLen() > emLen*8 {
1388- return ErrVerification
1389+ em := encrypt(pub, sig)
1390+
1391+ // Like in signPSSWithSalt, deal with mismatches between emLen and the size
1392+ // of the modulus. The spec would have us wire emLen into the encoding
1393+ // function, but we'd rather always encode to the size of the modulus and
1394+ // then strip leading zeroes if necessary. This only happens for weird
1395+ // modulus sizes anyway.
1396+ for len(em) > emLen && len(em) > 0 {
1397+ if em[0] != 0 {
1398+ return ErrVerification
1399+ }
1400+ em = em[1:]
1401 }
1402- em := m.FillBytes(make([]byte, emLen))
1403+
1404 return emsaPSSVerify(digest, em, emBits, opts.saltLength(), hash.New())
1405 }
1406diff --git a/src/crypto/rsa/pss_test.go b/src/crypto/rsa/pss_test.go
1407index c3a6d46..d018b43 100644
1408--- a/src/crypto/rsa/pss_test.go
1409+++ b/src/crypto/rsa/pss_test.go
1410@@ -233,7 +233,10 @@ func TestPSSSigning(t *testing.T) {
1411 }
1412 }
1413
1414-func TestSignWithPSSSaltLengthAuto(t *testing.T) {
1415+func TestPSS513(t *testing.T) {
1416+ // See Issue 42741, and separately, RFC 8017: "Note that the octet length of
1417+ // EM will be one less than k if modBits - 1 is divisible by 8 and equal to
1418+ // k otherwise, where k is the length in octets of the RSA modulus n."
1419 key, err := GenerateKey(rand.Reader, 513)
1420 if err != nil {
1421 t.Fatal(err)
1422@@ -246,8 +249,9 @@ func TestSignWithPSSSaltLengthAuto(t *testing.T) {
1423 if err != nil {
1424 t.Fatal(err)
1425 }
1426- if len(signature) == 0 {
1427- t.Fatal("empty signature returned")
1428+ err = VerifyPSS(&key.PublicKey, crypto.SHA256, digest[:], signature, nil)
1429+ if err != nil {
1430+ t.Error(err)
1431 }
1432 }
1433
1434diff --git a/src/crypto/rsa/rsa.go b/src/crypto/rsa/rsa.go
1435index 5a00ed2..29d9d31 100644
1436--- a/src/crypto/rsa/rsa.go
1437+++ b/src/crypto/rsa/rsa.go
1438@@ -19,13 +19,17 @@
1439 // over the public key primitive, the PrivateKey type implements the
1440 // Decrypter and Signer interfaces from the crypto package.
1441 //
1442-// The RSA operations in this package are not implemented using constant-time algorithms.
1443+// Operations in this package are implemented using constant-time algorithms,
1444+// except for [GenerateKey], [PrivateKey.Precompute], and [PrivateKey.Validate].
1445+// Every other operation only leaks the bit size of the involved values, which
1446+// all depend on the selected key size.
1447 package rsa
1448
1449 import (
1450 "crypto"
1451 "crypto/rand"
1452 "crypto/subtle"
1453+ "encoding/binary"
1454 "errors"
1455 "hash"
1456 "io"
1457@@ -35,7 +39,6 @@ import (
1458 "crypto/internal/randutil"
1459 )
1460
1461-var bigZero = big.NewInt(0)
1462 var bigOne = big.NewInt(1)
1463
1464 // A PublicKey represents the public part of an RSA key.
1465@@ -47,7 +50,7 @@ type PublicKey struct {
1466 // Size returns the modulus size in bytes. Raw signatures and ciphertexts
1467 // for or by this public key will have the same size.
1468 func (pub *PublicKey) Size() int {
1469- return (pub.N.BitLen() + 7) / 8
1470+ return (bigBitLen(pub.N) + 7) / 8
1471 }
1472
1473 // OAEPOptions is an interface for passing options to OAEP decryption using the
1474@@ -351,10 +354,19 @@ func mgf1XOR(out []byte, hash hash.Hash, seed []byte) {
1475 // too large for the size of the public key.
1476 var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA public key size")
1477
1478-func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int {
1479- e := big.NewInt(int64(pub.E))
1480- c.Exp(m, e, pub.N)
1481- return c
1482+func encrypt(pub *PublicKey, plaintext []byte) []byte {
1483+
1484+ N := modulusFromNat(natFromBig(pub.N))
1485+ m := natFromBytes(plaintext).expandFor(N)
1486+
1487+ e := make([]byte, 8)
1488+ binary.BigEndian.PutUint64(e, uint64(pub.E))
1489+ for len(e) > 1 && e[0] == 0 {
1490+ e = e[1:]
1491+ }
1492+
1493+ out := make([]byte, modulusSize(N))
1494+ return new(nat).exp(m, e, N).fillBytes(out)
1495 }
1496
1497 // EncryptOAEP encrypts the given message with RSA-OAEP.
1498@@ -404,12 +416,7 @@ func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, l
1499 mgf1XOR(db, hash, seed)
1500 mgf1XOR(seed, hash, db)
1501
1502- m := new(big.Int)
1503- m.SetBytes(em)
1504- c := encrypt(new(big.Int), pub, m)
1505-
1506- out := make([]byte, k)
1507- return c.FillBytes(out), nil
1508+ return encrypt(pub, em), nil
1509 }
1510
1511 // ErrDecryption represents a failure to decrypt a message.
1512@@ -451,98 +458,71 @@ func (priv *PrivateKey) Precompute() {
1513 }
1514 }
1515
1516-// decrypt performs an RSA decryption, resulting in a plaintext integer. If a
1517-// random source is given, RSA blinding is used.
1518-func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
1519- // TODO(agl): can we get away with reusing blinds?
1520- if c.Cmp(priv.N) > 0 {
1521- err = ErrDecryption
1522- return
1523+// decrypt performs an RSA decryption of ciphertext into out.
1524+func decrypt(priv *PrivateKey, ciphertext []byte) ([]byte, error) {
1525+
1526+ N := modulusFromNat(natFromBig(priv.N))
1527+ c := natFromBytes(ciphertext).expandFor(N)
1528+ if c.cmpGeq(N.nat) == 1 {
1529+ return nil, ErrDecryption
1530 }
1531 if priv.N.Sign() == 0 {
1532 return nil, ErrDecryption
1533 }
1534
1535- var ir *big.Int
1536- if random != nil {
1537- randutil.MaybeReadByte(random)
1538-
1539- // Blinding enabled. Blinding involves multiplying c by r^e.
1540- // Then the decryption operation performs (m^e * r^e)^d mod n
1541- // which equals mr mod n. The factor of r can then be removed
1542- // by multiplying by the multiplicative inverse of r.
1543-
1544- var r *big.Int
1545- ir = new(big.Int)
1546- for {
1547- r, err = rand.Int(random, priv.N)
1548- if err != nil {
1549- return
1550- }
1551- if r.Cmp(bigZero) == 0 {
1552- r = bigOne
1553- }
1554- ok := ir.ModInverse(r, priv.N)
1555- if ok != nil {
1556- break
1557- }
1558- }
1559- bigE := big.NewInt(int64(priv.E))
1560- rpowe := new(big.Int).Exp(r, bigE, priv.N) // N != 0
1561- cCopy := new(big.Int).Set(c)
1562- cCopy.Mul(cCopy, rpowe)
1563- cCopy.Mod(cCopy, priv.N)
1564- c = cCopy
1565- }
1566-
1567+ // Note that because our private decryption exponents are stored as big.Int,
1568+ // we potentially leak the exact number of bits of these exponents. This
1569+ // isn't great, but should be fine.
1570 if priv.Precomputed.Dp == nil {
1571- m = new(big.Int).Exp(c, priv.D, priv.N)
1572- } else {
1573- // We have the precalculated values needed for the CRT.
1574- m = new(big.Int).Exp(c, priv.Precomputed.Dp, priv.Primes[0])
1575- m2 := new(big.Int).Exp(c, priv.Precomputed.Dq, priv.Primes[1])
1576- m.Sub(m, m2)
1577- if m.Sign() < 0 {
1578- m.Add(m, priv.Primes[0])
1579- }
1580- m.Mul(m, priv.Precomputed.Qinv)
1581- m.Mod(m, priv.Primes[0])
1582- m.Mul(m, priv.Primes[1])
1583- m.Add(m, m2)
1584-
1585- for i, values := range priv.Precomputed.CRTValues {
1586- prime := priv.Primes[2+i]
1587- m2.Exp(c, values.Exp, prime)
1588- m2.Sub(m2, m)
1589- m2.Mul(m2, values.Coeff)
1590- m2.Mod(m2, prime)
1591- if m2.Sign() < 0 {
1592- m2.Add(m2, prime)
1593- }
1594- m2.Mul(m2, values.R)
1595- m.Add(m, m2)
1596- }
1597- }
1598-
1599- if ir != nil {
1600- // Unblind.
1601- m.Mul(m, ir)
1602- m.Mod(m, priv.N)
1603- }
1604-
1605- return
1606+ out := make([]byte, modulusSize(N))
1607+ return new(nat).exp(c, priv.D.Bytes(), N).fillBytes(out), nil
1608+ }
1609+
1610+ t0 := new(nat)
1611+ P := modulusFromNat(natFromBig(priv.Primes[0]))
1612+ Q := modulusFromNat(natFromBig(priv.Primes[1]))
1613+ // m = c ^ Dp mod p
1614+ m := new(nat).exp(t0.mod(c, P), priv.Precomputed.Dp.Bytes(), P)
1615+ // m2 = c ^ Dq mod q
1616+ m2 := new(nat).exp(t0.mod(c, Q), priv.Precomputed.Dq.Bytes(), Q)
1617+ // m = m - m2 mod p
1618+ m.modSub(t0.mod(m2, P), P)
1619+ // m = m * Qinv mod p
1620+ m.modMul(natFromBig(priv.Precomputed.Qinv).expandFor(P), P)
1621+ // m = m * q mod N
1622+ m.expandFor(N).modMul(t0.mod(Q.nat, N), N)
1623+ // m = m + m2 mod N
1624+ m.modAdd(m2.expandFor(N), N)
1625+
1626+ for i, values := range priv.Precomputed.CRTValues {
1627+ p := modulusFromNat(natFromBig(priv.Primes[2+i]))
1628+ // m2 = c ^ Exp mod p
1629+ m2.exp(t0.mod(c, p), values.Exp.Bytes(), p)
1630+ // m2 = m2 - m mod p
1631+ m2.modSub(t0.mod(m, p), p)
1632+ // m2 = m2 * Coeff mod p
1633+ m2.modMul(natFromBig(values.Coeff).expandFor(p), p)
1634+ // m2 = m2 * R mod N
1635+ R := natFromBig(values.R).expandFor(N)
1636+ m2.expandFor(N).modMul(R, N)
1637+ // m = m + m2 mod N
1638+ m.modAdd(m2, N)
1639+ }
1640+
1641+ out := make([]byte, modulusSize(N))
1642+ return m.fillBytes(out), nil
1643 }
1644
1645-func decryptAndCheck(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
1646- m, err = decrypt(random, priv, c)
1647+func decryptAndCheck(priv *PrivateKey, ciphertext []byte) (m []byte, err error) {
1648+ m, err = decrypt(priv, ciphertext)
1649 if err != nil {
1650 return nil, err
1651 }
1652
1653 // In order to defend against errors in the CRT computation, m^e is
1654 // calculated, which should match the original ciphertext.
1655- check := encrypt(new(big.Int), &priv.PublicKey, m)
1656- if c.Cmp(check) != 0 {
1657+ check := encrypt(&priv.PublicKey, m)
1658+ if subtle.ConstantTimeCompare(ciphertext, check) != 1 {
1659 return nil, errors.New("rsa: internal error")
1660 }
1661 return m, nil
1662@@ -554,9 +534,7 @@ func decryptAndCheck(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int
1663 // Encryption and decryption of a given message must use the same hash function
1664 // and sha256.New() is a reasonable choice.
1665 //
1666-// The random parameter, if not nil, is used to blind the private-key operation
1667-// and avoid timing side-channel attacks. Blinding is purely internal to this
1668-// function – the random data need not match that used when encrypting.
1669+// The random parameter is legacy and ignored, and it can be as nil.
1670 //
1671 // The label parameter must match the value given when encrypting. See
1672 // EncryptOAEP for details.
1673@@ -570,9 +548,7 @@ func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext
1674 return nil, ErrDecryption
1675 }
1676
1677- c := new(big.Int).SetBytes(ciphertext)
1678-
1679- m, err := decrypt(random, priv, c)
1680+ em, err := decrypt(priv, ciphertext)
1681 if err != nil {
1682 return nil, err
1683 }
1684@@ -581,10 +557,6 @@ func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext
1685 lHash := hash.Sum(nil)
1686 hash.Reset()
1687
1688- // We probably leak the number of leading zeros.
1689- // It's not clear that we can do anything about this.
1690- em := m.FillBytes(make([]byte, k))
1691-
1692 firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
1693
1694 seed := em[1 : hash.Size()+1]
1695--
16962.25.1
1697
generated by cgit v1.2.3-54-g00ecf (git 2.39.0) at 2024-05-05 22:42:36 +0000