[Cryptech-Commits] [sw/libhal] 02/02: First cut at reusing 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 rsa-blind-mutation
in repository sw/libhal.

commit 9d701b8a4da62de27b20f928f4385c46ece33d7f
Author: Rob Austein <sra at hactrn.net>
AuthorDate: Mon Apr 2 09:46:47 2018 -0400

    First cut at reusing RSA blinding factors.
    
    General technique here suggested by Peter Gutman.  If I got the math
    wrong, blame me, not Peter.
    
    This has not yet been tested to confirm that it returns correct
    results when using the blinding factors cache, and preliminary timing
    results suggest that we may be chasing the wrong performance problem.
    Unclear whether we'll ever really want to integrate this change, but
    pushing it on a branch to get it into repository history.
    
    If we do end up using this, the blinding factors cache will need minor
    redesign, principally to use the external SDRAM because main memory
    has gotten kind of full.  Some way to clear the cache when restarting
    the HSM would be nice, probably requires a `hal_rsa_init()` function.
---
 rsa.c | 57 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 56 insertions(+), 1 deletion(-)

diff --git a/rsa.c b/rsa.c
index 01d8290..e2884bd 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
@@ -425,6 +448,28 @@ static hal_error_t create_blinding_factors(hal_core_t *core, hal_rsa_key_t *key,
   if (key == NULL || bf == NULL || ubf == NULL)
     return HAL_ERROR_IMPOSSIBLE;
 
+#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);
+      return HAL_OK;
+    }
+  }
+#endif
+
   const int precalc = !(key->flags & RSA_FLAG_PRECALC_N_DONE);
   uint8_t rnd[fp_unsigned_bin_size(unconst_fp_int(key->n))];
   hal_error_t err = HAL_OK;
@@ -445,6 +490,16 @@ 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:
   memset(rnd, 0, sizeof(rnd));
   return err;