Make BN_GF2m_mod_arr more constant time

Experiments have shown that the lookup table used by BN_GF2m_mod_arr
introduces sufficient timing signal to recover the private key for an
attacker with access to cache timing information on the victim's host.
This only affects binary curves (which are less frequently used).

No CVE is considered necessary for this issue.

The fix is to replace the lookup table with an on-the-fly calculation of
the value from the table instead, which can be performed in constant time.

Thanks to Youngjoo Shin for reporting this issue.

Reviewed-by: Rich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/6270)

1 files changed, 17 insertions, 15 deletions

diff --git a/crypto/bn/bn_gf2m.c b/crypto/bn/bn_gf2m.c
index 287adf305a..0fc4460da8 100644
--- a/crypto/bn/bn_gf2m.c
+++ b/crypto/bn/bn_gf2m.c
@@ -22,30 +22,32 @@
  */
 # define MAX_ITERATIONS 50
 
-static const BN_ULONG SQR_tb[16] = { 0, 1, 4, 5, 16, 17, 20, 21,
-    64, 65, 68, 69, 80, 81, 84, 85
-};
+# define SQR_nibble(w)   ((((w) & 8) << 3) \
+                       |  (((w) & 4) << 2) \
+                       |  (((w) & 2) << 1) \
+                       |   ((w) & 1))
+
 
 /* Platform-specific macros to accelerate squaring. */
 # if defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 #  define SQR1(w) \
-    SQR_tb[(w) >> 60 & 0xF] << 56 | SQR_tb[(w) >> 56 & 0xF] << 48 | \
-    SQR_tb[(w) >> 52 & 0xF] << 40 | SQR_tb[(w) >> 48 & 0xF] << 32 | \
-    SQR_tb[(w) >> 44 & 0xF] << 24 | SQR_tb[(w) >> 40 & 0xF] << 16 | \
-    SQR_tb[(w) >> 36 & 0xF] <<  8 | SQR_tb[(w) >> 32 & 0xF]
+    SQR_nibble((w) >> 60) << 56 | SQR_nibble((w) >> 56) << 48 | \
+    SQR_nibble((w) >> 52) << 40 | SQR_nibble((w) >> 48) << 32 | \
+    SQR_nibble((w) >> 44) << 24 | SQR_nibble((w) >> 40) << 16 | \
+    SQR_nibble((w) >> 36) <<  8 | SQR_nibble((w) >> 32)
 #  define SQR0(w) \
-    SQR_tb[(w) >> 28 & 0xF] << 56 | SQR_tb[(w) >> 24 & 0xF] << 48 | \
-    SQR_tb[(w) >> 20 & 0xF] << 40 | SQR_tb[(w) >> 16 & 0xF] << 32 | \
-    SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >>  8 & 0xF] << 16 | \
-    SQR_tb[(w) >>  4 & 0xF] <<  8 | SQR_tb[(w)       & 0xF]
+    SQR_nibble((w) >> 28) << 56 | SQR_nibble((w) >> 24) << 48 | \
+    SQR_nibble((w) >> 20) << 40 | SQR_nibble((w) >> 16) << 32 | \
+    SQR_nibble((w) >> 12) << 24 | SQR_nibble((w) >>  8) << 16 | \
+    SQR_nibble((w) >>  4) <<  8 | SQR_nibble((w)      )
 # endif
 # ifdef THIRTY_TWO_BIT
 #  define SQR1(w) \
-    SQR_tb[(w) >> 28 & 0xF] << 24 | SQR_tb[(w) >> 24 & 0xF] << 16 | \
-    SQR_tb[(w) >> 20 & 0xF] <<  8 | SQR_tb[(w) >> 16 & 0xF]
+    SQR_nibble((w) >> 28) << 24 | SQR_nibble((w) >> 24) << 16 | \
+    SQR_nibble((w) >> 20) <<  8 | SQR_nibble((w) >> 16)
 #  define SQR0(w) \
-    SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >>  8 & 0xF] << 16 | \
-    SQR_tb[(w) >>  4 & 0xF] <<  8 | SQR_tb[(w)       & 0xF]
+    SQR_nibble((w) >> 12) << 24 | SQR_nibble((w) >>  8) << 16 | \
+    SQR_nibble((w) >>  4) <<  8 | SQR_nibble((w)      )
 # endif
 
 # if !defined(OPENSSL_BN_ASM_GF2m)