di_ops.c 4.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133
  1. /* Copyright (c) 2011-2012, 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 "di_ops.h"
  9. /**
  10. * Timing-safe version of memcmp. As memcmp, compare the <b>sz</b> bytes at
  11. * <b>a</b> with the <b>sz</b> bytes at <b>b</b>, and return less than 0 if
  12. * the bytes at <b>a</b> lexically precede those at <b>b</b>, 0 if the byte
  13. * ranges are equal, and greater than zero if the bytes at <b>a</b> lexically
  14. * follow those at <b>b</b>.
  15. *
  16. * This implementation differs from memcmp in that its timing behavior is not
  17. * data-dependent: it should return in the same amount of time regardless of
  18. * the contents of <b>a</b> and <b>b</b>.
  19. */
  20. int
  21. tor_memcmp(const void *a, const void *b, size_t len)
  22. {
  23. const uint8_t *x = a;
  24. const uint8_t *y = b;
  25. size_t i = len;
  26. int retval = 0;
  27. /* This loop goes from the end of the arrays to the start. At the
  28. * start of every iteration, before we decrement i, we have set
  29. * "retval" equal to the result of memcmp(a+i,b+i,len-i). During the
  30. * loop, we update retval by leaving it unchanged if x[i]==y[i] and
  31. * setting it to x[i]-y[i] if x[i]!= y[i].
  32. *
  33. * The following assumes we are on a system with two's-complement
  34. * arithmetic. We check for this at configure-time with the check
  35. * that sets USING_TWOS_COMPLEMENT. If we aren't two's complement, then
  36. * torint.h will stop compilation with an error.
  37. */
  38. while (i--) {
  39. int v1 = x[i];
  40. int v2 = y[i];
  41. int equal_p = v1 ^ v2;
  42. /* The following sets bits 8 and above of equal_p to 'equal_p ==
  43. * 0', and thus to v1 == v2. (To see this, note that if v1 ==
  44. * v2, then v1^v2 == equal_p == 0, so equal_p-1 == -1, which is the
  45. * same as ~0 on a two's-complement machine. Then note that if
  46. * v1 != v2, then 0 < v1 ^ v2 < 256, so 0 <= equal_p - 1 < 255.)
  47. */
  48. --equal_p;
  49. equal_p >>= 8;
  50. /* Thanks to (sign-preserving) arithmetic shift, equal_p is now
  51. * equal to -(v1 == v2), which is exactly what we need below.
  52. * (Since we're assuming two's-complement arithmetic, -1 is the
  53. * same as ~0 (all bits set).)
  54. *
  55. * (The result of an arithmetic shift on a negative value is
  56. * actually implementation-defined in standard C. So how do we
  57. * get away with assuming it? Easy. We check.) */
  58. #if ((-60 >> 8) != -1)
  59. #error "According to cpp, right-shift doesn't perform sign-extension."
  60. #endif
  61. #ifndef RSHIFT_DOES_SIGN_EXTEND
  62. #error "According to configure, right-shift doesn't perform sign-extension."
  63. #endif
  64. /* If v1 == v2, equal_p is ~0, so this will leave retval
  65. * unchanged; otherwise, equal_p is 0, so this will zero it. */
  66. retval &= equal_p;
  67. /* If v1 == v2, then this adds 0, and leaves retval unchanged.
  68. * Otherwise, we just zeroed retval, so this sets it to v1 - v2. */
  69. retval += (v1 - v2);
  70. /* There. Now retval is equal to its previous value if v1 == v2, and
  71. * equal to v1 - v2 if v1 != v2. */
  72. }
  73. return retval;
  74. }
  75. /**
  76. * Timing-safe memory comparison. Return true if the <b>sz</b> bytes at
  77. * <b>a</b> are the same as the <b>sz</b> bytes at <b>b</b>, and 0 otherwise.
  78. *
  79. * This implementation differs from !memcmp(a,b,sz) in that its timing
  80. * behavior is not data-dependent: it should return in the same amount of time
  81. * regardless of the contents of <b>a</b> and <b>b</b>. It differs from
  82. * !tor_memcmp(a,b,sz) by being faster.
  83. */
  84. int
  85. tor_memeq(const void *a, const void *b, size_t sz)
  86. {
  87. /* Treat a and b as byte ranges. */
  88. const uint8_t *ba = a, *bb = b;
  89. uint32_t any_difference = 0;
  90. while (sz--) {
  91. /* Set byte_diff to all of those bits that are different in *ba and *bb,
  92. * and advance both ba and bb. */
  93. const uint8_t byte_diff = *ba++ ^ *bb++;
  94. /* Set bits in any_difference if they are set in byte_diff. */
  95. any_difference |= byte_diff;
  96. }
  97. /* Now any_difference is 0 if there are no bits different between
  98. * a and b, and is nonzero if there are bits different between a
  99. * and b. Now for paranoia's sake, let's convert it to 0 or 1.
  100. *
  101. * (If we say "!any_difference", the compiler might get smart enough
  102. * to optimize-out our data-independence stuff above.)
  103. *
  104. * To unpack:
  105. *
  106. * If any_difference == 0:
  107. * any_difference - 1 == ~0
  108. * (any_difference - 1) >> 8 == 0x00ffffff
  109. * 1 & ((any_difference - 1) >> 8) == 1
  110. *
  111. * If any_difference != 0:
  112. * 0 < any_difference < 256, so
  113. * 0 < any_difference - 1 < 255
  114. * (any_difference - 1) >> 8 == 0
  115. * 1 & ((any_difference - 1) >> 8) == 0
  116. */
  117. return 1 & ((any_difference - 1) >> 8);
  118. }