Source file src/crypto/internal/fips140/rsa/pkcs1v22.go

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

View as plain text