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