Rewrite of table-based ghash code, for side-channel silence.

1 files changed, 37 insertions, 16 deletions

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<<GCM_TABLE_BITS)/2;
-  block16_zero (&ctx->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<<GCM_TABLE_BITS; i *= 2)
-    {
-      unsigned j;
-      for (j = 1; j < i; j++)
-	block16_xor3 (&ctx->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]);
 }