di_ops.c 8.5 KB

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