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