rsa_pk1.c revision 325337
1139776Simp/* crypto/rsa/rsa_pk1.c */ 275374Sbp/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 375374Sbp * All rights reserved. 475374Sbp * 575374Sbp * This package is an SSL implementation written 675374Sbp * by Eric Young (eay@cryptsoft.com). 775374Sbp * The implementation was written so as to conform with Netscapes SSL. 875374Sbp * 975374Sbp * This library is free for commercial and non-commercial use as long as 1075374Sbp * the following conditions are aheared to. The following conditions 1175374Sbp * apply to all code found in this distribution, be it the RC4, RSA, 1275374Sbp * lhash, DES, etc., code; not just the SSL code. The SSL documentation 1375374Sbp * included with this distribution is covered by the same copyright terms 1475374Sbp * except that the holder is Tim Hudson (tjh@cryptsoft.com). 1575374Sbp * 1675374Sbp * Copyright remains Eric Young's, and as such any Copyright notices in 1775374Sbp * the code are not to be removed. 1875374Sbp * If this package is used in a product, Eric Young should be given attribution 1975374Sbp * as the author of the parts of the library used. 2075374Sbp * This can be in the form of a textual message at program startup or 2175374Sbp * in documentation (online or textual) provided with the package. 2275374Sbp * 2375374Sbp * Redistribution and use in source and binary forms, with or without 2475374Sbp * modification, are permitted provided that the following conditions 2575374Sbp * are met: 2675374Sbp * 1. Redistributions of source code must retain the copyright 2775374Sbp * notice, this list of conditions and the following disclaimer. 2875374Sbp * 2. Redistributions in binary form must reproduce the above copyright 2975374Sbp * notice, this list of conditions and the following disclaimer in the 3075374Sbp * documentation and/or other materials provided with the distribution. 3175374Sbp * 3. All advertising materials mentioning features or use of this software 3275374Sbp * must display the following acknowledgement: 3375374Sbp * "This product includes cryptographic software written by 3475374Sbp * Eric Young (eay@cryptsoft.com)" 3575374Sbp * The word 'cryptographic' can be left out if the rouines from the library 3675374Sbp * being used are not cryptographic related :-). 3775374Sbp * 4. If you include any Windows specific code (or a derivative thereof) from 3875374Sbp * the apps directory (application code) you must include an acknowledgement: 3975374Sbp * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 4075374Sbp * 4175374Sbp * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 4275374Sbp * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 4375374Sbp * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 4475374Sbp * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 4575374Sbp * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 4675374Sbp * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 4775374Sbp * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 4875374Sbp * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 4975374Sbp * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 5075374Sbp * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 5175374Sbp * SUCH DAMAGE. 5275374Sbp * 5375374Sbp * The licence and distribution terms for any publically available version or 5475374Sbp * derivative of this code cannot be changed. i.e. this code cannot simply be 5575374Sbp * copied and put under another distribution licence 5675374Sbp * [including the GNU Public Licence.] 5775374Sbp */ 5875374Sbp 5975374Sbp#include "constant_time_locl.h" 6075374Sbp 6175374Sbp#include <stdio.h> 6275374Sbp#include "cryptlib.h" 6375374Sbp#include <openssl/bn.h> 6475374Sbp#include <openssl/rsa.h> 6575374Sbp#include <openssl/rand.h> 6675374Sbp 6775374Sbpint RSA_padding_add_PKCS1_type_1(unsigned char *to, int tlen, 6875374Sbp const unsigned char *from, int flen) 6975374Sbp{ 7075374Sbp int j; 7175374Sbp unsigned char *p; 7275374Sbp 7375374Sbp if (flen > (tlen - RSA_PKCS1_PADDING_SIZE)) { 7475374Sbp RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_TYPE_1, 7575374Sbp RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE); 7675374Sbp return (0); 7775374Sbp } 7875374Sbp 7975374Sbp p = (unsigned char *)to; 8075374Sbp 8175374Sbp *(p++) = 0; 8275374Sbp *(p++) = 1; /* Private Key BT (Block Type) */ 8375374Sbp 8475374Sbp /* pad out with 0xff data */ 8575374Sbp j = tlen - 3 - flen; 8675374Sbp memset(p, 0xff, j); 8775374Sbp p += j; 8875374Sbp *(p++) = '\0'; 8975374Sbp memcpy(p, from, (unsigned int)flen); 9075374Sbp return (1); 9175374Sbp} 9275374Sbp 9375374Sbpint RSA_padding_check_PKCS1_type_1(unsigned char *to, int tlen, 9475374Sbp const unsigned char *from, int flen, 9575374Sbp int num) 9675374Sbp{ 9775374Sbp int i, j; 9875374Sbp const unsigned char *p; 9975374Sbp 10075374Sbp p = from; 101103533Sbp if ((num != (flen + 1)) || (*(p++) != 01)) { 10275374Sbp RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1, 10375374Sbp RSA_R_BLOCK_TYPE_IS_NOT_01); 10475374Sbp return (-1); 10575374Sbp } 10675374Sbp 107103533Sbp /* scan over padding data */ 10875374Sbp j = flen - 1; /* one for type. */ 10975374Sbp for (i = 0; i < j; i++) { 11075374Sbp if (*p != 0xff) { /* should decrypt to 0xff */ 11175374Sbp if (*p == 0) { 11275374Sbp p++; 11375374Sbp break; 11475374Sbp } else { 11575374Sbp RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1, 11675374Sbp RSA_R_BAD_FIXED_HEADER_DECRYPT); 11775374Sbp return (-1); 11875374Sbp } 11975374Sbp } 12075374Sbp p++; 12175374Sbp } 12275374Sbp 12375374Sbp if (i == j) { 12475374Sbp RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1, 12575374Sbp RSA_R_NULL_BEFORE_BLOCK_MISSING); 12675374Sbp return (-1); 12775374Sbp } 12875374Sbp 12975374Sbp if (i < 8) { 13075374Sbp RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1, 13175374Sbp RSA_R_BAD_PAD_BYTE_COUNT); 13275374Sbp return (-1); 133106595Sjhb } 13475374Sbp i++; /* Skip over the '\0' */ 13575374Sbp j -= i; 13675374Sbp if (j > tlen) { 13775374Sbp RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1, RSA_R_DATA_TOO_LARGE); 13875374Sbp return (-1); 13975374Sbp } 14075374Sbp memcpy(to, p, (unsigned int)j); 14175374Sbp 14275374Sbp return (j); 14375374Sbp} 14475374Sbp 14575374Sbpint RSA_padding_add_PKCS1_type_2(unsigned char *to, int tlen, 14675374Sbp const unsigned char *from, int flen) 14775374Sbp{ 14875374Sbp int i, j; 14975374Sbp unsigned char *p; 15075374Sbp 15175374Sbp if (flen > (tlen - 11)) { 15275374Sbp RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_TYPE_2, 15375374Sbp RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE); 15475374Sbp return (0); 15575374Sbp } 15675374Sbp 15775374Sbp p = (unsigned char *)to; 15875374Sbp 15975374Sbp *(p++) = 0; 16075374Sbp *(p++) = 2; /* Public Key BT (Block Type) */ 16175374Sbp 16275374Sbp /* pad out with non-zero random data */ 16375374Sbp j = tlen - 3 - flen; 16475374Sbp 16575374Sbp if (RAND_bytes(p, j) <= 0) 16675374Sbp return (0); 16796755Strhodes for (i = 0; i < j; i++) { 16896755Strhodes if (*p == '\0') 16975374Sbp do { 17075374Sbp if (RAND_bytes(p, 1) <= 0) 17196755Strhodes return (0); 17275374Sbp } while (*p == '\0'); 17375374Sbp p++; 17475374Sbp } 17575374Sbp 17675374Sbp *(p++) = '\0'; 17775374Sbp 17875374Sbp memcpy(p, from, (unsigned int)flen); 17975374Sbp return (1); 18075374Sbp} 18175374Sbp 18275374Sbpint RSA_padding_check_PKCS1_type_2(unsigned char *to, int tlen, 18375374Sbp const unsigned char *from, int flen, 18475374Sbp int num) 18575374Sbp{ 18675374Sbp int i; 18775374Sbp /* |em| is the encoded message, zero-padded to exactly |num| bytes */ 18875374Sbp unsigned char *em = NULL; 18975374Sbp unsigned int good, found_zero_byte; 19075374Sbp int zero_index = 0, msg_index, mlen = -1; 19175374Sbp 19275374Sbp if (tlen < 0 || flen < 0) 19375374Sbp return -1; 19475374Sbp 19575374Sbp /* 19675374Sbp * PKCS#1 v1.5 decryption. See "PKCS #1 v2.2: RSA Cryptography Standard", 19775374Sbp * section 7.2.2. 19875374Sbp */ 19975374Sbp 20075374Sbp if (flen > num) 20175374Sbp goto err; 20275374Sbp 20396755Strhodes if (num < 11) 20496755Strhodes goto err; 20575374Sbp 20675374Sbp em = OPENSSL_malloc(num); 20796755Strhodes if (em == NULL) { 20875374Sbp RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2, ERR_R_MALLOC_FAILURE); 20975374Sbp return -1; 21075374Sbp } 21175374Sbp memset(em, 0, num); 21275374Sbp /* 213103533Sbp * Always do this zero-padding copy (even when num == flen) to avoid 214103533Sbp * leaking that information. The copy still leaks some side-channel 215103533Sbp * information, but it's impossible to have a fixed memory access 216103533Sbp * pattern since we can't read out of the bounds of |from|. 217103533Sbp * 218103533Sbp * TODO(emilia): Consider porting BN_bn2bin_padded from BoringSSL. 219103533Sbp */ 220103533Sbp memcpy(em + num - flen, from, flen); 221103533Sbp 222103533Sbp good = constant_time_is_zero(em[0]); 223103533Sbp good &= constant_time_eq(em[1], 2); 224103533Sbp 225103533Sbp found_zero_byte = 0; 226103533Sbp for (i = 2; i < num; i++) { 227103533Sbp unsigned int equals0 = constant_time_is_zero(em[i]); 228103533Sbp zero_index = 229103533Sbp constant_time_select_int(~found_zero_byte & equals0, i, 230103533Sbp zero_index); 231103533Sbp found_zero_byte |= equals0; 232103533Sbp } 233103533Sbp 234103533Sbp /* 235103533Sbp * PS must be at least 8 bytes long, and it starts two bytes into |em|. 236103533Sbp * If we never found a 0-byte, then |zero_index| is 0 and the check 237103533Sbp * also fails. 238103533Sbp */ 239103533Sbp good &= constant_time_ge((unsigned int)(zero_index), 2 + 8); 240103533Sbp 241103533Sbp /* 242103533Sbp * Skip the zero byte. This is incorrect if we never found a zero-byte 243103533Sbp * but in this case we also do not copy the message out. 244103533Sbp */ 245103533Sbp msg_index = zero_index + 1; 246103533Sbp mlen = num - msg_index; 247103533Sbp 248103533Sbp /* 249103533Sbp * For good measure, do this check in constant time as well; it could 250124434Stjr * leak something if |tlen| was assuming valid padding. 251116486Stjr */ 252108470Sschweikh good &= constant_time_ge((unsigned int)(tlen), (unsigned int)(mlen)); 253103533Sbp 254103533Sbp /* 255103533Sbp * We can't continue in constant-time because we need to copy the result 256103533Sbp * and we cannot fake its length. This unavoidably leaks timing 257103533Sbp * information at the API boundary. 258103533Sbp */ 259103533Sbp if (!good) { 260103533Sbp mlen = -1; 261103533Sbp goto err; 262103533Sbp } 263103533Sbp 264103533Sbp memcpy(to, em + msg_index, mlen); 265103533Sbp 266103533Sbp err: 267103533Sbp if (em != NULL) { 268103533Sbp OPENSSL_cleanse(em, num); 26975374Sbp OPENSSL_free(em); 270103533Sbp } 271103533Sbp if (mlen == -1) 272103533Sbp RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2, 273103533Sbp RSA_R_PKCS_DECODING_ERROR); 274103533Sbp return mlen; 275103533Sbp} 276103533Sbp