check reviewer --reviewer=emilia
[openssl.git] / 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 }