156083Skris/* crypto/rsa/rsa_pk1.c */ 256083Skris/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 356083Skris * All rights reserved. 456083Skris * 556083Skris * This package is an SSL implementation written 656083Skris * by Eric Young (eay@cryptsoft.com). 756083Skris * The implementation was written so as to conform with Netscapes SSL. 8280297Sjkim * 956083Skris * This library is free for commercial and non-commercial use as long as 1056083Skris * the following conditions are aheared to. The following conditions 1156083Skris * apply to all code found in this distribution, be it the RC4, RSA, 1256083Skris * lhash, DES, etc., code; not just the SSL code. The SSL documentation 1356083Skris * included with this distribution is covered by the same copyright terms 1456083Skris * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15280297Sjkim * 1656083Skris * Copyright remains Eric Young's, and as such any Copyright notices in 1756083Skris * the code are not to be removed. 1856083Skris * If this package is used in a product, Eric Young should be given attribution 1956083Skris * as the author of the parts of the library used. 2056083Skris * This can be in the form of a textual message at program startup or 2156083Skris * in documentation (online or textual) provided with the package. 22280297Sjkim * 2356083Skris * Redistribution and use in source and binary forms, with or without 2456083Skris * modification, are permitted provided that the following conditions 2556083Skris * are met: 2656083Skris * 1. Redistributions of source code must retain the copyright 2756083Skris * notice, this list of conditions and the following disclaimer. 2856083Skris * 2. Redistributions in binary form must reproduce the above copyright 2956083Skris * notice, this list of conditions and the following disclaimer in the 3056083Skris * documentation and/or other materials provided with the distribution. 3156083Skris * 3. All advertising materials mentioning features or use of this software 3256083Skris * must display the following acknowledgement: 3356083Skris * "This product includes cryptographic software written by 3456083Skris * Eric Young (eay@cryptsoft.com)" 3556083Skris * The word 'cryptographic' can be left out if the rouines from the library 3656083Skris * being used are not cryptographic related :-). 37280297Sjkim * 4. If you include any Windows specific code (or a derivative thereof) from 3856083Skris * the apps directory (application code) you must include an acknowledgement: 3956083Skris * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40280297Sjkim * 4156083Skris * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 4256083Skris * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 4356083Skris * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 4456083Skris * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 4556083Skris * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 4656083Skris * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 4756083Skris * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 4856083Skris * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 4956083Skris * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 5056083Skris * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 5156083Skris * SUCH DAMAGE. 52280297Sjkim * 5356083Skris * The licence and distribution terms for any publically available version or 5456083Skris * derivative of this code cannot be changed. i.e. this code cannot simply be 5556083Skris * copied and put under another distribution licence 5656083Skris * [including the GNU Public Licence.] 5756083Skris */ 5856083Skris 59273144Sjkim#include "constant_time_locl.h" 60273144Sjkim 6156083Skris#include <stdio.h> 6256083Skris#include "cryptlib.h" 6356083Skris#include <openssl/bn.h> 6456083Skris#include <openssl/rsa.h> 6556083Skris#include <openssl/rand.h> 6656083Skris 6756083Skrisint RSA_padding_add_PKCS1_type_1(unsigned char *to, int tlen, 68280297Sjkim const unsigned char *from, int flen) 69280297Sjkim{ 70280297Sjkim int j; 71280297Sjkim unsigned char *p; 7256083Skris 73280297Sjkim if (flen > (tlen - RSA_PKCS1_PADDING_SIZE)) { 74280297Sjkim RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_TYPE_1, 75280297Sjkim RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE); 76280297Sjkim return (0); 77280297Sjkim } 7856083Skris 79280297Sjkim p = (unsigned char *)to; 8056083Skris 81280297Sjkim *(p++) = 0; 82280297Sjkim *(p++) = 1; /* Private Key BT (Block Type) */ 8356083Skris 84280297Sjkim /* pad out with 0xff data */ 85280297Sjkim j = tlen - 3 - flen; 86280297Sjkim memset(p, 0xff, j); 87280297Sjkim p += j; 88280297Sjkim *(p++) = '\0'; 89280297Sjkim memcpy(p, from, (unsigned int)flen); 90280297Sjkim return (1); 91280297Sjkim} 92280297Sjkim 9356083Skrisint RSA_padding_check_PKCS1_type_1(unsigned char *to, int tlen, 94280297Sjkim const unsigned char *from, int flen, 95280297Sjkim int num) 96280297Sjkim{ 97280297Sjkim int i, j; 98280297Sjkim const unsigned char *p; 9956083Skris 100280297Sjkim p = from; 101337982Sjkim 102337982Sjkim /* 103337982Sjkim * The format is 104337982Sjkim * 00 || 01 || PS || 00 || D 105337982Sjkim * PS - padding string, at least 8 bytes of FF 106337982Sjkim * D - data. 107337982Sjkim */ 108337982Sjkim 109337982Sjkim if (num < 11) 110337982Sjkim return -1; 111337982Sjkim 112337982Sjkim /* Accept inputs with and without the leading 0-byte. */ 113337982Sjkim if (num == flen) { 114337982Sjkim if ((*p++) != 0x00) { 115337982Sjkim RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1, 116337982Sjkim RSA_R_INVALID_PADDING); 117337982Sjkim return -1; 118337982Sjkim } 119337982Sjkim flen--; 120337982Sjkim } 121337982Sjkim 122280297Sjkim if ((num != (flen + 1)) || (*(p++) != 01)) { 123280297Sjkim RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1, 124280297Sjkim RSA_R_BLOCK_TYPE_IS_NOT_01); 125280297Sjkim return (-1); 126280297Sjkim } 12756083Skris 128280297Sjkim /* scan over padding data */ 129280297Sjkim j = flen - 1; /* one for type. */ 130280297Sjkim for (i = 0; i < j; i++) { 131280297Sjkim if (*p != 0xff) { /* should decrypt to 0xff */ 132280297Sjkim if (*p == 0) { 133280297Sjkim p++; 134280297Sjkim break; 135280297Sjkim } else { 136280297Sjkim RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1, 137280297Sjkim RSA_R_BAD_FIXED_HEADER_DECRYPT); 138280297Sjkim return (-1); 139280297Sjkim } 140280297Sjkim } 141280297Sjkim p++; 142280297Sjkim } 14356083Skris 144280297Sjkim if (i == j) { 145280297Sjkim RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1, 146280297Sjkim RSA_R_NULL_BEFORE_BLOCK_MISSING); 147280297Sjkim return (-1); 148280297Sjkim } 14956083Skris 150280297Sjkim if (i < 8) { 151280297Sjkim RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1, 152280297Sjkim RSA_R_BAD_PAD_BYTE_COUNT); 153280297Sjkim return (-1); 154280297Sjkim } 155280297Sjkim i++; /* Skip over the '\0' */ 156280297Sjkim j -= i; 157280297Sjkim if (j > tlen) { 158280297Sjkim RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_1, RSA_R_DATA_TOO_LARGE); 159280297Sjkim return (-1); 160280297Sjkim } 161280297Sjkim memcpy(to, p, (unsigned int)j); 16256083Skris 163280297Sjkim return (j); 164280297Sjkim} 16556083Skris 16656083Skrisint RSA_padding_add_PKCS1_type_2(unsigned char *to, int tlen, 167280297Sjkim const unsigned char *from, int flen) 168280297Sjkim{ 169280297Sjkim int i, j; 170280297Sjkim unsigned char *p; 17156083Skris 172280297Sjkim if (flen > (tlen - 11)) { 173280297Sjkim RSAerr(RSA_F_RSA_PADDING_ADD_PKCS1_TYPE_2, 174280297Sjkim RSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE); 175280297Sjkim return (0); 176280297Sjkim } 17756083Skris 178280297Sjkim p = (unsigned char *)to; 17956083Skris 180280297Sjkim *(p++) = 0; 181280297Sjkim *(p++) = 2; /* Public Key BT (Block Type) */ 18256083Skris 183280297Sjkim /* pad out with non-zero random data */ 184280297Sjkim j = tlen - 3 - flen; 18556083Skris 186280297Sjkim if (RAND_bytes(p, j) <= 0) 187280297Sjkim return (0); 188280297Sjkim for (i = 0; i < j; i++) { 189280297Sjkim if (*p == '\0') 190280297Sjkim do { 191280297Sjkim if (RAND_bytes(p, 1) <= 0) 192280297Sjkim return (0); 193280297Sjkim } while (*p == '\0'); 194280297Sjkim p++; 195280297Sjkim } 19656083Skris 197280297Sjkim *(p++) = '\0'; 198280297Sjkim 199280297Sjkim memcpy(p, from, (unsigned int)flen); 200280297Sjkim return (1); 201280297Sjkim} 202280297Sjkim 20356083Skrisint RSA_padding_check_PKCS1_type_2(unsigned char *to, int tlen, 204280297Sjkim const unsigned char *from, int flen, 205280297Sjkim int num) 206280297Sjkim{ 207280297Sjkim int i; 208280297Sjkim /* |em| is the encoded message, zero-padded to exactly |num| bytes */ 209280297Sjkim unsigned char *em = NULL; 210344604Sjkim unsigned int good, found_zero_byte, mask; 211280297Sjkim int zero_index = 0, msg_index, mlen = -1; 21256083Skris 213280297Sjkim if (tlen < 0 || flen < 0) 214280297Sjkim return -1; 215273144Sjkim 216280297Sjkim /* 217280297Sjkim * PKCS#1 v1.5 decryption. See "PKCS #1 v2.2: RSA Cryptography Standard", 218280297Sjkim * section 7.2.2. 219280297Sjkim */ 220273144Sjkim 221344604Sjkim if (flen > num || num < 11) { 222344604Sjkim RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2, 223344604Sjkim RSA_R_PKCS_DECODING_ERROR); 224344604Sjkim return -1; 225344604Sjkim } 226273144Sjkim 227344604Sjkim em = OPENSSL_malloc(num); 228344604Sjkim if (em == NULL) { 229344604Sjkim RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2, ERR_R_MALLOC_FAILURE); 230344604Sjkim return -1; 231280297Sjkim } 232344604Sjkim /* 233344604Sjkim * Caller is encouraged to pass zero-padded message created with 234344604Sjkim * BN_bn2binpad. Trouble is that since we can't read out of |from|'s 235344604Sjkim * bounds, it's impossible to have an invariant memory access pattern 236344604Sjkim * in case |from| was not zero-padded in advance. 237344604Sjkim */ 238344604Sjkim for (from += flen, em += num, i = 0; i < num; i++) { 239344604Sjkim mask = ~constant_time_is_zero(flen); 240344604Sjkim flen -= 1 & mask; 241344604Sjkim from -= 1 & mask; 242344604Sjkim *--em = *from & mask; 243344604Sjkim } 24456083Skris 245348343Sjkim good = constant_time_is_zero(em[0]); 246348343Sjkim good &= constant_time_eq(em[1], 2); 24756083Skris 248344604Sjkim /* scan over padding data */ 249280297Sjkim found_zero_byte = 0; 250280297Sjkim for (i = 2; i < num; i++) { 251348343Sjkim unsigned int equals0 = constant_time_is_zero(em[i]); 252344604Sjkim 253344604Sjkim zero_index = constant_time_select_int(~found_zero_byte & equals0, 254344604Sjkim i, zero_index); 255280297Sjkim found_zero_byte |= equals0; 256280297Sjkim } 25756083Skris 258280297Sjkim /* 259348343Sjkim * PS must be at least 8 bytes long, and it starts two bytes into |em|. 260280297Sjkim * If we never found a 0-byte, then |zero_index| is 0 and the check 261280297Sjkim * also fails. 262280297Sjkim */ 263344604Sjkim good &= constant_time_ge(zero_index, 2 + 8); 264273144Sjkim 265280297Sjkim /* 266280297Sjkim * Skip the zero byte. This is incorrect if we never found a zero-byte 267280297Sjkim * but in this case we also do not copy the message out. 268280297Sjkim */ 269280297Sjkim msg_index = zero_index + 1; 270280297Sjkim mlen = num - msg_index; 271273144Sjkim 272280297Sjkim /* 273344604Sjkim * For good measure, do this check in constant time as well. 274280297Sjkim */ 275344604Sjkim good &= constant_time_ge(tlen, mlen); 276273144Sjkim 277280297Sjkim /* 278348343Sjkim * Move the result in-place by |num|-11-|mlen| bytes to the left. 279348343Sjkim * Then if |good| move |mlen| bytes from |em|+11 to |to|. 280348343Sjkim * Otherwise leave |to| unchanged. 281348343Sjkim * Copy the memory back in a way that does not reveal the size of 282348343Sjkim * the data being copied via a timing side channel. This requires copying 283348343Sjkim * parts of the buffer multiple times based on the bits set in the real 284348343Sjkim * length. Clear bits do a non-copy with identical access pattern. 285348343Sjkim * The loop below has overall complexity of O(N*log(N)). 286280297Sjkim */ 287348343Sjkim tlen = constant_time_select_int(constant_time_lt(num - 11, tlen), 288348343Sjkim num - 11, tlen); 289348343Sjkim for (msg_index = 1; msg_index < num - 11; msg_index <<= 1) { 290348343Sjkim mask = ~constant_time_eq(msg_index & (num - 11 - mlen), 0); 291348343Sjkim for (i = 11; i < num - msg_index; i++) 292348343Sjkim em[i] = constant_time_select_8(mask, em[i + msg_index], em[i]); 293280297Sjkim } 294348343Sjkim for (i = 0; i < tlen; i++) { 295348343Sjkim mask = good & constant_time_lt(i, mlen); 296348343Sjkim to[i] = constant_time_select_8(mask, em[i + 11], to[i]); 297348343Sjkim } 29856083Skris 299344604Sjkim OPENSSL_cleanse(em, num); 300344604Sjkim OPENSSL_free(em); 301344604Sjkim RSAerr(RSA_F_RSA_PADDING_CHECK_PKCS1_TYPE_2, RSA_R_PKCS_DECODING_ERROR); 302344604Sjkim err_clear_last_constant_time(1 & good); 303273144Sjkim 304344604Sjkim return constant_time_select_int(good, mlen, -1); 305280297Sjkim} 306