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