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