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