replaycache.c

Go to the documentation of this file.

 /* Copyright (c) 2012-2021, The Tor Project, Inc. */
 /* See LICENSE for licensing information */
 
/**
 * \file replaycache.c
 *
 * \brief Self-scrubbing replay cache for rendservice.c
 *
 * To prevent replay attacks, hidden services need to recognize INTRODUCE2
 * cells that they've already seen, and drop them.  If they didn't, then
 * sending the same INTRODUCE2 cell over and over would force the hidden
 * service to make a huge number of circuits to the same rendezvous
 * point, aiding traffic analysis.
 *
 * (It's not that simple, actually.  We only check for replays in the
 * RSA-encrypted portion of the handshake, since the rest of the handshake is
 * malleable.)
 *
 * This module is used from rendservice.c.
 */
 
#define REPLAYCACHE_PRIVATE
 
#include "core/or/or.h"
#include "feature/hs_common/replaycache.h"
 
/** Free the replaycache r and all of its entries.
 */
void
replaycache_free_(replaycache_t *r)
{
  if (!r) {
    log_info(LD_BUG, "replaycache_free() called on NULL");
    return;
  }
 
  if (r->digests_seen) digest256map_free(r->digests_seen, tor_free_);
 
  tor_free(r);
}
 
/** Allocate a new, empty replay detection cache, where horizon is the time
 * for entries to age out and interval is the time after which the cache
 * should be scrubbed for old entries.
 */
replaycache_t *
replaycache_new(time_t horizon, time_t interval)
{
  replaycache_t *r = NULL;
 
  if (horizon < 0) {
    log_info(LD_BUG, "replaycache_new() called with negative"
        " horizon parameter");
    goto err;
  }
 
  if (interval < 0) {
    log_info(LD_BUG, "replaycache_new() called with negative interval"
        " parameter");
    interval = 0;
  }
 
  r = tor_malloc(sizeof(*r));
  r->scrub_interval = interval;
  r->scrubbed = 0;
  r->horizon = horizon;
  r->digests_seen = digest256map_new();
 
 err:
  return r;
}
 
/** Check a digest without modifying the cache. Return its stored timestamp
 * through access_time, even if expired, so the caller can refresh it. */
static int
replaycache_test_and_elapsed_internal(time_t present, const replaycache_t *r,
                                      const uint8_t *digest, time_t *elapsed,
                                      time_t **access_time)
{
  *access_time = digest256map_get(r->digests_seen, digest);
  if (!*access_time || (r->horizon && **access_time < present - r->horizon)) {
    return 0;
  }
  if (elapsed) {
    *elapsed = present >= **access_time ? present - **access_time : 0;
  }
  return 1;
}
 
/** See documentation for replaycache_add_and_test().
 */
STATIC int
replaycache_add_and_test_internal(
    time_t present, replaycache_t *r, const void *data, size_t len,
    time_t *elapsed)
{
  int rv = 0;
  uint8_t digest[DIGEST256_LEN];
  time_t *access_time;
 
  /* sanity check */
  if (present <= 0 || !r || !data || len == 0) {
    log_info(LD_BUG, "replaycache_add_and_test_internal() called with stupid"
        " parameters; please fix this.");
    goto done;
  }
 
  /* compute digest */
  crypto_digest256((char *)digest, (const char *)data, len, DIGEST_SHA256);
 
  rv = replaycache_test_and_elapsed_internal(present, r, digest, elapsed,
                                             &access_time);
 
  /* seen before? */
  if (access_time != NULL) {
    /*
     * If it's ahead of the cached time, update
     */
    if (*access_time < present) {
      *access_time = present;
    }
  } else {
    /* No, so no hit and update the digest map with the current time */
    access_time = tor_malloc(sizeof(*access_time));
    *access_time = present;
    digest256map_set(r->digests_seen, digest, access_time);
  }
 
  /* now scrub the cache if it's time */
  replaycache_scrub_if_needed_internal(present, r);
 
 done:
  return rv;
}
 
/** See documentation for replaycache_scrub_if_needed().
 */
STATIC void
replaycache_scrub_if_needed_internal(time_t present, replaycache_t *r)
{
  digest256map_iter_t *itr = NULL;
  const uint8_t *digest;
  void *valp;
  time_t *access_time;
 
  /* sanity check */
  if (!r || !(r->digests_seen)) {
    log_info(LD_BUG, "replaycache_scrub_if_needed_internal() called with"
        " stupid parameters; please fix this.");
    return;
  }
 
  /* scrub time yet? (scrubbed == 0 indicates never scrubbed before) */
  if (present - r->scrubbed < r->scrub_interval && r->scrubbed > 0) return;
 
  /* if we're never expiring, don't bother scrubbing */
  if (r->horizon == 0) return;
 
  /* okay, scrub time */
  itr = digest256map_iter_init(r->digests_seen);
  while (!digest256map_iter_done(itr)) {
    digest256map_iter_get(itr, &digest, &valp);
    access_time = (time_t *)valp;
    /* aged out yet? */
    if (*access_time < present - r->horizon) {
      /* Advance the iterator and remove this one */
      itr = digest256map_iter_next_rmv(r->digests_seen, itr);
      /* Free the value removed */
      tor_free(access_time);
    } else {
      /* Just advance the iterator */
      itr = digest256map_iter_next(r->digests_seen, itr);
    }
  }
 
  /* update scrubbed timestamp */
  if (present > r->scrubbed) r->scrubbed = present;
}
 
/** Test the buffer of length len point to by data against the replay cache r;
 * the digest of the buffer will be added to the cache at the current time,
 * and the function will return 1 if it was already seen within the cache's
 * horizon, or 0 otherwise.
 */
int
replaycache_add_and_test(replaycache_t *r, const void *data, size_t len)
{
  return replaycache_add_and_test_internal(time(NULL), r, data, len, NULL);
}
 
/** Test for a cached digest without inserting, refreshing, or scrubbing any
 * entries. On a hit, optionally return the time since it was last added. */
int
replaycache_test_and_elapsed(const replaycache_t *r, const void *data,
                             size_t len, time_t *elapsed)
{
  uint8_t digest[DIGEST256_LEN];
  time_t *access_time;
 
  tor_assert(r);
  tor_assert(data);
  tor_assert(len);
 
  crypto_digest256((char *)digest, data, len, DIGEST_SHA256);
  return replaycache_test_and_elapsed_internal(time(NULL), r, digest, elapsed,
                                               &access_time);
}
 
/** Like replaycache_add_and_test(), but if it's a hit also return the time
 * elapsed since this digest was last seen.
 */
int
replaycache_add_test_and_elapsed(
    replaycache_t *r, const void *data, size_t len, time_t *elapsed)
{
  return replaycache_add_and_test_internal(time(NULL), r, data, len, elapsed);
}
 
/** Scrub aged entries out of r if sufficiently long has elapsed since r was
 * last scrubbed.
 */
void
replaycache_scrub_if_needed(replaycache_t *r)
{
  replaycache_scrub_if_needed_internal(time(NULL), r);
}
 
/** Return the number of entries currently stored in the given cache `r`. */
size_t
replay_cache_count(const replaycache_t *r)
{
  if (!r) {
    return 0;
  }
  return digest256map_size(r->digests_seen);
}