From 12db697bccf2ff732665b9c7668c0826513489e0 Mon Sep 17 00:00:00 2001 From: Thomas Pornin Date: Thu, 8 Feb 2018 15:50:10 +0100 Subject: [PATCH] Added API to share precomputations in EAX. --- inc/bearssl_aead.h | 93 +++++++++++++++++++++++++++++++++ src/aead/eax.c | 126 ++++++++++++++++++++++++++++++++++++++++++--- test/test_crypto.c | 58 +++++++++++++++++++++ 3 files changed, 270 insertions(+), 7 deletions(-) diff --git a/inc/bearssl_aead.h b/inc/bearssl_aead.h index b1e52a3..c495dc2 100644 --- a/inc/bearssl_aead.h +++ b/inc/bearssl_aead.h @@ -592,6 +592,20 @@ typedef struct { #endif } br_eax_context; +/** + * \brief EAX captured state. + * + * Some internal values computed by EAX may be captured at various + * points, and reused for another EAX run with the same secret key, + * for lower per-message overhead. Captured values do not depend on + * the nonce. + */ +typedef struct { +#ifndef BR_DOXYGEN_IGNORE + unsigned char st[3][16]; +#endif +} br_eax_state; + /** * \brief Initialize an EAX context. * @@ -608,6 +622,21 @@ typedef struct { */ void br_eax_init(br_eax_context *ctx, const br_block_ctrcbc_class **bctx); +/** + * \brief Capture pre-AAD state. + * + * This function precomputes key-dependent data, and stores it in the + * provided `st` structure. This structure should then be used with + * `br_eax_reset_pre_aad()`, or updated with `br_eax_get_aad_mac()` + * and then used with `br_eax_reset_post_aad()`. + * + * The EAX context structure is unmodified by this call. + * + * \param ctx EAX context structure. + * \param st recipient for captured state. + */ +void br_eax_capture(const br_eax_context *ctx, br_eax_state *st); + /** * \brief Reset an EAX context. * @@ -628,6 +657,52 @@ void br_eax_init(br_eax_context *ctx, const br_block_ctrcbc_class **bctx); */ void br_eax_reset(br_eax_context *ctx, const void *nonce, size_t len); +/** + * \brief Reset an EAX context with a pre-AAD captured state. + * + * This function is an alternative to `br_eax_reset()`, that reuses a + * previously captured state structure for lower per-message overhead. + * The state should have been populated with `br_eax_capture_state()` + * but not updated with `br_eax_get_aad_mac()`. + * + * After this function is called, additional authenticated data MUST + * be injected. At least one byte of additional authenticated data + * MUST be provided with `br_eax_aad_inject()`; computation result will + * be incorrect if `br_eax_flip()` is called right away. + * + * After injection of the AAD and call to `br_eax_flip()`, at least + * one message byte must be provided. Empty messages are not supported + * with this reset mode. + * + * \param ctx EAX context structure. + * \param st pre-AAD captured state. + * \param nonce EAX nonce to use. + * \param len EAX nonce length (in bytes). + */ +void br_eax_reset_pre_aad(br_eax_context *ctx, const br_eax_state *st, + const void *nonce, size_t len); + +/** + * \brief Reset an EAX context with a post-AAD captured state. + * + * This function is an alternative to `br_eax_reset()`, that reuses a + * previously captured state structure for lower per-message overhead. + * The state should have been populated with `br_eax_capture_state()` + * and then updated with `br_eax_get_aad_mac()`. + * + * After this function is called, message data MUST be injected. The + * `br_eax_flip()` function MUST NOT be called. At least one byte of + * message data MUST be provided with `br_eax_run()`; empty messages + * are not supported with this reset mode. + * + * \param ctx EAX context structure. + * \param st post-AAD captured state. + * \param nonce EAX nonce to use. + * \param len EAX nonce length (in bytes). + */ +void br_eax_reset_post_aad(br_eax_context *ctx, const br_eax_state *st, + const void *nonce, size_t len); + /** * \brief Inject additional authenticated data into EAX. * @@ -654,6 +729,24 @@ void br_eax_aad_inject(br_eax_context *ctx, const void *data, size_t len); */ void br_eax_flip(br_eax_context *ctx); +/** + * \brief Obtain a copy of the MAC on additional authenticated data. + * + * This function may be called only after `br_eax_flip()`; it copies the + * AAD-specific MAC value into the provided state. The MAC value depends + * on the secret key and the additional data itself, but not on the + * nonce. The updated state `st` is meant to be used as parameter for a + * further `br_eax_reset_post_aad()` call. + * + * \param ctx EAX context structure. + * \param st captured state to update. + */ +static inline void +br_eax_get_aad_mac(const br_eax_context *ctx, br_eax_state *st) +{ + memcpy(st->st[1], ctx->head, sizeof ctx->head); +} + /** * \brief Encrypt or decrypt some data with EAX. * diff --git a/src/aead/eax.c b/src/aead/eax.c index 07b1cb9..bcc704a 100644 --- a/src/aead/eax.c +++ b/src/aead/eax.c @@ -113,9 +113,16 @@ do_pad(br_eax_context *ctx) } /* - * Apply CBC-MAC on the provided data, with buffering management. This - * function assumes that on input, ctx->buf contains a full block of - * unprocessed data. + * Apply CBC-MAC on the provided data, with buffering management. + * + * Upon entry, two situations are acceptable: + * + * ctx->ptr == 0: there is no data to process in ctx->buf + * ctx->ptr == 16: there is a full block of unprocessed data in ctx->buf + * + * Upon exit, ctx->ptr may be zero only if it was already zero on entry, + * and len == 0. In all other situations, ctx->ptr will be non-zero on + * exit (and may have value 16). */ static void do_cbcmac_chunk(br_eax_context *ctx, const void *data, size_t len) @@ -132,7 +139,10 @@ do_cbcmac_chunk(br_eax_context *ctx, const void *data, size_t len) } else { len -= ptr; } - (*ctx->bctx)->mac(ctx->bctx, ctx->cbcmac, ctx->buf, sizeof ctx->buf); + if (ctx->ptr == 16) { + (*ctx->bctx)->mac(ctx->bctx, ctx->cbcmac, + ctx->buf, sizeof ctx->buf); + } (*ctx->bctx)->mac(ctx->bctx, ctx->cbcmac, data, len); memcpy(ctx->buf, (const unsigned char *)data + len, ptr); ctx->ptr = ptr; @@ -157,6 +167,27 @@ br_eax_init(br_eax_context *ctx, const br_block_ctrcbc_class **bctx) double_gf128(ctx->L4, ctx->L2); } +/* see bearssl_aead.h */ +void +br_eax_capture(const br_eax_context *ctx, br_eax_state *st) +{ + /* + * We capture the three OMAC* states _after_ processing the + * initial block (assuming that nonce, message and AAD are + * all non-empty). + */ + int i; + + memset(st->st, 0, sizeof st->st); + for (i = 0; i < 3; i ++) { + unsigned char tmp[16]; + + memset(tmp, 0, sizeof tmp); + tmp[15] = (unsigned char)i; + (*ctx->bctx)->mac(ctx->bctx, st->st[i], tmp, sizeof tmp); + } +} + /* see bearssl_aead.h */ void br_eax_reset(br_eax_context *ctx, const void *nonce, size_t len) @@ -173,6 +204,62 @@ br_eax_reset(br_eax_context *ctx, const void *nonce, size_t len) * Start OMAC^1 for the AAD ("header" in the EAX specification). */ omac_start(ctx, 1); + + /* + * We use ctx->head[0] as temporary flag to mark that we are + * using a "normal" reset(). + */ + ctx->head[0] = 0; +} + +/* see bearssl_aead.h */ +void +br_eax_reset_pre_aad(br_eax_context *ctx, const br_eax_state *st, + const void *nonce, size_t len) +{ + if (len == 0) { + omac_start(ctx, 0); + } else { + memcpy(ctx->cbcmac, st->st[0], sizeof ctx->cbcmac); + ctx->ptr = 0; + do_cbcmac_chunk(ctx, nonce, len); + } + do_pad(ctx); + memcpy(ctx->nonce, ctx->cbcmac, sizeof ctx->cbcmac); + + memcpy(ctx->cbcmac, st->st[1], sizeof ctx->cbcmac); + ctx->ptr = 0; + + memcpy(ctx->ctr, st->st[2], sizeof ctx->ctr); + + /* + * We use ctx->head[0] as a flag to indicate that we use a + * a recorded state, with ctx->ctr containing the preprocessed + * first block for OMAC^2. + */ + ctx->head[0] = 1; +} + +/* see bearssl_aead.h */ +void +br_eax_reset_post_aad(br_eax_context *ctx, const br_eax_state *st, + const void *nonce, size_t len) +{ + if (len == 0) { + omac_start(ctx, 0); + } else { + memcpy(ctx->cbcmac, st->st[0], sizeof ctx->cbcmac); + ctx->ptr = 0; + do_cbcmac_chunk(ctx, nonce, len); + } + do_pad(ctx); + memcpy(ctx->nonce, ctx->cbcmac, sizeof ctx->cbcmac); + memcpy(ctx->ctr, ctx->nonce, sizeof ctx->nonce); + + memcpy(ctx->head, st->st[1], sizeof ctx->head); + + memcpy(ctx->cbcmac, st->st[2], sizeof ctx->cbcmac); + ctx->ptr = 0; } /* see bearssl_aead.h */ @@ -211,6 +298,15 @@ br_eax_aad_inject(br_eax_context *ctx, const void *data, size_t len) void br_eax_flip(br_eax_context *ctx) { + int from_capture; + + /* + * ctx->head[0] may be non-zero if the context was reset with + * a pre-AAD captured state. In that case, ctx->ctr[] contains + * the state for OMAC^2 _after_ processing the first block. + */ + from_capture = ctx->head[0]; + /* * Complete the OMAC computation on the AAD. */ @@ -219,8 +315,15 @@ br_eax_flip(br_eax_context *ctx) /* * Start OMAC^2 for the encrypted data. + * If the context was initialized from a captured state, then + * the OMAC^2 value is in the ctr[] array. */ - omac_start(ctx, 2); + if (from_capture) { + memcpy(ctx->cbcmac, ctx->ctr, sizeof ctx->cbcmac); + ctx->ptr = 0; + } else { + omac_start(ctx, 2); + } /* * Initial counter value for CTR is the processed nonce. @@ -245,7 +348,12 @@ br_eax_run(br_eax_context *ctx, int encrypt, void *data, size_t len) dbuf = data; ptr = ctx->ptr; - if (ptr != 16) { + /* + * We may have ptr == 0 here if we initialized from a captured + * state. In that case, there is no partially consumed block + * or unprocessed data. + */ + if (ptr != 0 && ptr != 16) { /* * We have a partially consumed block. */ @@ -282,8 +390,12 @@ br_eax_run(br_eax_context *ctx, int encrypt, void *data, size_t len) /* * We now have a complete encrypted block in buf[] that must still * be processed with OMAC, and this is not the final buf. + * Exception: when ptr == 0, no block has been produced yet. */ - (*ctx->bctx)->mac(ctx->bctx, ctx->cbcmac, ctx->buf, sizeof ctx->buf); + if (ptr != 0) { + (*ctx->bctx)->mac(ctx->bctx, ctx->cbcmac, + ctx->buf, sizeof ctx->buf); + } /* * Do CTR encryption or decryption and CBC-MAC for all full blocks diff --git a/test/test_crypto.c b/test/test_crypto.c index e37034c..46f208c 100644 --- a/test/test_crypto.c +++ b/test/test_crypto.c @@ -5526,6 +5526,7 @@ test_EAX_inner(const char *name, const br_block_ctrcbc_class *vt) size_t plain_len, key_len, nonce_len, aad_len; br_aes_gen_ctrcbc_keys bc; br_eax_context ec; + br_eax_state st; unsigned char tmp[100], out[16]; size_t v, tag_len; @@ -5649,6 +5650,63 @@ test_EAX_inner(const char *name, const br_block_ctrcbc_class *vt) printf("."); fflush(stdout); + + /* + * For capture tests, we need the message to be non-empty. + */ + if (plain_len == 0) { + continue; + } + + /* + * Captured state, pre-AAD. This requires the AAD and the + * message to be non-empty. + */ + br_eax_capture(&ec, &st); + + if (aad_len > 0) { + br_eax_reset_pre_aad(&ec, &st, nonce, nonce_len); + br_eax_aad_inject(&ec, aad, aad_len); + br_eax_flip(&ec); + memcpy(tmp, plain, plain_len); + br_eax_run(&ec, 1, tmp, plain_len); + br_eax_get_tag(&ec, out); + check_equals("KAT EAX 9", tmp, cipher, plain_len); + check_equals("KAT EAX 10", out, tag, 16); + + br_eax_reset_pre_aad(&ec, &st, nonce, nonce_len); + br_eax_aad_inject(&ec, aad, aad_len); + br_eax_flip(&ec); + br_eax_run(&ec, 0, tmp, plain_len); + br_eax_get_tag(&ec, out); + check_equals("KAT EAX 11", tmp, plain, plain_len); + check_equals("KAT EAX 12", out, tag, 16); + } + + /* + * Captured state, post-AAD. This requires the message to + * be non-empty. + */ + br_eax_reset(&ec, nonce, nonce_len); + br_eax_aad_inject(&ec, aad, aad_len); + br_eax_flip(&ec); + br_eax_get_aad_mac(&ec, &st); + + br_eax_reset_post_aad(&ec, &st, nonce, nonce_len); + memcpy(tmp, plain, plain_len); + br_eax_run(&ec, 1, tmp, plain_len); + br_eax_get_tag(&ec, out); + check_equals("KAT EAX 13", tmp, cipher, plain_len); + check_equals("KAT EAX 14", out, tag, 16); + + br_eax_reset_post_aad(&ec, &st, nonce, nonce_len); + br_eax_run(&ec, 0, tmp, plain_len); + br_eax_get_tag(&ec, out); + check_equals("KAT EAX 15", tmp, plain, plain_len); + check_equals("KAT EAX 16", out, tag, 16); + + printf("."); + fflush(stdout); } printf(" done.\n"); -- 2.17.1