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