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 }