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/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 := make([]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 := make([]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 := make([]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 := make([]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
View as plain text