curve: use subtle::Choice for constant-time fixes (dalek-cryptograp…

…hy#665) Alternative to dalek-cryptography#659/dalek-cryptography#661 and dalek-cryptography#662 which leverages `subtle::Choice` and `subtle::ConditionallySelectable` as the optimization barriers. Really the previous masking was there to conditionally add the scalar field modulus on underflow, so instead of that, we can conditionally select zero or the modulus using a `Choice` constructed from the underflow bit.
jmwample · Jul 17, 2024 · 921bd7c · 921bd7c
1 parent 5b7082b
commit 921bd7c
Show file tree

Hide file tree

Showing 2 changed files with 14 additions and 16 deletions.
diff --git a/curve25519-dalek/src/backend/serial/u32/scalar.rs b/curve25519-dalek/src/backend/serial/u32/scalar.rs
@@ -12,7 +12,7 @@
 
 use core::fmt::Debug;
 use core::ops::{Index, IndexMut};
-use subtle::BlackBox;
+use subtle::{Choice, ConditionallySelectable};
 
 #[cfg(feature = "zeroize")]
 use zeroize::Zeroize;
@@ -187,23 +187,22 @@ impl Scalar29 {
     /// Compute `a - b` (mod l).
     pub fn sub(a: &Scalar29, b: &Scalar29) -> Scalar29 {
         let mut difference = Scalar29::ZERO;
-        let mask = BlackBox::new((1u32 << 29) - 1);
+        let mask = (1u32 << 29) - 1;
 
         // a - b
         let mut borrow: u32 = 0;
         for i in 0..9 {
             borrow = a[i].wrapping_sub(b[i] + (borrow >> 31));
-            difference[i] = borrow & mask.get();
+            difference[i] = borrow & mask;
         }
 
         // conditionally add l if the difference is negative
-        let underflow_mask = BlackBox::new(((borrow >> 31) ^ 1).wrapping_sub(1));
         let mut carry: u32 = 0;
         for i in 0..9 {
-            // SECURITY: `BlackBox` prevents LLVM from inserting a `jns` conditional on x86(_64)
-            // which can be used to bypass this section when `underflow_mask` is zero.
-            carry = (carry >> 29) + difference[i] + (constants::L[i] & underflow_mask.get());
-            difference[i] = carry & mask.get();
+            let underflow = Choice::from((borrow >> 31) as u8);
+            let addend = u32::conditional_select(&0, &constants::L[i], underflow);
+            carry = (carry >> 29) + difference[i] + addend;
+            difference[i] = carry & mask;
         }
 
         difference

diff --git a/curve25519-dalek/src/backend/serial/u64/scalar.rs b/curve25519-dalek/src/backend/serial/u64/scalar.rs
@@ -13,7 +13,7 @@
 
 use core::fmt::Debug;
 use core::ops::{Index, IndexMut};
-use subtle::BlackBox;
+use subtle::{Choice, ConditionallySelectable};
 
 #[cfg(feature = "zeroize")]
 use zeroize::Zeroize;
@@ -176,23 +176,22 @@ impl Scalar52 {
     /// Compute `a - b` (mod l)
     pub fn sub(a: &Scalar52, b: &Scalar52) -> Scalar52 {
         let mut difference = Scalar52::ZERO;
-        let mask = BlackBox::new((1u64 << 52) - 1);
+        let mask = (1u64 << 52) - 1;
 
         // a - b
         let mut borrow: u64 = 0;
         for i in 0..5 {
             borrow = a[i].wrapping_sub(b[i] + (borrow >> 63));
-            difference[i] = borrow & mask.get();
+            difference[i] = borrow & mask;
         }
 
         // conditionally add l if the difference is negative
-        let underflow_mask = BlackBox::new(((borrow >> 63) ^ 1).wrapping_sub(1));
         let mut carry: u64 = 0;
         for i in 0..5 {
-            // SECURITY: `BlackBox` prevents LLVM from inserting a `jns` conditional on x86(_64)
-            // which can be used to bypass this section when `underflow_mask` is zero.
-            carry = (carry >> 52) + difference[i] + (constants::L[i] & underflow_mask.get());
-            difference[i] = carry & mask.get();
+            let underflow = Choice::from((borrow >> 63) as u8);
+            let addend = u64::conditional_select(&0, &constants::L[i], underflow);
+            carry = (carry >> 52) + difference[i] + addend;
+            difference[i] = carry & mask;
         }
 
         difference