Tor  0.4.7.0-alpha-dev
di_ops.c
Go to the documentation of this file.
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 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  const uint8_t *x = a;
37  const uint8_t *y = b;
38  size_t i = len;
39  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  while (i--) {
53  int v1 = x[i];
54  int v2 = y[i];
55  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  --equal_p;
64 
65  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  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  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  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 tor_memeq(const void *a, const void *b, size_t sz)
108 {
109  /* Treat a and b as byte ranges. */
110  const uint8_t *ba = a, *bb = b;
111  uint32_t any_difference = 0;
112  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  const uint8_t byte_diff = *ba++ ^ *bb++;
116 
117  /* Set bits in any_difference if they are set in byte_diff. */
118  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  return 1 & ((any_difference - 1) >> 8);
144 }
145 
146 /* Implement di_digest256_map_t as a linked list of entries. */
148  /** Pointer to the next entry in the list. */
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
160 {
161  while (map) {
162  di_digest256_map_t *victim = map;
163  map = map->next;
164  if (free_fn)
165  free_fn(victim->val);
166  tor_free(victim);
167  }
168 }
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
177  const uint8_t *key, void *val)
178 {
179  di_digest256_map_t *new_ent;
180  {
181  void *old_val = dimap_search(*map, key, NULL);
182  raw_assert(! old_val);
183  raw_assert(val);
184  }
185  new_ent = tor_malloc_zero(sizeof(di_digest256_map_t));
186  new_ent->next = *map;
187  memcpy(new_ent->key, key, 32);
188  new_ent->val = val;
189  *map = new_ent;
190 }
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 dimap_search(const di_digest256_map_t *map, const uint8_t *key,
201  void *dflt_val)
202 {
203  uintptr_t result = (uintptr_t)dflt_val;
204 
205  while (map) {
206  uintptr_t r = (uintptr_t) tor_memeq(map->key, key, 32);
207  r -= 1; /* Now r is (uintptr_t)-1 if memeq returned false, and
208  * 0 if memeq returned true. */
209 
210  result &= r;
211  result |= ((uintptr_t)(map->val)) & ~r;
212 
213  map = map->next;
214  }
215 
216  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 safe_mem_is_zero(const void *mem, size_t sz)
225 {
226  uint32_t total = 0;
227  const uint8_t *ptr = mem;
228 
229  while (sz--) {
230  total |= *ptr++;
231  }
232 
233  /*coverity[overflow]*/
234  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 select_array_member_cumulative_timei(const uint64_t *entries, int n_entries,
260  uint64_t total, uint64_t rand_val)
261 {
262  int i, i_chosen=-1, n_chosen=0;
263  uint64_t total_so_far = 0;
264 
265  for (i = 0; i < n_entries; ++i) {
266  total_so_far += entries[i];
267  if (gt_i64_timei(total_so_far, rand_val)) {
268  i_chosen = i;
269  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  rand_val = INT64_MAX;
273  }
274  }
275  raw_assert(total_so_far == total);
276  raw_assert(n_chosen == 1);
277  raw_assert(i_chosen >= 0);
278  raw_assert(i_chosen < n_entries);
279 
280  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 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  const char mask = (char) -(signed char)s;
300 
301  char *destp = dest;
302  const char *srcp = src;
303  for (size_t i = 0; i < n; ++i) {
304  *destp = (*destp & ~mask) | (*srcp & mask);
305  ++destp;
306  ++srcp;
307  }
308 }
void * dimap_search(const di_digest256_map_t *map, const uint8_t *key, void *dflt_val)
Definition: di_ops.c:200
void dimap_add_entry(di_digest256_map_t **map, const uint8_t *key, void *val)
Definition: di_ops.c:176
void memcpy_if_true_timei(bool s, void *dest, const void *src, size_t n)
Definition: di_ops.c:296
int tor_memeq(const void *a, const void *b, size_t sz)
Definition: di_ops.c:107
int tor_memcmp(const void *a, const void *b, size_t len)
Definition: di_ops.c:31
static int gt_i64_timei(uint64_t a, uint64_t b)
Definition: di_ops.c:243
int select_array_member_cumulative_timei(const uint64_t *entries, int n_entries, uint64_t total, uint64_t rand_val)
Definition: di_ops.c:259
int safe_mem_is_zero(const void *mem, size_t sz)
Definition: di_ops.c:224
void dimap_free_(di_digest256_map_t *map, dimap_free_fn free_fn)
Definition: di_ops.c:159
Headers for di_ops.c.
void(* dimap_free_fn)(void *)
Definition: di_ops.h:55
Headers for util_malloc.c.
#define tor_free(p)
Definition: malloc.h:52
uint8_t key[32]
Definition: di_ops.c:151
struct di_digest256_map_t * next
Definition: di_ops.c:149
Headers for torerr.c.