AES CTR-DRGB: do not leak timing information
[openssl.git] / crypto / rand / drbg_ctr.c
1 /*
2  * Copyright 2011-2018 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the Apache License 2.0 (the "License").  You may not use
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
7  * https://www.openssl.org/source/license.html
8  */
9
10 #include <stdlib.h>
11 #include <string.h>
12 #include <openssl/crypto.h>
13 #include <openssl/err.h>
14 #include <openssl/rand.h>
15 #include "crypto/modes.h"
16 #include "internal/thread_once.h"
17 #include "rand_local.h"
18
19 /*
20  * Implementation of NIST SP 800-90A CTR DRBG.
21  */
22 static void inc_128(RAND_DRBG_CTR *ctr)
23 {
24     unsigned char *p = &ctr->V[0];
25     u32 n = 16, c = 1;
26
27     do {
28         --n;
29         c += p[n];
30         p[n] = (u8)c;
31         c >>= 8;
32     } while (n);
33 }
34
35 static void ctr_XOR(RAND_DRBG_CTR *ctr, const unsigned char *in, size_t inlen)
36 {
37     size_t i, n;
38
39     if (in == NULL || inlen == 0)
40         return;
41
42     /*
43      * Any zero padding will have no effect on the result as we
44      * are XORing. So just process however much input we have.
45      */
46     n = inlen < ctr->keylen ? inlen : ctr->keylen;
47     for (i = 0; i < n; i++)
48         ctr->K[i] ^= in[i];
49     if (inlen <= ctr->keylen)
50         return;
51
52     n = inlen - ctr->keylen;
53     if (n > 16) {
54         /* Should never happen */
55         n = 16;
56     }
57     for (i = 0; i < n; i++)
58         ctr->V[i] ^= in[i + ctr->keylen];
59 }
60
61 /*
62  * Process a complete block using BCC algorithm of SP 800-90A 10.3.3
63  */
64 __owur static int ctr_BCC_block(RAND_DRBG_CTR *ctr, unsigned char *out,
65                                 const unsigned char *in, int len)
66 {
67     int i, outlen = AES_BLOCK_SIZE;
68
69     for (i = 0; i < len; i++)
70         out[i] ^= in[i];
71
72     if (!EVP_CipherUpdate(ctr->ctx_df, out, &outlen, out, len)
73         || outlen != len)
74         return 0;
75     return 1;
76 }
77
78
79 /*
80  * Handle several BCC operations for as much data as we need for K and X
81  */
82 __owur static int ctr_BCC_blocks(RAND_DRBG_CTR *ctr, const unsigned char *in)
83 {
84     unsigned char in_tmp[48];
85     unsigned char num_of_blk = 2;
86
87     memcpy(in_tmp, in, 16);
88     memcpy(in_tmp + 16, in, 16);
89     if (ctr->keylen != 16) {
90         memcpy(in_tmp + 32, in, 16);
91         num_of_blk = 3;
92     }
93     return ctr_BCC_block(ctr, ctr->KX, in_tmp, AES_BLOCK_SIZE * num_of_blk);
94 }
95
96 /*
97  * Initialise BCC blocks: these have the value 0,1,2 in leftmost positions:
98  * see 10.3.1 stage 7.
99  */
100 __owur static int ctr_BCC_init(RAND_DRBG_CTR *ctr)
101 {
102     unsigned char bltmp[48] = {0};
103     unsigned char num_of_blk;
104
105     memset(ctr->KX, 0, 48);
106     num_of_blk = ctr->keylen == 16 ? 2 : 3;
107     bltmp[(AES_BLOCK_SIZE * 1) + 3] = 1;
108     bltmp[(AES_BLOCK_SIZE * 2) + 3] = 2;
109     return ctr_BCC_block(ctr, ctr->KX, bltmp, num_of_blk * AES_BLOCK_SIZE);
110 }
111
112 /*
113  * Process several blocks into BCC algorithm, some possibly partial
114  */
115 __owur static int ctr_BCC_update(RAND_DRBG_CTR *ctr,
116                                  const unsigned char *in, size_t inlen)
117 {
118     if (in == NULL || inlen == 0)
119         return 1;
120
121     /* If we have partial block handle it first */
122     if (ctr->bltmp_pos) {
123         size_t left = 16 - ctr->bltmp_pos;
124
125         /* If we now have a complete block process it */
126         if (inlen >= left) {
127             memcpy(ctr->bltmp + ctr->bltmp_pos, in, left);
128             if (!ctr_BCC_blocks(ctr, ctr->bltmp))
129                 return 0;
130             ctr->bltmp_pos = 0;
131             inlen -= left;
132             in += left;
133         }
134     }
135
136     /* Process zero or more complete blocks */
137     for (; inlen >= 16; in += 16, inlen -= 16) {
138         if (!ctr_BCC_blocks(ctr, in))
139             return 0;
140     }
141
142     /* Copy any remaining partial block to the temporary buffer */
143     if (inlen > 0) {
144         memcpy(ctr->bltmp + ctr->bltmp_pos, in, inlen);
145         ctr->bltmp_pos += inlen;
146     }
147     return 1;
148 }
149
150 __owur static int ctr_BCC_final(RAND_DRBG_CTR *ctr)
151 {
152     if (ctr->bltmp_pos) {
153         memset(ctr->bltmp + ctr->bltmp_pos, 0, 16 - ctr->bltmp_pos);
154         if (!ctr_BCC_blocks(ctr, ctr->bltmp))
155             return 0;
156     }
157     return 1;
158 }
159
160 __owur static int ctr_df(RAND_DRBG_CTR *ctr,
161                          const unsigned char *in1, size_t in1len,
162                          const unsigned char *in2, size_t in2len,
163                          const unsigned char *in3, size_t in3len)
164 {
165     static unsigned char c80 = 0x80;
166     size_t inlen;
167     unsigned char *p = ctr->bltmp;
168     int outlen = AES_BLOCK_SIZE;
169
170     if (!ctr_BCC_init(ctr))
171         return 0;
172     if (in1 == NULL)
173         in1len = 0;
174     if (in2 == NULL)
175         in2len = 0;
176     if (in3 == NULL)
177         in3len = 0;
178     inlen = in1len + in2len + in3len;
179     /* Initialise L||N in temporary block */
180     *p++ = (inlen >> 24) & 0xff;
181     *p++ = (inlen >> 16) & 0xff;
182     *p++ = (inlen >> 8) & 0xff;
183     *p++ = inlen & 0xff;
184
185     /* NB keylen is at most 32 bytes */
186     *p++ = 0;
187     *p++ = 0;
188     *p++ = 0;
189     *p = (unsigned char)((ctr->keylen + 16) & 0xff);
190     ctr->bltmp_pos = 8;
191     if (!ctr_BCC_update(ctr, in1, in1len)
192         || !ctr_BCC_update(ctr, in2, in2len)
193         || !ctr_BCC_update(ctr, in3, in3len)
194         || !ctr_BCC_update(ctr, &c80, 1)
195         || !ctr_BCC_final(ctr))
196         return 0;
197     /* Set up key K */
198     if (!EVP_CipherInit_ex(ctr->ctx_ecb, NULL, NULL, ctr->KX, NULL, -1))
199         return 0;
200     /* X follows key K */
201     if (!EVP_CipherUpdate(ctr->ctx_ecb, ctr->KX, &outlen, ctr->KX + ctr->keylen,
202                           AES_BLOCK_SIZE)
203         || outlen != AES_BLOCK_SIZE)
204         return 0;
205     if (!EVP_CipherUpdate(ctr->ctx_ecb, ctr->KX + 16, &outlen, ctr->KX,
206                           AES_BLOCK_SIZE)
207         || outlen != AES_BLOCK_SIZE)
208         return 0;
209     if (ctr->keylen != 16)
210         if (!EVP_CipherUpdate(ctr->ctx_ecb, ctr->KX + 32, &outlen,
211                               ctr->KX + 16, AES_BLOCK_SIZE)
212             || outlen != AES_BLOCK_SIZE)
213             return 0;
214     return 1;
215 }
216
217 /*
218  * NB the no-df Update in SP800-90A specifies a constant input length
219  * of seedlen, however other uses of this algorithm pad the input with
220  * zeroes if necessary and have up to two parameters XORed together,
221  * so we handle both cases in this function instead.
222  */
223 __owur static int ctr_update(RAND_DRBG *drbg,
224                              const unsigned char *in1, size_t in1len,
225                              const unsigned char *in2, size_t in2len,
226                              const unsigned char *nonce, size_t noncelen)
227 {
228     RAND_DRBG_CTR *ctr = &drbg->data.ctr;
229     int outlen = AES_BLOCK_SIZE;
230     unsigned char V_tmp[48], out[48];
231     unsigned char len;
232
233     /* correct key is already set up. */
234     memcpy(V_tmp, ctr->V, 16);
235     inc_128(ctr);
236     memcpy(V_tmp + 16, ctr->V, 16);
237     if (ctr->keylen == 16) {
238         len = 32;
239     } else {
240         inc_128(ctr);
241         memcpy(V_tmp + 32, ctr->V, 16);
242         len = 48;
243     }
244     if (!EVP_CipherUpdate(ctr->ctx_ecb, out, &outlen, V_tmp, len)
245             || outlen != len)
246         return 0;
247     memcpy(ctr->K, out, ctr->keylen);
248     memcpy(ctr->V, out + ctr->keylen, 16);
249
250     if ((drbg->flags & RAND_DRBG_FLAG_CTR_NO_DF) == 0) {
251         /* If no input reuse existing derived value */
252         if (in1 != NULL || nonce != NULL || in2 != NULL)
253             if (!ctr_df(ctr, in1, in1len, nonce, noncelen, in2, in2len))
254                 return 0;
255         /* If this a reuse input in1len != 0 */
256         if (in1len)
257             ctr_XOR(ctr, ctr->KX, drbg->seedlen);
258     } else {
259         ctr_XOR(ctr, in1, in1len);
260         ctr_XOR(ctr, in2, in2len);
261     }
262
263     if (!EVP_CipherInit_ex(ctr->ctx_ecb, NULL, NULL, ctr->K, NULL, -1)
264         || !EVP_CipherInit_ex(ctr->ctx_ctr, NULL, NULL, ctr->K, NULL, -1))
265         return 0;
266     return 1;
267 }
268
269 __owur static int drbg_ctr_instantiate(RAND_DRBG *drbg,
270                                        const unsigned char *entropy, size_t entropylen,
271                                        const unsigned char *nonce, size_t noncelen,
272                                        const unsigned char *pers, size_t perslen)
273 {
274     RAND_DRBG_CTR *ctr = &drbg->data.ctr;
275
276     if (entropy == NULL)
277         return 0;
278
279     memset(ctr->K, 0, sizeof(ctr->K));
280     memset(ctr->V, 0, sizeof(ctr->V));
281     if (!EVP_CipherInit_ex(ctr->ctx_ecb, NULL, NULL, ctr->K, NULL, -1))
282         return 0;
283
284     inc_128(ctr);
285     if (!ctr_update(drbg, entropy, entropylen, pers, perslen, nonce, noncelen))
286         return 0;
287     return 1;
288 }
289
290 __owur static int drbg_ctr_reseed(RAND_DRBG *drbg,
291                                   const unsigned char *entropy, size_t entropylen,
292                                   const unsigned char *adin, size_t adinlen)
293 {
294     RAND_DRBG_CTR *ctr = &drbg->data.ctr;
295
296     if (entropy == NULL)
297         return 0;
298
299     inc_128(ctr);
300     if (!ctr_update(drbg, entropy, entropylen, adin, adinlen, NULL, 0))
301         return 0;
302     return 1;
303 }
304
305 static void ctr96_inc(unsigned char *counter)
306 {
307     u32 n = 12, c = 1;
308
309     do {
310         --n;
311         c += counter[n];
312         counter[n] = (u8)c;
313         c >>= 8;
314     } while (n);
315 }
316
317 __owur static int drbg_ctr_generate(RAND_DRBG *drbg,
318                                     unsigned char *out, size_t outlen,
319                                     const unsigned char *adin, size_t adinlen)
320 {
321     RAND_DRBG_CTR *ctr = &drbg->data.ctr;
322     unsigned int ctr32, blocks;
323     int outl, buflen;
324
325     if (adin != NULL && adinlen != 0) {
326         inc_128(ctr);
327
328         if (!ctr_update(drbg, adin, adinlen, NULL, 0, NULL, 0))
329             return 0;
330         /* This means we reuse derived value */
331         if ((drbg->flags & RAND_DRBG_FLAG_CTR_NO_DF) == 0) {
332             adin = NULL;
333             adinlen = 1;
334         }
335     } else {
336         adinlen = 0;
337     }
338
339     inc_128(ctr);
340
341     if (outlen == 0) {
342         inc_128(ctr);
343
344         if (!ctr_update(drbg, adin, adinlen, NULL, 0, NULL, 0))
345             return 0;
346         return 1;
347     }
348
349     memset(out, 0, outlen);
350
351     do {
352         if (!EVP_CipherInit_ex(ctr->ctx_ctr,
353                                NULL, NULL, NULL, ctr->V, -1))
354             return 0;
355
356         /*-
357          * outlen has type size_t while EVP_CipherUpdate takes an
358          * int argument and thus cannot be guaranteed to process more
359          * than 2^31-1 bytes at a time. We process such huge generate
360          * requests in 2^30 byte chunks, which is the greatest multiple
361          * of AES block size lower than or equal to 2^31-1.
362          */
363         buflen = outlen > (1U << 30) ? (1U << 30) : outlen;
364         blocks = (buflen + 15) / 16;
365
366         ctr32 = GETU32(ctr->V + 12) + blocks;
367         if (ctr32 < blocks) {
368             /* 32-bit counter overflow into V. */
369             blocks -= ctr32;
370             buflen = blocks * 16;
371             ctr32 = 0;
372             ctr96_inc(ctr->V);
373         }
374         PUTU32(ctr->V + 12, ctr32);
375
376         if (!EVP_CipherUpdate(ctr->ctx_ctr, out, &outl, out, buflen)
377             || outl != buflen)
378             return 0;
379
380         out += buflen;
381         outlen -= buflen;
382     } while (outlen);
383
384     if (!ctr_update(drbg, adin, adinlen, NULL, 0, NULL, 0))
385         return 0;
386     return 1;
387 }
388
389 static int drbg_ctr_uninstantiate(RAND_DRBG *drbg)
390 {
391     EVP_CIPHER_CTX_free(drbg->data.ctr.ctx_ecb);
392     EVP_CIPHER_CTX_free(drbg->data.ctr.ctx_ctr);
393     EVP_CIPHER_CTX_free(drbg->data.ctr.ctx_df);
394     EVP_CIPHER_free(drbg->data.ctr.cipher_ecb);
395     EVP_CIPHER_free(drbg->data.ctr.cipher_ctr);
396     OPENSSL_cleanse(&drbg->data.ctr, sizeof(drbg->data.ctr));
397     return 1;
398 }
399
400 static RAND_DRBG_METHOD drbg_ctr_meth = {
401     drbg_ctr_instantiate,
402     drbg_ctr_reseed,
403     drbg_ctr_generate,
404     drbg_ctr_uninstantiate
405 };
406
407 int drbg_ctr_init(RAND_DRBG *drbg)
408 {
409     RAND_DRBG_CTR *ctr = &drbg->data.ctr;
410     size_t keylen;
411     EVP_CIPHER *cipher_ecb = NULL;
412     EVP_CIPHER *cipher_ctr = NULL;
413
414     switch (drbg->type) {
415     default:
416         /* This can't happen, but silence the compiler warning. */
417         return 0;
418     case NID_aes_128_ctr:
419         keylen = 16;
420         cipher_ecb = EVP_CIPHER_fetch(drbg->libctx, "AES-128-ECB", "");
421         cipher_ctr = EVP_CIPHER_fetch(drbg->libctx, "AES-128-CTR", "");
422         break;
423     case NID_aes_192_ctr:
424         keylen = 24;
425         cipher_ecb = EVP_CIPHER_fetch(drbg->libctx, "AES-192-ECB", "");
426         cipher_ctr = EVP_CIPHER_fetch(drbg->libctx, "AES-192-CTR", "");
427         break;
428     case NID_aes_256_ctr:
429         keylen = 32;
430         cipher_ecb = EVP_CIPHER_fetch(drbg->libctx, "AES-256-ECB", "");
431         cipher_ctr = EVP_CIPHER_fetch(drbg->libctx, "AES-256-CTR", "");
432         break;
433     }
434     if (cipher_ecb == NULL || cipher_ctr == NULL)
435         return 0;
436
437     EVP_CIPHER_free(ctr->cipher_ecb);
438     ctr->cipher_ecb = cipher_ecb;
439     EVP_CIPHER_free(ctr->cipher_ctr);
440     ctr->cipher_ctr = cipher_ctr;
441
442     ctr->keylen = keylen;
443     if (ctr->ctx_ecb == NULL)
444         ctr->ctx_ecb = EVP_CIPHER_CTX_new();
445     if (ctr->ctx_ctr == NULL)
446         ctr->ctx_ctr = EVP_CIPHER_CTX_new();
447     if (ctr->ctx_ecb == NULL || ctr->ctx_ctr == NULL
448         || !EVP_CipherInit_ex(ctr->ctx_ecb,
449                               ctr->cipher_ecb, NULL, NULL, NULL, 1)
450         || !EVP_CipherInit_ex(ctr->ctx_ctr,
451                               ctr->cipher_ctr, NULL, NULL, NULL, 1))
452         return 0;
453
454     drbg->meth = &drbg_ctr_meth;
455     drbg->strength = keylen * 8;
456     drbg->seedlen = keylen + 16;
457
458     if ((drbg->flags & RAND_DRBG_FLAG_CTR_NO_DF) == 0) {
459         /* df initialisation */
460         static const unsigned char df_key[32] = {
461             0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
462             0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
463             0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
464             0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f
465         };
466
467         if (ctr->ctx_df == NULL)
468             ctr->ctx_df = EVP_CIPHER_CTX_new();
469         if (ctr->ctx_df == NULL)
470             return 0;
471         /* Set key schedule for df_key */
472         if (!EVP_CipherInit_ex(ctr->ctx_df,
473                                ctr->cipher_ecb, NULL, df_key, NULL, 1))
474             return 0;
475
476         drbg->min_entropylen = ctr->keylen;
477         drbg->max_entropylen = DRBG_MAX_LENGTH;
478         drbg->min_noncelen = drbg->min_entropylen / 2;
479         drbg->max_noncelen = DRBG_MAX_LENGTH;
480         drbg->max_perslen = DRBG_MAX_LENGTH;
481         drbg->max_adinlen = DRBG_MAX_LENGTH;
482     } else {
483 #ifdef FIPS_MODE
484         RANDerr(RAND_F_DRBG_CTR_INIT,
485                 RAND_R_DERIVATION_FUNCTION_MANDATORY_FOR_FIPS);
486         return 0;
487 #else
488         drbg->min_entropylen = drbg->seedlen;
489         drbg->max_entropylen = drbg->seedlen;
490         /* Nonce not used */
491         drbg->min_noncelen = 0;
492         drbg->max_noncelen = 0;
493         drbg->max_perslen = drbg->seedlen;
494         drbg->max_adinlen = drbg->seedlen;
495 #endif
496     }
497
498     drbg->max_request = 1 << 16;
499
500     return 1;
501 }