1 // -*- mode: rust; -*-
2 //
3 // This file is part of subtle, part of the dalek cryptography project.
4 // Copyright (c) 2016-2018 isis lovecruft, Henry de Valence
5 // See LICENSE for licensing information.
6 //
7 // Authors:
8 // - isis agora lovecruft <isis@patternsinthevoid.net>
9 // - Henry de Valence <hdevalence@hdevalence.ca>
10
11 #![no_std]
12 #![cfg_attr(feature = "nightly", feature(asm))]
13 #![cfg_attr(feature = "nightly", feature(external_doc))]
14 #![cfg_attr(feature = "nightly", doc(include = "../README.md"))]
15 #![cfg_attr(feature = "nightly", deny(missing_docs))]
16 #![doc(html_logo_url = "https://doc.dalek.rs/assets/dalek-logo-clear.png")]
17
18 //! Note that docs will only build on nightly Rust until
19 //! [RFC 1990 stabilizes](https://github.com/rust-lang/rust/issues/44732).
20
21 #[cfg(feature = "std")]
22 #[macro_use]
23 extern crate std;
24
25 use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Neg, Not};
26
27 /// The `Choice` struct represents a choice for use in conditional
28 /// assignment.
29 ///
30 /// It is a wrapper around a `u8`, which should have the value either
31 /// `1` (true) or `0` (false).
32 ///
33 /// With the `nightly` feature enabled, the conversion from `u8` to
34 /// `Choice` passes the value through an optimization barrier, as a
35 /// best-effort attempt to prevent the compiler from inferring that the
36 /// `Choice` value is a boolean. This strategy is based on Tim
37 /// Maclean's [work on `rust-timing-shield`][rust-timing-shield],
38 /// which attempts to provide a more comprehensive approach for
39 /// preventing software side-channels in Rust code.
40 ///
41 /// The `Choice` struct implements operators for AND, OR, XOR, and
42 /// NOT, to allow combining `Choice` values.
43 /// These operations do not short-circuit.
44 ///
45 /// [rust-timing-shield]: https://www.chosenplaintext.ca/open-source/rust-timing-shield/security
46 #[derive(Copy, Clone, Debug)]
47 pub struct Choice(u8);
48
49 impl Choice {
50 /// Unwrap the `Choice` wrapper to reveal the underlying `u8`.
51 ///
52 /// # Note
53 ///
54 /// This function only exists as an escape hatch for the rare case
55 /// where it's not possible to use one of the `subtle`-provided
56 /// trait impls.
57 #[inline]
unwrap_u8(&self) -> u858 pub fn unwrap_u8(&self) -> u8 {
59 self.0
60 }
61 }
62
63 impl From<Choice> for bool {
64 /// Convert the `Choice` wrapper into a `bool`, depending on whether
65 /// the underlying `u8` was a `0` or a `1`.
66 ///
67 /// # Note
68 ///
69 /// This function exists to avoid having higher-level cryptographic protocol
70 /// implementations duplicating this pattern.
71 ///
72 /// The intended use case for this conversion is at the _end_ of a
73 /// higher-level primitive implementation: for example, in checking a keyed
74 /// MAC, where the verification should happen in constant-time (and thus use
75 /// a `Choice`) but it is safe to return a `bool` at the end of the
76 /// verification.
77 #[inline]
from(source: Choice) -> bool78 fn from(source: Choice) -> bool {
79 debug_assert!(source.0 == 0u8 || source.0 == 1u8);
80 source.0 != 0
81 }
82 }
83
84 impl BitAnd for Choice {
85 type Output = Choice;
86 #[inline]
bitand(self, rhs: Choice) -> Choice87 fn bitand(self, rhs: Choice) -> Choice {
88 (self.0 & rhs.0).into()
89 }
90 }
91
92 impl BitAndAssign for Choice {
93 #[inline]
bitand_assign(&mut self, rhs: Choice)94 fn bitand_assign(&mut self, rhs: Choice) {
95 *self = *self & rhs;
96 }
97 }
98
99 impl BitOr for Choice {
100 type Output = Choice;
101 #[inline]
bitor(self, rhs: Choice) -> Choice102 fn bitor(self, rhs: Choice) -> Choice {
103 (self.0 | rhs.0).into()
104 }
105 }
106
107 impl BitOrAssign for Choice {
108 #[inline]
bitor_assign(&mut self, rhs: Choice)109 fn bitor_assign(&mut self, rhs: Choice) {
110 *self = *self | rhs;
111 }
112 }
113
114 impl BitXor for Choice {
115 type Output = Choice;
116 #[inline]
bitxor(self, rhs: Choice) -> Choice117 fn bitxor(self, rhs: Choice) -> Choice {
118 (self.0 ^ rhs.0).into()
119 }
120 }
121
122 impl BitXorAssign for Choice {
123 #[inline]
bitxor_assign(&mut self, rhs: Choice)124 fn bitxor_assign(&mut self, rhs: Choice) {
125 *self = *self ^ rhs;
126 }
127 }
128
129 impl Not for Choice {
130 type Output = Choice;
131 #[inline]
not(self) -> Choice132 fn not(self) -> Choice {
133 (1u8 & (!self.0)).into()
134 }
135 }
136
137 /// This function is a best-effort attempt to prevent the compiler
138 /// from knowing anything about the value of the returned `u8`, other
139 /// than its type.
140 ///
141 /// Uses inline asm when available, otherwise it's a no-op.
142 #[cfg(all(
143 feature = "nightly",
144 not(any(target_arch = "asmjs", target_arch = "wasm32"))
145 ))]
black_box(input: u8) -> u8146 fn black_box(input: u8) -> u8 {
147 debug_assert!(input == 0u8 || input == 1u8);
148
149 // Pretend to access a register containing the input. We "volatile" here
150 // because some optimisers treat assembly templates without output operands
151 // as "volatile" while others do not.
152 unsafe { asm!("" :: "r"(&input) :: "volatile") }
153
154 input
155 }
156 #[cfg(any(
157 target_arch = "asmjs",
158 target_arch = "wasm32",
159 not(feature = "nightly")
160 ))]
161 #[inline(never)]
black_box(input: u8) -> u8162 fn black_box(input: u8) -> u8 {
163 debug_assert!(input == 0u8 || input == 1u8);
164 // We don't have access to inline assembly or test::black_box or ...
165 //
166 // Bailing out, hopefully the compiler doesn't use the fact that `input` is 0 or 1.
167 input
168 }
169
170 impl From<u8> for Choice {
171 #[inline]
from(input: u8) -> Choice172 fn from(input: u8) -> Choice {
173 // Our goal is to prevent the compiler from inferring that the value held inside the
174 // resulting `Choice` struct is really an `i1` instead of an `i8`.
175 Choice(black_box(input))
176 }
177 }
178
179 /// An `Eq`-like trait that produces a `Choice` instead of a `bool`.
180 ///
181 /// # Example
182 ///
183 /// ```
184 /// use subtle::ConstantTimeEq;
185 /// let x: u8 = 5;
186 /// let y: u8 = 13;
187 ///
188 /// assert_eq!(x.ct_eq(&y).unwrap_u8(), 0);
189 /// assert_eq!(x.ct_eq(&x).unwrap_u8(), 1);
190 /// ```
191 pub trait ConstantTimeEq {
192 /// Determine if two items are equal.
193 ///
194 /// The `ct_eq` function should execute in constant time.
195 ///
196 /// # Returns
197 ///
198 /// * `Choice(1u8)` if `self == other`;
199 /// * `Choice(0u8)` if `self != other`.
200 #[inline]
ct_eq(&self, other: &Self) -> Choice201 fn ct_eq(&self, other: &Self) -> Choice;
202 }
203
204 impl<T: ConstantTimeEq> ConstantTimeEq for [T] {
205 /// Check whether two slices of `ConstantTimeEq` types are equal.
206 ///
207 /// # Note
208 ///
209 /// This function short-circuits if the lengths of the input slices
210 /// are different. Otherwise, it should execute in time independent
211 /// of the slice contents.
212 ///
213 /// Since arrays coerce to slices, this function works with fixed-size arrays:
214 ///
215 /// ```
216 /// # use subtle::ConstantTimeEq;
217 /// #
218 /// let a: [u8; 8] = [0,1,2,3,4,5,6,7];
219 /// let b: [u8; 8] = [0,1,2,3,0,1,2,3];
220 ///
221 /// let a_eq_a = a.ct_eq(&a);
222 /// let a_eq_b = a.ct_eq(&b);
223 ///
224 /// assert_eq!(a_eq_a.unwrap_u8(), 1);
225 /// assert_eq!(a_eq_b.unwrap_u8(), 0);
226 /// ```
227 #[inline]
ct_eq(&self, _rhs: &[T]) -> Choice228 fn ct_eq(&self, _rhs: &[T]) -> Choice {
229 let len = self.len();
230
231 // Short-circuit on the *lengths* of the slices, not their
232 // contents.
233 if len != _rhs.len() {
234 return Choice::from(0);
235 }
236
237 // This loop shouldn't be shortcircuitable, since the compiler
238 // shouldn't be able to reason about the value of the `u8`
239 // unwrapped from the `ct_eq` result.
240 let mut x = 1u8;
241 for (ai, bi) in self.iter().zip(_rhs.iter()) {
242 x &= ai.ct_eq(bi).unwrap_u8();
243 }
244
245 x.into()
246 }
247 }
248
249 /// Given the bit-width `$bit_width` and the corresponding primitive
250 /// unsigned and signed types `$t_u` and `$t_i` respectively, generate
251 /// an `ConstantTimeEq` implementation.
252 macro_rules! generate_integer_equal {
253 ($t_u:ty, $t_i:ty, $bit_width:expr) => {
254 impl ConstantTimeEq for $t_u {
255 #[inline]
256 fn ct_eq(&self, other: &$t_u) -> Choice {
257 // First construct x such that self == other iff all bits of x are 1
258 let mut x: $t_u = !(self ^ other);
259
260 // Now compute the and of all bits of x.
261 //
262 // e.g. for a u8, do:
263 //
264 // x &= x >> 4;
265 // x &= x >> 2;
266 // x &= x >> 1;
267 //
268 let mut shift: usize = $bit_width / 2;
269 while shift >= 1 {
270 x &= x >> shift;
271 shift /= 2;
272 }
273
274 (x as u8).into()
275 }
276 }
277 impl ConstantTimeEq for $t_i {
278 #[inline]
279 fn ct_eq(&self, other: &$t_i) -> Choice {
280 // Bitcast to unsigned and call that implementation.
281 (*self as $t_u).ct_eq(&(*other as $t_u))
282 }
283 }
284 };
285 }
286
287 generate_integer_equal!(u8, i8, 8);
288 generate_integer_equal!(u16, i16, 16);
289 generate_integer_equal!(u32, i32, 32);
290 generate_integer_equal!(u64, i64, 64);
291 #[cfg(feature = "i128")]
292 generate_integer_equal!(u128, i128, 128);
293 generate_integer_equal!(usize, isize, ::core::mem::size_of::<usize>() * 8);
294
295 /// Select one of two inputs according to a `Choice` in constant time.
296 ///
297 /// # Examples
298 ///
299 /// ```
300 /// # use subtle;
301 /// use subtle::ConditionallySelectable;
302 /// use subtle::Choice;
303 /// let a: i32 = 5;
304 /// let b: i32 = 13;
305 ///
306 /// assert_eq!(i32::conditional_select(&a, &b, Choice::from(0)), a);
307 /// assert_eq!(i32::conditional_select(&a, &b, Choice::from(1)), b);
308 /// ```
309 pub trait ConditionallySelectable {
310 /// Select `a` or `b` according to `choice`.
311 ///
312 /// # Returns
313 ///
314 /// * `a` if `choice == Choice(0)`;
315 /// * `b` if `choice == Choice(1)`.
316 ///
317 /// This function should execute in constant time.
318 #[inline]
conditional_select(a: &Self, b: &Self, choice: Choice) -> Self319 fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self;
320 }
321
322 macro_rules! to_signed_int {
323 (u8) => {
324 i8
325 };
326 (u16) => {
327 i16
328 };
329 (u32) => {
330 i32
331 };
332 (u64) => {
333 i64
334 };
335 (u128) => {
336 i128
337 };
338 (i8) => {
339 i8
340 };
341 (i16) => {
342 i16
343 };
344 (i32) => {
345 i32
346 };
347 (i64) => {
348 i64
349 };
350 (i128) => {
351 i128
352 };
353 }
354
355 macro_rules! generate_integer_conditional_select {
356 ($($t:tt)*) => ($(
357 impl ConditionallySelectable for $t {
358 #[inline]
359 fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
360 // if choice = 0, mask = (-0) = 0000...0000
361 // if choice = 1, mask = (-1) = 1111...1111
362 let mask = -(choice.unwrap_u8() as to_signed_int!($t)) as $t;
363 a ^ ((mask) & (a ^ b))
364 }
365 }
366 )*)
367 }
368
369 generate_integer_conditional_select!( u8 i8);
370 generate_integer_conditional_select!( u16 i16);
371 generate_integer_conditional_select!( u32 i32);
372 generate_integer_conditional_select!( u64 i64);
373 #[cfg(feature = "i128")]
374 generate_integer_conditional_select!(u128 i128);
375
376 /// A type which can be conditionally negated in constant time.
377 ///
378 /// # Note
379 ///
380 /// A generic implementation of `ConditionallyNegatable` is provided for types
381 /// which are `ConditionallyNegatable + Neg`.
382 pub trait ConditionallyNegatable {
383 /// Negate `self` if `choice == Choice(1)`; otherwise, leave it
384 /// unchanged.
385 ///
386 /// This function should execute in constant time.
387 #[inline]
conditional_negate(&mut self, choice: Choice)388 fn conditional_negate(&mut self, choice: Choice);
389 }
390
391 impl<T> ConditionallyNegatable for T
392 where
393 T: ConditionallyAssignable,
394 for<'a> &'a T: Neg<Output = T>,
395 {
396 #[inline]
conditional_negate(&mut self, choice: Choice)397 fn conditional_negate(&mut self, choice: Choice) {
398 // Need to cast to eliminate mutability
399 let self_neg: T = -(self as &T);
400 self.conditional_assign(&self_neg, choice);
401 }
402 }
403
404 /// A type which can be conditionally assigned in constant time.
405 pub trait ConditionallyAssignable {
406 /// Conditionally assign `other` to `self`, according to `choice`.
407 ///
408 /// This function should execute in constant time.
409 ///
410 /// # Examples
411 ///
412 /// ```
413 /// # extern crate subtle;
414 /// use subtle::ConditionallyAssignable;
415 /// #
416 /// # fn main() {
417 /// let mut x: u8 = 13;
418 /// let y: u8 = 42;
419 ///
420 /// x.conditional_assign(&y, 0.into());
421 /// assert_eq!(x, 13);
422 /// x.conditional_assign(&y, 1.into());
423 /// assert_eq!(x, 42);
424 /// # }
425 /// ```
426 ///
427 #[inline]
conditional_assign(&mut self, other: &Self, choice: Choice)428 fn conditional_assign(&mut self, other: &Self, choice: Choice);
429 }
430
431 impl<T> ConditionallyAssignable for T
432 where
433 T: ConditionallySelectable,
434 {
435 #[inline]
conditional_assign(&mut self, other: &Self, choice: Choice)436 fn conditional_assign(&mut self, other: &Self, choice: Choice) {
437 *self = T::conditional_select(self, other, choice);
438 }
439 }
440
441 /// A type which is conditionally swappable in constant time.
442 pub trait ConditionallySwappable {
443 /// Conditionally swap `self` and `other` if `choice == 1`; otherwise,
444 /// reassign both unto themselves.
445 ///
446 /// # Note
447 ///
448 /// This trait is generically implemented for any type which implements
449 /// `ConditionallyAssignable + Copy`.
450 #[inline]
conditional_swap(&mut self, other: &mut Self, choice: Choice)451 fn conditional_swap(&mut self, other: &mut Self, choice: Choice);
452 }
453
454 impl<T> ConditionallySwappable for T
455 where
456 T: ConditionallyAssignable + Copy,
457 {
458 #[inline]
conditional_swap(&mut self, other: &mut T, choice: Choice)459 fn conditional_swap(&mut self, other: &mut T, choice: Choice) {
460 let temp: T = *self;
461 self.conditional_assign(&other, choice);
462 other.conditional_assign(&temp, choice);
463 }
464 }
465