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