commit 642664838ae91b943c6fd061f595253ac2ebe06c
author David Benjamin <davidben@google.com> Sat Oct 12 21:36:17 2019 -0400
committer CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org> Tue Oct 15 19:34:44 2019 +0000
tree 3c2d0bbeadb3953b6ddbe6fe0aac3991e6ea5be6
parent 841a40a2769bb92e395906b547464546f886785c

Simplify bn_miller_rabin_iteration slightly.

We don't need both mask variables. If we know we have a composite
witness, we return immediately, so the only time we mask off
instructions is when we know we have a nonwitness.

Change-Id: I2b99f3114a79ce2dc1a37706835d2abfe93a716e
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/38167
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: Adam Langley <agl@google.com>

crypto/fipsmodule/bn/prime.c

diff --git a/crypto/fipsmodule/bn/prime.c b/crypto/fipsmodule/bn/prime.c
index 37a73bf..8c70e69 100644
--- a/crypto/fipsmodule/bn/prime.c
+++ b/crypto/fipsmodule/bn/prime.c
@@ -650,27 +650,24 @@
     goto err;
   }
 
-  // loop_done is all ones if the loop has completed and all zeros otherwise.
-  crypto_word_t loop_done = 0;
   // is_possibly_prime is all ones if we have determined |b| is not a composite
   // witness for |w|. This is equivalent to going to step 4.7 in the original
-  // algorithm.
+  // algorithm. To avoid timing leaks, we run the algorithm to the end for prime
+  // inputs.
   crypto_word_t is_possibly_prime = 0;
 
   // Step 4.4. If z = 1 or z = w-1, b is not a composite witness and w is still
   // possibly prime.
-  loop_done = BN_equal_consttime(z, miller_rabin->one_mont) |
-              BN_equal_consttime(z, miller_rabin->w1_mont);
-  loop_done = 0 - loop_done;   // Make it all zeros or all ones.
-  is_possibly_prime = loop_done;  // Go to step 4.7 if |loop_done|.
+  is_possibly_prime = BN_equal_consttime(z, miller_rabin->one_mont) |
+                      BN_equal_consttime(z, miller_rabin->w1_mont);
+  is_possibly_prime = 0 - is_possibly_prime;  // Make it all zeros or all ones.
 
   // Step 4.5.
   //
   // To avoid leaking |a|, we run the loop to |w_bits| and mask off all
   // iterations once |j| = |a|.
   for (int j = 1; j < miller_rabin->w_bits; j++) {
-    loop_done |= constant_time_eq_int(j, miller_rabin->a);
-    if (loop_done & ~is_possibly_prime) {
+    if (constant_time_eq_int(j, miller_rabin->a) & ~is_possibly_prime) {
       // If the loop is done and we haven't seen z = 1 or z = w-1 yet, the
       // value is composite and we can break in variable time.
       break;
@@ -683,17 +680,14 @@
 
     // Step 4.5.2. If z = w-1 and the loop is not done, this is not a composite
     // witness.
-    crypto_word_t z_is_w1_mont =
-        BN_equal_consttime(z, miller_rabin->w1_mont) & ~loop_done;
-    z_is_w1_mont = 0 - z_is_w1_mont;  // Make it all zeros or all ones.
-    loop_done |= z_is_w1_mont;
+    crypto_word_t z_is_w1_mont = BN_equal_consttime(z, miller_rabin->w1_mont);
+    z_is_w1_mont = 0 - z_is_w1_mont;    // Make it all zeros or all ones.
     is_possibly_prime |= z_is_w1_mont;  // Go to step 4.7 if |z_is_w1_mont|.
 
     // Step 4.5.3. If z = 1 and the loop is not done, the previous value of z
     // was not -1. There are no non-trivial square roots of 1 modulo a prime, so
     // w is composite and we may exit in variable time.
-    if (BN_equal_consttime(z, miller_rabin->one_mont) & ~loop_done) {
-      assert(!is_possibly_prime);
+    if (BN_equal_consttime(z, miller_rabin->one_mont) & ~is_possibly_prime) {
       break;
     }
   }