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