...
Run Format

Source file src/crypto/rsa/pkcs1v15.go

     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