...
Run Format

Source file src/crypto/rsa/pkcs1v15.go

Documentation: crypto/rsa

     1  // Copyright 2009 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  import (
     8  	"crypto"
     9  	"crypto/subtle"
    10  	"errors"
    11  	"io"
    12  	"math/big"
    13  )
    14  
    15  // This file implements encryption and decryption using PKCS#1 v1.5 padding.
    16  
    17  // PKCS1v15DecrypterOpts is for passing options to PKCS#1 v1.5 decryption using
    18  // the crypto.Decrypter interface.
    19  type PKCS1v15DecryptOptions struct {
    20  	// SessionKeyLen is the length of the session key that is being
    21  	// decrypted. If not zero, then a padding error during decryption will
    22  	// cause a random plaintext of this length to be returned rather than
    23  	// an error. These alternatives happen in constant time.
    24  	SessionKeyLen int
    25  }
    26  
    27  // EncryptPKCS1v15 encrypts the given message with RSA and the padding
    28  // scheme from PKCS#1 v1.5.  The message must be no longer than the
    29  // length of the public modulus minus 11 bytes.
    30  //
    31  // The rand parameter is used as a source of entropy to ensure that
    32  // encrypting the same message twice doesn't result in the same
    33  // ciphertext.
    34  //
    35  // WARNING: use of this function to encrypt plaintexts other than
    36  // session keys is dangerous. Use RSA OAEP in new protocols.
    37  func EncryptPKCS1v15(rand io.Reader, pub *PublicKey, msg []byte) ([]byte, error) {
    38  	if err := checkPub(pub); err != nil {
    39  		return nil, err
    40  	}
    41  	k := (pub.N.BitLen() + 7) / 8
    42  	if len(msg) > k-11 {
    43  		return nil, ErrMessageTooLong
    44  	}
    45  
    46  	// EM = 0x00 || 0x02 || PS || 0x00 || M
    47  	em := make([]byte, k)
    48  	em[1] = 2
    49  	ps, mm := em[2:len(em)-len(msg)-1], em[len(em)-len(msg):]
    50  	err := nonZeroRandomBytes(ps, rand)
    51  	if err != nil {
    52  		return nil, err
    53  	}
    54  	em[len(em)-len(msg)-1] = 0
    55  	copy(mm, msg)
    56  
    57  	m := new(big.Int).SetBytes(em)
    58  	c := encrypt(new(big.Int), pub, m)
    59  
    60  	copyWithLeftPad(em, c.Bytes())
    61  	return em, nil
    62  }
    63  
    64  // DecryptPKCS1v15 decrypts a plaintext using RSA and the padding scheme from PKCS#1 v1.5.
    65  // If rand != nil, it uses RSA blinding to avoid timing side-channel attacks.
    66  //
    67  // Note that whether this function returns an error or not discloses secret
    68  // information. If an attacker can cause this function to run repeatedly and
    69  // learn whether each instance returned an error then they can decrypt and
    70  // forge signatures as if they had the private key. See
    71  // DecryptPKCS1v15SessionKey for a way of solving this problem.
    72  func DecryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) ([]byte, error) {
    73  	if err := checkPub(&priv.PublicKey); err != nil {
    74  		return nil, err
    75  	}
    76  	valid, out, index, err := decryptPKCS1v15(rand, priv, ciphertext)
    77  	if err != nil {
    78  		return nil, err
    79  	}
    80  	if valid == 0 {
    81  		return nil, ErrDecryption
    82  	}
    83  	return out[index:], nil
    84  }
    85  
    86  // DecryptPKCS1v15SessionKey decrypts a session key using RSA and the padding scheme from PKCS#1 v1.5.
    87  // If rand != nil, it uses RSA blinding to avoid timing side-channel attacks.
    88  // It returns an error if the ciphertext is the wrong length or if the
    89  // ciphertext is greater than the public modulus. Otherwise, no error is
    90  // returned. If the padding is valid, the resulting plaintext message is copied
    91  // into key. Otherwise, key is unchanged. These alternatives occur in constant
    92  // time. It is intended that the user of this function generate a random
    93  // session key beforehand and continue the protocol with the resulting value.
    94  // This will remove any possibility that an attacker can learn any information
    95  // about the plaintext.
    96  // See ``Chosen Ciphertext Attacks Against Protocols Based on the RSA
    97  // Encryption Standard PKCS #1'', Daniel Bleichenbacher, Advances in Cryptology
    98  // (Crypto '98).
    99  //
   100  // Note that if the session key is too small then it may be possible for an
   101  // attacker to brute-force it. If they can do that then they can learn whether
   102  // a random value was used (because it'll be different for the same ciphertext)
   103  // and thus whether the padding was correct. This defeats the point of this
   104  // function. Using at least a 16-byte key will protect against this attack.
   105  func DecryptPKCS1v15SessionKey(rand io.Reader, priv *PrivateKey, ciphertext []byte, key []byte) error {
   106  	if err := checkPub(&priv.PublicKey); err != nil {
   107  		return err
   108  	}
   109  	k := (priv.N.BitLen() + 7) / 8
   110  	if k-(len(key)+3+8) < 0 {
   111  		return ErrDecryption
   112  	}
   113  
   114  	valid, em, index, err := decryptPKCS1v15(rand, priv, ciphertext)
   115  	if err != nil {
   116  		return err
   117  	}
   118  
   119  	if len(em) != k {
   120  		// This should be impossible because decryptPKCS1v15 always
   121  		// returns the full slice.
   122  		return ErrDecryption
   123  	}
   124  
   125  	valid &= subtle.ConstantTimeEq(int32(len(em)-index), int32(len(key)))
   126  	subtle.ConstantTimeCopy(valid, key, em[len(em)-len(key):])
   127  	return nil
   128  }
   129  
   130  // decryptPKCS1v15 decrypts ciphertext using priv and blinds the operation if
   131  // rand is not nil. It returns one or zero in valid that indicates whether the
   132  // plaintext was correctly structured. In either case, the plaintext is
   133  // returned in em so that it may be read independently of whether it was valid
   134  // in order to maintain constant memory access patterns. If the plaintext was
   135  // valid then index contains the index of the original message in em.
   136  func decryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) (valid int, em []byte, index int, err error) {
   137  	k := (priv.N.BitLen() + 7) / 8
   138  	if k < 11 {
   139  		err = ErrDecryption
   140  		return
   141  	}
   142  
   143  	c := new(big.Int).SetBytes(ciphertext)
   144  	m, err := decrypt(rand, priv, c)
   145  	if err != nil {
   146  		return
   147  	}
   148  
   149  	em = leftPad(m.Bytes(), k)
   150  	firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
   151  	secondByteIsTwo := subtle.ConstantTimeByteEq(em[1], 2)
   152  
   153  	// The remainder of the plaintext must be a string of non-zero random
   154  	// octets, followed by a 0, followed by the message.
   155  	//   lookingForIndex: 1 iff we are still looking for the zero.
   156  	//   index: the offset of the first zero byte.
   157  	lookingForIndex := 1
   158  
   159  	for i := 2; i < len(em); i++ {
   160  		equals0 := subtle.ConstantTimeByteEq(em[i], 0)
   161  		index = subtle.ConstantTimeSelect(lookingForIndex&equals0, i, index)
   162  		lookingForIndex = subtle.ConstantTimeSelect(equals0, 0, lookingForIndex)
   163  	}
   164  
   165  	// The PS padding must be at least 8 bytes long, and it starts two
   166  	// bytes into em.
   167  	validPS := subtle.ConstantTimeLessOrEq(2+8, index)
   168  
   169  	valid = firstByteIsZero & secondByteIsTwo & (^lookingForIndex & 1) & validPS
   170  	index = subtle.ConstantTimeSelect(valid, index+1, 0)
   171  	return valid, em, index, nil
   172  }
   173  
   174  // nonZeroRandomBytes fills the given slice with non-zero random octets.
   175  func nonZeroRandomBytes(s []byte, rand io.Reader) (err error) {
   176  	_, err = io.ReadFull(rand, s)
   177  	if err != nil {
   178  		return
   179  	}
   180  
   181  	for i := 0; i < len(s); i++ {
   182  		for s[i] == 0 {
   183  			_, err = io.ReadFull(rand, s[i:i+1])
   184  			if err != nil {
   185  				return
   186  			}
   187  			// In tests, the PRNG may return all zeros so we do
   188  			// this to break the loop.
   189  			s[i] ^= 0x42
   190  		}
   191  	}
   192  
   193  	return
   194  }
   195  
   196  // These are ASN1 DER structures:
   197  //   DigestInfo ::= SEQUENCE {
   198  //     digestAlgorithm AlgorithmIdentifier,
   199  //     digest OCTET STRING
   200  //   }
   201  // For performance, we don't use the generic ASN1 encoder. Rather, we
   202  // precompute a prefix of the digest value that makes a valid ASN1 DER string
   203  // with the correct contents.
   204  var hashPrefixes = map[crypto.Hash][]byte{
   205  	crypto.MD5:       {0x30, 0x20, 0x30, 0x0c, 0x06, 0x08, 0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x02, 0x05, 0x05, 0x00, 0x04, 0x10},
   206  	crypto.SHA1:      {0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 0x0e, 0x03, 0x02, 0x1a, 0x05, 0x00, 0x04, 0x14},
   207  	crypto.SHA224:    {0x30, 0x2d, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x04, 0x05, 0x00, 0x04, 0x1c},
   208  	crypto.SHA256:    {0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, 0x05, 0x00, 0x04, 0x20},
   209  	crypto.SHA384:    {0x30, 0x41, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x02, 0x05, 0x00, 0x04, 0x30},
   210  	crypto.SHA512:    {0x30, 0x51, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03, 0x05, 0x00, 0x04, 0x40},
   211  	crypto.MD5SHA1:   {}, // A special TLS case which doesn't use an ASN1 prefix.
   212  	crypto.RIPEMD160: {0x30, 0x20, 0x30, 0x08, 0x06, 0x06, 0x28, 0xcf, 0x06, 0x03, 0x00, 0x31, 0x04, 0x14},
   213  }
   214  
   215  // SignPKCS1v15 calculates the signature of hashed using
   216  // RSASSA-PKCS1-V1_5-SIGN from RSA PKCS#1 v1.5.  Note that hashed must
   217  // be the result of hashing the input message using the given hash
   218  // function. If hash is zero, hashed is signed directly. This isn't
   219  // advisable except for interoperability.
   220  //
   221  // If rand is not nil then RSA blinding will be used to avoid timing
   222  // side-channel attacks.
   223  //
   224  // This function is deterministic. Thus, if the set of possible
   225  // messages is small, an attacker may be able to build a map from
   226  // messages to signatures and identify the signed messages. As ever,
   227  // signatures provide authenticity, not confidentiality.
   228  func SignPKCS1v15(rand io.Reader, priv *PrivateKey, hash crypto.Hash, hashed []byte) ([]byte, error) {
   229  	hashLen, prefix, err := pkcs1v15HashInfo(hash, len(hashed))
   230  	if err != nil {
   231  		return nil, err
   232  	}
   233  
   234  	tLen := len(prefix) + hashLen
   235  	k := (priv.N.BitLen() + 7) / 8
   236  	if k < tLen+11 {
   237  		return nil, ErrMessageTooLong
   238  	}
   239  
   240  	// EM = 0x00 || 0x01 || PS || 0x00 || T
   241  	em := make([]byte, k)
   242  	em[1] = 1
   243  	for i := 2; i < k-tLen-1; i++ {
   244  		em[i] = 0xff
   245  	}
   246  	copy(em[k-tLen:k-hashLen], prefix)
   247  	copy(em[k-hashLen:k], hashed)
   248  
   249  	m := new(big.Int).SetBytes(em)
   250  	c, err := decryptAndCheck(rand, priv, m)
   251  	if err != nil {
   252  		return nil, err
   253  	}
   254  
   255  	copyWithLeftPad(em, c.Bytes())
   256  	return em, nil
   257  }
   258  
   259  // VerifyPKCS1v15 verifies an RSA PKCS#1 v1.5 signature.
   260  // hashed is the result of hashing the input message using the given hash
   261  // function and sig is the signature. A valid signature is indicated by
   262  // returning a nil error. If hash is zero then hashed is used directly. This
   263  // isn't advisable except for interoperability.
   264  func VerifyPKCS1v15(pub *PublicKey, hash crypto.Hash, hashed []byte, sig []byte) error {
   265  	hashLen, prefix, err := pkcs1v15HashInfo(hash, len(hashed))
   266  	if err != nil {
   267  		return err
   268  	}
   269  
   270  	tLen := len(prefix) + hashLen
   271  	k := (pub.N.BitLen() + 7) / 8
   272  	if k < tLen+11 {
   273  		return ErrVerification
   274  	}
   275  
   276  	c := new(big.Int).SetBytes(sig)
   277  	m := encrypt(new(big.Int), pub, c)
   278  	em := leftPad(m.Bytes(), k)
   279  	// EM = 0x00 || 0x01 || PS || 0x00 || T
   280  
   281  	ok := subtle.ConstantTimeByteEq(em[0], 0)
   282  	ok &= subtle.ConstantTimeByteEq(em[1], 1)
   283  	ok &= subtle.ConstantTimeCompare(em[k-hashLen:k], hashed)
   284  	ok &= subtle.ConstantTimeCompare(em[k-tLen:k-hashLen], prefix)
   285  	ok &= subtle.ConstantTimeByteEq(em[k-tLen-1], 0)
   286  
   287  	for i := 2; i < k-tLen-1; i++ {
   288  		ok &= subtle.ConstantTimeByteEq(em[i], 0xff)
   289  	}
   290  
   291  	if ok != 1 {
   292  		return ErrVerification
   293  	}
   294  
   295  	return nil
   296  }
   297  
   298  func pkcs1v15HashInfo(hash crypto.Hash, inLen int) (hashLen int, prefix []byte, err error) {
   299  	// Special case: crypto.Hash(0) is used to indicate that the data is
   300  	// signed directly.
   301  	if hash == 0 {
   302  		return inLen, nil, nil
   303  	}
   304  
   305  	hashLen = hash.Size()
   306  	if inLen != hashLen {
   307  		return 0, nil, errors.New("crypto/rsa: input must be hashed message")
   308  	}
   309  	prefix, ok := hashPrefixes[hash]
   310  	if !ok {
   311  		return 0, nil, errors.New("crypto/rsa: unsupported hash function")
   312  	}
   313  	return
   314  }
   315  
   316  // copyWithLeftPad copies src to the end of dest, padding with zero bytes as
   317  // needed.
   318  func copyWithLeftPad(dest, src []byte) {
   319  	numPaddingBytes := len(dest) - len(src)
   320  	for i := 0; i < numPaddingBytes; i++ {
   321  		dest[i] = 0
   322  	}
   323  	copy(dest[numPaddingBytes:], src)
   324  }
   325  

View as plain text