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 rsa_padding_add_PKCS1_type_2_with_libctx(OPENSSL_CTX *libctx,
 128                                              unsigned char *to, int tlen,
 129                                              const unsigned char *from,
 130                                              int flen)
 131 {
 132     int i, j;
 133     unsigned char *p;
 134
 135     if (flen > (tlen - RSA_PKCS1_PADDING_SIZE)) {
 136         RSAerr(0, RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE);
 137         return 0;
 138     }
 139
 140     p = (unsigned char *)to;
 141
 142     *(p++) = 0;
 143     *(p++) = 2;                 /* Public Key BT (Block Type) */
 144
 145     /* pad out with non-zero random data */
 146     j = tlen - 3 - flen;
 147
 148     if (RAND_bytes_ex(libctx, p, j) <= 0)
 149         return 0;
 150     for (i = 0; i < j; i++) {
 151         if (*p == '\0')
 152             do {
 153                 if (RAND_bytes_ex(libctx, p, 1) <= 0)
 154                     return 0;
 155             } while (*p == '\0');
 156         p++;
 157     }
 158
 159     *(p++) = '\0';
 160
 161     memcpy(p, from, (unsigned int)flen);
 162     return 1;
 163 }
 164
 165 int RSA_padding_add_PKCS1_type_2(unsigned char *to, int tlen,
 166                                  const unsigned char *from, int flen)
 167 {
 168     return rsa_padding_add_PKCS1_type_2_with_libctx(NULL, to, tlen, from, flen);
 169 }
 170
 171 int RSA_padding_check_PKCS1_type_2(unsigned char *to, int tlen,
 172                                    const unsigned char *from, int flen,
 173                                    int num)
 174 {
 175     int i;
 176     /* |em| is the encoded message, zero-padded to exactly |num| bytes */
 177     unsigned char *em = NULL;
 178     unsigned int good, found_zero_byte, mask;
 179     int zero_index = 0, msg_index, mlen = -1;
 180
 181     if (tlen <= 0 || flen <= 0)
 182         return -1;
 183
 184     /*
 185      * PKCS#1 v1.5 decryption. See "PKCS #1 v2.2: RSA Cryptography Standard",
 186      * section 7.2.2.
 187      */
 188
 189     if (flen > num || num < RSA_PKCS1_PADDING_SIZE) {
 190         RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2,
 191                RSA_R_PKCS_DECODING_ERROR);
 192         return -1;
 193     }
 194
 195     em = OPENSSL_malloc(num);
 196     if (em == NULL) {
 197         RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2, ERR_R_MALLOC_FAILURE);
 198         return -1;
 199     }
 200     /*
 201      * Caller is encouraged to pass zero-padded message created with
 202      * BN_bn2binpad. Trouble is that since we can't read out of |from|'s
 203      * bounds, it's impossible to have an invariant memory access pattern
 204      * in case |from| was not zero-padded in advance.
 205      */
 206     for (from += flen, em += num, i = 0; i < num; i++) {
 207         mask = ~constant_time_is_zero(flen);
 208         flen -= 1 & mask;
 209         from -= 1 & mask;
 210         *--em = *from & mask;
 211     }
 212
 213     good = constant_time_is_zero(em[0]);
 214     good &= constant_time_eq(em[1], 2);
 215
 216     /* scan over padding data */
 217     found_zero_byte = 0;
 218     for (i = 2; i < num; i++) {
 219         unsigned int equals0 = constant_time_is_zero(em[i]);
 220
 221         zero_index = constant_time_select_int(~found_zero_byte & equals0,
 222                                               i, zero_index);
 223         found_zero_byte |= equals0;
 224     }
 225
 226     /*
 227      * PS must be at least 8 bytes long, and it starts two bytes into |em|.
 228      * If we never found a 0-byte, then |zero_index| is 0 and the check
 229      * also fails.
 230      */
 231     good &= constant_time_ge(zero_index, 2 + 8);
 232
 233     /*
 234      * Skip the zero byte. This is incorrect if we never found a zero-byte
 235      * but in this case we also do not copy the message out.
 236      */
 237     msg_index = zero_index + 1;
 238     mlen = num - msg_index;
 239
 240     /*
 241      * For good measure, do this check in constant time as well.
 242      */
 243     good &= constant_time_ge(tlen, mlen);
 244
 245     /*
 246      * Move the result in-place by |num|-RSA_PKCS1_PADDING_SIZE-|mlen| bytes to the left.
 247      * Then if |good| move |mlen| bytes from |em|+RSA_PKCS1_PADDING_SIZE to |to|.
 248      * Otherwise leave |to| unchanged.
 249      * Copy the memory back in a way that does not reveal the size of
 250      * the data being copied via a timing side channel. This requires copying
 251      * parts of the buffer multiple times based on the bits set in the real
 252      * length. Clear bits do a non-copy with identical access pattern.
 253      * The loop below has overall complexity of O(N*log(N)).
 254      */
 255     tlen = constant_time_select_int(constant_time_lt(num - RSA_PKCS1_PADDING_SIZE, tlen),
 256                                     num - RSA_PKCS1_PADDING_SIZE, tlen);
 257     for (msg_index = 1; msg_index < num - RSA_PKCS1_PADDING_SIZE; msg_index <<= 1) {
 258         mask = ~constant_time_eq(msg_index & (num - RSA_PKCS1_PADDING_SIZE - mlen), 0);
 259         for (i = RSA_PKCS1_PADDING_SIZE; i < num - msg_index; i++)
 260             em[i] = constant_time_select_8(mask, em[i + msg_index], em[i]);
 261     }
 262     for (i = 0; i < tlen; i++) {
 263         mask = good & constant_time_lt(i, mlen);
 264         to[i] = constant_time_select_8(mask, em[i + RSA_PKCS1_PADDING_SIZE], to[i]);
 265     }
 266
 267     OPENSSL_clear_free(em, num);
 268 #ifndef FIPS_MODE
 269     /*
 270      * This trick doesn't work in the FIPS provider because libcrypto manages
 271      * the error stack. Instead we opt not to put an error on the stack at all
 272      * in case of padding failure in the FIPS provider.
 273      */
 274     RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2, RSA_R_PKCS_DECODING_ERROR);
 275     err_clear_last_constant_time(1 & good);
 276 #endif
 277
 278     return constant_time_select_int(good, mlen, -1);
 279 }
 280
 281 /*
 282  * rsa_padding_check_PKCS1_type_2_TLS() checks and removes the PKCS1 type 2
 283  * padding from a decrypted RSA message in a TLS signature. The result is stored
 284  * in the buffer pointed to by |to| which should be |tlen| bytes long. |tlen|
 285  * must be at least SSL_MAX_MASTER_KEY_LENGTH. The original decrypted message
 286  * should be stored in |from| which must be |flen| bytes in length and padded
 287  * such that |flen == RSA_size()|. The TLS protocol version that the client
 288  * originally requested should be passed in |client_version|. Some buggy clients
 289  * can exist which use the negotiated version instead of the originally
 290  * requested protocol version. If it is necessary to work around this bug then
 291  * the negotiated protocol version can be passed in |alt_version|, otherwise 0
 292  * should be passed.
 293  *
 294  * If the passed message is publicly invalid or some other error that can be
 295  * treated in non-constant time occurs then -1 is returned. On success the
 296  * length of the decrypted data is returned. This will always be
 297  * SSL_MAX_MASTER_KEY_LENGTH. If an error occurs that should be treated in
 298  * constant time then this function will appear to return successfully, but the
 299  * decrypted data will be randomly generated (as per
 300  * https://tools.ietf.org/html/rfc5246#section-7.4.7.1).
 301  */
 302 int rsa_padding_check_PKCS1_type_2_TLS(OPENSSL_CTX *libctx, unsigned char *to,
 303                                        size_t tlen, 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 }