crypto/rsa/rsa_pk1.c

   1 /*
   2  * Copyright 1995-2020 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the Apache License 2.0 (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 /*
  11  * RSA low level APIs are deprecated for public use, but still ok for
  12  * internal use.
  13  */
  14 #include "internal/deprecated.h"
  15
  16 #include "internal/constant_time.h"
  17
  18 #include <stdio.h>
  19 #include <openssl/bn.h>
  20 #include <openssl/rsa.h>
  21 #include <openssl/rand.h>
  22 /* Just for the SSL_MAX_MASTER_KEY_LENGTH value */
  23 #include <openssl/ssl.h>
  24 #include "internal/cryptlib.h"
  25 #include "crypto/rsa.h"
  26 #include "rsa_local.h"
  27
  28 int RSA_padding_add_PKCS1_type_1(unsigned char *to, int tlen,
  29                                  const unsigned char *from, int flen)
  30 {
  31     int j;
  32     unsigned char *p;
  33
  34     if (flen > (tlen - RSA_PKCS1_PADDING_SIZE)) {
  35         RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_TYPE_1,
  36                RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE);
  37         return 0;
  38     }
  39
  40     p = (unsigned char *)to;
  41
  42     *(p++) = 0;
  43     *(p++) = 1;                 /* Private Key BT (Block Type) */
  44
  45     /* pad out with 0xff data */
  46     j = tlen - 3 - flen;
  47     memset(p, 0xff, j);
  48     p += j;
  49     *(p++) = '\0';
  50     memcpy(p, from, (unsigned int)flen);
  51     return 1;
  52 }
  53
  54 int RSA_padding_check_PKCS1_type_1(unsigned char *to, int tlen,
  55                                    const unsigned char *from, int flen,
  56                                    int num)
  57 {
  58     int i, j;
  59     const unsigned char *p;
  60
  61     p = from;
  62
  63     /*
  64      * The format is
  65      * 00 || 01 || PS || 00 || D
  66      * PS - padding string, at least 8 bytes of FF
  67      * D  - data.
  68      */
  69
  70     if (num < RSA_PKCS1_PADDING_SIZE)
  71         return -1;
  72
  73     /* Accept inputs with and without the leading 0-byte. */
  74     if (num == flen) {
  75         if ((*p++) != 0x00) {
  76             RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1,
  77                    RSA_R_INVALID_PADDING);
  78             return -1;
  79         }
  80         flen--;
  81     }
  82
  83     if ((num != (flen + 1)) || (*(p++) != 0x01)) {
  84         RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1,
  85                RSA_R_BLOCK_TYPE_IS_NOT_01);
  86         return -1;
  87     }
  88
  89     /* scan over padding data */
  90     j = flen - 1;               /* one for type. */
  91     for (i = 0; i < j; i++) {
  92         if (*p != 0xff) {       /* should decrypt to 0xff */
  93             if (*p == 0) {
  94                 p++;
  95                 break;
  96             } else {
  97                 RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1,
  98                        RSA_R_BAD_FIXED_HEADER_DECRYPT);
  99                 return -1;
 100             }
 101         }
 102         p++;
 103     }
 104
 105     if (i == j) {
 106         RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1,
 107                RSA_R_NULL_BEFORE_BLOCK_MISSING);
 108         return -1;
 109     }
 110
 111     if (i < 8) {
 112         RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1,
 113                RSA_R_BAD_PAD_BYTE_COUNT);
 114         return -1;
 115     }
 116     i++;                        /* Skip over the '\0' */
 117     j -= i;
 118     if (j > tlen) {
 119         RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1, RSA_R_DATA_TOO_LARGE);
 120         return -1;
 121     }
 122     memcpy(to, p, (unsigned int)j);
 123
 124     return j;
 125 }
 126
 127 int ossl_rsa_padding_add_PKCS1_type_2_ex(OPENSSL_CTX *libctx, unsigned char *to,
 128                                          int tlen, const unsigned char *from,
 129                                          int flen)
 130 {
 131     int i, j;
 132     unsigned char *p;
 133
 134     if (flen > (tlen - RSA_PKCS1_PADDING_SIZE)) {
 135         RSAerr(0, RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE);
 136         return 0;
 137     }
 138
 139     p = (unsigned char *)to;
 140
 141     *(p++) = 0;
 142     *(p++) = 2;                 /* Public Key BT (Block Type) */
 143
 144     /* pad out with non-zero random data */
 145     j = tlen - 3 - flen;
 146
 147     if (RAND_bytes_ex(libctx, p, j) <= 0)
 148         return 0;
 149     for (i = 0; i < j; i++) {
 150         if (*p == '\0')
 151             do {
 152                 if (RAND_bytes_ex(libctx, p, 1) <= 0)
 153                     return 0;
 154             } while (*p == '\0');
 155         p++;
 156     }
 157
 158     *(p++) = '\0';
 159
 160     memcpy(p, from, (unsigned int)flen);
 161     return 1;
 162 }
 163
 164 int RSA_padding_add_PKCS1_type_2(unsigned char *to, int tlen,
 165                                  const unsigned char *from, int flen)
 166 {
 167     return ossl_rsa_padding_add_PKCS1_type_2_ex(NULL, to, tlen, from, flen);
 168 }
 169
 170 int RSA_padding_check_PKCS1_type_2(unsigned char *to, int tlen,
 171                                    const unsigned char *from, int flen,
 172                                    int num)
 173 {
 174     int i;
 175     /* |em| is the encoded message, zero-padded to exactly |num| bytes */
 176     unsigned char *em = NULL;
 177     unsigned int good, found_zero_byte, mask;
 178     int zero_index = 0, msg_index, mlen = -1;
 179
 180     if (tlen <= 0 || flen <= 0)
 181         return -1;
 182
 183     /*
 184      * PKCS#1 v1.5 decryption. See "PKCS #1 v2.2: RSA Cryptography Standard",
 185      * section 7.2.2.
 186      */
 187
 188     if (flen > num || num < RSA_PKCS1_PADDING_SIZE) {
 189         RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2,
 190                RSA_R_PKCS_DECODING_ERROR);
 191         return -1;
 192     }
 193
 194     em = OPENSSL_malloc(num);
 195     if (em == NULL) {
 196         RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2, ERR_R_MALLOC_FAILURE);
 197         return -1;
 198     }
 199     /*
 200      * Caller is encouraged to pass zero-padded message created with
 201      * BN_bn2binpad. Trouble is that since we can't read out of |from|'s
 202      * bounds, it's impossible to have an invariant memory access pattern
 203      * in case |from| was not zero-padded in advance.
 204      */
 205     for (from += flen, em += num, i = 0; i < num; i++) {
 206         mask = ~constant_time_is_zero(flen);
 207         flen -= 1 & mask;
 208         from -= 1 & mask;
 209         *--em = *from & mask;
 210     }
 211
 212     good = constant_time_is_zero(em[0]);
 213     good &= constant_time_eq(em[1], 2);
 214
 215     /* scan over padding data */
 216     found_zero_byte = 0;
 217     for (i = 2; i < num; i++) {
 218         unsigned int equals0 = constant_time_is_zero(em[i]);
 219
 220         zero_index = constant_time_select_int(~found_zero_byte & equals0,
 221                                               i, zero_index);
 222         found_zero_byte |= equals0;
 223     }
 224
 225     /*
 226      * PS must be at least 8 bytes long, and it starts two bytes into |em|.
 227      * If we never found a 0-byte, then |zero_index| is 0 and the check
 228      * also fails.
 229      */
 230     good &= constant_time_ge(zero_index, 2 + 8);
 231
 232     /*
 233      * Skip the zero byte. This is incorrect if we never found a zero-byte
 234      * but in this case we also do not copy the message out.
 235      */
 236     msg_index = zero_index + 1;
 237     mlen = num - msg_index;
 238
 239     /*
 240      * For good measure, do this check in constant time as well.
 241      */
 242     good &= constant_time_ge(tlen, mlen);
 243
 244     /*
 245      * Move the result in-place by |num|-RSA_PKCS1_PADDING_SIZE-|mlen| bytes to the left.
 246      * Then if |good| move |mlen| bytes from |em|+RSA_PKCS1_PADDING_SIZE to |to|.
 247      * Otherwise leave |to| unchanged.
 248      * Copy the memory back in a way that does not reveal the size of
 249      * the data being copied via a timing side channel. This requires copying
 250      * parts of the buffer multiple times based on the bits set in the real
 251      * length. Clear bits do a non-copy with identical access pattern.
 252      * The loop below has overall complexity of O(N*log(N)).
 253      */
 254     tlen = constant_time_select_int(constant_time_lt(num - RSA_PKCS1_PADDING_SIZE, tlen),
 255                                     num - RSA_PKCS1_PADDING_SIZE, tlen);
 256     for (msg_index = 1; msg_index < num - RSA_PKCS1_PADDING_SIZE; msg_index <<= 1) {
 257         mask = ~constant_time_eq(msg_index & (num - RSA_PKCS1_PADDING_SIZE - mlen), 0);
 258         for (i = RSA_PKCS1_PADDING_SIZE; i < num - msg_index; i++)
 259             em[i] = constant_time_select_8(mask, em[i + msg_index], em[i]);
 260     }
 261     for (i = 0; i < tlen; i++) {
 262         mask = good & constant_time_lt(i, mlen);
 263         to[i] = constant_time_select_8(mask, em[i + RSA_PKCS1_PADDING_SIZE], to[i]);
 264     }
 265
 266     OPENSSL_clear_free(em, num);
 267 #ifndef FIPS_MODULE
 268     /*
 269      * This trick doesn't work in the FIPS provider because libcrypto manages
 270      * the error stack. Instead we opt not to put an error on the stack at all
 271      * in case of padding failure in the FIPS provider.
 272      */
 273     RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2, RSA_R_PKCS_DECODING_ERROR);
 274     err_clear_last_constant_time(1 & good);
 275 #endif
 276
 277     return constant_time_select_int(good, mlen, -1);
 278 }
 279
 280 /*
 281  * ossl_rsa_padding_check_PKCS1_type_2_TLS() checks and removes the PKCS1 type 2
 282  * padding from a decrypted RSA message in a TLS signature. The result is stored
 283  * in the buffer pointed to by |to| which should be |tlen| bytes long. |tlen|
 284  * must be at least SSL_MAX_MASTER_KEY_LENGTH. The original decrypted message
 285  * should be stored in |from| which must be |flen| bytes in length and padded
 286  * such that |flen == RSA_size()|. The TLS protocol version that the client
 287  * originally requested should be passed in |client_version|. Some buggy clients
 288  * can exist which use the negotiated version instead of the originally
 289  * requested protocol version. If it is necessary to work around this bug then
 290  * the negotiated protocol version can be passed in |alt_version|, otherwise 0
 291  * should be passed.
 292  *
 293  * If the passed message is publicly invalid or some other error that can be
 294  * treated in non-constant time occurs then -1 is returned. On success the
 295  * length of the decrypted data is returned. This will always be
 296  * SSL_MAX_MASTER_KEY_LENGTH. If an error occurs that should be treated in
 297  * constant time then this function will appear to return successfully, but the
 298  * decrypted data will be randomly generated (as per
 299  * https://tools.ietf.org/html/rfc5246#section-7.4.7.1).
 300  */
 301 int ossl_rsa_padding_check_PKCS1_type_2_TLS(OPENSSL_CTX *libctx,
 302                                             unsigned char *to, size_t tlen,
 303                                             const unsigned char *from,
 304                                             size_t flen, int client_version,
 305                                             int alt_version)
 306 {
 307     unsigned int i, good, version_good;
 308     unsigned char rand_premaster_secret[SSL_MAX_MASTER_KEY_LENGTH];
 309
 310     /*
 311      * If these checks fail then either the message in publicly invalid, or
 312      * we've been called incorrectly. We can fail immediately.
 313      */
 314     if (flen < RSA_PKCS1_PADDING_SIZE + SSL_MAX_MASTER_KEY_LENGTH
 315             || tlen < SSL_MAX_MASTER_KEY_LENGTH) {
 316         ERR_raise(ERR_LIB_RSA, RSA_R_PKCS_DECODING_ERROR);
 317         return -1;
 318     }
 319
 320     /*
 321      * Generate a random premaster secret to use in the event that we fail
 322      * to decrypt.
 323      */
 324     if (RAND_priv_bytes_ex(libctx, rand_premaster_secret,
 325                            sizeof(rand_premaster_secret)) <= 0) {
 326         ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
 327         return -1;
 328     }
 329
 330     good = constant_time_is_zero(from[0]);
 331     good &= constant_time_eq(from[1], 2);
 332
 333     /* Check we have the expected padding data */
 334     for (i = 2; i < flen - SSL_MAX_MASTER_KEY_LENGTH - 1; i++)
 335         good &= ~constant_time_is_zero_8(from[i]);
 336     good &= constant_time_is_zero_8(from[flen - SSL_MAX_MASTER_KEY_LENGTH - 1]);
 337
 338
 339     /*
 340      * If the version in the decrypted pre-master secret is correct then
 341      * version_good will be 0xff, otherwise it'll be zero. The
 342      * Klima-Pokorny-Rosa extension of Bleichenbacher's attack
 343      * (http://eprint.iacr.org/2003/052/) exploits the version number
 344      * check as a "bad version oracle". Thus version checks are done in
 345      * constant time and are treated like any other decryption error.
 346      */
 347     version_good =
 348         constant_time_eq(from[flen - SSL_MAX_MASTER_KEY_LENGTH],
 349                          (client_version >> 8) & 0xff);
 350     version_good &=
 351         constant_time_eq(from[flen - SSL_MAX_MASTER_KEY_LENGTH + 1],
 352                          client_version & 0xff);
 353
 354     /*
 355      * The premaster secret must contain the same version number as the
 356      * ClientHello to detect version rollback attacks (strangely, the
 357      * protocol does not offer such protection for DH ciphersuites).
 358      * However, buggy clients exist that send the negotiated protocol
 359      * version instead if the server does not support the requested
 360      * protocol version. If SSL_OP_TLS_ROLLBACK_BUG is set then we tolerate
 361      * such clients. In that case alt_version will be non-zero and set to
 362      * the negotiated version.
 363      */
 364     if (alt_version > 0) {
 365         unsigned int workaround_good;
 366
 367         workaround_good =
 368             constant_time_eq(from[flen - SSL_MAX_MASTER_KEY_LENGTH],
 369                              (alt_version >> 8) & 0xff);
 370         workaround_good &=
 371             constant_time_eq(from[flen - SSL_MAX_MASTER_KEY_LENGTH + 1],
 372                              alt_version & 0xff);
 373         version_good |= workaround_good;
 374     }
 375
 376     good &= version_good;
 377
 378
 379     /*
 380      * Now copy the result over to the to buffer if good, or random data if
 381      * not good.
 382      */
 383     for (i = 0; i < SSL_MAX_MASTER_KEY_LENGTH; i++) {
 384         to[i] =
 385             constant_time_select_8(good,
 386                                    from[flen - SSL_MAX_MASTER_KEY_LENGTH + i],
 387                                    rand_premaster_secret[i]);
 388     }
 389
 390     /*
 391      * We must not leak whether a decryption failure occurs because of
 392      * Bleichenbacher's attack on PKCS #1 v1.5 RSA padding (see RFC 2246,
 393      * section 7.4.7.1). The code follows that advice of the TLS RFC and
 394      * generates a random premaster secret for the case that the decrypt
 395      * fails. See https://tools.ietf.org/html/rfc5246#section-7.4.7.1
 396      * So, whether we actually succeeded or not, return success.
 397      */
 398
 399     return SSL_MAX_MASTER_KEY_LENGTH;
 400 }