Implement fixed-window exponentiation to mitigate hyper-threading

timing attacks.

BN_FLG_EXP_CONSTTIME requests this algorithm, and this done by default for
RSA/DSA/DH private key computations unless
RSA_FLAG_NO_EXP_CONSTTIME/DSA_FLAG_NO_EXP_CONSTTIME/
DH_FLAG_NO_EXP_CONSTTIME is set.

Submitted by: Matthew D Wood
Reviewed by: Bodo Moeller

1 files changed, 39 insertions, 0 deletions

diff --git a/crypto/bn/bn_lcl.h b/crypto/bn/bn_lcl.h
index 45e19221aa..1c680fc3ce 100644
--- a/crypto/bn/bn_lcl.h
+++ b/crypto/bn/bn_lcl.h
@@ -163,6 +163,45 @@ extern "C" {
 
 
 
+/* BN_mod_exp_mont_conttime is based on the assumption that the
+ * L1 data cache line width of the target processor is at least
+ * the following value.
+ */
+#define MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH	( 64 )
+#define MOD_EXP_CTIME_MIN_CACHE_LINE_MASK	(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - 1)
+
+/* Window sizes optimized for fixed window size modular exponentiation
+ * algorithm (BN_mod_exp_mont_consttime).
+ *
+ * To achieve the security goals of BN_mode_exp_mont_consttime, the
+ * maximum size of the window must not exceed
+ * log_2(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH). 
+ *
+ * Window size thresholds are defined for cache line sizes of 32 and 64,
+ * cache line sizes where log_2(32)=5 and log_2(64)=6 respectively. A
+ * window size of 7 should only be used on processors that have a 128
+ * byte or greater cache line size.
+ */
+#if MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 64
+
+#  define BN_window_bits_for_ctime_exponent_size(b) \
+		((b) > 937 ? 6 : \
+		 (b) > 306 ? 5 : \
+		 (b) >  89 ? 4 : \
+		 (b) >  22 ? 3 : 1)
+#  define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE	(6)
+
+#elif MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 32
+
+#  define BN_window_bits_for_ctime_exponent_size(b) \
+		((b) > 306 ? 5 : \
+		 (b) >  89 ? 4 : \
+		 (b) >  22 ? 3 : 1)
+#  define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE	(5)
+
+#endif
+
+
 /* Pentium pro 16,16,16,32,64 */
 /* Alpha       16,16,16,16.64 */
 #define BN_MULL_SIZE_NORMAL			(16) /* 32 */