consistenttime/
lib.rs

1//Copyright 2016 William Cody Laeder
2//
3//Licensed under the Apache License, Version 2.0 (the "License");
4//you may not use this file except in compliance with the License.
5//you may obtain a copy of the License at
6//
7//  http://www.apache.org/licenses/LICENSE-2.0
8//
9//Unless required by applicable law or agreed to in writing, software
10//distrubuted under the License is distrubuted on as "AS IS" BASIS,
11//WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12//See the License for the specific language governing permissions and
13//limitations under the License.
14
15
16//!Consistent Time
17//!
18//!The goal of this crate is to offer constant time functions which most
19//!cryptographic computing protocols require to prevent side channel 
20//!timing attacks. 
21//!
22//!These algorithms are not implemented to be efficient. But to take the
23//!same number of processor cycles if their outcome/path is true, or false.
24//!The reference used for this crate is [Go-Lang's
25//!crypto/subtile](https://golang.org/src/crypto/subtle/constant_time.go)
26//!Which implements a handful of constant time algorithms.
27//!
28//!I took the liberity of generalizing them out to all unsigned sizes
29//!supported by Rust-Lang. Everything inside of this crate is defined
30//!as a macro. This makes writing the extremely repetive code for all
31//!types a lot easier.
32//!
33//!There is internal unsafe code to handle converting `bool` to `u8`
34//!and vice versa. The machine instructions generated for these
35//!operations involve no branches or comparison operators,
36//!see the notes in the source code.
37//!
38//!As of the most recent commit there has been an _extreme_ divergence
39//!from the Go-Lang source. LLVM does MUCH heavier optimizations then 
40//!Go-ASM does and some _combat_ was necessary. As of
41//!
42//!`consistenttime = "0.2"`
43//!
44//!I am reasonably confident it provides the advertised guarantees.
45
46
47#![no_std]
48use core::mem::transmute as trans;
49
50const MAX_U8: u8 = ::core::u8::MAX;
51const MAX_U16: u16 = ::core::u16::MAX;
52const MAX_U32: u32 = ::core::u32::MAX;
53const MAX_U64: u64 = ::core::u64::MAX;
54const MAX_USIZE: usize = ::core::usize::MAX;
55
56
57
58/*
59 * Rust booleans are effectively u8's with typing sugar.
60 * True = 0x01
61 * False = 0x00
62 *
63 * One can recover the true/false value via unsafe function
64 *
65 * fn to_val<X>(b: bool) -> X {
66 *      let val: u8 = unsafe{ ::core::mem::transmute(b) };
67 *      val as X
68 * }
69 *
70 * For the type u64 (and using the sugar [#inline(never)]
71 * this will compile down to:
72 *
73 *    mov rax dil
74 *    ret
75 *
76 * One can likely from that example determine how _other_
77 * integer formats are dervived.
78 *
79 * The test below asserts this behavior.
80 *
81 * :.:.:
82 *
83 * When converting from ~some~ uint to a bool the reverse
84 * is sligtly true. Consider the equality operation
85 *
86 *    let mut z: u16 = MAX ^ (x^y);
87 *    z >> 8;
88 *    z >> 4;
89 *    z >> 2;
90 *    z >> 1;
91 *    let val = z as u8;
92 *    unsafe{ ::core::mem::transmute(val) }; //returns bool
93 *
94 * The ASM generated for the last two operations
95 *
96 *    let val = z as u8;
97 *    unsafe{ ::core::mem::transmute(val)};
98 *
99 * It is simply
100 *
101 *    andl $1, %eax
102 *    retq
103 *
104 * The typing is gone at compile time.
105 */
106#[test]
107fn test_bool_representation() {
108    let t: bool = true;
109    let f: bool = false;
110    let t_val: u8 = unsafe{ ::core::mem::transmute(t) };
111    let f_val: u8 = unsafe{ ::core::mem::transmute(f) };
112    assert_eq!( t_val, 0x01u8);
113    assert_eq!( f_val, 0x00u8);
114}
115
116/*
117 * The purpose of the below macro is two fold. 
118 *  1. Define the function to do constant unsigned integer comparisons
119 *  2. Define a *fairly* comphensive test to validate that function.
120 *
121 */
122macro_rules! ct_eq_gen {
123    ($name: ident, $code: ty, $max: expr, $($shr: expr),*
124        ;; $test_name: ident, $test_v0: expr, $test_v1: expr) => {
125        ///Tests if two values are equal in constant time.
126        ///
127        ///Completely avoids branching.
128        #[no_mangle]
129        #[inline(never)]
130        pub extern "C" fn $name( x: $code, y: $code) -> bool {
131            let mut z: $code = $max ^ (x^y);
132            $(
133                z &= z.wrapping_shr($shr);
134            )*
135            /* 
136             * Convert to a boolean
137             * This is 99% syntax sugar
138             * z will get moved eax about 5 instructions before this
139             * The only operation done here is
140             *
141             *    andl $1, %eax
142             *
143             *  Which just asserts the structure of a boolean
144             *  remain 0x01 or 0x00.
145             */
146            let val = z as u8;
147            unsafe{trans(val)}
148        }
149        #[test]
150        fn $test_name() {
151            let x: $code = $test_v0;
152            let y: $code = $test_v1;
153            assert_eq!( $name($max,$max), true);
154            assert_eq!( $name(x,x), true);
155            assert_eq!( $name(y,y), true);
156            assert_eq!( $name(0,0), true);
157            assert_eq!( $name(1,1), true);
158            assert_eq!( $name($max,0), false);
159            assert_eq!( $name($max,1), false);
160            assert_eq!( $name($max,x), false);
161            assert_eq!( $name($max,y), false);
162            assert_eq!( $name(y,1), false);
163            assert_eq!( $name(x,1), false);
164            assert_eq!( $name(y,0), false);
165            assert_eq!( $name(x,0), false);
166            assert_eq!( $name(x,y), false);
167            $(
168                assert_eq!( $name($shr,$shr), true);
169                assert_eq!( $name($shr,0), false);
170                assert_eq!( $name($shr,$max), false);
171            )*
172        }
173    }
174}
175ct_eq_gen!(ct_u8_eq,u8,MAX_U8,4,2,1;;
176    test_ct_u8_eq, 155, 15);
177ct_eq_gen!(ct_u16_eq,u16,MAX_U16,8,4,2,1;;
178    test_ct_u16_eq, 32000, 5);
179ct_eq_gen!(ct_u32_eq,u32,MAX_U32,16,8,4,2,1;;
180    test_ct_u32_eq, 2000000, 15);
181ct_eq_gen!(ct_u64_eq,u64,MAX_U64,32,16,8,4,2,1;;
182    test_ct_u64_eq, 25893654215879, 2);
183#[cfg(target_pointer_width = "32")]
184ct_eq_gen!(ct_usize_eq,usize,MAX_USIZE,16,8,4,2,1;;
185    test_ct_u32_eq, 2082600, 15);
186#[cfg(target_pointer_width = "64")]
187ct_eq_gen!(ct_usize_eq,usize,MAX_USIZE,32,16,8,4,2,1;;
188    test_ct_usize_eq, 859632175648921456, 5);
189
190macro_rules! ct_eq_slice_gen {
191    ($name:ident,$eq:ident,$code: ty;;$test_name:ident,$max: expr) => {
192        ///Check the equality of slices.
193        ///
194        ///This will transverse the entire slice reguardless of if a
195        ///conflict is found early or not. This way an external hacker
196        ///can not guess the contents of a buffer byte by byte and 
197        ///carefully measure the timing responses.
198        #[no_mangle]
199        pub extern "C" fn $name( x: &[$code], y: &[$code]) -> bool {
200            let x_len = x.len();
201            let y_len = y.len();
202            if x_len != y_len {
203               return false;
204            }
205            let mut flag: $code = 0;
206            for i in 0..x_len {
207                flag |= x[i] ^ y[i];
208            }
209            $eq(flag,0)
210        }
211        #[test]
212        fn $test_name() {
213            let x: [$code;10] = [0,0,0,0,0,0,0,0,0,0];
214            let y: [$code;10] = [$max,$max,$max,$max,$max,$max,$max,$max,$max,$max];
215            let z: [$code;10] = [1,1,1,1,1,1,1,1,1,1];
216            assert_eq!( $name( &x, &x), true);
217            assert_eq!( $name( &y, &y), true);
218            assert_eq!( $name( &z, &z), true);
219            assert_eq!( $name( &x, &y), false);
220            assert_eq!( $name( &x, &y), false);
221            assert_eq!( $name( &y, &z), false);
222        }
223    }
224}
225ct_eq_slice_gen!(ct_u8_slice_eq,ct_u8_eq,u8;;
226    test_ct_u8_slice_eq, MAX_U8);
227ct_eq_slice_gen!(ct_u16_slice_eq,ct_u16_eq,u16;;
228    test_ct_u16_slice_eq, MAX_U16);
229ct_eq_slice_gen!(ct_u32_slice_eq,ct_u32_eq,u32;;
230    test_ct_u32_slice_eq, MAX_U32);
231ct_eq_slice_gen!(ct_u64_slice_eq,ct_u64_eq,u64;;
232    test_ct_u64_slice_eq, MAX_U64);
233ct_eq_slice_gen!(ct_usize_slice_eq,ct_usize_eq,usize;;
234    test_ct_usize_slice_eq, MAX_USIZE);
235
236
237macro_rules! ct_select_gen {
238    ($name:ident,$max:expr,$code:ty;;$test_name:ident,$v0:expr,$v1:expr) => {
239        ///Optional swapping.
240        ///
241        ///Allow to set a varible optionally at the same speed without
242        ///branching, or changing speed.
243        ///
244        ///Returns X if flag == True.
245        ///
246        ///Returns Y if flag == False.
247        ///
248        ///At compile time this becomes a CMOV. This _is_ a brach.
249        ///The branch misprediction cost is ~20cycles. And if this
250        ///is incurred does not depend on the input, but the 
251        ///random state of our machine + quantum winds.
252        ///
253        ///This should provide a consistent guarantee of speed.
254        #[no_mangle]
255        #[inline(never)]
256        pub extern "C" fn $name(flag: bool, x: $code, y: $code) -> $code {
257            let val: u8 = unsafe{trans(flag)};
258            let flag = val as $code;
259            (($max ^ flag.wrapping_sub(1))&x)|(flag.wrapping_sub(1)&y)
260        }
261        #[test]
262        fn $test_name() {
263            assert_eq!( $name(true,$v0,$v1), $v0);
264            assert_eq!( $name(false,$v0,$v1), $v1);
265            assert_eq!( $name(true,$v1,$v0), $v1);
266            assert_eq!( $name(false,$v1,$v0), $v0);
267            assert_eq!( $name(true,$v0,$max), $v0);
268            assert_eq!( $name(false,$v0,$max), $max);
269            assert_eq!( $name(true,$max,$v0), $max);
270            assert_eq!( $name(false,$max,$v0), $v0);
271            assert_eq!( $name(true,$max,$v1), $max);
272            assert_eq!( $name(false,$max,$v1), $v1);
273            assert_eq!( $name(true,$v1,$max), $v1);
274            assert_eq!( $name(false,$v1,$max), $max);
275        }
276    }
277}
278
279ct_select_gen!(ct_select_u8,MAX_U8,u8;;
280    test_ct_select_u8,155,4);
281ct_select_gen!(ct_select_u16,MAX_U16,u16;;
282    test_ct_select_u16,30597,4);
283ct_select_gen!(ct_select_u32,MAX_U32,u32;;
284    test_ct_select_u32,0x0DD74AA2,4);
285ct_select_gen!(ct_select_u64,MAX_U64,u64;;
286    test_ct_select_u64,155,4);
287ct_select_gen!(ct_select_usize,MAX_USIZE,usize;;
288    test_ct_select_usize,155,4);
289
290macro_rules! ct_constant_copy_gen {
291    ($name:ident,$max:expr,$code:ty,$copy_symbol: ident
292    ;;$test_name:ident,$sl_eq:ident,$other_test:ident) => {
293        ///Optional buffer copying
294        ///
295        ///IF flag == True THEN X will be set to Y
296        ///
297        ///If flag == False THEN X is unchanged
298        ///
299        ///#Panic:
300        ///
301        ///This function will panic if X and Y are not equal length. 
302        #[no_mangle]
303        pub extern "C" fn $name(flag: bool, x: &mut [$code], y: &[$code]) {
304            let x_len = x.len();
305            let y_len = y.len();
306            if x_len != y_len {
307                panic!("Consistent Time: Attempted to copy between non-equal lens");
308            }
309            for i in 0..x_len {
310                let y_temp = y[i].clone();
311                let x_temp = x[i].clone();
312                x[i] = $copy_symbol(flag,y_temp,x_temp); 
313            }
314        }
315        #[test]
316        fn $test_name() {
317            let base: [$code;10] = [0,0,0,0,0,0,0,0,0,0];
318            let mut x: [$code;10] = [0,0,0,0,0,0,0,0,0,0];
319            let y: [$code;10] = [$max,$max,$max,$max,$max,$max,$max,$max,$max,$max];
320            $name(false,&mut x, &y);
321            assert_eq!( $sl_eq(&x,&base), true);
322            $name(true,&mut x, &y);
323            assert_eq!( $sl_eq(&x,&base), false);
324            assert_eq!( $sl_eq(&x,&y), true);
325        }
326        #[test]
327        #[should_panic]
328        fn $other_test() {
329            let base: [$code;10] = [0,0,0,0,0,0,0,0,0,0];
330            let mut x: [$code;9] = [0,0,0,0,0,0,0,0,0];
331            //trigger panic
332            //even on false evaluation
333            //value of flag is irrelevant
334            $name(false,&mut x,&base);
335        }
336    }
337}
338ct_constant_copy_gen!(ct_copy_u8,MAX_U8,u8,ct_select_u8;;
339    test_ct_copy_u8,ct_u8_slice_eq,test_ct_copy_u8_panic);
340ct_constant_copy_gen!(ct_copy_u16,MAX_U16,u16,ct_select_u16;;
341    test_ct_copy_u16,ct_u16_slice_eq,test_ct_copy_u16_panic);
342ct_constant_copy_gen!(ct_copy_u32,MAX_U32,u32,ct_select_u32;;
343    test_ct_copy_u32,ct_u32_slice_eq,test_ct_copy_u32_panic);
344ct_constant_copy_gen!(ct_copy_u64,MAX_U64,u64,ct_select_u64;;
345    test_ct_copy_u64,ct_u64_slice_eq,test_ct_copy_u64_panic);
346ct_constant_copy_gen!(ct_copy_usize,MAX_USIZE,usize,ct_select_usize;;
347    test_ct_copy_usize,ct_usize_slice_eq,test_ct_copy_usize_panic);
consistenttime/lib.rs

consistenttime/
lib.rs
