Added AESCTR_DRBG implementation (beta).
authorThomas Pornin <pornin@bolet.org>
Tue, 31 Jul 2018 22:50:13 +0000 (00:50 +0200)
committerThomas Pornin <pornin@bolet.org>
Tue, 31 Jul 2018 22:50:13 +0000 (00:50 +0200)
inc/bearssl_rand.h
mk/Rules.mk
mk/mkrules.sh
src/rand/aesctr_drbg.c [new file with mode: 0644]
test/test_crypto.c
test/test_speed.c

index 060cb40..e22d5d4 100644 (file)
@@ -28,6 +28,8 @@
 #include <stddef.h>
 #include <stdint.h>
 
+#include "bearssl_block.h"
+
 #ifdef __cplusplus
 extern "C" {
 #endif
@@ -93,6 +95,32 @@ extern "C" {
  * no currently known security penalty for exceeding the NIST limits,
  * and, in any case, HMAC_DRBG usage in implementing SSL/TLS always
  * stays much below these thresholds.
+ *
+ *
+ * ## AESCTR_DRBG
+ *
+ * AESCTR_DRBG is a custom PRNG based on AES-128 in CTR mode. This is
+ * meant to be used only in situations where you are desperate for
+ * speed, and have an hardware-optimized AES/CTR implementation. Whether
+ * this will yield perceptible improvements depends on what you use the
+ * pseudorandom bytes for, and how many you want; for instance, RSA key
+ * pair generation uses a substantial amount of randomness, and using
+ * AESCTR_DRBG instead of HMAC_DRBG yields a 15 to 20% increase in key
+ * generation speed on a recent x86 CPU (Intel Core i7-6567U at 3.30 GHz).
+ *
+ * Internally, it uses CTR mode with successive counter values, starting
+ * at zero (counter value expressed over 128 bits, big-endian convention).
+ * The counter is not allowed to reach 32768; thus, every 32768*16 bytes
+ * at most, the `update()` function is run (on an empty seed, if none is
+ * provided). The `update()` function computes the new AES-128 key by
+ * applying a custom hash function to the concatenation of a state-dependent
+ * word (encryption of an all-one block with the current key) and the new
+ * seed. The custom hash function uses Hirose's construction over AES-256;
+ * see the comments in `aesctr_drbg.c` for details.
+ *
+ * This DRBG does not follow an existing standard, and thus should be
+ * considered as inadequate for production use until it has been properly
+ * analysed.
  */
 
 /**
@@ -288,6 +316,79 @@ typedef int (*br_prng_seeder)(const br_prng_class **ctx);
  */
 br_prng_seeder br_prng_seeder_system(const char **name);
 
+/**
+ * \brief Context for AESCTR_DRBG.
+ *
+ * The context contents are opaque, except the first field, which
+ * supports OOP.
+ */
+typedef struct {
+       /**
+        * \brief Pointer to the vtable.
+        *
+        * This field is set with the initialisation method/function.
+        */
+       const br_prng_class *vtable;
+#ifndef BR_DOXYGEN_IGNORE
+       br_aes_gen_ctr_keys sk;
+       uint32_t cc;
+#endif
+} br_aesctr_drbg_context;
+
+/**
+ * \brief Statically allocated, constant vtable for AESCTR_DRBG.
+ */
+extern const br_prng_class br_aesctr_drbg_vtable;
+
+/**
+ * \brief AESCTR_DRBG initialisation.
+ *
+ * The context to initialise is provided as a pointer to its first field
+ * (the vtable pointer); this function sets that first field to a
+ * pointer to the vtable.
+ *
+ * The internal AES key is first set to the all-zero key; then, the
+ * `br_aesctr_drbg_update()` function is called with the provided `seed`.
+ * The call is performed even if the seed length (`seed_len`) is zero.
+ *
+ * The `aesctr` parameter defines the underlying AES/CTR implementation.
+ *
+ * \param ctx            HMAC_DRBG context to initialise.
+ * \param digest_class   vtable for the underlying hash function.
+ * \param seed           initial seed (can be `NULL` if `seed_len` is zero).
+ * \param seed_len       initial seed length (in bytes).
+ */
+void br_aesctr_drbg_init(br_aesctr_drbg_context *ctx,
+       const br_block_ctr_class *aesctr, const void *seed, size_t seed_len);
+
+/**
+ * \brief Random bytes generation with AESCTR_DRBG.
+ *
+ * This method produces `len` pseudorandom bytes, in the `out`
+ * buffer. The context is updated accordingly.
+ *
+ * \param ctx   AESCTR_DRBG context.
+ * \param out   output buffer.
+ * \param len   number of pseudorandom bytes to produce.
+ */
+void br_aesctr_drbg_generate(br_aesctr_drbg_context *ctx,
+       void *out, size_t len);
+
+/**
+ * \brief Inject additional seed bytes in AESCTR_DRBG.
+ *
+ * The provided seed bytes are added into the AESCTR_DRBG internal
+ * entropy pool. The process does not _replace_ existing entropy,
+ * thus pushing non-random bytes (i.e. bytes which are known to the
+ * attackers) does not degrade the overall quality of generated bytes.
+ *
+ * \param ctx        AESCTR_DRBG context.
+ * \param seed       additional seed.
+ * \param seed_len   additional seed length (in bytes).
+ */
+void br_aesctr_drbg_update(br_aesctr_drbg_context *ctx,
+       const void *seed, size_t seed_len);
+
 #ifdef __cplusplus
 }
 #endif
index 1ffc020..88195fd 100644 (file)
@@ -122,6 +122,7 @@ OBJ = \
  $(OBJDIR)$Pi62_modpow2$O \
  $(OBJDIR)$Phmac$O \
  $(OBJDIR)$Phmac_ct$O \
+ $(OBJDIR)$Paesctr_drbg$O \
  $(OBJDIR)$Phmac_drbg$O \
  $(OBJDIR)$Psysrng$O \
  $(OBJDIR)$Prsa_default_keygen$O \
@@ -701,6 +702,9 @@ $(OBJDIR)$Phmac$O: src$Pmac$Phmac.c $(HEADERSPRIV)
 $(OBJDIR)$Phmac_ct$O: src$Pmac$Phmac_ct.c $(HEADERSPRIV)
        $(CC) $(CFLAGS) $(INCFLAGS) $(CCOUT)$(OBJDIR)$Phmac_ct$O src$Pmac$Phmac_ct.c
 
+$(OBJDIR)$Paesctr_drbg$O: src$Prand$Paesctr_drbg.c $(HEADERSPRIV)
+       $(CC) $(CFLAGS) $(INCFLAGS) $(CCOUT)$(OBJDIR)$Paesctr_drbg$O src$Prand$Paesctr_drbg.c
+
 $(OBJDIR)$Phmac_drbg$O: src$Prand$Phmac_drbg.c $(HEADERSPRIV)
        $(CC) $(CFLAGS) $(INCFLAGS) $(CCOUT)$(OBJDIR)$Phmac_drbg$O src$Prand$Phmac_drbg.c
 
index 038d8c0..0e3895e 100755 (executable)
@@ -170,6 +170,7 @@ coresrc=" \
        src/int/i62_modpow2.c \
        src/mac/hmac.c \
        src/mac/hmac_ct.c \
+       src/rand/aesctr_drbg.c \
        src/rand/hmac_drbg.c \
        src/rand/sysrng.c \
        src/rsa/rsa_default_keygen.c \
diff --git a/src/rand/aesctr_drbg.c b/src/rand/aesctr_drbg.c
new file mode 100644 (file)
index 0000000..8dbd501
--- /dev/null
@@ -0,0 +1,206 @@
+/*
+ * Copyright (c) 2018 Thomas Pornin <pornin@bolet.org>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining 
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be 
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+ * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+ * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#include "inner.h"
+
+/* see bearssl_rand.h */
+void
+br_aesctr_drbg_init(br_aesctr_drbg_context *ctx,
+       const br_block_ctr_class *aesctr,
+       const void *seed, size_t len)
+{
+       unsigned char tmp[16];
+
+       ctx->vtable = &br_aesctr_drbg_vtable;
+       memset(tmp, 0, sizeof tmp);
+       aesctr->init(&ctx->sk.vtable, tmp, 16);
+       ctx->cc = 0;
+       br_aesctr_drbg_update(ctx, seed, len);
+}
+
+/* see bearssl_rand.h */
+void
+br_aesctr_drbg_generate(br_aesctr_drbg_context *ctx, void *out, size_t len)
+{
+       unsigned char *buf;
+       unsigned char iv[12];
+
+       buf = out;
+       memset(iv, 0, sizeof iv);
+       while (len > 0) {
+               size_t clen;
+
+               /*
+                * We generate data by blocks of at most 65280 bytes. This
+                * allows for unambiguously testing the counter overflow
+                * condition; also, it should work on 16-bit architectures
+                * (where 'size_t' is 16 bits only).
+                */
+               clen = len;
+               if (clen > 65280) {
+                       clen = 65280;
+               }
+
+               /*
+                * We make sure that the counter won't exceed the configured
+                * limit.
+                */
+               if ((uint32_t)(ctx->cc + ((clen + 15) >> 4)) > 32768) {
+                       clen = (32768 - ctx->cc) << 4;
+                       if (clen > len) {
+                               clen = len;
+                       }
+               }
+
+               /*
+                * Run CTR.
+                */
+               memset(buf, 0, clen);
+               ctx->cc = ctx->sk.vtable->run(&ctx->sk.vtable,
+                       iv, ctx->cc, buf, clen);
+               buf += clen;
+               len -= clen;
+
+               /*
+                * Every 32768 blocks, we force a state update.
+                */
+               if (ctx->cc >= 32768) {
+                       br_aesctr_drbg_update(ctx, NULL, 0);
+               }
+       }
+}
+
+/* see bearssl_rand.h */
+void
+br_aesctr_drbg_update(br_aesctr_drbg_context *ctx, const void *seed, size_t len)
+{
+       /*
+        * We use a Hirose construction on AES-256 to make a hash function.
+        * Function definition:
+        *  - running state consists in two 16-byte blocks G and H
+        *  - initial values of G and H are conventional
+        *  - there is a fixed block-sized constant C
+        *  - for next data block m:
+        *      set AES key to H||m
+        *      G' = E(G) xor G
+        *      H' = E(G xor C) xor G xor C
+        *      G <- G', H <- H'
+        *  - once all blocks have been processed, output is H||G
+        *
+        * Constants:
+        *   G_init = B6 B6 ... B6
+        *   H_init = A5 A5 ... A5
+        *   C      = 01 00 ... 00
+        *
+        * With this hash function h(), we compute the new state as
+        * follows:
+        *  - produce a state-dependent value s as encryption of an
+        *    all-one block with AES and the current key
+        *  - compute the new key as the first 128 bits of h(s||seed)
+        *
+        * Original Hirose article:
+        *    https://www.iacr.org/archive/fse2006/40470213/40470213.pdf
+        */
+
+       unsigned char s[16], iv[12];
+       unsigned char G[16], H[16];
+       int first;
+
+       /*
+        * Use an all-one IV to get a fresh output block that depends on the
+        * current seed.
+        */
+       memset(iv, 0xFF, sizeof iv);
+       memset(s, 0, 16);
+       ctx->sk.vtable->run(&ctx->sk.vtable, iv, 0xFFFFFFFF, s, 16);
+
+       /*
+        * Set G[] and H[] to conventional start values.
+        */
+       memset(G, 0xB6, sizeof G);
+       memset(H, 0x5A, sizeof H);
+
+       /*
+        * Process the concatenation of the current state and the seed
+        * with the custom hash function.
+        */
+       first = 1;
+       for (;;) {
+               unsigned char tmp[32];
+               unsigned char newG[16];
+
+               /*
+                * Assemble new key H||m into tmp[].
+                */
+               memcpy(tmp, H, 16);
+               if (first) {
+                       memcpy(tmp + 16, s, 16);
+                       first = 0;
+               } else {
+                       size_t clen;
+
+                       if (len == 0) {
+                               break;
+                       }
+                       clen = len < 16 ? len : 16;
+                       memcpy(tmp + 16, seed, clen);
+                       memset(tmp + 16 + clen, 0, 16 - clen);
+                       seed = (const unsigned char *)seed + clen;
+                       len -= clen;
+               }
+               ctx->sk.vtable->init(&ctx->sk.vtable, tmp, 32);
+
+               /*
+                * Compute new G and H values.
+                */
+               memcpy(iv, G, 12);
+               memcpy(newG, G, 16);
+               ctx->sk.vtable->run(&ctx->sk.vtable, iv,
+                       br_dec32be(G + 12), newG, 16);
+               iv[0] ^= 0x01;
+               memcpy(H, G, 16);
+               H[0] ^= 0x01;
+               ctx->sk.vtable->run(&ctx->sk.vtable, iv,
+                       br_dec32be(G + 12), H, 16);
+               memcpy(G, newG, 16);
+       }
+
+       /*
+        * Output hash value is H||G. We truncate it to its first 128 bits,
+        * i.e. H; that's our new AES key.
+        */
+       ctx->sk.vtable->init(&ctx->sk.vtable, H, 16);
+       ctx->cc = 0;
+}
+
+/* see bearssl_rand.h */
+const br_prng_class br_aesctr_drbg_vtable = {
+       sizeof(br_aesctr_drbg_context),
+       (void (*)(const br_prng_class **, const void *, const void *, size_t))
+               &br_aesctr_drbg_init,
+       (void (*)(const br_prng_class **, void *, size_t))
+               &br_aesctr_drbg_generate,
+       (void (*)(const br_prng_class **, const void *, size_t))
+               &br_aesctr_drbg_update
+};
index acfabd0..60a431c 100644 (file)
@@ -1074,6 +1074,41 @@ test_HMAC_DRBG(void)
        fflush(stdout);
 }
 
