1 // -*- mode: rust; -*-
2 //
3 // This file is part of subtle, part of the dalek cryptography project.
4 // Copyright (c) 2016-2018 isis lovecruft, Henry de Valence
5 // See LICENSE for licensing information.
6 //
7 // Authors:
8 // - isis agora lovecruft <isis@patternsinthevoid.net>
9 // - Henry de Valence <hdevalence@hdevalence.ca>
10
11 #![no_std]
12 #![cfg_attr(feature = "nightly", feature(external_doc))]
13 #![cfg_attr(feature = "nightly", doc(include = "../README.md"))]
14 #![cfg_attr(feature = "nightly", deny(missing_docs))]
15 #![doc(html_logo_url = "https://doc.dalek.rs/assets/dalek-logo-clear.png")]
16 #![doc(html_root_url = "https://docs.rs/subtle/2.4.0")]
17
18 //! Note that docs will only build on nightly Rust until
19 //! [RFC 1990 stabilizes](https://github.com/rust-lang/rust/issues/44732).
20
21 #[cfg(feature = "std")]
22 #[macro_use]
23 extern crate std;
24
25 #[cfg(test)]
26 extern crate rand;
27
28 use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Neg, Not};
29 use core::option::Option;
30
31 /// The `Choice` struct represents a choice for use in conditional assignment.
32 ///
33 /// It is a wrapper around a `u8`, which should have the value either `1` (true)
34 /// or `0` (false).
35 ///
36 /// The conversion from `u8` to `Choice` passes the value through an optimization
37 /// barrier, as a best-effort attempt to prevent the compiler from inferring that
38 /// the `Choice` value is a boolean. This strategy is based on Tim Maclean's
39 /// [work on `rust-timing-shield`][rust-timing-shield], which attempts to provide
40 /// a more comprehensive approach for preventing software side-channels in Rust
41 /// code.
42 ///
43 /// The `Choice` struct implements operators for AND, OR, XOR, and NOT, to allow
44 /// combining `Choice` values. These operations do not short-circuit.
45 ///
46 /// [rust-timing-shield]:
47 /// https://www.chosenplaintext.ca/open-source/rust-timing-shield/security
48 #[derive(Copy, Clone, Debug)]
49 pub struct Choice(u8);
50
51 impl Choice {
52 /// Unwrap the `Choice` wrapper to reveal the underlying `u8`.
53 ///
54 /// # Note
55 ///
56 /// This function only exists as an **escape hatch** for the rare case
57 /// where it's not possible to use one of the `subtle`-provided
58 /// trait impls.
59 ///
60 /// **To convert a `Choice` to a `bool`, use the `From` implementation instead.**
61 #[inline]
unwrap_u8(&self) -> u862 pub fn unwrap_u8(&self) -> u8 {
63 self.0
64 }
65 }
66
67 impl From<Choice> for bool {
68 /// Convert the `Choice` wrapper into a `bool`, depending on whether
69 /// the underlying `u8` was a `0` or a `1`.
70 ///
71 /// # Note
72 ///
73 /// This function exists to avoid having higher-level cryptographic protocol
74 /// implementations duplicating this pattern.
75 ///
76 /// The intended use case for this conversion is at the _end_ of a
77 /// higher-level primitive implementation: for example, in checking a keyed
78 /// MAC, where the verification should happen in constant-time (and thus use
79 /// a `Choice`) but it is safe to return a `bool` at the end of the
80 /// verification.
81 #[inline]
from(source: Choice) -> bool82 fn from(source: Choice) -> bool {
83 debug_assert!((source.0 == 0u8) | (source.0 == 1u8));
84 source.0 != 0
85 }
86 }
87
88 impl BitAnd for Choice {
89 type Output = Choice;
90 #[inline]
bitand(self, rhs: Choice) -> Choice91 fn bitand(self, rhs: Choice) -> Choice {
92 (self.0 & rhs.0).into()
93 }
94 }
95
96 impl BitAndAssign for Choice {
97 #[inline]
bitand_assign(&mut self, rhs: Choice)98 fn bitand_assign(&mut self, rhs: Choice) {
99 *self = *self & rhs;
100 }
101 }
102
103 impl BitOr for Choice {
104 type Output = Choice;
105 #[inline]
bitor(self, rhs: Choice) -> Choice106 fn bitor(self, rhs: Choice) -> Choice {
107 (self.0 | rhs.0).into()
108 }
109 }
110
111 impl BitOrAssign for Choice {
112 #[inline]
bitor_assign(&mut self, rhs: Choice)113 fn bitor_assign(&mut self, rhs: Choice) {
114 *self = *self | rhs;
115 }
116 }
117
118 impl BitXor for Choice {
119 type Output = Choice;
120 #[inline]
bitxor(self, rhs: Choice) -> Choice121 fn bitxor(self, rhs: Choice) -> Choice {
122 (self.0 ^ rhs.0).into()
123 }
124 }
125
126 impl BitXorAssign for Choice {
127 #[inline]
bitxor_assign(&mut self, rhs: Choice)128 fn bitxor_assign(&mut self, rhs: Choice) {
129 *self = *self ^ rhs;
130 }
131 }
132
133 impl Not for Choice {
134 type Output = Choice;
135 #[inline]
not(self) -> Choice136 fn not(self) -> Choice {
137 (1u8 & (!self.0)).into()
138 }
139 }
140
141 /// This function is a best-effort attempt to prevent the compiler from knowing
142 /// anything about the value of the returned `u8`, other than its type.
143 ///
144 /// Because we want to support stable Rust, we don't have access to inline
145 /// assembly or test::black_box, so we use the fact that volatile values will
146 /// never be elided to register values.
147 ///
148 /// Note: Rust's notion of "volatile" is subject to change over time. While this
149 /// code may break in a non-destructive way in the future, “constant-time” code
150 /// is a continually moving target, and this is better than doing nothing.
151 #[inline(never)]
black_box(input: u8) -> u8152 fn black_box(input: u8) -> u8 {
153 debug_assert!((input == 0u8) | (input == 1u8));
154
155 unsafe {
156 // Optimization barrier
157 //
158 // Unsafe is ok, because:
159 // - &input is not NULL;
160 // - size of input is not zero;
161 // - u8 is neither Sync, nor Send;
162 // - u8 is Copy, so input is always live;
163 // - u8 type is always properly aligned.
164 core::ptr::read_volatile(&input as *const u8)
165 }
166 }
167
168 impl From<u8> for Choice {
169 #[inline]
from(input: u8) -> Choice170 fn from(input: u8) -> Choice {
171 // Our goal is to prevent the compiler from inferring that the value held inside the
172 // resulting `Choice` struct is really an `i1` instead of an `i8`.
173 Choice(black_box(input))
174 }
175 }
176
177 /// An `Eq`-like trait that produces a `Choice` instead of a `bool`.
178 ///
179 /// # Example
180 ///
181 /// ```
182 /// use subtle::ConstantTimeEq;
183 /// let x: u8 = 5;
184 /// let y: u8 = 13;
185 ///
186 /// assert_eq!(x.ct_eq(&y).unwrap_u8(), 0);
187 /// assert_eq!(x.ct_eq(&x).unwrap_u8(), 1);
188 /// ```
189 pub trait ConstantTimeEq {
190 /// Determine if two items are equal.
191 ///
192 /// The `ct_eq` function should execute in constant time.
193 ///
194 /// # Returns
195 ///
196 /// * `Choice(1u8)` if `self == other`;
197 /// * `Choice(0u8)` if `self != other`.
198 #[inline]
ct_eq(&self, other: &Self) -> Choice199 fn ct_eq(&self, other: &Self) -> Choice;
200 }
201
202 impl<T: ConstantTimeEq> ConstantTimeEq for [T] {
203 /// Check whether two slices of `ConstantTimeEq` types are equal.
204 ///
205 /// # Note
206 ///
207 /// This function short-circuits if the lengths of the input slices
208 /// are different. Otherwise, it should execute in time independent
209 /// of the slice contents.
210 ///
211 /// Since arrays coerce to slices, this function works with fixed-size arrays:
212 ///
213 /// ```
214 /// # use subtle::ConstantTimeEq;
215 /// #
216 /// let a: [u8; 8] = [0,1,2,3,4,5,6,7];
217 /// let b: [u8; 8] = [0,1,2,3,0,1,2,3];
218 ///
219 /// let a_eq_a = a.ct_eq(&a);
220 /// let a_eq_b = a.ct_eq(&b);
221 ///
222 /// assert_eq!(a_eq_a.unwrap_u8(), 1);
223 /// assert_eq!(a_eq_b.unwrap_u8(), 0);
224 /// ```
225 #[inline]
ct_eq(&self, _rhs: &[T]) -> Choice226 fn ct_eq(&self, _rhs: &[T]) -> Choice {
227 let len = self.len();
228
229 // Short-circuit on the *lengths* of the slices, not their
230 // contents.
231 if len != _rhs.len() {
232 return Choice::from(0);
233 }
234
235 // This loop shouldn't be shortcircuitable, since the compiler
236 // shouldn't be able to reason about the value of the `u8`
237 // unwrapped from the `ct_eq` result.
238 let mut x = 1u8;
239 for (ai, bi) in self.iter().zip(_rhs.iter()) {
240 x &= ai.ct_eq(bi).unwrap_u8();
241 }
242
243 x.into()
244 }
245 }
246
247 impl ConstantTimeEq for Choice {
248 #[inline]
ct_eq(&self, rhs: &Choice) -> Choice249 fn ct_eq(&self, rhs: &Choice) -> Choice {
250 !(*self ^ *rhs)
251 }
252 }
253
254 /// Given the bit-width `$bit_width` and the corresponding primitive
255 /// unsigned and signed types `$t_u` and `$t_i` respectively, generate
256 /// an `ConstantTimeEq` implementation.
257 macro_rules! generate_integer_equal {
258 ($t_u:ty, $t_i:ty, $bit_width:expr) => {
259 impl ConstantTimeEq for $t_u {
260 #[inline]
261 fn ct_eq(&self, other: &$t_u) -> Choice {
262 // x == 0 if and only if self == other
263 let x: $t_u = self ^ other;
264
265 // If x == 0, then x and -x are both equal to zero;
266 // otherwise, one or both will have its high bit set.
267 let y: $t_u = (x | x.wrapping_neg()) >> ($bit_width - 1);
268
269 // Result is the opposite of the high bit (now shifted to low).
270 ((y ^ (1 as $t_u)) as u8).into()
271 }
272 }
273 impl ConstantTimeEq for $t_i {
274 #[inline]
275 fn ct_eq(&self, other: &$t_i) -> Choice {
276 // Bitcast to unsigned and call that implementation.
277 (*self as $t_u).ct_eq(&(*other as $t_u))
278 }
279 }
280 };
281 }
282
283 generate_integer_equal!(u8, i8, 8);
284 generate_integer_equal!(u16, i16, 16);
285 generate_integer_equal!(u32, i32, 32);
286 generate_integer_equal!(u64, i64, 64);
287 #[cfg(feature = "i128")]
288 generate_integer_equal!(u128, i128, 128);
289 generate_integer_equal!(usize, isize, ::core::mem::size_of::<usize>() * 8);
290
291 /// A type which can be conditionally selected in constant time.
292 ///
293 /// This trait also provides generic implementations of conditional
294 /// assignment and conditional swaps.
295 pub trait ConditionallySelectable: Copy {
296 /// Select `a` or `b` according to `choice`.
297 ///
298 /// # Returns
299 ///
300 /// * `a` if `choice == Choice(0)`;
301 /// * `b` if `choice == Choice(1)`.
302 ///
303 /// This function should execute in constant time.
304 ///
305 /// # Example
306 ///
307 /// ```
308 /// # extern crate subtle;
309 /// use subtle::ConditionallySelectable;
310 /// #
311 /// # fn main() {
312 /// let x: u8 = 13;
313 /// let y: u8 = 42;
314 ///
315 /// let z = u8::conditional_select(&x, &y, 0.into());
316 /// assert_eq!(z, x);
317 /// let z = u8::conditional_select(&x, &y, 1.into());
318 /// assert_eq!(z, y);
319 /// # }
320 /// ```
321 #[inline]
conditional_select(a: &Self, b: &Self, choice: Choice) -> Self322 fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self;
323
324 /// Conditionally assign `other` to `self`, according to `choice`.
325 ///
326 /// This function should execute in constant time.
327 ///
328 /// # Example
329 ///
330 /// ```
331 /// # extern crate subtle;
332 /// use subtle::ConditionallySelectable;
333 /// #
334 /// # fn main() {
335 /// let mut x: u8 = 13;
336 /// let mut y: u8 = 42;
337 ///
338 /// x.conditional_assign(&y, 0.into());
339 /// assert_eq!(x, 13);
340 /// x.conditional_assign(&y, 1.into());
341 /// assert_eq!(x, 42);
342 /// # }
343 /// ```
344 #[inline]
conditional_assign(&mut self, other: &Self, choice: Choice)345 fn conditional_assign(&mut self, other: &Self, choice: Choice) {
346 *self = Self::conditional_select(self, other, choice);
347 }
348
349 /// Conditionally swap `self` and `other` if `choice == 1`; otherwise,
350 /// reassign both unto themselves.
351 ///
352 /// This function should execute in constant time.
353 ///
354 /// # Example
355 ///
356 /// ```
357 /// # extern crate subtle;
358 /// use subtle::ConditionallySelectable;
359 /// #
360 /// # fn main() {
361 /// let mut x: u8 = 13;
362 /// let mut y: u8 = 42;
363 ///
364 /// u8::conditional_swap(&mut x, &mut y, 0.into());
365 /// assert_eq!(x, 13);
366 /// assert_eq!(y, 42);
367 /// u8::conditional_swap(&mut x, &mut y, 1.into());
368 /// assert_eq!(x, 42);
369 /// assert_eq!(y, 13);
370 /// # }
371 /// ```
372 #[inline]
conditional_swap(a: &mut Self, b: &mut Self, choice: Choice)373 fn conditional_swap(a: &mut Self, b: &mut Self, choice: Choice) {
374 let t: Self = *a;
375 a.conditional_assign(&b, choice);
376 b.conditional_assign(&t, choice);
377 }
378 }
379
380 macro_rules! to_signed_int {
381 (u8) => {
382 i8
383 };
384 (u16) => {
385 i16
386 };
387 (u32) => {
388 i32
389 };
390 (u64) => {
391 i64
392 };
393 (u128) => {
394 i128
395 };
396 (i8) => {
397 i8
398 };
399 (i16) => {
400 i16
401 };
402 (i32) => {
403 i32
404 };
405 (i64) => {
406 i64
407 };
408 (i128) => {
409 i128
410 };
411 }
412
413 macro_rules! generate_integer_conditional_select {
414 ($($t:tt)*) => ($(
415 impl ConditionallySelectable for $t {
416 #[inline]
417 fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
418 // if choice = 0, mask = (-0) = 0000...0000
419 // if choice = 1, mask = (-1) = 1111...1111
420 let mask = -(choice.unwrap_u8() as to_signed_int!($t)) as $t;
421 a ^ (mask & (a ^ b))
422 }
423
424 #[inline]
425 fn conditional_assign(&mut self, other: &Self, choice: Choice) {
426 // if choice = 0, mask = (-0) = 0000...0000
427 // if choice = 1, mask = (-1) = 1111...1111
428 let mask = -(choice.unwrap_u8() as to_signed_int!($t)) as $t;
429 *self ^= mask & (*self ^ *other);
430 }
431
432 #[inline]
433 fn conditional_swap(a: &mut Self, b: &mut Self, choice: Choice) {
434 // if choice = 0, mask = (-0) = 0000...0000
435 // if choice = 1, mask = (-1) = 1111...1111
436 let mask = -(choice.unwrap_u8() as to_signed_int!($t)) as $t;
437 let t = mask & (*a ^ *b);
438 *a ^= t;
439 *b ^= t;
440 }
441 }
442 )*)
443 }
444
445 generate_integer_conditional_select!( u8 i8);
446 generate_integer_conditional_select!( u16 i16);
447 generate_integer_conditional_select!( u32 i32);
448 generate_integer_conditional_select!( u64 i64);
449 #[cfg(feature = "i128")]
450 generate_integer_conditional_select!(u128 i128);
451
452 impl ConditionallySelectable for Choice {
453 #[inline]
conditional_select(a: &Self, b: &Self, choice: Choice) -> Self454 fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
455 Choice(u8::conditional_select(&a.0, &b.0, choice))
456 }
457 }
458
459 /// A type which can be conditionally negated in constant time.
460 ///
461 /// # Note
462 ///
463 /// A generic implementation of `ConditionallyNegatable` is provided
464 /// for types `T` which are `ConditionallySelectable` and have `Neg`
465 /// implemented on `&T`.
466 pub trait ConditionallyNegatable {
467 /// Negate `self` if `choice == Choice(1)`; otherwise, leave it
468 /// unchanged.
469 ///
470 /// This function should execute in constant time.
471 #[inline]
conditional_negate(&mut self, choice: Choice)472 fn conditional_negate(&mut self, choice: Choice);
473 }
474
475 impl<T> ConditionallyNegatable for T
476 where
477 T: ConditionallySelectable,
478 for<'a> &'a T: Neg<Output = T>,
479 {
480 #[inline]
conditional_negate(&mut self, choice: Choice)481 fn conditional_negate(&mut self, choice: Choice) {
482 // Need to cast to eliminate mutability
483 let self_neg: T = -(self as &T);
484 self.conditional_assign(&self_neg, choice);
485 }
486 }
487
488 /// The `CtOption<T>` type represents an optional value similar to the
489 /// [`Option<T>`](core::option::Option) type but is intended for
490 /// use in constant time APIs.
491 ///
492 /// Any given `CtOption<T>` is either `Some` or `None`, but unlike
493 /// `Option<T>` these variants are not exposed. The
494 /// [`is_some()`](CtOption::is_some) method is used to determine if
495 /// the value is `Some`, and [`unwrap_or()`](CtOption::unwrap_or) and
496 /// [`unwrap_or_else()`](CtOption::unwrap_or_else) methods are
497 /// provided to access the underlying value. The value can also be
498 /// obtained with [`unwrap()`](CtOption::unwrap) but this will panic
499 /// if it is `None`.
500 ///
501 /// Functions that are intended to be constant time may not produce
502 /// valid results for all inputs, such as square root and inversion
503 /// operations in finite field arithmetic. Returning an `Option<T>`
504 /// from these functions makes it difficult for the caller to reason
505 /// about the result in constant time, and returning an incorrect
506 /// value burdens the caller and increases the chance of bugs.
507 #[derive(Clone, Copy, Debug)]
508 pub struct CtOption<T> {
509 value: T,
510 is_some: Choice,
511 }
512
513 impl<T> From<CtOption<T>> for Option<T> {
514 /// Convert the `CtOption<T>` wrapper into an `Option<T>`, depending on whether
515 /// the underlying `is_some` `Choice` was a `0` or a `1` once unwrapped.
516 ///
517 /// # Note
518 ///
519 /// This function exists to avoid ending up with ugly, verbose and/or bad handled
520 /// conversions from the `CtOption<T>` wraps to an `Option<T>` or `Result<T, E>`.
521 /// This implementation doesn't intend to be constant-time nor try to protect the
522 /// leakage of the `T` since the `Option<T>` will do it anyways.
from(source: CtOption<T>) -> Option<T>523 fn from(source: CtOption<T>) -> Option<T> {
524 if source.is_some().unwrap_u8() == 1u8 {
525 Option::Some(source.value)
526 } else {
527 None
528 }
529 }
530 }
531
532 impl<T> CtOption<T> {
533 /// This method is used to construct a new `CtOption<T>` and takes
534 /// a value of type `T`, and a `Choice` that determines whether
535 /// the optional value should be `Some` or not. If `is_some` is
536 /// false, the value will still be stored but its value is never
537 /// exposed.
538 #[inline]
new(value: T, is_some: Choice) -> CtOption<T>539 pub fn new(value: T, is_some: Choice) -> CtOption<T> {
540 CtOption {
541 value: value,
542 is_some: is_some,
543 }
544 }
545
546 /// This returns the underlying value but panics if it
547 /// is not `Some`.
548 #[inline]
unwrap(self) -> T549 pub fn unwrap(self) -> T {
550 assert_eq!(self.is_some.unwrap_u8(), 1);
551
552 self.value
553 }
554
555 /// This returns the underlying value if it is `Some`
556 /// or the provided value otherwise.
557 #[inline]
unwrap_or(self, def: T) -> T where T: ConditionallySelectable,558 pub fn unwrap_or(self, def: T) -> T
559 where
560 T: ConditionallySelectable,
561 {
562 T::conditional_select(&def, &self.value, self.is_some)
563 }
564
565 /// This returns the underlying value if it is `Some`
566 /// or the value produced by the provided closure otherwise.
567 #[inline]
unwrap_or_else<F>(self, f: F) -> T where T: ConditionallySelectable, F: FnOnce() -> T,568 pub fn unwrap_or_else<F>(self, f: F) -> T
569 where
570 T: ConditionallySelectable,
571 F: FnOnce() -> T,
572 {
573 T::conditional_select(&f(), &self.value, self.is_some)
574 }
575
576 /// Returns a true `Choice` if this value is `Some`.
577 #[inline]
is_some(&self) -> Choice578 pub fn is_some(&self) -> Choice {
579 self.is_some
580 }
581
582 /// Returns a true `Choice` if this value is `None`.
583 #[inline]
is_none(&self) -> Choice584 pub fn is_none(&self) -> Choice {
585 !self.is_some
586 }
587
588 /// Returns a `None` value if the option is `None`, otherwise
589 /// returns a `CtOption` enclosing the value of the provided closure.
590 /// The closure is given the enclosed value or, if the option is
591 /// `None`, it is provided a dummy value computed using
592 /// `Default::default()`.
593 ///
594 /// This operates in constant time, because the provided closure
595 /// is always called.
596 #[inline]
map<U, F>(self, f: F) -> CtOption<U> where T: Default + ConditionallySelectable, F: FnOnce(T) -> U,597 pub fn map<U, F>(self, f: F) -> CtOption<U>
598 where
599 T: Default + ConditionallySelectable,
600 F: FnOnce(T) -> U,
601 {
602 CtOption::new(
603 f(T::conditional_select(
604 &T::default(),
605 &self.value,
606 self.is_some,
607 )),
608 self.is_some,
609 )
610 }
611
612 /// Returns a `None` value if the option is `None`, otherwise
613 /// returns the result of the provided closure. The closure is
614 /// given the enclosed value or, if the option is `None`, it
615 /// is provided a dummy value computed using `Default::default()`.
616 ///
617 /// This operates in constant time, because the provided closure
618 /// is always called.
619 #[inline]
and_then<U, F>(self, f: F) -> CtOption<U> where T: Default + ConditionallySelectable, F: FnOnce(T) -> CtOption<U>,620 pub fn and_then<U, F>(self, f: F) -> CtOption<U>
621 where
622 T: Default + ConditionallySelectable,
623 F: FnOnce(T) -> CtOption<U>,
624 {
625 let mut tmp = f(T::conditional_select(
626 &T::default(),
627 &self.value,
628 self.is_some,
629 ));
630 tmp.is_some &= self.is_some;
631
632 tmp
633 }
634
635 /// Returns `self` if it contains a value, and otherwise returns the result of
636 /// calling `f`. The provided function `f` is always called.
637 #[inline]
or_else<F>(self, f: F) -> CtOption<T> where T: ConditionallySelectable, F: FnOnce() -> CtOption<T>,638 pub fn or_else<F>(self, f: F) -> CtOption<T>
639 where
640 T: ConditionallySelectable,
641 F: FnOnce() -> CtOption<T>,
642 {
643 let is_none = self.is_none();
644 let f = f();
645
646 Self::conditional_select(&self, &f, is_none)
647 }
648 }
649
650 impl<T: ConditionallySelectable> ConditionallySelectable for CtOption<T> {
conditional_select(a: &Self, b: &Self, choice: Choice) -> Self651 fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
652 CtOption::new(
653 T::conditional_select(&a.value, &b.value, choice),
654 Choice::conditional_select(&a.is_some, &b.is_some, choice),
655 )
656 }
657 }
658
659 impl<T: ConstantTimeEq> ConstantTimeEq for CtOption<T> {
660 /// Two `CtOption<T>`s are equal if they are both `Some` and
661 /// their values are equal, or both `None`.
662 #[inline]
ct_eq(&self, rhs: &CtOption<T>) -> Choice663 fn ct_eq(&self, rhs: &CtOption<T>) -> Choice {
664 let a = self.is_some();
665 let b = rhs.is_some();
666
667 (a & b & self.value.ct_eq(&rhs.value)) | (!a & !b)
668 }
669 }
670
671 /// A type which can be compared in some manner and be determined to be greater
672 /// than another of the same type.
673 pub trait ConstantTimeGreater {
674 /// Determine whether `self > other`.
675 ///
676 /// The bitwise-NOT of the return value of this function should be usable to
677 /// determine if `self <= other`.
678 ///
679 /// This function should execute in constant time.
680 ///
681 /// # Returns
682 ///
683 /// A `Choice` with a set bit if `self > other`, and with no set bits
684 /// otherwise.
685 ///
686 /// # Example
687 ///
688 /// ```
689 /// # extern crate subtle;
690 /// use subtle::ConstantTimeGreater;
691 ///
692 /// let x: u8 = 13;
693 /// let y: u8 = 42;
694 ///
695 /// let x_gt_y = x.ct_gt(&y);
696 ///
697 /// assert_eq!(x_gt_y.unwrap_u8(), 0);
698 ///
699 /// let y_gt_x = y.ct_gt(&x);
700 ///
701 /// assert_eq!(y_gt_x.unwrap_u8(), 1);
702 ///
703 /// let x_gt_x = x.ct_gt(&x);
704 ///
705 /// assert_eq!(x_gt_x.unwrap_u8(), 0);
706 /// ```
ct_gt(&self, other: &Self) -> Choice707 fn ct_gt(&self, other: &Self) -> Choice;
708 }
709
710 macro_rules! generate_unsigned_integer_greater {
711 ($t_u: ty, $bit_width: expr) => {
712 impl ConstantTimeGreater for $t_u {
713 /// Returns Choice::from(1) iff x > y, and Choice::from(0) iff x <= y.
714 ///
715 /// # Note
716 ///
717 /// This algoritm would also work for signed integers if we first
718 /// flip the top bit, e.g. `let x: u8 = x ^ 0x80`, etc.
719 #[inline]
720 fn ct_gt(&self, other: &$t_u) -> Choice {
721 let gtb = self & !other; // All the bits in self that are greater than their corresponding bits in other.
722 let mut ltb = !self & other; // All the bits in self that are less than their corresponding bits in other.
723 let mut pow = 1;
724
725 // Less-than operator is okay here because it's dependent on the bit-width.
726 while pow < $bit_width {
727 ltb |= ltb >> pow; // Bit-smear the highest set bit to the right.
728 pow += pow;
729 }
730 let mut bit = gtb & !ltb; // Select the highest set bit.
731 let mut pow = 1;
732
733 while pow < $bit_width {
734 bit |= bit >> pow; // Shift it to the right until we end up with either 0 or 1.
735 pow += pow;
736 }
737 // XXX We should possibly do the above flattening to 0 or 1 in the
738 // Choice constructor rather than making it a debug error?
739 Choice::from((bit & 1) as u8)
740 }
741 }
742 }
743 }
744
745 generate_unsigned_integer_greater!(u8, 8);
746 generate_unsigned_integer_greater!(u16, 16);
747 generate_unsigned_integer_greater!(u32, 32);
748 generate_unsigned_integer_greater!(u64, 64);
749 #[cfg(feature = "i128")]
750 generate_unsigned_integer_greater!(u128, 128);
751
752 /// A type which can be compared in some manner and be determined to be less
753 /// than another of the same type.
754 pub trait ConstantTimeLess: ConstantTimeEq + ConstantTimeGreater {
755 /// Determine whether `self < other`.
756 ///
757 /// The bitwise-NOT of the return value of this function should be usable to
758 /// determine if `self >= other`.
759 ///
760 /// A default implementation is provided and implemented for the unsigned
761 /// integer types.
762 ///
763 /// This function should execute in constant time.
764 ///
765 /// # Returns
766 ///
767 /// A `Choice` with a set bit if `self < other`, and with no set bits
768 /// otherwise.
769 ///
770 /// # Example
771 ///
772 /// ```
773 /// # extern crate subtle;
774 /// use subtle::ConstantTimeLess;
775 ///
776 /// let x: u8 = 13;
777 /// let y: u8 = 42;
778 ///
779 /// let x_lt_y = x.ct_lt(&y);
780 ///
781 /// assert_eq!(x_lt_y.unwrap_u8(), 1);
782 ///
783 /// let y_lt_x = y.ct_lt(&x);
784 ///
785 /// assert_eq!(y_lt_x.unwrap_u8(), 0);
786 ///
787 /// let x_lt_x = x.ct_lt(&x);
788 ///
789 /// assert_eq!(x_lt_x.unwrap_u8(), 0);
790 /// ```
791 #[inline]
ct_lt(&self, other: &Self) -> Choice792 fn ct_lt(&self, other: &Self) -> Choice {
793 !self.ct_gt(other) & !self.ct_eq(other)
794 }
795 }
796
797 impl ConstantTimeLess for u8 {}
798 impl ConstantTimeLess for u16 {}
799 impl ConstantTimeLess for u32 {}
800 impl ConstantTimeLess for u64 {}
801 #[cfg(feature = "i128")]
802 impl ConstantTimeLess for u128 {}
803