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