+static void
+test_AESCTR_DRBG(void)
+{
+       br_aesctr_drbg_context ctx;
+       const br_block_ctr_class *ictr;
+       unsigned char tmp1[64], tmp2[64];
+
+       printf("Test AESCTR_DRBG: ");
+       fflush(stdout);
+
+       ictr = br_aes_x86ni_ctr_get_vtable();
+       if (ictr == NULL) {
+               ictr = br_aes_pwr8_ctr_get_vtable();
+               if (ictr == NULL) {
+#if BR_64
+                       ictr = &br_aes_ct64_ctr_vtable;
+#else
+                       ictr = &br_aes_ct_ctr_vtable;
+#endif
+               }
+       }
+       br_aesctr_drbg_init(&ctx, ictr, NULL, 0);
+       ctx.vtable->generate(&ctx.vtable, tmp1, sizeof tmp1);
+       ctx.vtable->update(&ctx.vtable, "new seed", 8);
+       ctx.vtable->generate(&ctx.vtable, tmp2, sizeof tmp2);
+
+       if (memcmp(tmp1, tmp2, sizeof tmp1) == 0) {
+               fprintf(stderr, "AESCTR_DRBG failure\n");
+               exit(EXIT_FAILURE);
+       }
+
+       printf("done.\n");
+       fflush(stdout);
+}
+
 static void
 do_KAT_PRF(br_tls_prf_impl prf,
        const char *ssecret, const char *label, const char *sseed,
@@ -7965,6 +8000,7 @@ static const struct {
        STU(multihash),
        STU(HMAC),
        STU(HMAC_DRBG),
+       STU(AESCTR_DRBG),
        STU(PRF),
        STU(AES_big),
        STU(AES_small),
index 43d062a..38da572 100644 (file)
@@ -684,7 +684,11 @@ test_speed_rsa_inner(char *name,
        unsigned char tmp[sizeof RSA_N];
        int i;
        long num;
+       /*
        br_hmac_drbg_context rng;
+       */
+       br_aesctr_drbg_context rng;
+       const br_block_ctr_class *ictr;
 
        memset(tmp, 'R', sizeof tmp);
        tmp[0] = 0;
@@ -744,7 +748,21 @@ test_speed_rsa_inner(char *name,
                fflush(stdout);
                return;
        }
+       /*
        br_hmac_drbg_init(&rng, &br_sha256_vtable, "RSA keygen seed", 15);
+       */
+       ictr = br_aes_x86ni_ctr_get_vtable();
+       if (ictr == NULL) {
+               ictr = br_aes_pwr8_ctr_get_vtable();
+               if (ictr == NULL) {
+#if BR_64
+                       ictr = &br_aes_ct64_ctr_vtable;
+#else
+                       ictr = &br_aes_ct_ctr_vtable;
+#endif
+               }
+       }
+       br_aesctr_drbg_init(&rng, ictr, "RSA keygen seed", 15);
 
        num = 10;
        for (;;) {