pkcs1v22.mx raw
1 // Copyright 2013 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 package rsa
6
7 // This file implements the RSASSA-PSS signature scheme and the RSAES-OAEP
8 // encryption scheme according to RFC 8017, aka PKCS #1 v2.2.
9
10 import (
11 "bytes"
12 "crypto/internal/fips140"
13 "crypto/internal/fips140/drbg"
14 "crypto/internal/fips140/sha256"
15 "crypto/internal/fips140/sha3"
16 "crypto/internal/fips140/sha512"
17 "crypto/internal/fips140/subtle"
18 "errors"
19 "hash"
20 "io"
21 )
22
23 // Per RFC 8017, Section 9.1
24 //
25 // EM = MGF1 xor DB || H( 8*0x00 || mHash || salt ) || 0xbc
26 //
27 // where
28 //
29 // DB = PS || 0x01 || salt
30 //
31 // and PS can be empty so
32 //
33 // emLen = dbLen + hLen + 1 = psLen + sLen + hLen + 2
34 //
35
36 // incCounter increments a four byte, big-endian counter.
37 func incCounter(c *[4]byte) {
38 if c[3]++; c[3] != 0 {
39 return
40 }
41 if c[2]++; c[2] != 0 {
42 return
43 }
44 if c[1]++; c[1] != 0 {
45 return
46 }
47 c[0]++
48 }
49
50 // mgf1XOR XORs the bytes in out with a mask generated using the MGF1 function
51 // specified in PKCS #1 v2.1.
52 func mgf1XOR(out []byte, hash hash.Hash, seed []byte) {
53 var counter [4]byte
54 var digest []byte
55
56 done := 0
57 for done < len(out) {
58 hash.Reset()
59 hash.Write(seed)
60 hash.Write(counter[0:4])
61 digest = hash.Sum(digest[:0])
62
63 for i := 0; i < len(digest) && done < len(out); i++ {
64 out[done] ^= digest[i]
65 done++
66 }
67 incCounter(&counter)
68 }
69 }
70
71 func emsaPSSEncode(mHash []byte, emBits int, salt []byte, hash hash.Hash) ([]byte, error) {
72 // See RFC 8017, Section 9.1.1.
73
74 hLen := hash.Size()
75 sLen := len(salt)
76 emLen := (emBits + 7) / 8
77
78 // 1. If the length of M is greater than the input limitation for the
79 // hash function (2^61 - 1 octets for SHA-1), output "message too
80 // long" and stop.
81 //
82 // 2. Let mHash = Hash(M), an octet string of length hLen.
83
84 if len(mHash) != hLen {
85 return nil, errors.New("crypto/rsa: input must be hashed with given hash")
86 }
87
88 // 3. If emLen < hLen + sLen + 2, output "encoding error" and stop.
89
90 if emLen < hLen+sLen+2 {
91 return nil, ErrMessageTooLong
92 }
93
94 em := []byte{:emLen}
95 psLen := emLen - sLen - hLen - 2
96 db := em[:psLen+1+sLen]
97 h := em[psLen+1+sLen : emLen-1]
98
99 // 4. Generate a random octet string salt of length sLen; if sLen = 0,
100 // then salt is the empty string.
101 //
102 // 5. Let
103 // M' = (0x)00 00 00 00 00 00 00 00 || mHash || salt;
104 //
105 // M' is an octet string of length 8 + hLen + sLen with eight
106 // initial zero octets.
107 //
108 // 6. Let H = Hash(M'), an octet string of length hLen.
109
110 var prefix [8]byte
111
112 hash.Reset()
113 hash.Write(prefix[:])
114 hash.Write(mHash)
115 hash.Write(salt)
116
117 h = hash.Sum(h[:0])
118
119 // 7. Generate an octet string PS consisting of emLen - sLen - hLen - 2
120 // zero octets. The length of PS may be 0.
121 //
122 // 8. Let DB = PS || 0x01 || salt; DB is an octet string of length
123 // emLen - hLen - 1.
124
125 db[psLen] = 0x01
126 copy(db[psLen+1:], salt)
127
128 // 9. Let dbMask = MGF(H, emLen - hLen - 1).
129 //
130 // 10. Let maskedDB = DB \xor dbMask.
131
132 mgf1XOR(db, hash, h)
133
134 // 11. Set the leftmost 8 * emLen - emBits bits of the leftmost octet in
135 // maskedDB to zero.
136
137 db[0] &= 0xff >> (8*emLen - emBits)
138
139 // 12. Let EM = maskedDB || H || 0xbc.
140 em[emLen-1] = 0xbc
141
142 // 13. Output EM.
143 return em, nil
144 }
145
146 const pssSaltLengthAutodetect = -1
147
148 func emsaPSSVerify(mHash, em []byte, emBits, sLen int, hash hash.Hash) error {
149 // See RFC 8017, Section 9.1.2.
150
151 hLen := hash.Size()
152 emLen := (emBits + 7) / 8
153 if emLen != len(em) {
154 return errors.New("rsa: internal error: inconsistent length")
155 }
156
157 // 1. If the length of M is greater than the input limitation for the
158 // hash function (2^61 - 1 octets for SHA-1), output "inconsistent"
159 // and stop.
160 //
161 // 2. Let mHash = Hash(M), an octet string of length hLen.
162 if hLen != len(mHash) {
163 return ErrVerification
164 }
165
166 // 3. If emLen < hLen + sLen + 2, output "inconsistent" and stop.
167 if emLen < hLen+sLen+2 {
168 return ErrVerification
169 }
170
171 // 4. If the rightmost octet of EM does not have hexadecimal value
172 // 0xbc, output "inconsistent" and stop.
173 if em[emLen-1] != 0xbc {
174 return ErrVerification
175 }
176
177 // 5. Let maskedDB be the leftmost emLen - hLen - 1 octets of EM, and
178 // let H be the next hLen octets.
179 db := em[:emLen-hLen-1]
180 h := em[emLen-hLen-1 : emLen-1]
181
182 // 6. If the leftmost 8 * emLen - emBits bits of the leftmost octet in
183 // maskedDB are not all equal to zero, output "inconsistent" and
184 // stop.
185 var bitMask byte = 0xff >> (8*emLen - emBits)
186 if em[0] & ^bitMask != 0 {
187 return ErrVerification
188 }
189
190 // 7. Let dbMask = MGF(H, emLen - hLen - 1).
191 //
192 // 8. Let DB = maskedDB \xor dbMask.
193 mgf1XOR(db, hash, h)
194
195 // 9. Set the leftmost 8 * emLen - emBits bits of the leftmost octet in DB
196 // to zero.
197 db[0] &= bitMask
198
199 // If we don't know the salt length, look for the 0x01 delimiter.
200 if sLen == pssSaltLengthAutodetect {
201 psLen := bytes.IndexByte(db, 0x01)
202 if psLen < 0 {
203 return ErrVerification
204 }
205 sLen = len(db) - psLen - 1
206 }
207
208 // FIPS 186-5, Section 5.4(g): "the length (in bytes) of the salt (sLen)
209 // shall satisfy 0 ≤ sLen ≤ hLen".
210 if sLen > hLen {
211 fips140.RecordNonApproved()
212 }
213
214 // 10. If the emLen - hLen - sLen - 2 leftmost octets of DB are not zero
215 // or if the octet at position emLen - hLen - sLen - 1 (the leftmost
216 // position is "position 1") does not have hexadecimal value 0x01,
217 // output "inconsistent" and stop.
218 psLen := emLen - hLen - sLen - 2
219 for _, e := range db[:psLen] {
220 if e != 0x00 {
221 return ErrVerification
222 }
223 }
224 if db[psLen] != 0x01 {
225 return ErrVerification
226 }
227
228 // 11. Let salt be the last sLen octets of DB.
229 salt := db[len(db)-sLen:]
230
231 // 12. Let
232 // M' = (0x)00 00 00 00 00 00 00 00 || mHash || salt ;
233 // M' is an octet string of length 8 + hLen + sLen with eight
234 // initial zero octets.
235 //
236 // 13. Let H' = Hash(M'), an octet string of length hLen.
237 hash.Reset()
238 var prefix [8]byte
239 hash.Write(prefix[:])
240 hash.Write(mHash)
241 hash.Write(salt)
242
243 h0 := hash.Sum(nil)
244
245 // 14. If H = H', output "consistent." Otherwise, output "inconsistent."
246 if !bytes.Equal(h0, h) {
247 return ErrVerification
248 }
249 return nil
250 }
251
252 // PSSMaxSaltLength returns the maximum salt length for a given public key and
253 // hash function.
254 func PSSMaxSaltLength(pub *PublicKey, hash hash.Hash) (int, error) {
255 saltLength := (pub.N.BitLen()-1+7)/8 - 2 - hash.Size()
256 if saltLength < 0 {
257 return 0, ErrMessageTooLong
258 }
259 // FIPS 186-5, Section 5.4(g): "the length (in bytes) of the salt (sLen)
260 // shall satisfy 0 ≤ sLen ≤ hLen".
261 if fips140.Enabled && saltLength > hash.Size() {
262 return hash.Size(), nil
263 }
264 return saltLength, nil
265 }
266
267 // SignPSS calculates the signature of hashed using RSASSA-PSS.
268 func SignPSS(rand io.Reader, priv *PrivateKey, hash hash.Hash, hashed []byte, saltLength int) ([]byte, error) {
269 fipsSelfTest()
270 fips140.RecordApproved()
271 checkApprovedHash(hash)
272
273 // Note that while we don't commit to deterministic execution with respect
274 // to the rand stream, we also don't apply MaybeReadByte, so per Hyrum's Law
275 // it's probably relied upon by some. It's a tolerable promise because a
276 // well-specified number of random bytes is included in the signature, in a
277 // well-specified way.
278
279 if saltLength < 0 {
280 return nil, errors.New("crypto/rsa: salt length cannot be negative")
281 }
282 // FIPS 186-5, Section 5.4(g): "the length (in bytes) of the salt (sLen)
283 // shall satisfy 0 ≤ sLen ≤ hLen".
284 if saltLength > hash.Size() {
285 fips140.RecordNonApproved()
286 }
287 salt := []byte{:saltLength}
288 if err := drbg.ReadWithReaderDeterministic(rand, salt); err != nil {
289 return nil, err
290 }
291
292 emBits := priv.pub.N.BitLen() - 1
293 em, err := emsaPSSEncode(hashed, emBits, salt, hash)
294 if err != nil {
295 return nil, err
296 }
297
298 // RFC 8017: "Note that the octet length of EM will be one less than k if
299 // modBits - 1 is divisible by 8 and equal to k otherwise, where k is the
300 // length in octets of the RSA modulus n." 🙄
301 //
302 // This is extremely annoying, as all other encrypt and decrypt inputs are
303 // always the exact same size as the modulus. Since it only happens for
304 // weird modulus sizes, fix it by padding inefficiently.
305 if emLen, k := len(em), priv.pub.Size(); emLen < k {
306 emNew := []byte{:k}
307 copy(emNew[k-emLen:], em)
308 em = emNew
309 }
310
311 return decrypt(priv, em, withCheck)
312 }
313
314 // VerifyPSS verifies sig with RSASSA-PSS automatically detecting the salt length.
315 func VerifyPSS(pub *PublicKey, hash hash.Hash, digest []byte, sig []byte) error {
316 return verifyPSS(pub, hash, digest, sig, pssSaltLengthAutodetect)
317 }
318
319 // VerifyPSS verifies sig with RSASSA-PSS and an expected salt length.
320 func VerifyPSSWithSaltLength(pub *PublicKey, hash hash.Hash, digest []byte, sig []byte, saltLength int) error {
321 if saltLength < 0 {
322 return errors.New("crypto/rsa: salt length cannot be negative")
323 }
324 return verifyPSS(pub, hash, digest, sig, saltLength)
325 }
326
327 func verifyPSS(pub *PublicKey, hash hash.Hash, digest []byte, sig []byte, saltLength int) error {
328 fipsSelfTest()
329 fips140.RecordApproved()
330 checkApprovedHash(hash)
331 if fipsApproved, err := checkPublicKey(pub); err != nil {
332 return err
333 } else if !fipsApproved {
334 fips140.RecordNonApproved()
335 }
336
337 if len(sig) != pub.Size() {
338 return ErrVerification
339 }
340
341 emBits := pub.N.BitLen() - 1
342 emLen := (emBits + 7) / 8
343 em, err := encrypt(pub, sig)
344 if err != nil {
345 return ErrVerification
346 }
347
348 // Like in signPSSWithSalt, deal with mismatches between emLen and the size
349 // of the modulus. The spec would have us wire emLen into the encoding
350 // function, but we'd rather always encode to the size of the modulus and
351 // then strip leading zeroes if necessary. This only happens for weird
352 // modulus sizes anyway.
353 for len(em) > emLen && len(em) > 0 {
354 if em[0] != 0 {
355 return ErrVerification
356 }
357 em = em[1:]
358 }
359
360 return emsaPSSVerify(digest, em, emBits, saltLength, hash)
361 }
362
363 func checkApprovedHash(hash hash.Hash) {
364 switch hash.(type) {
365 case *sha256.Digest, *sha512.Digest, *sha3.Digest:
366 default:
367 fips140.RecordNonApproved()
368 }
369 }
370
371 // EncryptOAEP encrypts the given message with RSAES-OAEP.
372 func EncryptOAEP(hash, mgfHash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, label []byte) ([]byte, error) {
373 // Note that while we don't commit to deterministic execution with respect
374 // to the random stream, we also don't apply MaybeReadByte, so per Hyrum's
375 // Law it's probably relied upon by some. It's a tolerable promise because a
376 // well-specified number of random bytes is included in the ciphertext, in a
377 // well-specified way.
378
379 fipsSelfTest()
380 fips140.RecordApproved()
381 checkApprovedHash(hash)
382 if fipsApproved, err := checkPublicKey(pub); err != nil {
383 return nil, err
384 } else if !fipsApproved {
385 fips140.RecordNonApproved()
386 }
387 k := pub.Size()
388 if len(msg) > k-2*hash.Size()-2 {
389 return nil, ErrMessageTooLong
390 }
391
392 hash.Reset()
393 hash.Write(label)
394 lHash := hash.Sum(nil)
395
396 em := []byte{:k}
397 seed := em[1 : 1+hash.Size()]
398 db := em[1+hash.Size():]
399
400 copy(db[0:hash.Size()], lHash)
401 db[len(db)-len(msg)-1] = 1
402 copy(db[len(db)-len(msg):], msg)
403
404 if err := drbg.ReadWithReaderDeterministic(random, seed); err != nil {
405 return nil, err
406 }
407
408 mgf1XOR(db, mgfHash, seed)
409 mgf1XOR(seed, mgfHash, db)
410
411 return encrypt(pub, em)
412 }
413
414 // DecryptOAEP decrypts ciphertext using RSAES-OAEP.
415 func DecryptOAEP(hash, mgfHash hash.Hash, priv *PrivateKey, ciphertext []byte, label []byte) ([]byte, error) {
416 fipsSelfTest()
417 fips140.RecordApproved()
418 checkApprovedHash(hash)
419
420 k := priv.pub.Size()
421 if len(ciphertext) > k ||
422 k < hash.Size()*2+2 {
423 return nil, ErrDecryption
424 }
425
426 em, err := decrypt(priv, ciphertext, noCheck)
427 if err != nil {
428 return nil, err
429 }
430
431 hash.Reset()
432 hash.Write(label)
433 lHash := hash.Sum(nil)
434
435 firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
436
437 seed := em[1 : hash.Size()+1]
438 db := em[hash.Size()+1:]
439
440 mgf1XOR(seed, mgfHash, db)
441 mgf1XOR(db, mgfHash, seed)
442
443 lHash2 := db[0:hash.Size()]
444
445 // We have to validate the plaintext in constant time in order to avoid
446 // attacks like: J. Manger. A Chosen Ciphertext Attack on RSA Optimal
447 // Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1
448 // v2.0. In J. Kilian, editor, Advances in Cryptology.
449 lHash2Good := subtle.ConstantTimeCompare(lHash, lHash2)
450
451 // The remainder of the plaintext must be zero or more 0x00, followed
452 // by 0x01, followed by the message.
453 // lookingForIndex: 1 iff we are still looking for the 0x01
454 // index: the offset of the first 0x01 byte
455 // invalid: 1 iff we saw a non-zero byte before the 0x01.
456 var lookingForIndex, index, invalid int
457 lookingForIndex = 1
458 rest := db[hash.Size():]
459
460 for i := 0; i < len(rest); i++ {
461 equals0 := subtle.ConstantTimeByteEq(rest[i], 0)
462 equals1 := subtle.ConstantTimeByteEq(rest[i], 1)
463 index = subtle.ConstantTimeSelect(lookingForIndex&equals1, i, index)
464 lookingForIndex = subtle.ConstantTimeSelect(equals1, 0, lookingForIndex)
465 invalid = subtle.ConstantTimeSelect(lookingForIndex&^equals0, 1, invalid)
466 }
467
468 if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 {
469 return nil, ErrDecryption
470 }
471
472 return rest[index+1:], nil
473 }
474