bitcoin_hashes/
cmp.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//! Useful comparison functions.
4
5/// Compare two slices for equality in fixed time. Panics if the slices are of non-equal length.
6///
7/// This works by XOR'ing each byte of the two inputs together and keeping an OR counter of the
8/// results.
9///
10/// Instead of doing fancy bit twiddling to try to outsmart the compiler and prevent early exits,
11/// which is not guaranteed to remain stable as compilers get ever smarter, we take the hit of
12/// writing each intermediate value to memory with a volatile write and then re-reading it with a
13/// volatile read. This should remain stable across compiler upgrades, but is much slower.
14///
15/// As of rust 1.31.0 disassembly looks completely within reason for this, see
16/// <https://godbolt.org/z/mMbGQv>.
17pub fn fixed_time_eq(a: &[u8], b: &[u8]) -> bool {
18    assert!(a.len() == b.len());
19    let count = a.len();
20    let lhs = &a[..count];
21    let rhs = &b[..count];
22
23    let mut r: u8 = 0;
24    for i in 0..count {
25        let mut rs = unsafe { core::ptr::read_volatile(&r) };
26        rs |= lhs[i] ^ rhs[i];
27        unsafe {
28            core::ptr::write_volatile(&mut r, rs);
29        }
30    }
31    {
32        let mut t = unsafe { core::ptr::read_volatile(&r) };
33        t |= t >> 4;
34        unsafe {
35            core::ptr::write_volatile(&mut r, t);
36        }
37    }
38    {
39        let mut t = unsafe { core::ptr::read_volatile(&r) };
40        t |= t >> 2;
41        unsafe {
42            core::ptr::write_volatile(&mut r, t);
43        }
44    }
45    {
46        let mut t = unsafe { core::ptr::read_volatile(&r) };
47        t |= t >> 1;
48        unsafe {
49            core::ptr::write_volatile(&mut r, t);
50        }
51    }
52    unsafe { (::core::ptr::read_volatile(&r) & 1) == 0 }
53}
54
55#[test]
56fn eq_test() {
57    assert!(fixed_time_eq(&[0b00000000], &[0b00000000]));
58    assert!(fixed_time_eq(&[0b00000001], &[0b00000001]));
59    assert!(fixed_time_eq(&[0b00000010], &[0b00000010]));
60    assert!(fixed_time_eq(&[0b00000100], &[0b00000100]));
61    assert!(fixed_time_eq(&[0b00001000], &[0b00001000]));
62    assert!(fixed_time_eq(&[0b00010000], &[0b00010000]));
63    assert!(fixed_time_eq(&[0b00100000], &[0b00100000]));
64    assert!(fixed_time_eq(&[0b01000000], &[0b01000000]));
65    assert!(fixed_time_eq(&[0b10000000], &[0b10000000]));
66    assert!(fixed_time_eq(&[0b11111111], &[0b11111111]));
67
68    assert!(!fixed_time_eq(&[0b00000001], &[0b00000000]));
69    assert!(!fixed_time_eq(&[0b00000001], &[0b11111111]));
70    assert!(!fixed_time_eq(&[0b00000010], &[0b00000000]));
71    assert!(!fixed_time_eq(&[0b00000010], &[0b11111111]));
72    assert!(!fixed_time_eq(&[0b00000100], &[0b00000000]));
73    assert!(!fixed_time_eq(&[0b00000100], &[0b11111111]));
74    assert!(!fixed_time_eq(&[0b00001000], &[0b00000000]));
75    assert!(!fixed_time_eq(&[0b00001000], &[0b11111111]));
76    assert!(!fixed_time_eq(&[0b00010000], &[0b00000000]));
77    assert!(!fixed_time_eq(&[0b00010000], &[0b11111111]));
78    assert!(!fixed_time_eq(&[0b00100000], &[0b00000000]));
79    assert!(!fixed_time_eq(&[0b00100000], &[0b11111111]));
80    assert!(!fixed_time_eq(&[0b01000000], &[0b00000000]));
81    assert!(!fixed_time_eq(&[0b01000000], &[0b11111111]));
82    assert!(!fixed_time_eq(&[0b10000000], &[0b00000000]));
83    assert!(!fixed_time_eq(&[0b10000000], &[0b11111111]));
84
85    assert!(fixed_time_eq(&[0b00000000, 0b00000000], &[0b00000000, 0b00000000]));
86    assert!(!fixed_time_eq(&[0b00000001, 0b00000000], &[0b00000000, 0b00000000]));
87    assert!(!fixed_time_eq(&[0b00000000, 0b00000001], &[0b00000000, 0b00000000]));
88    assert!(!fixed_time_eq(&[0b00000000, 0b00000000], &[0b00000001, 0b00000000]));
89    assert!(!fixed_time_eq(&[0b00000000, 0b00000000], &[0b00000001, 0b00000001]));
90}
91
92#[cfg(bench)]
93mod benches {
94    use test::Bencher;
95
96    use crate::cmp::fixed_time_eq;
97    use crate::{sha256, sha512, Hash};
98
99    #[bench]
100    fn bench_32b_constant_time_cmp_ne(bh: &mut Bencher) {
101        let hash_a = sha256::Hash::hash(&[0; 1]);
102        let hash_b = sha256::Hash::hash(&[1; 1]);
103        bh.iter(|| fixed_time_eq(&hash_a[..], &hash_b[..]))
104    }
105
106    #[bench]
107    fn bench_32b_slice_cmp_ne(bh: &mut Bencher) {
108        let hash_a = sha256::Hash::hash(&[0; 1]);
109        let hash_b = sha256::Hash::hash(&[1; 1]);
110        bh.iter(|| &hash_a[..] == &hash_b[..])
111    }
112
113    #[bench]
114    fn bench_32b_constant_time_cmp_eq(bh: &mut Bencher) {
115        let hash_a = sha256::Hash::hash(&[0; 1]);
116        let hash_b = sha256::Hash::hash(&[0; 1]);
117        bh.iter(|| fixed_time_eq(&hash_a[..], &hash_b[..]))
118    }
119
120    #[bench]
121    fn bench_32b_slice_cmp_eq(bh: &mut Bencher) {
122        let hash_a = sha256::Hash::hash(&[0; 1]);
123        let hash_b = sha256::Hash::hash(&[0; 1]);
124        bh.iter(|| &hash_a[..] == &hash_b[..])
125    }
126
127    #[bench]
128    fn bench_64b_constant_time_cmp_ne(bh: &mut Bencher) {
129        let hash_a = sha512::Hash::hash(&[0; 1]);
130        let hash_b = sha512::Hash::hash(&[1; 1]);
131        bh.iter(|| fixed_time_eq(&hash_a[..], &hash_b[..]))
132    }
133
134    #[bench]
135    fn bench_64b_slice_cmp_ne(bh: &mut Bencher) {
136        let hash_a = sha512::Hash::hash(&[0; 1]);
137        let hash_b = sha512::Hash::hash(&[1; 1]);
138        bh.iter(|| &hash_a[..] == &hash_b[..])
139    }
140
141    #[bench]
142    fn bench_64b_constant_time_cmp_eq(bh: &mut Bencher) {
143        let hash_a = sha512::Hash::hash(&[0; 1]);
144        let hash_b = sha512::Hash::hash(&[0; 1]);
145        bh.iter(|| fixed_time_eq(&hash_a[..], &hash_b[..]))
146    }
147
148    #[bench]
149    fn bench_64b_slice_cmp_eq(bh: &mut Bencher) {
150        let hash_a = sha512::Hash::hash(&[0; 1]);
151        let hash_b = sha512::Hash::hash(&[0; 1]);
152        bh.iter(|| &hash_a[..] == &hash_b[..])
153    }
154}
bitcoin_hashes/cmp.rs

bitcoin_hashes/
cmp.rs
