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