From cfbc702d3d64c209784b664eeab8867b603f4d4c Mon Sep 17 00:00:00 2001 From: Thomas Pornin Date: Wed, 1 Aug 2018 00:50:13 +0200 Subject: [PATCH] Added AESCTR_DRBG implementation (beta). --- inc/bearssl_rand.h | 101 ++++++++++++++++++++ mk/Rules.mk | 4 + mk/mkrules.sh | 1 + src/rand/aesctr_drbg.c | 206 +++++++++++++++++++++++++++++++++++++++++ test/test_crypto.c | 36 +++++++ test/test_speed.c | 18 ++++ 6 files changed, 366 insertions(+) create mode 100644 src/rand/aesctr_drbg.c diff --git a/inc/bearssl_rand.h b/inc/bearssl_rand.h index 060cb40..e22d5d4 100644 --- a/inc/bearssl_rand.h +++ b/inc/bearssl_rand.h @@ -28,6 +28,8 @@ #include #include +#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 diff --git a/mk/Rules.mk b/mk/Rules.mk index 1ffc020..88195fd 100644 --- a/mk/Rules.mk +++ b/mk/Rules.mk @@ -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 diff --git a/mk/mkrules.sh b/mk/mkrules.sh index 038d8c0..0e3895e 100755 --- a/mk/mkrules.sh +++ b/mk/mkrules.sh @@ -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 index 0000000..8dbd501 --- /dev/null +++ b/src/rand/aesctr_drbg.c @@ -0,0 +1,206 @@ +/* + * Copyright (c) 2018 Thomas Pornin + * + * 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 +}; diff --git a/test/test_crypto.c b/test/test_crypto.c index acfabd0..60a431c 100644 --- a/test/test_crypto.c +++ b/test/test_crypto.c @@ -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), diff --git a/test/test_speed.c b/test/test_speed.c index 43d062a..38da572 100644 --- a/test/test_speed.c +++ b/test/test_speed.c @@ -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 (;;) { -- 2.17.1