[Cryptech-Commits] [sw/libhal] 02/02: Add small cache for RSA blinding factors.

[git at cryptech.is]

This is an automated email from the git hooks/post-receive script.

sra at hactrn.net pushed a commit to branch master
in repository sw/libhal.

commit 8d72d9d3b3e0aeb9af68df85f555944c0558eb4f
Author: Rob Austein <sra at hactrn.net>
AuthorDate: Sun May 20 15:40:08 2018 -0400

    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.
---
 hal_internal.h |  2 ++
 locks.c        | 31 ++++++++++++++---------------
 rsa.c          | 61 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 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
@@ -101,6 +101,15 @@
 #define HAL_RSA_MAX_OPERAND_LENGTH MODEXPA7_OPERAND_BYTES
 #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;
 }