Add small cache for RSA blinding factors.

Generating new RSA blinding factors turns out to be relatively
expensive, but we can amortize that cost by maintaining a small cache
and simply mutating old values after each use with a cheaper
operation.  Squaring works, pretty much by definition.

Blinding factors are only sort-of-sensitive: we don't want them to
leak out of the HSM, but they're only based on the public modulus, not
the private key components, and we're only using them to foil side
channel attacks, so the risk involved in caching them seems small.

For the moment, the cache is very small, since we only care about this
for bulk signature operations.  Tune this later if it becomes an issue.

3 files changed, 76 insertions, 18 deletions

diff --git a/hal_internal.h b/hal_internal.h
index a97a8f2..922562a 100644
--- a/hal_internal.h
+++ b/hal_internal.h
@@ -144,6 +144,8 @@ extern void hal_critical_section_start(void);
 extern void hal_critical_section_end(void);
 extern void hal_ks_lock(void);
 extern void hal_ks_unlock(void);
+extern void hal_rsa_bf_lock(void);
+extern void hal_rsa_bf_unlock(void);
 extern void hal_task_yield(void);
 
 /*
diff --git a/locks.c b/locks.c
index 9b81769..968ae98 100644
--- a/locks.c
+++ b/locks.c
@@ -77,29 +77,26 @@
  * Critical sections -- disable preemption BRIEFLY.
  */
 
-WEAK_FUNCTION void hal_critical_section_start(void)
-{
-  return;
-}
-
-WEAK_FUNCTION void hal_critical_section_end(void)
-{
-  return;
-}
+WEAK_FUNCTION void hal_critical_section_start(void) { return; }
+WEAK_FUNCTION void hal_critical_section_end(void)   { return; }
 
 /*
  * Keystore lock -- lock call blocks indefinitely.
  */
 
-WEAK_FUNCTION void hal_ks_lock(void)
-{
-  return;
-}
+WEAK_FUNCTION void hal_ks_lock(void)   { return; }
+WEAK_FUNCTION void hal_ks_unlock(void) { return; }
 
-WEAK_FUNCTION void hal_ks_unlock(void)
-{
-  return;
-}
+/*
+ * RSA blinding cache lock -- lock call blocks indefinitely.
+ */
+
+WEAK_FUNCTION void hal_rsa_bf_lock(void)   { return; }
+WEAK_FUNCTION void hal_rsa_bf_unlock(void) { return; }
+
+/*
+ * Non-preemptive task yield.
+ */
 
 WEAK_FUNCTION void hal_task_yield(void)
 {
diff --git a/rsa.c b/rsa.c
index 01d8290..8b55c93 100644
--- a/rsa.c
+++ b/rsa.c
@@ -12,7 +12,7 @@
  * St Denis's libtomcrypt code.
  *
  * Authors: Rob Austein
- * Copyright (c) 2015, NORDUnet A/S
+ * Copyright (c) 2015-2018, NORDUnet A/S
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -102,6 +102,15 @@
 #endif
 
 /*
+ * How big to make the blinding factors cache.
+ * Zero disables the cache entirely.
+ */
+
+#ifndef HAL_RSA_BLINDING_CACHE_SIZE
+#define HAL_RSA_BLINDING_CACHE_SIZE 2
+#endif
+
+/*
  * Whether we want debug output.
  */
 
@@ -123,6 +132,20 @@ void hal_rsa_set_blinding(const int onoff)
   blinding = onoff;
 }
 
+#if HAL_RSA_BLINDING_CACHE_SIZE > 0
+
+typedef struct {
+  unsigned lru;
+  fp_int n[1], bf[1], ubf[1];
+} bfc_slot_t;
+
+static struct {
+  unsigned lru;
+  bfc_slot_t slot[HAL_RSA_BLINDING_CACHE_SIZE];
+} bfc;
+
+#endif
+
 /*
  * RSA key implementation.  This structure type is private to this
  * module, anything else that needs to touch one of these just gets a
@@ -429,6 +452,31 @@ static hal_error_t create_blinding_factors(hal_core_t *core, hal_rsa_key_t *key,
   uint8_t rnd[fp_unsigned_bin_size(unconst_fp_int(key->n))];
   hal_error_t err = HAL_OK;
 
+  hal_rsa_bf_lock();
+
+#if HAL_RSA_BLINDING_CACHE_SIZE > 0
+  unsigned best_delta = 0;
+  int      best_index = 0;
+
+  for (int i = 0; i < HAL_RSA_BLINDING_CACHE_SIZE; i++) {
+    bfc_slot_t *b = &bfc.slot[i];
+    const unsigned delta = bfc.lru - b->lru;
+    if (delta > best_delta) {
+      best_delta = delta;
+      best_index = i;
+    }
+    if (fp_cmp_mag(b->n, key->n) == FP_EQ) {
+      if (fp_sqrmod(b->bf,  key->n, b->bf)  != FP_OKAY ||
+          fp_sqrmod(b->ubf, key->n, b->ubf) != FP_OKAY)
+        continue;               /* should never happen, but be safe */
+      fp_copy(b->bf, bf);
+      fp_copy(b->ubf, ubf);
+      err = HAL_OK;
+      goto fail;
+    }
+  }
+#endif
+
   if ((err = hal_get_random(NULL, rnd, sizeof(rnd))) != HAL_OK)
     goto fail;
 
@@ -445,7 +493,18 @@ static hal_error_t create_blinding_factors(hal_core_t *core, hal_rsa_key_t *key,
 
   FP_CHECK(fp_invmod(ubf, unconst_fp_int(key->n), ubf));
 
+#if HAL_RSA_BLINDING_CACHE_SIZE > 0
+  {
+    bfc_slot_t *b = &bfc.slot[best_index];
+    fp_copy(key->n, b->n);
+    fp_copy(bf,  b->bf);
+    fp_copy(ubf, b->ubf);
+    b->lru = ++bfc.lru;
+  }
+#endif
+
  fail:
+  hal_rsa_bf_unlock();
   memset(rnd, 0, sizeof(rnd));
   return err;
 }