Line data Source code
1 : /* Copyright (c) 2011-2021, The Tor Project, Inc. */
2 : /* See LICENSE for licensing information */
3 :
4 : /**
5 : * \file di_ops.c
6 : * \brief Functions for data-independent operations.
7 : **/
8 :
9 : #include "orconfig.h"
10 : #include "lib/ctime/di_ops.h"
11 : #include "lib/err/torerr.h"
12 : #include "lib/malloc/malloc.h"
13 :
14 : #include <string.h>
15 :
16 : /**
17 : * Timing-safe version of memcmp. As memcmp, compare the <b>sz</b> bytes at
18 : * <b>a</b> with the <b>sz</b> bytes at <b>b</b>, and return less than 0 if
19 : * the bytes at <b>a</b> lexically precede those at <b>b</b>, 0 if the byte
20 : * ranges are equal, and greater than zero if the bytes at <b>a</b> lexically
21 : * follow those at <b>b</b>.
22 : *
23 : * This implementation differs from memcmp in that its timing behavior is not
24 : * data-dependent: it should return in the same amount of time regardless of
25 : * the contents of <b>a</b> and <b>b</b>.
26 : *
27 : * Note that if all you care about is equality, this implementation is
28 : * overkill: it would be better to use tor_memeq() or tor_memneq().
29 : */
30 : int
31 408309 : tor_memcmp(const void *a, const void *b, size_t len)
32 : {
33 : #ifdef HAVE_TIMINGSAFE_MEMCMP
34 : return timingsafe_memcmp(a, b, len);
35 : #else
36 408309 : const uint8_t *x = a;
37 408309 : const uint8_t *y = b;
38 408309 : size_t i = len;
39 408309 : int retval = 0;
40 :
41 : /* This loop goes from the end of the arrays to the start. At the
42 : * start of every iteration, before we decrement i, we have set
43 : * "retval" equal to the result of memcmp(a+i,b+i,len-i). During the
44 : * loop, we update retval by leaving it unchanged if x[i]==y[i] and
45 : * setting it to x[i]-y[i] if x[i]!= y[i].
46 : *
47 : * The following assumes we are on a system with two's-complement
48 : * arithmetic. We check for this at configure-time with the check
49 : * that sets USING_TWOS_COMPLEMENT. If we aren't two's complement, then
50 : * torint.h will stop compilation with an error.
51 : */
52 6527363 : while (i--) {
53 6119054 : int v1 = x[i];
54 6119054 : int v2 = y[i];
55 6119054 : int equal_p = v1 ^ v2;
56 :
57 : /* The following sets bits 8 and above of equal_p to 'equal_p ==
58 : * 0', and thus to v1 == v2. (To see this, note that if v1 ==
59 : * v2, then v1^v2 == equal_p == 0, so equal_p-1 == -1, which is the
60 : * same as ~0 on a two's-complement machine. Then note that if
61 : * v1 != v2, then 0 < v1 ^ v2 < 256, so 0 <= equal_p - 1 < 255.)
62 : */
63 6119054 : --equal_p;
64 :
65 6119054 : equal_p >>= 8;
66 : /* Thanks to (sign-preserving) arithmetic shift, equal_p is now
67 : * equal to -(v1 == v2), which is exactly what we need below.
68 : * (Since we're assuming two's-complement arithmetic, -1 is the
69 : * same as ~0 (all bits set).)
70 : *
71 : * (The result of an arithmetic shift on a negative value is
72 : * actually implementation-defined in standard C. So how do we
73 : * get away with assuming it? Easy. We check.) */
74 : #if ((-60 >> 8) != -1)
75 : #error "cpp says right-shift doesn't perform sign-extension."
76 : #endif
77 : #ifndef RSHIFT_DOES_SIGN_EXTEND
78 : #error "configure says right-shift doesn't perform sign-extension."
79 : #endif
80 :
81 : /* If v1 == v2, equal_p is ~0, so this will leave retval
82 : * unchanged; otherwise, equal_p is 0, so this will zero it. */
83 6119054 : retval &= equal_p;
84 :
85 : /* If v1 == v2, then this adds 0, and leaves retval unchanged.
86 : * Otherwise, we just zeroed retval, so this sets it to v1 - v2. */
87 6119054 : retval += (v1 - v2);
88 :
89 : /* There. Now retval is equal to its previous value if v1 == v2, and
90 : * equal to v1 - v2 if v1 != v2. */
91 : }
92 :
93 408309 : return retval;
94 : #endif /* defined(HAVE_TIMINGSAFE_MEMCMP) */
95 : }
96 :
97 : /**
98 : * Timing-safe memory comparison. Return true if the <b>sz</b> bytes at
99 : * <b>a</b> are the same as the <b>sz</b> bytes at <b>b</b>, and 0 otherwise.
100 : *
101 : * This implementation differs from !memcmp(a,b,sz) in that its timing
102 : * behavior is not data-dependent: it should return in the same amount of time
103 : * regardless of the contents of <b>a</b> and <b>b</b>. It differs from
104 : * !tor_memcmp(a,b,sz) by being faster.
105 : */
106 : int
107 178028 : tor_memeq(const void *a, const void *b, size_t sz)
108 : {
109 : /* Treat a and b as byte ranges. */
110 178028 : const uint8_t *ba = a, *bb = b;
111 178028 : uint32_t any_difference = 0;
112 2902487 : while (sz--) {
113 : /* Set byte_diff to all of those bits that are different in *ba and *bb,
114 : * and advance both ba and bb. */
115 2724459 : const uint8_t byte_diff = *ba++ ^ *bb++;
116 :
117 : /* Set bits in any_difference if they are set in byte_diff. */
118 2724459 : any_difference |= byte_diff;
119 : }
120 :
121 : /* Now any_difference is 0 if there are no bits different between
122 : * a and b, and is nonzero if there are bits different between a
123 : * and b. Now for paranoia's sake, let's convert it to 0 or 1.
124 : *
125 : * (If we say "!any_difference", the compiler might get smart enough
126 : * to optimize-out our data-independence stuff above.)
127 : *
128 : * To unpack:
129 : *
130 : * If any_difference == 0:
131 : * any_difference - 1 == ~0
132 : * (any_difference - 1) >> 8 == 0x00ffffff
133 : * 1 & ((any_difference - 1) >> 8) == 1
134 : *
135 : * If any_difference != 0:
136 : * 0 < any_difference < 256, so
137 : * 0 <= any_difference - 1 < 255
138 : * (any_difference - 1) >> 8 == 0
139 : * 1 & ((any_difference - 1) >> 8) == 0
140 : */
141 :
142 : /*coverity[overflow]*/
143 178028 : return 1 & ((any_difference - 1) >> 8);
144 : }
145 :
146 : /* Implement di_digest256_map_t as a linked list of entries. */
147 : struct di_digest256_map_t {
148 : /** Pointer to the next entry in the list. */
149 : struct di_digest256_map_t *next;
150 : /** Key for this entry. */
151 : uint8_t key[32];
152 : /** Value for this entry. */
153 : void *val;
154 : };
155 :
156 : /** Release all storage held in <b>map</b>, calling free_fn on each value
157 : * as we go. */
158 : void
159 4 : dimap_free_(di_digest256_map_t *map, dimap_free_fn free_fn)
160 : {
161 11 : while (map) {
162 7 : di_digest256_map_t *victim = map;
163 7 : map = map->next;
164 7 : if (free_fn)
165 3 : free_fn(victim->val);
166 7 : tor_free(victim);
167 : }
168 4 : }
169 :
170 : /** Adjust the map at *<b>map</b>, adding an entry for <b>key</b> ->
171 : * <b>val</b>, where <b>key</b> is a DIGEST256_LEN-byte key.
172 : *
173 : * The caller MUST NOT add a key that already appears in the map.
174 : */
175 : void
176 7 : dimap_add_entry(di_digest256_map_t **map,
177 : const uint8_t *key, void *val)
178 : {
179 7 : di_digest256_map_t *new_ent;
180 : {
181 7 : void *old_val = dimap_search(*map, key, NULL);
182 7 : raw_assert(! old_val);
183 7 : raw_assert(val);
184 : }
185 7 : new_ent = tor_malloc_zero(sizeof(di_digest256_map_t));
186 7 : new_ent->next = *map;
187 7 : memcpy(new_ent->key, key, 32);
188 7 : new_ent->val = val;
189 7 : *map = new_ent;
190 7 : }
191 :
192 : /** Search the map at <b>map</b> for an entry whose key is <b>key</b> (a
193 : * DIGEST256_LEN-byte key) returning the corresponding value if we found one,
194 : * and returning <b>dflt_val</b> if the key wasn't found.
195 : *
196 : * This operation takes an amount of time dependent only on the length of
197 : * <b>map</b>, not on the position or presence of <b>key</b> within <b>map</b>.
198 : */
199 : void *
200 24 : dimap_search(const di_digest256_map_t *map, const uint8_t *key,
201 : void *dflt_val)
202 : {
203 24 : uintptr_t result = (uintptr_t)dflt_val;
204 :
205 61 : while (map) {
206 37 : uintptr_t r = (uintptr_t) tor_memeq(map->key, key, 32);
207 37 : r -= 1; /* Now r is (uintptr_t)-1 if memeq returned false, and
208 : * 0 if memeq returned true. */
209 :
210 37 : result &= r;
211 37 : result |= ((uintptr_t)(map->val)) & ~r;
212 :
213 37 : map = map->next;
214 : }
215 :
216 24 : return (void *)result;
217 : }
218 :
219 : /**
220 : * Return true iff the <b>sz</b> bytes at <b>mem</b> are all zero. Runs in
221 : * time independent of the contents of <b>mem</b>.
222 : */
223 : int
224 98121 : safe_mem_is_zero(const void *mem, size_t sz)
225 : {
226 98121 : uint32_t total = 0;
227 98121 : const uint8_t *ptr = mem;
228 :
229 2790562 : while (sz--) {
230 2692441 : total |= *ptr++;
231 : }
232 :
233 : /*coverity[overflow]*/
234 98121 : return 1 & ((total - 1) >> 8);
235 : }
236 :
237 : /** Time-invariant 64-bit greater-than; works on two integers in the range
238 : * (0,INT64_MAX). */
239 : #if SIZEOF_VOID_P == 8
240 : #define gt_i64_timei(a,b) ((a) > (b))
241 : #else
242 : static inline int
243 : gt_i64_timei(uint64_t a, uint64_t b)
244 : {
245 : int64_t diff = (int64_t) (b - a);
246 : int res = diff >> 63;
247 : return res & 1;
248 : }
249 : #endif /* SIZEOF_VOID_P == 8 */
250 :
251 : /**
252 : * Given an array of list of <b>n_entries</b> uint64_t values, whose sum is
253 : * <b>total</b>, find the first i such that the total of all elements 0...i is
254 : * greater than rand_val.
255 : *
256 : * Try to perform this operation in a constant-time way.
257 : */
258 : int
259 51956 : select_array_member_cumulative_timei(const uint64_t *entries, int n_entries,
260 : uint64_t total, uint64_t rand_val)
261 : {
262 51956 : int i, i_chosen=-1, n_chosen=0;
263 51956 : uint64_t total_so_far = 0;
264 :
265 782578 : for (i = 0; i < n_entries; ++i) {
266 730622 : total_so_far += entries[i];
267 730622 : if (gt_i64_timei(total_so_far, rand_val)) {
268 51956 : i_chosen = i;
269 51956 : n_chosen++;
270 : /* Set rand_val to INT64_MAX rather than stopping the loop. This way,
271 : * the time we spend in the loop does not leak which element we chose. */
272 51956 : rand_val = INT64_MAX;
273 : }
274 : }
275 51956 : raw_assert(total_so_far == total);
276 51956 : raw_assert(n_chosen == 1);
277 51956 : raw_assert(i_chosen >= 0);
278 51956 : raw_assert(i_chosen < n_entries);
279 :
280 51956 : return i_chosen;
281 : }
282 :
283 : /**
284 : * If <b>s</b> is true, then copy <b>n</b> bytes from <b>src</b> to
285 : * <b>dest</b>. Otherwise leave <b>dest</b> alone.
286 : *
287 : * This function behaves the same as
288 : *
289 : * if (s)
290 : * memcpy(dest, src, n);
291 : *
292 : * except that it tries to run in the same amount of time whether <b>s</b> is
293 : * true or not.
294 : **/
295 : void
296 126 : memcpy_if_true_timei(bool s, void *dest, const void *src, size_t n)
297 : {
298 : // If s is true, mask will be ~0. If s is false, mask will be 0.
299 126 : const char mask = (char) -(signed char)s;
300 :
301 126 : char *destp = dest;
302 126 : const char *srcp = src;
303 4290 : for (size_t i = 0; i < n; ++i) {
304 4164 : *destp = (*destp & ~mask) | (*srcp & mask);
305 4164 : ++destp;
306 4164 : ++srcp;
307 : }
308 126 : }
|
