From 5251c8fe842b2121b19e384f862d35ccd2053cc0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Niels=20M=C3=B6ller?= Date: Thu, 13 Apr 2023 19:11:25 +0200 Subject: Rewrite of table-based ghash code, for side-channel silence. --- ghash-set-key.c | 53 +++++++++++++++++++++++++++++++++++++---------------- 1 file changed, 37 insertions(+), 16 deletions(-) (limited to 'ghash-set-key.c') diff --git a/ghash-set-key.c b/ghash-set-key.c index 0e91afcb..da1c90f0 100644 --- a/ghash-set-key.c +++ b/ghash-set-key.c @@ -51,25 +51,46 @@ _nettle_ghash_set_key_c (struct gcm_key *ctx, const union nettle_block16 *key); #define _nettle_ghash_set_key _nettle_ghash_set_key_c #endif +#if GCM_TABLE_BITS < 7 +# error Unsupported table size. +#endif + /* Implements a lookup table for processors without carryless-mul instruction. */ void _ghash_set_key (struct gcm_key *ctx, const union nettle_block16 *key) { - /* Middle element if GCM_TABLE_BITS > 0, otherwise the first - element */ - unsigned i = (1<h[0]); - ctx->h[i] = *key; - - /* Algorithm 3 from the gcm paper. First do powers of two, then do - the rest by adding. */ - while (i /= 2) - block16_mulx_ghash (&ctx->h[i], &ctx->h[2*i]); - for (i = 2; i < 1<h[i+j], &ctx->h[i], &ctx->h[j]); - } + /* Table elements hold the key, premultiplied by all needed powers + of x. Element ordering follows the order bits are processed in + _ghash_update, alternating u64[0] and u64[1] bits, starting from + the least significant end. In the gcm bit order, bits (left to + right) correspond to x powers (the numbers) like + + |0...7|8...15|...|56...63|64...71|72...79|...|120...127| + + where | indicates the byte boundaries. On little endian, these + bits are in u64 like + + u64[0]: | 56...63 48...55 40...47 32...39 24...31 16...23 8...15 0...7| + u64[1]: |120...127 112...129 104...111 96...103 88...95 80...87 72...79 64...71| + + With big-endian, we instead get + + u64[0]: |0...63| + u64[1]: |64...127| + */ +#if WORDS_BIGENDIAN +# define INDEX_PERMUTE 63 +#else +# define INDEX_PERMUTE 7 +#endif + unsigned i; + + block16_set (&ctx->h[2*INDEX_PERMUTE], key); + for (i = 1; i < 64; i++) + block16_mulx_ghash(&ctx->h[2*(i ^ INDEX_PERMUTE)], &ctx->h[2*((i-1) ^ INDEX_PERMUTE)]); + + block16_mulx_ghash(&ctx->h[2*INDEX_PERMUTE + 1], &ctx->h[2*(63^INDEX_PERMUTE)]); + for (i = 1; i < 64; i++) + block16_mulx_ghash(&ctx->h[2*(i ^ INDEX_PERMUTE)+1], &ctx->h[2*((i-1) ^ INDEX_PERMUTE)+1]); } -- cgit v1.2.1