1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
/// Identity function accepting a `u8` as input and outputting that same `u8` as
/// output, while blocking the compiler from applying optimizations across this node in the data
/// dependence graph.
///
/// This is an **internal utility** of rust-timing-shield that users of the framework will not
/// normally need to use.
///
/// # Background
///
/// rust-timing-shield has essentially two goals: (1) prevent the programmer from writing code that
/// they shouldn't, and (2) prevent the compiler from transforming a programmer's secure code
/// into vulnerable code. This function is a small primitive that assists in accomplishing the 2nd
/// goal.
///
/// An important rule of protecting code from timing attacks is to ensure that a program never
/// branches on a secret value. In rust-timing-shield terminology, we should never emit a
/// branch conditional on a `TpBool`. The Rust compiler uses many LLVM optimization passes that may
/// produce a conditional branch where none was written by the programmer, so we must remove the
/// compiler's ability to identify situations where a conditional branch could reasonably be
/// introduced. The most problematic optimizations identified so far output [an LLVM IR `select`
/// instruction](https://llvm.org/docs/LangRef.html#select-instruction).
///
/// Of course, it is legal for the compiler to emit `select` instructions in any situation as long
/// as the output and side effects of the code remain the same. For example, it could expand this
/// code:
///
/// ```
/// fn add(a: u8, b: u8) -> u8 {
/// a + b
/// }
/// ```
///
/// to:
///
/// ```
/// fn add(a: u8, b: u8) -> u8 {
/// if a == 5 && b == 5 {
/// return 10;
/// }
/// if a == 7 && b == 5 {
/// return 12;
/// }
/// a + b
/// }
/// ```
///
/// The current implementation of rust-timing-shield assumes that this is ridiculous and wouldn't
/// happen. In particular, an assumption is made that the compiler will only insert a `select` for
/// "values of boolean origin". For example, this branchless code:
///
/// ```
/// fn add_bool(number: u8, b: bool) -> u8 {
/// number + (b as u8)
/// }
/// ```
///
/// could reasonably, under this assumption, be rewritten with a branch:
///
/// ```
/// fn add_bool(number: u8, b: bool) -> u8 {
/// if b {
/// return number + 1;
/// }
///
/// number
/// }
/// ```
///
/// since `b as u8` is a "value of boolean origin". Based on the empirical tests of the Rust
/// compiler and a review of how LLVM optimization passes are implemented, this assumption appears
/// to be reasonable.
///
/// Now, with this assumption in place, rust-timing-shield only needs to ensure that all
/// timing-protected values either are not of boolean origin or hide their origin from the
/// compiler. This is accomplished in two steps:
///
/// 1. All timing-protected boolean values (`TpBool`) are stored as `u8` values and never as
/// `bool`, even in intermediate computations.
/// 2. `TpBool::protect(bool)` converts the `bool` to a `u8` and uses an optimization barrier (this
/// function) to hide the origin of the `u8`.
///
/// # Usage
///
/// `optimization_barrier_u8` is a low-cost (but not zero-cost) way to hide a value's origin from the compiler. If a
/// value passes through an optimization barrier, the compiler will be able to perform
/// optimizations on computations prior to the barrier and optimizations on computations after the
/// barrier, but will be unable to perform optimizations *across* the barrier.
///
/// It is important that the barrier interrupt the flow of a value from one part of the program to
/// the next. As an example of incorrect usage:
///
/// ```
/// # use timing_shield::barriers::optimization_barrier_u8;
/// #
/// fn add_bool(number: u8, secret_condition: bool) -> u8 {
/// let secret_condition_u8 = secret_condition as u8;
///
/// // WRONG: barrier does not interrupt data flow
/// optimization_barrier_u8(secret_condition_u8);
///
/// number + secret_condition_u8
/// }
/// ```
///
/// Here, the return value from `optimization_barrier_u8` is unused, so the optimization barrier
/// has no effect. An optimization barrier must be the single connection between two parts of the
/// program's data dependence graph:
///
/// ```
/// # use timing_shield::barriers::optimization_barrier_u8;
/// #
/// fn add_bool(number: u8, secret_condition: bool) -> u8 {
/// let secret_condition_u8 = secret_condition as u8;
///
/// // Override the previous definition to avoid accidentally using the pre-barrier value
/// let secret_condition_u8 = optimization_barrier_u8(secret_condition_u8);
///
/// number + secret_condition_u8
/// }
/// ```
///
/// In rust-timing-shield, optimization barriers are used to hide when a `u8` is of boolean origin.
/// The use of a barrier prevents the compiler from identifying that the `u8` value after the
/// barrier is the same value that was cast from a `bool` before the barrier. This suppresses the
/// many optimizations that would transform the timing-leak-proof branchless computations with `u8`
/// values that rust-timing-shield produces into branching computations that leak boolean values.
///
/// # Performance considerations
///
/// `optimization_barrier_u8` is currently implemented as an empty inline assembly block. The `u8`
/// input value is provided as an input/output register to the assembly block and then immediately
/// returned as is. Although the assembly block is a no-op, LLVM is forced to assume that the value
/// may have changed and can make no assumptions about what the output may be. The Rust Unstable
/// reference [describes the assembly block as a black
/// box](https://doc.rust-lang.org/unstable-book/library-features/asm.html):
///
/// > “The compiler cannot assume that the instructions in the asm are the ones that will
/// actually end up executed. This effectively means that the compiler must treat the `asm!` as a
/// black box and only take the interface specification into account, not the instructions
/// themselves.”
///
/// Since no actual assembler instructions are provided, it might seem that this function call
/// would have zero overhead after inlining. However, there are other considerations that may
/// affect performance:
///
/// - The barrier will (obviously) prevent matching on code patterns that span across the barrier.
/// This is intended.
/// - The barrier will force the compiler to schedule an actual register to hold the value
/// temporarily.
/// - The barrier will force the value into a single register, which may impair the compiler's
/// ability to perform optimizations such as auto-vectorization.
/// - Constant folding cannot proceed past a barrier.
///
/// For these reasons, optimization barriers are only used where necessary to minimize any
/// potential impact on performance, keeping rust-timing-shield zero-cost for as many applications
/// as possible.