replaycache.c 5.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216
  1. /* Copyright (c) 2012-2017, The Tor Project, Inc. */
  2. /* See LICENSE for licensing information */
  3. /**
  4. * \file replaycache.c
  5. *
  6. * \brief Self-scrubbing replay cache for rendservice.c
  7. *
  8. * To prevent replay attacks, hidden services need to recognize INTRODUCE2
  9. * cells that they've already seen, and drop them. If they didn't, then
  10. * sending the same INTRODUCE2 cell over and over would force the hidden
  11. * service to make a huge number of circuits to the same rendezvous
  12. * point, aiding traffic analysis.
  13. *
  14. * (It's not that simple, actually. We only check for replays in the
  15. * RSA-encrypted portion of the handshake, since the rest of the handshake is
  16. * malleable.)
  17. *
  18. * This module is used from rendservice.c.
  19. */
  20. #define REPLAYCACHE_PRIVATE
  21. #include "or.h"
  22. #include "replaycache.h"
  23. /** Free the replaycache r and all of its entries.
  24. */
  25. void
  26. replaycache_free_(replaycache_t *r)
  27. {
  28. if (!r) {
  29. log_info(LD_BUG, "replaycache_free() called on NULL");
  30. return;
  31. }
  32. if (r->digests_seen) digest256map_free(r->digests_seen, tor_free_);
  33. tor_free(r);
  34. }
  35. /** Allocate a new, empty replay detection cache, where horizon is the time
  36. * for entries to age out and interval is the time after which the cache
  37. * should be scrubbed for old entries.
  38. */
  39. replaycache_t *
  40. replaycache_new(time_t horizon, time_t interval)
  41. {
  42. replaycache_t *r = NULL;
  43. if (horizon < 0) {
  44. log_info(LD_BUG, "replaycache_new() called with negative"
  45. " horizon parameter");
  46. goto err;
  47. }
  48. if (interval < 0) {
  49. log_info(LD_BUG, "replaycache_new() called with negative interval"
  50. " parameter");
  51. interval = 0;
  52. }
  53. r = tor_malloc(sizeof(*r));
  54. r->scrub_interval = interval;
  55. r->scrubbed = 0;
  56. r->horizon = horizon;
  57. r->digests_seen = digest256map_new();
  58. err:
  59. return r;
  60. }
  61. /** See documentation for replaycache_add_and_test()
  62. */
  63. STATIC int
  64. replaycache_add_and_test_internal(
  65. time_t present, replaycache_t *r, const void *data, size_t len,
  66. time_t *elapsed)
  67. {
  68. int rv = 0;
  69. uint8_t digest[DIGEST256_LEN];
  70. time_t *access_time;
  71. /* sanity check */
  72. if (present <= 0 || !r || !data || len == 0) {
  73. log_info(LD_BUG, "replaycache_add_and_test_internal() called with stupid"
  74. " parameters; please fix this.");
  75. goto done;
  76. }
  77. /* compute digest */
  78. crypto_digest256((char *)digest, (const char *)data, len, DIGEST_SHA256);
  79. /* check map */
  80. access_time = digest256map_get(r->digests_seen, digest);
  81. /* seen before? */
  82. if (access_time != NULL) {
  83. /*
  84. * If it's far enough in the past, no hit. If the horizon is zero, we
  85. * never expire.
  86. */
  87. if (*access_time >= present - r->horizon || r->horizon == 0) {
  88. /* replay cache hit, return 1 */
  89. rv = 1;
  90. /* If we want to output an elapsed time, do so */
  91. if (elapsed) {
  92. if (present >= *access_time) {
  93. *elapsed = present - *access_time;
  94. } else {
  95. /* We shouldn't really be seeing hits from the future, but... */
  96. *elapsed = 0;
  97. }
  98. }
  99. }
  100. /*
  101. * If it's ahead of the cached time, update
  102. */
  103. if (*access_time < present) {
  104. *access_time = present;
  105. }
  106. } else {
  107. /* No, so no hit and update the digest map with the current time */
  108. access_time = tor_malloc(sizeof(*access_time));
  109. *access_time = present;
  110. digest256map_set(r->digests_seen, digest, access_time);
  111. }
  112. /* now scrub the cache if it's time */
  113. replaycache_scrub_if_needed_internal(present, r);
  114. done:
  115. return rv;
  116. }
  117. /** See documentation for replaycache_scrub_if_needed()
  118. */
  119. STATIC void
  120. replaycache_scrub_if_needed_internal(time_t present, replaycache_t *r)
  121. {
  122. digest256map_iter_t *itr = NULL;
  123. const uint8_t *digest;
  124. void *valp;
  125. time_t *access_time;
  126. /* sanity check */
  127. if (!r || !(r->digests_seen)) {
  128. log_info(LD_BUG, "replaycache_scrub_if_needed_internal() called with"
  129. " stupid parameters; please fix this.");
  130. return;
  131. }
  132. /* scrub time yet? (scrubbed == 0 indicates never scrubbed before) */
  133. if (present - r->scrubbed < r->scrub_interval && r->scrubbed > 0) return;
  134. /* if we're never expiring, don't bother scrubbing */
  135. if (r->horizon == 0) return;
  136. /* okay, scrub time */
  137. itr = digest256map_iter_init(r->digests_seen);
  138. while (!digest256map_iter_done(itr)) {
  139. digest256map_iter_get(itr, &digest, &valp);
  140. access_time = (time_t *)valp;
  141. /* aged out yet? */
  142. if (*access_time < present - r->horizon) {
  143. /* Advance the iterator and remove this one */
  144. itr = digest256map_iter_next_rmv(r->digests_seen, itr);
  145. /* Free the value removed */
  146. tor_free(access_time);
  147. } else {
  148. /* Just advance the iterator */
  149. itr = digest256map_iter_next(r->digests_seen, itr);
  150. }
  151. }
  152. /* update scrubbed timestamp */
  153. if (present > r->scrubbed) r->scrubbed = present;
  154. }
  155. /** Test the buffer of length len point to by data against the replay cache r;
  156. * the digest of the buffer will be added to the cache at the current time,
  157. * and the function will return 1 if it was already seen within the cache's
  158. * horizon, or 0 otherwise.
  159. */
  160. int
  161. replaycache_add_and_test(replaycache_t *r, const void *data, size_t len)
  162. {
  163. return replaycache_add_and_test_internal(time(NULL), r, data, len, NULL);
  164. }
  165. /** Like replaycache_add_and_test(), but if it's a hit also return the time
  166. * elapsed since this digest was last seen.
  167. */
  168. int
  169. replaycache_add_test_and_elapsed(
  170. replaycache_t *r, const void *data, size_t len, time_t *elapsed)
  171. {
  172. return replaycache_add_and_test_internal(time(NULL), r, data, len, elapsed);
  173. }
  174. /** Scrub aged entries out of r if sufficiently long has elapsed since r was
  175. * last scrubbed.
  176. */
  177. void
  178. replaycache_scrub_if_needed(replaycache_t *r)
  179. {
  180. replaycache_scrub_if_needed_internal(time(NULL), r);
  181. }