bouncycastle_utils/
ct.rs

1//! A set of constant-time helper functions for the following:
2//!
3//! * Basic arithmetic operations such as less-than(x, y), is_zero(x), etc.
4//! * Conditional operations such as select and swap whose output depends on whether the condition is true or false.
5//! * Implementing boolean operators for Condition\<T\>: &, &=, |, |=, ^, ^=.
6
7use core::ops::*;
8
9mod sealed {
10    pub(super) trait Sealed {}
11}
12
13struct MaskType<T>(core::marker::PhantomData<T>);
14
15trait SupportedMaskType: sealed::Sealed {}
16
17macro_rules! supported_mask_type {
18    ($($t:ty),+) => {
19        $(
20            impl sealed::Sealed for MaskType<$t> {}
21            impl SupportedMaskType for MaskType<$t> {}
22        )+
23    };
24}
25
26supported_mask_type!(i64, u64);
27
28/// Helper functions for checking some condition on some data using constant-time operations.
29#[derive(Clone, Copy)]
30#[must_use]
31#[repr(transparent)]
32pub struct Condition<T>(T)
33where
34    MaskType<T>: SupportedMaskType;
35
36impl<T> Condition<T> where MaskType<T>: SupportedMaskType {}
37
38impl Condition<i64> {
39    // TODO: there are a bunch of impls in here that seem to be generic and not related to i64,
40    //       could those be moved to a generic impl<T> for Condition<T> ?
41
42    /// TRUE is the bit vector of all 1's
43    pub const TRUE: Self = Self(-1);
44    /// FALSE is the bit vector of all 0's
45    pub const FALSE: Self = Self(0);
46    ///
47    pub const fn from_bool<const VALUE: bool>() -> Self {
48        Self(-(VALUE as i64))
49    }
50    ///
51    pub const fn from_bool_var(value: bool) -> Self {
52        Self(-(value as i64))
53    }
54    ///
55    pub const fn is_bit_set(value: i64, bit: i64) -> Self {
56        Self(-((value >> bit) & 1))
57    }
58    ///
59    pub const fn is_negative(value: i64) -> Self {
60        Self(value >> 63)
61    }
62    ///
63    pub const fn is_not_zero(value: i64) -> Self {
64        Self::is_negative(-Self::or_halves(value))
65    }
66    ///
67    pub const fn is_zero(value: i64) -> Self {
68        Self::is_negative(Self::or_halves(value) - 1)
69    }
70    ///
71    pub const fn is_equal(x: i64, y: i64) -> Self {
72        Self::is_zero(x ^ y)
73    }
74    ///
75    pub const fn is_lt(x: i64, y: i64) -> Self {
76        Self::is_negative(x - y)
77    }
78    ///
79    // Note: this cannot currently be marked as const, since it either needs a (non-const) not (!) or a boolean OR is_zero.
80    pub fn is_lte(x: i64, y: i64) -> Self {
81        !Self::is_gt(x, y)
82    }
83    ///
84    pub const fn is_gt(x: i64, y: i64) -> Self {
85        Self::is_lt(y, x)
86    }
87    ///
88    // Note: this cannot currently be marked as const, since it either needs a (non-const) not (!) or a boolean OR is_zero.
89    pub fn is_gte(x: i64, y: i64) -> Self {
90        !Self::is_lt(x, y)
91    }
92    ///
93    pub fn is_within_range(value: i64, min: i64, max: i64) -> Self {
94        Self::is_gte(value, min) & Self::is_lte(value, max)
95    }
96    ///
97    pub fn is_in_list(value: i64, list: &[i64]) -> Self {
98        // Research question: is this actually constant-time?
99        // A clever compiler might turn this into a short-circuiting loop.
100        // A quick google search shows that rust doesn't have the ability to annotate specific code blocks
101        // as no-optimize; the only option is to insert direct assembly.
102
103        let mut c = Self::FALSE;
104        for i in 0..list.len() {
105            let diff = value ^ list[i];
106            c |= Condition::<i64>::is_zero(diff);
107        }
108
109        c
110    }
111
112    /// Conditionally move the source value to the destination if the condition is true, otherwise nothing is moved.
113    pub fn mov(self, src: i64, dst: &mut i64) {
114        *dst = self.select(src, *dst);
115    }
116
117    /// Conditionally negate the value.
118    ///
119    /// negate(-1) gives -3
120    ///
121    /// `value` is `-1` (i.e., all bits are `1`, `...1111`)
122    ///
123    /// Condition `self.0` is 1 (`...0001`) (assuming `TRUE`)
124    ///
125    /// XOR operation was executed as `value ^ self.0`
126    ///
127    /// Then `...1111 XOR ...0001 = ...1110` (i.e., `-2`)
128    ///
129    /// Subtraction operation is `wrapping_sub(self.0)`
130    ///
131    /// Then `-2 - 1 = -3`
132    ///
133    /// As a result, `1`, which is the negation of `-1`, should be returned, but `-3` is output.
134    ///
135    /// Therefore, if the [`Self::TRUE`] constant value of the i64 [`Condition`] implementation is changed to `-1`,
136    /// the test also runs normally.
137    pub const fn negate(self, value: i64) -> i64 {
138        (value ^ self.0).wrapping_sub(self.0)
139    }
140    ///
141    pub const fn or_halves(value: i64) -> i64 {
142        (value | (value >> 32)) & 0xFFFFFFFF
143    }
144    /// Conditional selection: return `true_value` if the condition is true, otherwise return `false_value`.
145    pub const fn select(self, true_value: i64, false_value: i64) -> i64 {
146        (true_value & self.0) | (false_value & !self.0)
147    }
148    /// Conditional swap: returns (lhs, rhs) if the condition is true, otherwise returns (rhs, lhs).
149    pub const fn swap(self, lhs: i64, rhs: i64) -> (i64, i64) {
150        (self.select(rhs, lhs), self.select(lhs, rhs))
151    }
152    ///
153    pub const fn to_bool_var(self) -> bool {
154        self.0 != 0
155    }
156}
157
158// TODO: We should do Condition<u8>.
159//       then and change Hex and Base64 to use this.
160//       (there's probably no noticeable performance difference u8 and u64 bit ops on a 64-bit machine,
161//       but there would be on a 8, 16, or 32-bit machine.)
162impl Condition<u64> {
163    /// TRUE is the bit vector of all 1's
164    pub const TRUE: Self = Self(u64::MAX);
165    /// FALSE is the bit vector of all 0's
166    pub const FALSE: Self = Self(0);
167
168    /// this is the core logic for constant-time mask generation for unsigned integers
169    ///   Unlike signed integers where we can rely on Two's Complement via negation `-(v as i64)`,
170    ///   for u64 we must use wrapping subtraction to achieve the all-ones bit pattern (u64::MAX) for true
171    pub const fn from_bool<const VALUE: bool>() -> Self {
172        // If VALUE is true (1) -> 0 - 1 = u64::MAX (All 1s)
173        // If VALUE is false (0) -> 0 - 0 = 0 (All 0s)
174        Self(0u64.wrapping_sub(VALUE as u64))
175    }
176    /// impl the select function manually for u64
177    ///    although a fully generic `impl<T>` would be the ultimate long-term goal
178    pub fn select(self, a: u64, b: u64) -> u64 {
179        let mask = self.0;
180        (a & mask) | (b & !mask)
181    }
182    ///
183    pub fn is_true(&self) -> bool {
184        self.0 != 0
185    }
186}
187
188impl<T> BitAnd for Condition<T>
189where
190    MaskType<T>: SupportedMaskType,
191    T: BitAnd<T, Output = T>,
192{
193    type Output = Self;
194    fn bitand(self, rhs: Self) -> Self {
195        Self(self.0 & rhs.0)
196    }
197}
198
199impl<T> BitAndAssign for Condition<T>
200where
201    MaskType<T>: SupportedMaskType,
202    T: BitAndAssign<T>,
203{
204    fn bitand_assign(&mut self, rhs: Self) {
205        self.0 &= rhs.0;
206    }
207}
208
209impl<T> BitOr for Condition<T>
210where
211    MaskType<T>: SupportedMaskType,
212    T: BitOr<T, Output = T>,
213{
214    type Output = Self;
215    fn bitor(self, rhs: Self) -> Self {
216        Self(self.0 | rhs.0)
217    }
218}
219
220impl<T> BitOrAssign for Condition<T>
221where
222    MaskType<T>: SupportedMaskType,
223    T: BitOrAssign<T>,
224{
225    fn bitor_assign(&mut self, rhs: Self) {
226        self.0 |= rhs.0;
227    }
228}
229
230impl<T> BitXor for Condition<T>
231where
232    MaskType<T>: SupportedMaskType,
233    T: BitXor<T, Output = T>,
234{
235    type Output = Self;
236    fn bitxor(self, rhs: Self) -> Self {
237        Self(self.0 ^ rhs.0)
238    }
239}
240
241impl<T> BitXorAssign for Condition<T>
242where
243    MaskType<T>: SupportedMaskType,
244    T: BitXorAssign<T>,
245{
246    fn bitxor_assign(&mut self, rhs: Self) {
247        self.0 ^= rhs.0;
248    }
249}
250
251impl<T> Not for Condition<T>
252where
253    MaskType<T>: SupportedMaskType,
254    T: Not<Output = T>,
255{
256    type Output = Self;
257    fn not(self) -> Self {
258        Self(!self.0)
259    }
260}
261
262/// Rust doesn't guarantee that anything can truly be constant-time under all compilation targets
263/// and optimization levels. The following presents the standard constant-time shape.
264pub fn ct_eq_bytes(a: &[u8], b: &[u8]) -> bool {
265    if a.len() != b.len() {
266        return false;
267    }
268    let mut result = 0u8;
269    for i in 0..a.len() {
270        result |= core::hint::black_box(a[i] ^ b[i]);
271    }
272    result == 0
273}
274
275/// Rust doesn't guarantee that anything can truly be constant-time under all compilation targets
276/// and optimization levels. The following presents the standard constant-time shape.
277pub fn ct_eq_zero_bytes(a: &[u8]) -> bool {
278    let mut result = 0u8;
279    for i in 0..a.len() {
280        result |= core::hint::black_box(a[i]);
281    }
282    result == 0
283}
284
285/// Copies either the contents of `a` or `b` into `out` according to `take_a`
286/// and it does it in a constant-time manner without branching.
287pub fn conditional_copy_bytes<const LEN: usize>(
288    a: &[u8; LEN],
289    b: &[u8; LEN],
290    out: &mut [u8; LEN],
291    take_a: bool,
292) {
293    // we want the behaviour of
294    //  if take_a { 0xFF } else { 0x00 }
295    // but without using any branches that could leak timing signals
296    let mask: u8 = (take_a as u8)
297        | (take_a as u8) << 1
298        | (take_a as u8) << 2
299        | (take_a as u8) << 3
300        | (take_a as u8) << 4
301        | (take_a as u8) << 5
302        | (take_a as u8) << 6
303        | (take_a as u8) << 7;
304
305    debug_assert_eq!(mask, if take_a { 0xFF } else { 0x00 });
306
307    for i in 0..LEN {
308        out[i] = core::hint::black_box(a[i] & mask) | core::hint::black_box(b[i] & !mask);
309    }
310}
bouncycastle_utils/ct.rs

bouncycastle_utils/
ct.rs
