rsa_pk1.c revision 273149
153642Sguido/* crypto/rsa/rsa_pk1.c */ 280482Sdarrenr/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 353642Sguido * All rights reserved. 480482Sdarrenr * 553642Sguido * This package is an SSL implementation written 692685Sdarrenr * by Eric Young (eay@cryptsoft.com). 792685Sdarrenr * The implementation was written so as to conform with Netscapes SSL. 892685Sdarrenr * 953642Sguido * This library is free for commercial and non-commercial use as long as 1053642Sguido * the following conditions are aheared to. The following conditions 1153642Sguido * apply to all code found in this distribution, be it the RC4, RSA, 1253642Sguido * lhash, DES, etc., code; not just the SSL code. The SSL documentation 1353642Sguido * included with this distribution is covered by the same copyright terms 1453642Sguido * except that the holder is Tim Hudson (tjh@cryptsoft.com). 1553642Sguido * 1653642Sguido * Copyright remains Eric Young's, and as such any Copyright notices in 1753642Sguido * the code are not to be removed. 1853642Sguido * If this package is used in a product, Eric Young should be given attribution 1960850Sdarrenr * as the author of the parts of the library used. 2053642Sguido * This can be in the form of a textual message at program startup or 2153642Sguido * in documentation (online or textual) provided with the package. 2253642Sguido * 2353642Sguido * Redistribution and use in source and binary forms, with or without 2453642Sguido * modification, are permitted provided that the following conditions 2553642Sguido * are met: 2653642Sguido * 1. Redistributions of source code must retain the copyright 2753642Sguido * notice, this list of conditions and the following disclaimer. 2853642Sguido * 2. Redistributions in binary form must reproduce the above copyright 2957096Sguido * notice, this list of conditions and the following disclaimer in the 3053642Sguido * documentation and/or other materials provided with the distribution. 3153642Sguido * 3. All advertising materials mentioning features or use of this software 3253642Sguido * must display the following acknowledgement: 3353642Sguido * "This product includes cryptographic software written by 3453642Sguido * Eric Young (eay@cryptsoft.com)" 3553642Sguido * The word 'cryptographic' can be left out if the rouines from the library 3653642Sguido * being used are not cryptographic related :-). 3753642Sguido * 4. If you include any Windows specific code (or a derivative thereof) from 3853642Sguido * the apps directory (application code) you must include an acknowledgement: 3953642Sguido * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 4053642Sguido * 4153642Sguido * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 4253642Sguido * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 4353642Sguido * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 4453642Sguido * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 4564105Sroberto * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 4653642Sguido * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 4753642Sguido * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 4853642Sguido * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 4953642Sguido * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 5053642Sguido * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 5153642Sguido * SUCH DAMAGE. 5253642Sguido * 5353642Sguido * The licence and distribution terms for any publically available version or 5453642Sguido * derivative of this code cannot be changed. i.e. this code cannot simply be 5553642Sguido * copied and put under another distribution licence 5653642Sguido * [including the GNU Public Licence.] 5753642Sguido */ 5853642Sguido 5953642Sguido#include "constant_time_locl.h" 6053642Sguido 6153642Sguido#include <stdio.h> 6253642Sguido#include "cryptlib.h" 6353642Sguido#include <openssl/bn.h> 6453642Sguido#include <openssl/rsa.h> 6553642Sguido#include <openssl/rand.h> 6653642Sguido 6753642Sguidoint RSA_padding_add_PKCS1_type_1(unsigned char *to, int tlen, 6853642Sguido const unsigned char *from, int flen) 6953642Sguido { 7053642Sguido int j; 7153642Sguido unsigned char *p; 7253642Sguido 7353642Sguido if (flen > (tlen-RSA_PKCS1_PADDING_SIZE)) 7453642Sguido { 7553642Sguido RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_TYPE_1,RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE); 7680482Sdarrenr return(0); 7753642Sguido } 7853642Sguido 7953642Sguido p=(unsigned char *)to; 8053642Sguido 8153642Sguido *(p++)=0; 8253642Sguido *(p++)=1; /* Private Key BT (Block Type) */ 8353642Sguido 8453642Sguido /* pad out with 0xff data */ 8553642Sguido j=tlen-3-flen; 8653642Sguido memset(p,0xff,j); 8753642Sguido p+=j; 8853642Sguido *(p++)='\0'; 8953642Sguido memcpy(p,from,(unsigned int)flen); 9053642Sguido return(1); 9153642Sguido } 9253642Sguido 9353642Sguidoint RSA_padding_check_PKCS1_type_1(unsigned char *to, int tlen, 9453642Sguido const unsigned char *from, int flen, int num) 9553642Sguido { 9653642Sguido int i,j; 9753642Sguido const unsigned char *p; 9853642Sguido 9953642Sguido p=from; 10053642Sguido if ((num != (flen+1)) || (*(p++) != 01)) 10153642Sguido { 10253642Sguido RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1,RSA_R_BLOCK_TYPE_IS_NOT_01); 10353642Sguido return(-1); 10453642Sguido } 10553642Sguido 10680482Sdarrenr /* scan over padding data */ 10780482Sdarrenr j=flen-1; /* one for type. */ 10880482Sdarrenr for (i=0; i<j; i++) 10980482Sdarrenr { 11053642Sguido if (*p != 0xff) /* should decrypt to 0xff */ 11153642Sguido { 11253642Sguido if (*p == 0) 11380482Sdarrenr { p++; break; } 11453642Sguido else { 11553642Sguido RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1,RSA_R_BAD_FIXED_HEADER_DECRYPT); 11653642Sguido return(-1); 11753642Sguido } 11853642Sguido } 11953642Sguido p++; 12053642Sguido } 12153642Sguido 12253642Sguido if (i == j) 12353642Sguido { 12453642Sguido RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1,RSA_R_NULL_BEFORE_BLOCK_MISSING); 12553642Sguido return(-1); 12660850Sdarrenr } 12753642Sguido 12860850Sdarrenr if (i < 8) 12953642Sguido { 13060850Sdarrenr RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1,RSA_R_BAD_PAD_BYTE_COUNT); 13160850Sdarrenr return(-1); 13280482Sdarrenr } 13380482Sdarrenr i++; /* Skip over the '\0' */ 13453642Sguido j-=i; 13553642Sguido if (j > tlen) 13653642Sguido { 13753642Sguido RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1,RSA_R_DATA_TOO_LARGE); 13853642Sguido return(-1); 13953642Sguido } 14053642Sguido memcpy(to,p,(unsigned int)j); 14153642Sguido 14253642Sguido return(j); 14353642Sguido } 14453642Sguido 14553642Sguidoint RSA_padding_add_PKCS1_type_2(unsigned char *to, int tlen, 14680482Sdarrenr const unsigned char *from, int flen) 14780482Sdarrenr { 14853642Sguido int i,j; 14953642Sguido unsigned char *p; 15053642Sguido 15180482Sdarrenr if (flen > (tlen-11)) 15260850Sdarrenr { 15360850Sdarrenr RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_TYPE_2,RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE); 15453642Sguido return(0); 15553642Sguido } 15653642Sguido 15753642Sguido p=(unsigned char *)to; 15853642Sguido 15953642Sguido *(p++)=0; 16053642Sguido *(p++)=2; /* Public Key BT (Block Type) */ 16180482Sdarrenr 16280482Sdarrenr /* pad out with non-zero random data */ 16380482Sdarrenr j=tlen-3-flen; 16453642Sguido 16553642Sguido if (RAND_bytes(p,j) <= 0) 16653642Sguido return(0); 16780482Sdarrenr for (i=0; i<j; i++) 16853642Sguido { 16980482Sdarrenr if (*p == '\0') 17080482Sdarrenr do { 17180482Sdarrenr if (RAND_bytes(p,1) <= 0) 17280482Sdarrenr return(0); 17380482Sdarrenr } while (*p == '\0'); 17480482Sdarrenr p++; 17580482Sdarrenr } 17680482Sdarrenr 17780482Sdarrenr *(p++)='\0'; 17880482Sdarrenr 17980482Sdarrenr memcpy(p,from,(unsigned int)flen); 18080482Sdarrenr return(1); 18180482Sdarrenr } 18280482Sdarrenr 18380482Sdarrenrint RSA_padding_check_PKCS1_type_2(unsigned char *to, int tlen, 18480482Sdarrenr const unsigned char *from, int flen, int num) 18580482Sdarrenr { 18680482Sdarrenr int i; 18780482Sdarrenr /* |em| is the encoded message, zero-padded to exactly |num| bytes */ 18880482Sdarrenr unsigned char *em = NULL; 18980482Sdarrenr unsigned int good, found_zero_byte; 19080482Sdarrenr int zero_index = 0, msg_index, mlen = -1; 19180482Sdarrenr 19253642Sguido if (tlen < 0 || flen < 0) 19353642Sguido return -1; 19480482Sdarrenr 19580482Sdarrenr /* PKCS#1 v1.5 decryption. See "PKCS #1 v2.2: RSA Cryptography 19680482Sdarrenr * Standard", section 7.2.2. */ 19780482Sdarrenr 19853642Sguido if (flen > num) 19980482Sdarrenr goto err; 20053642Sguido 20153642Sguido if (num < 11) 20280482Sdarrenr goto err; 20353642Sguido 20480482Sdarrenr em = OPENSSL_malloc(num); 20580482Sdarrenr if (em == NULL) 20653642Sguido { 20780482Sdarrenr RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2, ERR_R_MALLOC_FAILURE); 20880482Sdarrenr return -1; 20953642Sguido } 21053642Sguido memset(em, 0, num); 21153642Sguido /* 21253642Sguido * Always do this zero-padding copy (even when num == flen) to avoid 21353642Sguido * leaking that information. The copy still leaks some side-channel 21453642Sguido * information, but it's impossible to have a fixed memory access 21553642Sguido * pattern since we can't read out of the bounds of |from|. 21653642Sguido * 21753642Sguido * TODO(emilia): Consider porting BN_bn2bin_padded from BoringSSL. 21853642Sguido */ 21953642Sguido memcpy(em + num - flen, from, flen); 22053642Sguido 22153642Sguido good = constant_time_is_zero(em[0]); 22253642Sguido good &= constant_time_eq(em[1], 2); 22353642Sguido 22453642Sguido found_zero_byte = 0; 22553642Sguido for (i = 2; i < num; i++) 22653642Sguido { 22753642Sguido unsigned int equals0 = constant_time_is_zero(em[i]); 22853642Sguido zero_index = constant_time_select_int(~found_zero_byte & equals0, i, zero_index); 22953642Sguido found_zero_byte |= equals0; 23053642Sguido } 23153642Sguido 23253642Sguido /* 23353642Sguido * PS must be at least 8 bytes long, and it starts two bytes into |em|. 23453642Sguido * If we never found a 0-byte, then |zero_index| is 0 and the check 23553642Sguido * also fails. 23660850Sdarrenr */ 23753642Sguido good &= constant_time_ge((unsigned int)(zero_index), 2 + 8); 23853642Sguido 23953642Sguido /* Skip the zero byte. This is incorrect if we never found a zero-byte 24053642Sguido * but in this case we also do not copy the message out. */ 24160850Sdarrenr msg_index = zero_index + 1; 24260850Sdarrenr mlen = num - msg_index; 24360850Sdarrenr 24480482Sdarrenr /* For good measure, do this check in constant time as well; it could 24553642Sguido * leak something if |tlen| was assuming valid padding. */ 24653642Sguido good &= constant_time_ge((unsigned int)(tlen), (unsigned int)(mlen)); 24760850Sdarrenr 24860850Sdarrenr /* 24960850Sdarrenr * We can't continue in constant-time because we need to copy the result 25053642Sguido * and we cannot fake its length. This unavoidably leaks timing 25153642Sguido * information at the API boundary. 25253642Sguido * TODO(emilia): this could be addressed at the call site, 25353642Sguido * see BoringSSL commit 0aa0767340baf925bda4804882aab0cb974b2d26. 25453642Sguido */ 25553642Sguido if (!good) 25680482Sdarrenr { 25753642Sguido mlen = -1; 25853642Sguido goto err; 25953642Sguido } 26053642Sguido 26153642Sguido memcpy(to, em + msg_index, mlen); 26253642Sguido 26353642Sguidoerr: 26453642Sguido if (em != NULL) 26553642Sguido OPENSSL_free(em); 26653642Sguido if (mlen == -1) 26753642Sguido RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2, RSA_R_PKCS_DECODING_ERROR); 26853642Sguido return mlen; 26980482Sdarrenr } 27080482Sdarrenr