src/or/replaycache.c

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