crypto/rsa/rsa_pk1.c

   1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   2  * All rights reserved.
   3  *
   4  * This package is an SSL implementation written
   5  * by Eric Young (eay@cryptsoft.com).
   6  * The implementation was written so as to conform with Netscapes SSL.
   7  *
   8  * This library is free for commercial and non-commercial use as long as
   9  * the following conditions are aheared to.  The following conditions
  10  * apply to all code found in this distribution, be it the RC4, RSA,
  11  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  12  * included with this distribution is covered by the same copyright terms
  13  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  14  *
  15  * Copyright remains Eric Young's, and as such any Copyright notices in
  16  * the code are not to be removed.
  17  * If this package is used in a product, Eric Young should be given attribution
  18  * as the author of the parts of the library used.
  19  * This can be in the form of a textual message at program startup or
  20  * in documentation (online or textual) provided with the package.
  21  *
  22  * Redistribution and use in source and binary forms, with or without
  23  * modification, are permitted provided that the following conditions
  24  * are met:
  25  * 1. Redistributions of source code must retain the copyright
  26  *    notice, this list of conditions and the following disclaimer.
  27  * 2. Redistributions in binary form must reproduce the above copyright
  28  *    notice, this list of conditions and the following disclaimer in the
  29  *    documentation and/or other materials provided with the distribution.
  30  * 3. All advertising materials mentioning features or use of this software
  31  *    must display the following acknowledgement:
  32  *    "This product includes cryptographic software written by
  33  *     Eric Young (eay@cryptsoft.com)"
  34  *    The word 'cryptographic' can be left out if the rouines from the library
  35  *    being used are not cryptographic related :-).
  36  * 4. If you include any Windows specific code (or a derivative thereof) from
  37  *    the apps directory (application code) you must include an acknowledgement:
  38  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  39  *
  40  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  41  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  43  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  44  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  45  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  46  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  48  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  49  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  50  * SUCH DAMAGE.
  51  *
  52  * The licence and distribution terms for any publically available version or
  53  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  54  * copied and put under another distribution licence
  55  * [including the GNU Public Licence.]
  56  */
  57
  58 #include "internal/constant_time_locl.h"
  59
  60 #include <stdio.h>
  61 #include "internal/cryptlib.h"
  62 #include <openssl/bn.h>
  63 #include <openssl/rsa.h>
  64 #include <openssl/rand.h>
  65
  66 int RSA_padding_add_PKCS1_type_1(unsigned char *to, int tlen,
  67                                  const unsigned char *from, int flen)
  68 {
  69     int j;
  70     unsigned char *p;
  71
  72     if (flen > (tlen - RSA_PKCS1_PADDING_SIZE)) {
  73         RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_TYPE_1,
  74                RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE);
  75         return (0);
  76     }
  77
  78     p = (unsigned char *)to;
  79
  80     *(p++) = 0;
  81     *(p++) = 1;                 /* Private Key BT (Block Type) */
  82
  83     /* pad out with 0xff data */
  84     j = tlen - 3 - flen;
  85     memset(p, 0xff, j);
  86     p += j;
  87     *(p++) = '\0';
  88     memcpy(p, from, (unsigned int)flen);
  89     return (1);
  90 }
  91
  92 int RSA_padding_check_PKCS1_type_1(unsigned char *to, int tlen,
  93                                    const unsigned char *from, int flen,
  94                                    int num)
  95 {
  96     int i, j;
  97     const unsigned char *p;
  98
  99     p = from;
 100
 101     /*
 102      * The format is
 103      * 00 || 01 || PS || 00 || D
 104      * PS - padding string, at least 8 bytes of FF
 105      * D  - data.
 106      */
 107
 108     if (num < 11)
 109         return -1;
 110
 111     /* Accept inputs with and without the leading 0-byte. */
 112     if (num == flen) {
 113         if ((*p++) != 0x00) {
 114             RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1,
 115                    RSA_R_INVALID_PADDING);
 116             return -1;
 117         }
 118         flen--;
 119     }
 120
 121     if ((num != (flen + 1)) || (*(p++) != 0x01)) {
 122         RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1,
 123                RSA_R_BLOCK_TYPE_IS_NOT_01);
 124         return (-1);
 125     }
 126
 127     /* scan over padding data */
 128     j = flen - 1;               /* one for type. */
 129     for (i = 0; i < j; i++) {
 130         if (*p != 0xff) {       /* should decrypt to 0xff */
 131             if (*p == 0) {
 132                 p++;
 133                 break;
 134             } else {
 135                 RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1,
 136                        RSA_R_BAD_FIXED_HEADER_DECRYPT);
 137                 return (-1);
 138             }
 139         }
 140         p++;
 141     }
 142
 143     if (i == j) {
 144         RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1,
 145                RSA_R_NULL_BEFORE_BLOCK_MISSING);
 146         return (-1);
 147     }
 148
 149     if (i < 8) {
 150         RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1,
 151                RSA_R_BAD_PAD_BYTE_COUNT);
 152         return (-1);
 153     }
 154     i++;                        /* Skip over the '\0' */
 155     j -= i;
 156     if (j > tlen) {
 157         RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1, RSA_R_DATA_TOO_LARGE);
 158         return (-1);
 159     }
 160     memcpy(to, p, (unsigned int)j);
 161
 162     return (j);
 163 }
 164
 165 int RSA_padding_add_PKCS1_type_2(unsigned char *to, int tlen,
 166                                  const unsigned char *from, int flen)
 167 {
 168     int i, j;
 169     unsigned char *p;
 170
 171     if (flen > (tlen - 11)) {
 172         RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_TYPE_2,
 173                RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE);
 174         return (0);
 175     }
 176
 177     p = (unsigned char *)to;
 178
 179     *(p++) = 0;
 180     *(p++) = 2;                 /* Public Key BT (Block Type) */
 181
 182     /* pad out with non-zero random data */
 183     j = tlen - 3 - flen;
 184
 185     if (RAND_bytes(p, j) <= 0)
 186         return (0);
 187     for (i = 0; i < j; i++) {
 188         if (*p == '\0')
 189             do {
 190                 if (RAND_bytes(p, 1) <= 0)
 191                     return (0);
 192             } while (*p == '\0');
 193         p++;
 194     }
 195
 196     *(p++) = '\0';
 197
 198     memcpy(p, from, (unsigned int)flen);
 199     return (1);
 200 }
 201
 202 int RSA_padding_check_PKCS1_type_2(unsigned char *to, int tlen,
 203                                    const unsigned char *from, int flen,
 204                                    int num)
 205 {
 206     int i;
 207     /* |em| is the encoded message, zero-padded to exactly |num| bytes */
 208     unsigned char *em = NULL;
 209     unsigned int good, found_zero_byte;
 210     int zero_index = 0, msg_index, mlen = -1;
 211
 212     if (tlen < 0 || flen < 0)
 213         return -1;
 214
 215     /*
 216      * PKCS#1 v1.5 decryption. See "PKCS #1 v2.2: RSA Cryptography Standard",
 217      * section 7.2.2.
 218      */
 219
 220     if (flen > num)
 221         goto err;
 222
 223     if (num < 11)
 224         goto err;
 225
 226     em = OPENSSL_zalloc(num);
 227     if (em == NULL) {
 228         RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2, ERR_R_MALLOC_FAILURE);
 229         return -1;
 230     }
 231     /*
 232      * Always do this zero-padding copy (even when num == flen) to avoid
 233      * leaking that information. The copy still leaks some side-channel
 234      * information, but it's impossible to have a fixed  memory access
 235      * pattern since we can't read out of the bounds of |from|.
 236      *
 237      * TODO(emilia): Consider porting BN_bn2bin_padded from BoringSSL.
 238      */
 239     memcpy(em + num - flen, from, flen);
 240
 241     good = constant_time_is_zero(em[0]);
 242     good &= constant_time_eq(em[1], 2);
 243
 244     found_zero_byte = 0;
 245     for (i = 2; i < num; i++) {
 246         unsigned int equals0 = constant_time_is_zero(em[i]);
 247         zero_index =
 248             constant_time_select_int(~found_zero_byte & equals0, i,
 249                                      zero_index);
 250         found_zero_byte |= equals0;
 251     }
 252
 253     /*
 254      * PS must be at least 8 bytes long, and it starts two bytes into |em|.
 255      * If we never found a 0-byte, then |zero_index| is 0 and the check
 256      * also fails.
 257      */
 258     good &= constant_time_ge((unsigned int)(zero_index), 2 + 8);
 259
 260     /*
 261      * Skip the zero byte. This is incorrect if we never found a zero-byte
 262      * but in this case we also do not copy the message out.
 263      */
 264     msg_index = zero_index + 1;
 265     mlen = num - msg_index;
 266
 267     /*
 268      * For good measure, do this check in constant time as well; it could
 269      * leak something if |tlen| was assuming valid padding.
 270      */
 271     good &= constant_time_ge((unsigned int)(tlen), (unsigned int)(mlen));
 272
 273     /*
 274      * We can't continue in constant-time because we need to copy the result
 275      * and we cannot fake its length. This unavoidably leaks timing
 276      * information at the API boundary.
 277      * TODO(emilia): this could be addressed at the call site,
 278      * see BoringSSL commit 0aa0767340baf925bda4804882aab0cb974b2d26.
 279      */
 280     if (!good) {
 281         mlen = -1;
 282         goto err;
 283     }
 284
 285     memcpy(to, em + msg_index, mlen);
 286
 287  err:
 288     OPENSSL_free(em);
 289     if (mlen == -1)
 290         RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2,
 291                RSA_R_PKCS_DECODING_ERROR);
 292     return mlen;
 293 }