33e1b324c6a5758ac694dc0d6043e28718bdff71
[openssl.git] / crypto / rand / drbg_ctr.c
1 /*
2  * Copyright 2011-2020 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             if (ctr32 != 0) {
370                 blocks -= ctr32;
371                 buflen = blocks * 16;
372                 ctr32 = 0;
373             }
374             ctr96_inc(ctr->V);
375         }
376         PUTU32(ctr->V + 12, ctr32);
377
378         if (!EVP_CipherUpdate(ctr->ctx_ctr, out, &outl, out, buflen)
379             || outl != buflen)
380             return 0;
381
382         out += buflen;
383         outlen -= buflen;
384     } while (outlen);
385
386     if (!ctr_update(drbg, adin, adinlen, NULL, 0, NULL, 0))
387         return 0;
388     return 1;
389 }
390
391 static int drbg_ctr_uninstantiate(RAND_DRBG *drbg)
392 {
393     EVP_CIPHER_CTX_free(drbg->data.ctr.ctx_ecb);
394     EVP_CIPHER_CTX_free(drbg->data.ctr.ctx_ctr);
395     EVP_CIPHER_CTX_free(drbg->data.ctr.ctx_df);
396     EVP_CIPHER_free(drbg->data.ctr.cipher_ecb);
397     EVP_CIPHER_free(drbg->data.ctr.cipher_ctr);
398     OPENSSL_cleanse(&drbg->data.ctr, sizeof(drbg->data.ctr));
399     return 1;
400 }
401
402 static RAND_DRBG_METHOD drbg_ctr_meth = {
403     drbg_ctr_instantiate,
404     drbg_ctr_reseed,
405     drbg_ctr_generate,
406     drbg_ctr_uninstantiate
407 };
408
409 int drbg_ctr_init(RAND_DRBG *drbg)
410 {
411     RAND_DRBG_CTR *ctr = &drbg->data.ctr;
412     size_t keylen;
413     EVP_CIPHER *cipher_ecb = NULL;
414     EVP_CIPHER *cipher_ctr = NULL;
415
416     switch (drbg->type) {
417     default:
418         /* This can't happen, but silence the compiler warning. */
419         return 0;
420     case NID_aes_128_ctr:
421         keylen = 16;
422         cipher_ecb = EVP_CIPHER_fetch(drbg->libctx, "AES-128-ECB", "");
423         cipher_ctr = EVP_CIPHER_fetch(drbg->libctx, "AES-128-CTR", "");
424         break;
425     case NID_aes_192_ctr:
426         keylen = 24;
427         cipher_ecb = EVP_CIPHER_fetch(drbg->libctx, "AES-192-ECB", "");
428         cipher_ctr = EVP_CIPHER_fetch(drbg->libctx, "AES-192-CTR", "");
429         break;
430     case NID_aes_256_ctr:
431         keylen = 32;
432         cipher_ecb = EVP_CIPHER_fetch(drbg->libctx, "AES-256-ECB", "");
433         cipher_ctr = EVP_CIPHER_fetch(drbg->libctx, "AES-256-CTR", "");
434         break;
435     }
436     if (cipher_ecb == NULL || cipher_ctr == NULL)
437         return 0;
438
439     EVP_CIPHER_free(ctr->cipher_ecb);
440     ctr->cipher_ecb = cipher_ecb;
441     EVP_CIPHER_free(ctr->cipher_ctr);
442     ctr->cipher_ctr = cipher_ctr;
443
444     ctr->keylen = keylen;
445     if (ctr->ctx_ecb == NULL)
446         ctr->ctx_ecb = EVP_CIPHER_CTX_new();
447     if (ctr->ctx_ctr == NULL)
448         ctr->ctx_ctr = EVP_CIPHER_CTX_new();
449     if (ctr->ctx_ecb == NULL || ctr->ctx_ctr == NULL
450         || !EVP_CipherInit_ex(ctr->ctx_ecb,
451                               ctr->cipher_ecb, NULL, NULL, NULL, 1)
452         || !EVP_CipherInit_ex(ctr->ctx_ctr,
453                               ctr->cipher_ctr, NULL, NULL, NULL, 1))
454         return 0;
455
456     drbg->meth = &drbg_ctr_meth;
457     drbg->strength = keylen * 8;
458     drbg->seedlen = keylen + 16;
459
460     if ((drbg->flags & RAND_DRBG_FLAG_CTR_NO_DF) == 0) {
461         /* df initialisation */
462         static const unsigned char df_key[32] = {
463             0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
464             0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
465             0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
466             0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f
467         };
468
469         if (ctr->ctx_df == NULL)
470             ctr->ctx_df = EVP_CIPHER_CTX_new();
471         if (ctr->ctx_df == NULL)
472             return 0;
473         /* Set key schedule for df_key */
474         if (!EVP_CipherInit_ex(ctr->ctx_df,
475                                ctr->cipher_ecb, NULL, df_key, NULL, 1))
476             return 0;
477
478         drbg->min_entropylen = ctr->keylen;
479         drbg->max_entropylen = DRBG_MAX_LENGTH;
480         drbg->min_noncelen = drbg->min_entropylen / 2;
481         drbg->max_noncelen = DRBG_MAX_LENGTH;
482         drbg->max_perslen = DRBG_MAX_LENGTH;
483         drbg->max_adinlen = DRBG_MAX_LENGTH;
484     } else {
485 #ifdef FIPS_MODULE
486         RANDerr(RAND_F_DRBG_CTR_INIT,
487                 RAND_R_DERIVATION_FUNCTION_MANDATORY_FOR_FIPS);
488         return 0;
489 #else
490         drbg->min_entropylen = drbg->seedlen;
491         drbg->max_entropylen = drbg->seedlen;
492         /* Nonce not used */
493         drbg->min_noncelen = 0;
494         drbg->max_noncelen = 0;
495         drbg->max_perslen = drbg->seedlen;
496         drbg->max_adinlen = drbg->seedlen;
497 #endif
498     }
499
500     drbg->max_request = 1 << 16;
501
502     return 1;
503 }