Merge branch 'bug25552_ope_squashed'

18 files changed, 605 insertions, 303 deletions

diff --git a/changes/bug25552 b/changes/bug25552
new file mode 100644
index 0000000000..8d0488a462
--- /dev/null
+++ b/changes/bug25552
@@ -0,0 +1,5 @@
+  o Major feature (onion services):
+    - Improve revision counter generation in next-gen onion services. Onion
+      services can now scale by hosting multiple instances on different hosts
+      without synchronization between them, which was previously impossible
+      because descriptors would get rejected by HSDirs. Addresses ticket 25552.
diff --git a/src/feature/dircommon/voting_schedule.c b/src/feature/dircommon/voting_schedule.c
index 84c016c2b9..07e65ef06d 100644
--- a/src/feature/dircommon/voting_schedule.c
+++ b/src/feature/dircommon/voting_schedule.c
@@ -168,7 +168,7 @@ voting_schedule_get_next_valid_after_time(void)
 
  done:
   if (need_to_recalculate_voting_schedule) {
-    voting_schedule_recalculate_timing(get_options(), now);
+    voting_schedule_recalculate_timing(get_options(), approx_time());
     voting_schedule.created_on_demand = 1;
   }
 
diff --git a/src/feature/hs/hs_common.c b/src/feature/hs/hs_common.c
index 723cfa6ea8..328430be08 100644
--- a/src/feature/hs/hs_common.c
+++ b/src/feature/hs/hs_common.c
@@ -1102,8 +1102,7 @@ hs_in_period_between_tp_and_srv,(const networkstatus_t *consensus, time_t now))
   /* Get start time of next TP and of current SRV protocol run, and check if we
    * are between them. */
   valid_after = consensus->valid_after;
-  srv_start_time =
-    sr_state_get_start_time_of_current_protocol_run(valid_after);
+  srv_start_time = sr_state_get_start_time_of_current_protocol_run();
   tp_start_time = hs_get_start_time_of_next_time_period(srv_start_time);
 
   if (valid_after >= srv_start_time && valid_after < tp_start_time) {
diff --git a/src/feature/hs/hs_service.c b/src/feature/hs/hs_service.c
index 8b4de21387..54204dd070 100644
--- a/src/feature/hs/hs_service.c
+++ b/src/feature/hs/hs_service.c
@@ -17,6 +17,7 @@
 #include "core/mainloop/connection.h"
 #include "lib/crypt_ops/crypto_rand.h"
 #include "lib/crypt_ops/crypto_util.h"
+#include "lib/crypt_ops/crypto_ope.h"
 #include "feature/dircache/directory.h"
 #include "core/mainloop/main.h"
 #include "feature/nodelist/networkstatus.h"
@@ -102,7 +103,8 @@ static smartlist_t *hs_service_staging_list;
 static int consider_republishing_hs_descriptors = 0;
 
 /* Static declaration. */
-static void set_descriptor_revision_counter(hs_descriptor_t *hs_desc);
+static void set_descriptor_revision_counter(hs_service_descriptor_t *hs_desc,
+                                            time_t now, bool is_current);
 static void move_descriptors(hs_service_t *src, hs_service_t *dst);
 
 /* Helper: Function to compare two objects in the service map. Return 1 if the
@@ -443,7 +445,7 @@ service_intro_point_new(const extend_info_t *ei, unsigned int is_legacy)
     if (BUG(intro_point_max_lifetime < intro_point_min_lifetime)) {
       goto err;
     }
-    ip->time_to_expire = time(NULL) +
+    ip->time_to_expire = approx_time() +
       crypto_rand_int_range(intro_point_min_lifetime,intro_point_max_lifetime);
   }
 
@@ -1084,6 +1086,7 @@ service_descriptor_free_(hs_service_descriptor_t *desc)
     SMARTLIST_FOREACH(desc->previous_hsdirs, char *, s, tor_free(s));
     smartlist_free(desc->previous_hsdirs);
   }
+  crypto_ope_free(desc->ope_cipher);
   tor_free(desc);
 }
 
@@ -1388,13 +1391,30 @@ build_service_desc_plaintext(const hs_service_t *service,
   return ret;
 }
 
+/** Compute the descriptor's OPE cipher for encrypting revision counters. */
+static crypto_ope_t *
+generate_ope_cipher_for_desc(const hs_service_descriptor_t *hs_desc)
+{
+  /* Compute OPE key as H("rev-counter-generation" | blinded privkey) */
+  uint8_t key[DIGEST256_LEN];
+  crypto_digest_t *digest = crypto_digest256_new(DIGEST_SHA3_256);
+  const char ope_key_prefix[] = "rev-counter-generation";
+  const ed25519_secret_key_t *eph_privkey = &hs_desc->blinded_kp.seckey;
+  crypto_digest_add_bytes(digest, ope_key_prefix, sizeof(ope_key_prefix));
+  crypto_digest_add_bytes(digest, (char*)eph_privkey->seckey,
+                          sizeof(eph_privkey->seckey));
+  crypto_digest_get_digest(digest, (char *)key, sizeof(key));
+  crypto_digest_free(digest);
+
+  return crypto_ope_new(key);
+}
+
 /* For the given service and descriptor object, create the key material which
  * is the blinded keypair and the descriptor signing keypair. Return 0 on
  * success else -1 on error where the generated keys MUST be ignored. */
 static int
 build_service_desc_keys(const hs_service_t *service,
-                        hs_service_descriptor_t *desc,
-                        uint64_t time_period_num)
+                        hs_service_descriptor_t *desc)
 {
   int ret = 0;
   ed25519_keypair_t kp;
@@ -1410,10 +1430,17 @@ build_service_desc_keys(const hs_service_t *service,
   memcpy(&kp.pubkey, &service->keys.identity_pk, sizeof(kp.pubkey));
   memcpy(&kp.seckey, &service->keys.identity_sk, sizeof(kp.seckey));
   /* Build blinded keypair for this time period. */
-  hs_build_blinded_keypair(&kp, NULL, 0, time_period_num, &desc->blinded_kp);
+  hs_build_blinded_keypair(&kp, NULL, 0, desc->time_period_num,
+                           &desc->blinded_kp);
   /* Let's not keep too much traces of our keys in memory. */
   memwipe(&kp, 0, sizeof(kp));
 
+  /* Compute the OPE cipher struct (it's tied to the current blinded key) */
+  log_info(LD_GENERAL,
+           "Getting OPE for TP#%u", (unsigned) desc->time_period_num);
+  tor_assert_nonfatal(!desc->ope_cipher);
+  desc->ope_cipher = generate_ope_cipher_for_desc(desc);
+
   /* No need for extra strong, this is a temporary key only for this
    * descriptor. Nothing long term. */
   if (ed25519_keypair_generate(&desc->signing_kp, 0) < 0) {
@@ -1444,10 +1471,12 @@ build_service_descriptor(hs_service_t *service, time_t now,
   tor_assert(desc_out);
 
   desc = service_descriptor_new();
+
+  /* Set current time period */
   desc->time_period_num = time_period_num;
 
   /* Create the needed keys so we can setup the descriptor content. */
-  if (build_service_desc_keys(service, desc, time_period_num) < 0) {
+  if (build_service_desc_keys(service, desc) < 0) {
     goto err;
   }
   /* Setup plaintext descriptor content. */
@@ -1459,9 +1488,6 @@ build_service_descriptor(hs_service_t *service, time_t now,
     goto err;
   }
 
-  /* Set the revision counter for this descriptor */
-  set_descriptor_revision_counter(desc->desc);
-
   /* Let's make sure that we've created a descriptor that can actually be
    * encoded properly. This function also checks if the encoded output is
    * decodable after. */
@@ -1769,7 +1795,6 @@ service_desc_schedule_upload(hs_service_descriptor_t *desc,
 /* Update the given descriptor from the given service. The possible update
  * actions includes:
  *    - Picking missing intro points if needed.
- *    - Incrementing the revision counter if needed.
  */
 static void
 update_service_descriptor(hs_service_t *service,
@@ -1933,19 +1958,12 @@ cleanup_intro_points(hs_service_t *service, time_t now)
 /* Set the next rotation time of the descriptors for the given service for the
  * time now. */
 static void
-set_rotation_time(hs_service_t *service, time_t now)
+set_rotation_time(hs_service_t *service)
 {
-  time_t valid_after;
-  const networkstatus_t *ns = networkstatus_get_live_consensus(now);
-  if (ns) {
-    valid_after = ns->valid_after;
-  } else {
-    valid_after = now;
-  }
-
   tor_assert(service);
+
   service->state.next_rotation_time =
-    sr_state_get_start_time_of_current_protocol_run(valid_after) +
+    sr_state_get_start_time_of_current_protocol_run() +
     sr_state_get_protocol_run_duration();
 
   {
@@ -2012,7 +2030,7 @@ should_rotate_descriptors(hs_service_t *service, time_t now)
  * will be freed, the next one put in as the current and finally the next
  * descriptor pointer is NULLified. */
 static void
-rotate_service_descriptors(hs_service_t *service, time_t now)
+rotate_service_descriptors(hs_service_t *service)
 {
   if (service->desc_current) {
     /* Close all IP circuits for the descriptor. */
@@ -2027,7 +2045,7 @@ rotate_service_descriptors(hs_service_t *service, time_t now)
   service->desc_next = NULL;
 
   /* We've just rotated, set the next time for the rotation. */
-  set_rotation_time(service, now);
+  set_rotation_time(service);
 }
 
 /* Rotate descriptors for each service if needed. A non existing current
@@ -2055,7 +2073,7 @@ rotate_all_descriptors(time_t now)
              service->desc_current, service->desc_next,
              safe_str_client(service->onion_address));
 
-    rotate_service_descriptors(service, now);
+    rotate_service_descriptors(service);
   } FOR_EACH_SERVICE_END;
 }
 
@@ -2077,7 +2095,7 @@ run_housekeeping_event(time_t now)
       /* Set the next rotation time of the descriptors. If it's Oct 25th
        * 23:47:00, the next rotation time is when the next SRV is computed
        * which is at Oct 26th 00:00:00 that is in 13 minutes. */
-      set_rotation_time(service, now);
+      set_rotation_time(service);
     }
 
     /* Cleanup invalid intro points from the service descriptor. */
@@ -2326,13 +2344,17 @@ upload_descriptor_to_hsdir(const hs_service_t *service,
     int is_next_desc = (service->desc_next == desc);
     const uint8_t *idx = (is_next_desc) ? hsdir->hsdir_index.store_second:
                                           hsdir->hsdir_index.store_first;
+    char *blinded_pubkey_log_str =
+      tor_strdup(hex_str((char*)&desc->blinded_kp.pubkey.pubkey, 32));
     log_info(LD_REND, "Service %s %s descriptor of revision %" PRIu64
-                      " initiated upload request to %s with index %s",
+                      " initiated upload request to %s with index %s (%s)",
              safe_str_client(service->onion_address),
              (is_next_desc) ? "next" : "current",
              desc->desc->plaintext_data.revision_counter,
              safe_str_client(node_describe(hsdir)),
-             safe_str_client(hex_str((const char *) idx, 32)));
+             safe_str_client(hex_str((const char *) idx, 32)),
+             safe_str_client(blinded_pubkey_log_str));
+    tor_free(blinded_pubkey_log_str);
 
     /* Fire a UPLOAD control port event. */
     hs_control_desc_event_upload(service->onion_address, hsdir->identity,
@@ -2344,197 +2366,77 @@ upload_descriptor_to_hsdir(const hs_service_t *service,
   return;
 }
 
-/** Return a newly-allocated string for our state file which contains revision
- *  counter information for <b>desc</b>. The format is:
+/** Set the revision counter in <b>hs_desc</b>. We do this by encrypting a
+ *  timestamp using an OPE scheme and using the ciphertext as our revision
+ *  counter.
  *
- *     HidServRevCounter <blinded_pubkey> <rev_counter>
- */
-STATIC char *
-encode_desc_rev_counter_for_state(const hs_service_descriptor_t *desc)
-{
-  char *state_str = NULL;
-  char blinded_pubkey_b64[ED25519_BASE64_LEN+1];
-  uint64_t rev_counter = desc->desc->plaintext_data.revision_counter;
-  const ed25519_public_key_t *blinded_pubkey = &desc->blinded_kp.pubkey;
-
-  /* Turn the blinded key into b64 so that we save it on state */
-  tor_assert(blinded_pubkey);
-  if (ed25519_public_to_base64(blinded_pubkey_b64, blinded_pubkey) < 0) {
-    goto done;
-  }
-
-  /* Format is: <blinded key> <rev counter> */
-  tor_asprintf(&state_str, "%s %" PRIu64, blinded_pubkey_b64, rev_counter);
-
-  log_info(LD_GENERAL, "[!] Adding rev counter %" PRIu64 " for %s!",
-           rev_counter, blinded_pubkey_b64);
-
- done:
-  return state_str;
-}
-
-/** Update HS descriptor revision counters in our state by removing the old
- *  ones and writing down the ones that are currently active. */
+ *  If <b>is_current</b> is true, then this is the current HS descriptor,
+ *  otherwise it's the next one. */
 static void
-update_revision_counters_in_state(void)
-{
-  config_line_t *lines = NULL;
-  config_line_t **nextline = &lines;
-  or_state_t *state = get_or_state();
-
-  /* Prepare our state structure with the rev counters */
-  FOR_EACH_SERVICE_BEGIN(service) {
-    FOR_EACH_DESCRIPTOR_BEGIN(service, desc) {
-      /* We don't want to save zero counters */
-      if (desc->desc->plaintext_data.revision_counter == 0) {
-        continue;
-      }
-
-      *nextline = tor_malloc_zero(sizeof(config_line_t));
-      (*nextline)->key = tor_strdup("HidServRevCounter");
-      (*nextline)->value = encode_desc_rev_counter_for_state(desc);
-      nextline = &(*nextline)->next;
-    } FOR_EACH_DESCRIPTOR_END;
-  } FOR_EACH_SERVICE_END;
-
-  /* Remove the old rev counters, and replace them with the new ones */
-  config_free_lines(state->HidServRevCounter);
-  state->HidServRevCounter = lines;
-
-  /* Set the state as dirty since we just edited it */
-  if (!get_options()->AvoidDiskWrites) {
-    or_state_mark_dirty(state, 0);
-  }
-}
-
-/** Scan the string <b>state_line</b> for the revision counter of the service
- *  with <b>blinded_pubkey</b>. Set <b>service_found_out</b> to True if the
- *  line is relevant to this service, and return the cached revision
- *  counter. Else set <b>service_found_out</b> to False. */
-STATIC uint64_t
-check_state_line_for_service_rev_counter(const char *state_line,
-                                    const ed25519_public_key_t *blinded_pubkey,
-                                    int *service_found_out)
+set_descriptor_revision_counter(hs_service_descriptor_t *hs_desc, time_t now,
+                                bool is_current)
 {
-  smartlist_t *items = NULL;
-  int ok;
-  ed25519_public_key_t pubkey_in_state;
   uint64_t rev_counter = 0;
 
-  tor_assert(service_found_out);
-  tor_assert(state_line);
-  tor_assert(blinded_pubkey);
+  /* Get current time */
+  time_t srv_start = 0;
 
-  /* Assume that the line is not for this service */
-  *service_found_out = 0;
-
-  /* Start parsing the state line */
-  items = smartlist_new();
-  smartlist_split_string(items, state_line, NULL,
-                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, -1);
-  if (smartlist_len(items) < 2) {
-    log_warn(LD_GENERAL, "Incomplete rev counter line. Ignoring.");
-    goto done;
-  }
-
-  char *b64_key_str = smartlist_get(items, 0);
-  char *saved_rev_counter_str = smartlist_get(items, 1);
-
-  /* Parse blinded key to check if it's for this hidden service */
-  if (ed25519_public_from_base64(&pubkey_in_state, b64_key_str) < 0) {
-    log_warn(LD_GENERAL, "Unable to base64 key in revcount line. Ignoring.");
-    goto done;
-  }
-  /* State line not for this hidden service */
-  if (!ed25519_pubkey_eq(&pubkey_in_state, blinded_pubkey)) {
-    goto done;
-  }
-
-  rev_counter = tor_parse_uint64(saved_rev_counter_str,
-                                 10, 0, UINT64_MAX, &ok, NULL);
-  if (!ok) {
-    log_warn(LD_GENERAL, "Unable to parse rev counter. Ignoring.");
-    goto done;
+  /* As our revision counter plaintext value, we use the seconds since the
+   * start of the SR protocol run that is relevant to this descriptor. This is
+   * guaranteed to be a positive value since we need the SRV to start making a
+   * descriptor (so that we know where to upload it).
+   *
+   * Depending on whether we are building the current or the next descriptor,
+   * services use a different SRV value. See [SERVICEUPLOAD] in
+   * rend-spec-v3.txt:
+   *
+   * In particular, for the current descriptor (aka first descriptor), Tor
+   * always uses the previous SRV for uploading the descriptor, and hence we
+   * should use the start time of the previous protocol run here.
+   *
+   * Whereas for the next descriptor (aka second descriptor), Tor always uses
+   * the current SRV for uploading the descriptor.  and hence we use the start
+   * time of the current protocol run.
+   */
+  if (is_current) {
+    srv_start = sr_state_get_start_time_of_previous_protocol_run();
+  } else {
+    srv_start = sr_state_get_start_time_of_current_protocol_run();
   }
 
-  /* Since we got this far, the line was for this service */
-  *service_found_out = 1;
-
-  log_info(LD_GENERAL, "Found rev counter for %s: %" PRIu64,
-           b64_key_str, rev_counter);
-
- done:
-  tor_assert(items);
-  SMARTLIST_FOREACH(items, char*, s, tor_free(s));
-  smartlist_free(items);
-
-  return rev_counter;
-}
-
-/** Dig into our state file and find the current revision counter for the
- *  service with blinded key <b>blinded_pubkey</b>. If no revision counter is
- *  found, return 0. */
-static uint64_t
-get_rev_counter_for_service(const ed25519_public_key_t *blinded_pubkey)
-{
-  or_state_t *state = get_or_state();
-  config_line_t *line;
+  log_info(LD_REND, "Setting rev counter for TP #%u: "
+           "SRV started at %d, now %d (%s)",
+           (unsigned) hs_desc->time_period_num, (int)srv_start,
+           (int)now, is_current ? "current" : "next");
 
-  /* Set default value for rev counters (if not found) to 0 */
-  uint64_t final_rev_counter = 0;
+  tor_assert_nonfatal(now >= srv_start);
 
-  for (line = state->HidServRevCounter ; line ; line = line->next) {
-    int service_found = 0;
-    uint64_t rev_counter = 0;
+  /* Compute seconds elapsed since the start of the time period. That's the
+   * number of seconds of how long this blinded key has been active. */
+  time_t seconds_since_start_of_srv = now - srv_start;
 
-    tor_assert(!strcmp(line->key, "HidServRevCounter"));
+  /* Increment by one so that we are definitely sure this is strictly
+   * positive and not zero. */
+  seconds_since_start_of_srv++;
 
-    /* Scan all the HidServRevCounter lines till we find the line for this
-       service: */
-    rev_counter = check_state_line_for_service_rev_counter(line->value,
-                                                           blinded_pubkey,
-                                                           &service_found);
-    if (service_found) {
-      final_rev_counter = rev_counter;
-      goto done;
-    }
+  /* Check for too big inputs. */
+  if (BUG(seconds_since_start_of_srv > OPE_INPUT_MAX)) {
+    seconds_since_start_of_srv = OPE_INPUT_MAX;
   }
 
- done:
-  return final_rev_counter;
-}
-
-/** Update the value of the revision counter for <b>hs_desc</b> and save it on
-    our state file. */
-static void
-increment_descriptor_revision_counter(hs_descriptor_t *hs_desc)
-{
-  /* Find stored rev counter if it exists */
-  uint64_t rev_counter =
-    get_rev_counter_for_service(&hs_desc->plaintext_data.blinded_pubkey);
+  /* Now we compute the final revision counter value by encrypting the
+     plaintext using our OPE cipher: */
+  tor_assert(hs_desc->ope_cipher);
+  rev_counter = crypto_ope_encrypt(hs_desc->ope_cipher,
+                                   (int) seconds_since_start_of_srv);
 
-  /* Increment the revision counter of <b>hs_desc</b> so the next update (which
-   * will trigger an upload) will have the right value. We do this at this
-   * stage to only do it once because a descriptor can have many updates before
-   * being uploaded. By doing it at upload, we are sure to only increment by 1
-   * and thus avoid leaking how many operations we made on the descriptor from
-   * the previous one before uploading. */
-  rev_counter++;
-  hs_desc->plaintext_data.revision_counter = rev_counter;
+  /* The OPE module returns CRYPTO_OPE_ERROR in case of errors. */
+  tor_assert_nonfatal(rev_counter < CRYPTO_OPE_ERROR);
 
-  update_revision_counters_in_state();
-}
+  log_info(LD_REND, "Encrypted revision counter %d to %ld",
+           (int) seconds_since_start_of_srv, (long int) rev_counter);
 
-/** Set the revision counter in <b>hs_desc</b>, using the state file to find
- *  the current counter value if it exists. */
-static void
-set_descriptor_revision_counter(hs_descriptor_t *hs_desc)
-{
-  /* Find stored rev counter if it exists */
-  uint64_t rev_counter =
-    get_rev_counter_for_service(&hs_desc->plaintext_data.blinded_pubkey);
-
-  hs_desc->plaintext_data.revision_counter = rev_counter;
+  hs_desc->desc->plaintext_data.revision_counter = rev_counter;
 }
 
 /* Encode and sign the service descriptor desc and upload it to the
@@ -2592,9 +2494,6 @@ upload_descriptor_to_all(const hs_service_t *service,
               safe_str_client(service->onion_address), fmt_next_time);
   }
 
-  /* Update the revision counter of this descriptor */
-  increment_descriptor_revision_counter(desc->desc);
-
   smartlist_free(responsible_dirs);
   return;
 }
@@ -2734,6 +2633,10 @@ run_upload_descriptor_event(time_t now)
        * accurate because all circuits have been established. */
       build_desc_intro_points(service, desc, now);
 
+      /* Set the desc revision counter right before uploading */
+      set_descriptor_revision_counter(desc, approx_time(),
+                                      service->desc_current == desc);
+
       upload_descriptor_to_all(service, desc);
     } FOR_EACH_DESCRIPTOR_END;
   } FOR_EACH_SERVICE_END;
diff --git a/src/feature/hs/hs_service.h b/src/feature/hs/hs_service.h
index 22bfcacc26..4cd05e3897 100644
--- a/src/feature/hs/hs_service.h
+++ b/src/feature/hs/hs_service.h
@@ -131,6 +131,10 @@ typedef struct hs_service_descriptor_t {
    *  from this list, this means we received new dirinfo and we need to
    *  reupload our descriptor. */
   smartlist_t *previous_hsdirs;
+
+  /** The OPE cipher for encrypting revision counters for this descriptor.
+   *  Tied to the descriptor blinded key. */
+  struct crypto_ope_t *ope_cipher;
 } hs_service_descriptor_t;
 
 /* Service key material. */
@@ -346,19 +350,10 @@ STATIC void build_all_descriptors(time_t now);
 STATIC void update_all_descriptors(time_t now);
 STATIC void run_upload_descriptor_event(time_t now);
 
-STATIC char *
-encode_desc_rev_counter_for_state(const hs_service_descriptor_t *desc);
-
 STATIC void service_descriptor_free_(hs_service_descriptor_t *desc);
 #define service_descriptor_free(d) \
   FREE_AND_NULL(hs_service_descriptor_t, \
                            service_descriptor_free_, (d))
-
-STATIC uint64_t
-check_state_line_for_service_rev_counter(const char *state_line,
-                                    const ed25519_public_key_t *blinded_pubkey,
-                                    int *service_found_out);
-
 STATIC int
 write_address_to_file(const hs_service_t *service, const char *fname_);
 
@@ -375,4 +370,3 @@ STATIC int service_desc_hsdirs_changed(const hs_service_t *service,
 #endif /* defined(HS_SERVICE_PRIVATE) */
 
 #endif /* !defined(TOR_HS_SERVICE_H) */
-
diff --git a/src/feature/hs_common/shared_random_client.c b/src/feature/hs_common/shared_random_client.c
index 329f053d3b..ff98a719db 100644
--- a/src/feature/hs_common/shared_random_client.c
+++ b/src/feature/hs_common/shared_random_client.c
@@ -222,24 +222,44 @@ sr_parse_srv(const smartlist_t *args)
   return srv;
 }
 
-/** Return the start time of the current SR protocol run. For example, if the
- *  time is 23/06/2017 23:47:08 and a full SR protocol run is 24 hours, this
- *  function should return 23/06/2017 00:00:00. */
+/** Return the start time of the current SR protocol run using the times from
+ *  the current consensus. For example, if the latest consensus valid-after is
+ *  23/06/2017 23:00:00 and a full SR protocol run is 24 hours, this function
+ *  returns 23/06/2017 00:00:00. */
 time_t
-sr_state_get_start_time_of_current_protocol_run(time_t now)
+sr_state_get_start_time_of_current_protocol_run(void)
 {
   int total_rounds = SHARED_RANDOM_N_ROUNDS * SHARED_RANDOM_N_PHASES;
   int voting_interval = get_voting_interval();
   /* Find the time the current round started. */
-  time_t beginning_of_current_round = get_start_time_of_current_round();
+  time_t beginning_of_curr_round = get_start_time_of_current_round();
 
   /* Get current SR protocol round */
-  int current_round = (now / voting_interval) % total_rounds;
+  int curr_round_slot;
+  curr_round_slot = (beginning_of_curr_round / voting_interval) % total_rounds;
 
   /* Get start time by subtracting the time elapsed from the beginning of the
      protocol run */
-  time_t time_elapsed_since_start_of_run = current_round * voting_interval;
-  return beginning_of_current_round - time_elapsed_since_start_of_run;
+  time_t time_elapsed_since_start_of_run = curr_round_slot * voting_interval;
+
+  log_debug(LD_GENERAL, "Current SRV proto run: Start of current round: %u. "
+            "Time elapsed: %u (%d)", (unsigned) beginning_of_curr_round,
+            (unsigned) time_elapsed_since_start_of_run, voting_interval);
+
+  return beginning_of_curr_round - time_elapsed_since_start_of_run;
+}
+
+/** Return the start time of the previous SR protocol run. See
+ *  sr_state_get_start_time_of_current_protocol_run() for more details.  */
+time_t
+sr_state_get_start_time_of_previous_protocol_run(void)
+{
+  time_t start_time_of_current_run =
+    sr_state_get_start_time_of_current_protocol_run();
+
+  /* We get the start time of previous protocol run, by getting the start time
+   * of current run and the subtracting a full protocol run from that. */
+  return start_time_of_current_run - sr_state_get_protocol_run_duration();
 }
 
 /** Return the time (in seconds) it takes to complete a full SR protocol phase
diff --git a/src/feature/hs_common/shared_random_client.h b/src/feature/hs_common/shared_random_client.h
index 497a015c18..0e26f530a4 100644
--- a/src/feature/hs_common/shared_random_client.h
+++ b/src/feature/hs_common/shared_random_client.h
@@ -34,7 +34,8 @@ sr_srv_t *sr_parse_srv(const smartlist_t *args);
 /* Number of phase we have in a protocol. */
 #define SHARED_RANDOM_N_PHASES 2
 
-time_t sr_state_get_start_time_of_current_protocol_run(time_t now);
+time_t sr_state_get_start_time_of_current_protocol_run(void);
+time_t sr_state_get_start_time_of_previous_protocol_run(void);
 unsigned int sr_state_get_phase_duration(void);
 unsigned int sr_state_get_protocol_run_duration(void);
 time_t get_start_time_of_current_round(void);
diff --git a/src/lib/crypt_ops/crypto_ope.c b/src/lib/crypt_ops/crypto_ope.c
new file mode 100644
index 0000000000..ca42ae4341
--- /dev/null
+++ b/src/lib/crypt_ops/crypto_ope.c
@@ -0,0 +1,185 @@
+/* Copyright (c) 2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * A rudimentary order-preserving encryption scheme.
+ *
+ * To compute the encryption of N, this scheme uses an AES-CTR stream to
+ * generate M-byte values, and adds the first N of them together. (+1 each to
+ * insure that the ciphertexts are strictly decreasing.)
+ *
+ * We use this for generating onion service revision counters based on the
+ * current time, without leaking the amount of skew in our view of the current
+ * time.  MUCH more analysis would be needed before using it for anything
+ * else!
+ */
+
+#include "orconfig.h"
+
+#define CRYPTO_OPE_PRIVATE
+#include "lib/crypt_ops/crypto_ope.h"
+#include "lib/crypt_ops/crypto.h"
+#include "lib/crypt_ops/crypto_util.h"
+#include "lib/log/util_bug.h"
+#include "lib/malloc/malloc.h"
+#include "lib/arch/bytes.h"
+
+#include <string.h>
+
+/**
+ * How infrequent should the precomputed values be for this encryption?
+ * The choice of this value creates a space/time tradeoff.
+ *
+ * Note that this value must be a multiple of 16; see
+ * ope_get_cipher()
+ */
+#define SAMPLE_INTERVAL 1024
+/** Number of precomputed samples to make for each OPE key. */
+#define N_SAMPLES (OPE_INPUT_MAX / SAMPLE_INTERVAL)
+
+struct crypto_ope_t {
+  /** An AES key for use with this object. */
+  uint8_t key[OPE_KEY_LEN];
+  /** Cached intermediate encryption values at SAMPLE_INTERVAL,
+   * SAMPLE_INTERVAL*2,...SAMPLE_INTERVAL*N_SAMPLES */
+  uint64_t samples[N_SAMPLES];
+};
+
+/** The type to add up in order to produce our OPE ciphertexts */
+typedef uint16_t ope_val_t;
+
+#ifdef WORDS_BIG_ENDIAN
+/** Convert an OPE value to little-endian */
+static inline ope_val_t
+ope_val_to_le(ope_val_t x)
+{
+  return
+    ((x) >> 8) |
+    (((x)&0xff) << 8);
+}
+#else
+#define ope_val_to_le(x) (x)
+#endif
+
+/**
+ * Return a new AES256-CTR stream cipher object for <b>ope</b>, ready to yield
+ * bytes from the stream at position <b>initial_idx</b>.
+ *
+ * Note that because the index is converted directly to an IV, it must be a
+ * multiple of the AES block size (16).
+ */
+STATIC crypto_cipher_t *
+ope_get_cipher(const crypto_ope_t *ope, uint32_t initial_idx)
+{
+  uint8_t iv[CIPHER_IV_LEN];
+  tor_assert((initial_idx & 0xf) == 0);
+  uint32_t n = tor_htonl(initial_idx >> 4);
+  memset(iv, 0, sizeof(iv));
+  memcpy(iv + CIPHER_IV_LEN - sizeof(n), &n, sizeof(n));
+
+  return crypto_cipher_new_with_iv_and_bits(ope->key,
+                                            iv,
+                                            OPE_KEY_LEN * 8);
+}
+
+/**
+ * Retrieve and add the next <b>n</b> values from the stream cipher <b>c</b>,
+ * and return their sum.
+ *
+ * Note that values are taken in little-endian order (for performance on
+ * prevalent hardware), and are mapped from range 0..2^n-1 to range 1..2^n (so
+ * that each input encrypts to a different output).
+ *
+ * NOTE: this function is not constant-time.
+ */
+STATIC uint64_t
+sum_values_from_cipher(crypto_cipher_t *c, size_t n)
+{
+#define BUFSZ 256
+  ope_val_t buf[BUFSZ];
+  uint64_t total = 0;
+  unsigned i;
+  while (n >= BUFSZ) {
+    memset(buf, 0, sizeof(buf));
+    crypto_cipher_crypt_inplace(c, (char*)buf, BUFSZ*sizeof(ope_val_t));
+
+    for (i = 0; i < BUFSZ; ++i) {
+      total += ope_val_to_le(buf[i]);
+      total += 1;
+    }
+    n -= BUFSZ;
+  }
+
+  memset(buf, 0, n*sizeof(ope_val_t));
+  crypto_cipher_crypt_inplace(c, (char*)buf, n*sizeof(ope_val_t));
+  for (i = 0; i < n; ++i) {
+    total += ope_val_to_le(buf[i]);
+    total += 1;
+  }
+
+  memset(buf, 0, sizeof(buf));
+  return total;
+}
+
+/**
+ * Return a new crypto_ope_t object, using the provided 256-bit key.
+ */
+crypto_ope_t *
+crypto_ope_new(const uint8_t *key)
+{
+  crypto_ope_t *ope = tor_malloc_zero(sizeof(crypto_ope_t));
+  memcpy(ope->key, key, OPE_KEY_LEN);
+
+  crypto_cipher_t *cipher = ope_get_cipher(ope, 0);
+
+  uint64_t v = 0;
+  int i;
+  for (i = 0; i < N_SAMPLES; ++i) {
+    v += sum_values_from_cipher(cipher, SAMPLE_INTERVAL);
+    ope->samples[i] = v;
+  }
+
+  crypto_cipher_free(cipher);
+  return ope;
+}
+
+/** Free all storage held in <>ope</b>. */
+void
+crypto_ope_free_(crypto_ope_t *ope)
+{
+  if (!ope)
+    return;
+  memwipe(ope, 0, sizeof(*ope));
+  tor_free(ope);
+}
+
+/**
+ * Return the encrypted value corresponding to <b>input</b>.  The input value
+ * must be in range 1..OPE_INPUT_MAX.  Returns CRYPTO_OPE_ERROR on an invalid
+ * input.
+ *
+ * NOTE: this function is not constant-time.
+ */
+uint64_t
+crypto_ope_encrypt(const crypto_ope_t *ope, int plaintext)
+{
+  if (plaintext <= 0 || plaintext > OPE_INPUT_MAX)
+    return CRYPTO_OPE_ERROR;
+
+  const int sample_idx = (plaintext / SAMPLE_INTERVAL);
+  const int starting_iv = sample_idx * SAMPLE_INTERVAL;
+  const int remaining_values =  plaintext - starting_iv;
+  uint64_t v;
+  if (sample_idx == 0) {
+    v = 0;
+  } else {
+    v = ope->samples[sample_idx - 1];
+  }
+  crypto_cipher_t *cipher = ope_get_cipher(ope, starting_iv*sizeof(ope_val_t));
+
+  v += sum_values_from_cipher(cipher, remaining_values);
+
+  crypto_cipher_free(cipher);
+
+  return v;
+}
diff --git a/src/lib/crypt_ops/crypto_ope.h b/src/lib/crypt_ops/crypto_ope.h
new file mode 100644
index 0000000000..c62ed2a942
--- /dev/null
+++ b/src/lib/crypt_ops/crypto_ope.h
@@ -0,0 +1,46 @@
+/* Copyright (c) 2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef CRYPTO_OPE_H
+#define CRYPTO_OPE_H
+
+#include "orconfig.h"
+#include "lib/cc/torint.h"
+#include "lib/crypt_ops/crypto_ope.h"
+#include "lib/testsupport/testsupport.h"
+
+/** Length of OPE key, in bytes. */
+#define OPE_KEY_LEN 32
+
+/** Largest value that can be passed to crypto_ope_encrypt().
+ *
+ *  Expressed as 2^18 because the OPE system prefers powers of two.
+ *
+ *  The current max value stands for about 70 hours. The rationale here is as
+ *  follows: The rev counter is the time of seconds since the start of an SRV
+ *  period. SRVs are useful for about 48 hours (that's how long they stick
+ *  around on the consensus). Let's also add 12 hours of drift for clock skewed
+ *  services that might be using an old consensus and we arrive to 60
+ *  hours. The max value should be beyond that.
+ */
+#define OPE_INPUT_MAX (1<<18)
+
+#define CRYPTO_OPE_ERROR UINT64_MAX
+
+typedef struct crypto_ope_t crypto_ope_t;
+
+crypto_ope_t *crypto_ope_new(const uint8_t *key);
+void crypto_ope_free_(crypto_ope_t *ope);
+#define crypto_ope_free(ope) \
+  FREE_AND_NULL(crypto_ope_t, crypto_ope_free_, (ope))
+
+uint64_t crypto_ope_encrypt(const crypto_ope_t *ope, int plaintext);
+
+#ifdef CRYPTO_OPE_PRIVATE
+struct aes_cnt_cipher;
+STATIC struct aes_cnt_cipher *ope_get_cipher(const crypto_ope_t *ope,
+                                              uint32_t initial_idx);
+STATIC uint64_t sum_values_from_cipher(struct aes_cnt_cipher *c, size_t n);
+#endif
+
+#endif
diff --git a/src/lib/crypt_ops/include.am b/src/lib/crypt_ops/include.am
index 1b88b880d0..017d7956d0 100644
--- a/src/lib/crypt_ops/include.am
+++ b/src/lib/crypt_ops/include.am
@@ -14,6 +14,7 @@ src_lib_libtor_crypt_ops_a_SOURCES =			\
 	src/lib/crypt_ops/crypto_ed25519.c		\
 	src/lib/crypt_ops/crypto_format.c		\
 	src/lib/crypt_ops/crypto_hkdf.c			\
+	src/lib/crypt_ops/crypto_ope.c          	\
 	src/lib/crypt_ops/crypto_openssl_mgt.c		\
 	src/lib/crypt_ops/crypto_pwbox.c		\
 	src/lib/crypt_ops/crypto_rand.c			\
@@ -38,6 +39,7 @@ noinst_HEADERS +=					\
 	src/lib/crypt_ops/crypto.h			\
 	src/lib/crypt_ops/crypto_hkdf.h			\
 	src/lib/crypt_ops/crypto_openssl_mgt.h		\
+	src/lib/crypt_ops/crypto_ope.h          	\
 	src/lib/crypt_ops/crypto_pwbox.h		\
 	src/lib/crypt_ops/crypto_rand.h			\
 	src/lib/crypt_ops/crypto_rsa.h			\
diff --git a/src/test/include.am b/src/test/include.am
index 6a4b561736..81b089b8f7 100644
--- a/src/test/include.am
+++ b/src/test/include.am
@@ -117,6 +117,7 @@ src_test_test_SOURCES += \
 	src/test/test_controller.c \
 	src/test/test_controller_events.c \
 	src/test/test_crypto.c \
+	src/test/test_crypto_ope.c \
 	src/test/test_crypto_openssl.c \
 	src/test/test_data.c \
 	src/test/test_dir.c \
diff --git a/src/test/ope_ref.py b/src/test/ope_ref.py
new file mode 100644
index 0000000000..3677e57a61
--- /dev/null
+++ b/src/test/ope_ref.py
@@ -0,0 +1,40 @@
+#!/usr/bin/python3
+# Copyright 2018, The Tor Project, Inc. See LICENSE for licensing info.
+
+# Reference implementation for our rudimentary OPE code, used to
+# generate test vectors. See crypto_ope.c for more details.
+
+from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
+from cryptography.hazmat.primitives.ciphers.algorithms import AES
+from cryptography.hazmat.backends import default_backend
+
+from binascii import a2b_hex
+
+#randomly generated and values.
+KEY = a2b_hex(
+    "19e05891d55232c08c2cad91d612fdb9cbd6691949a0742434a76c80bc6992fe")
+PTS = [ 121132, 82283, 72661, 72941, 123122, 12154, 121574, 11391, 65845,
+        86301, 61284, 70505, 30438, 60150, 114800, 109403, 21893, 123569,
+        95617, 48561, 53334, 92746, 7110, 9612, 106958, 46889, 87790, 68878,
+        47917, 121128, 108602, 28217, 69498, 63870, 57542, 122148, 46254,
+        42850, 92661, 57720]
+
+IV = b'\x00' * 16
+
+backend = default_backend()
+
+def words():
+    cipher = Cipher(algorithms.AES(KEY), modes.CTR(IV), backend=backend)
+    e = cipher.encryptor()
+    while True:
+        v = e.update(b'\x00\x00')
+        yield v[0] + 256 * v[1] + 1
+
+def encrypt(n):
+    return sum(w for w, _ in zip(words(), range(n)))
+
+def example(n):
+    return ' {{ {}, UINT64_C({}) }},'.format(n, encrypt(n))
+
+for v in PTS:
+    print(example(v))
diff --git a/src/test/test.c b/src/test/test.c
index 2addeec968..745aa987aa 100644
--- a/src/test/test.c
+++ b/src/test/test.c
@@ -865,6 +865,7 @@ struct testgroup_t testgroups[] = {
   { "control/", controller_tests },
   { "control/event/", controller_event_tests },
   { "crypto/", crypto_tests },
+  { "crypto/ope/", crypto_ope_tests },
   { "crypto/openssl/", crypto_openssl_tests },
   { "dir/", dir_tests },
   { "dir_handle_get/", dir_handle_get_tests },
diff --git a/src/test/test.h b/src/test/test.h
index 602acca1cd..bfe50cbb8c 100644
--- a/src/test/test.h
+++ b/src/test/test.h
@@ -203,6 +203,7 @@ extern struct testcase_t container_tests[];
 extern struct testcase_t controller_tests[];
 extern struct testcase_t controller_event_tests[];
 extern struct testcase_t crypto_tests[];
+extern struct testcase_t crypto_ope_tests[];
 extern struct testcase_t crypto_openssl_tests[];
 extern struct testcase_t dir_tests[];
 extern struct testcase_t dir_handle_get_tests[];
diff --git a/src/test/test_crypto_ope.c b/src/test/test_crypto_ope.c
new file mode 100644
index 0000000000..7dcad7b4b2
--- /dev/null
+++ b/src/test/test_crypto_ope.c
@@ -0,0 +1,152 @@
+/* Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2017, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "orconfig.h"
+
+#define CRYPTO_OPE_PRIVATE
+
+#include "lib/crypt_ops/crypto_ope.h"
+#include "lib/crypt_ops/crypto.h"
+#include "lib/encoding/binascii.h"
+#include "test/test.h"
+#include "tinytest.h"
+
+#include <stddef.h>
+#include <string.h>
+
+static void
+test_crypto_ope_consistency(void *arg)
+{
+  (void)arg;
+
+  crypto_ope_t *ope = NULL;
+  crypto_cipher_t *aes = NULL;
+  const int TEST_VALS[] = { 5, 500, 1023, 1024, 1025, 2046, 2047, 2048, 2049,
+                            10000, OPE_INPUT_MAX };
+  unsigned i;
+  const uint8_t key[32] = "A fixed key, chosen arbitrarily.";
+
+  ope = crypto_ope_new(key);
+  tt_assert(ope);
+
+  uint64_t last_val = 0;
+  for (i = 0; i < ARRAY_LENGTH(TEST_VALS); ++i) {
+    aes = ope_get_cipher(ope, 0);
+    int val = TEST_VALS[i];
+    uint64_t v1 = crypto_ope_encrypt(ope, val);
+    uint64_t v2 = sum_values_from_cipher(aes, val);
+    tt_u64_op(v1, OP_EQ, v2);
+    tt_u64_op(v2, OP_GT, last_val);
+    last_val = v2;
+    crypto_cipher_free(aes);
+  }
+
+ done:
+  crypto_cipher_free(aes);
+  crypto_ope_free(ope);
+}
+
+static void
+test_crypto_ope_oob(void *arg)
+{
+  (void)arg;
+
+  crypto_ope_t *ope = NULL;
+  const uint8_t key[32] = "A fixed key, chosen arbitrarily.";
+  ope = crypto_ope_new(key);
+
+  tt_u64_op(UINT64_MAX, OP_EQ, crypto_ope_encrypt(ope,INT_MIN));
+  tt_u64_op(UINT64_MAX, OP_EQ, crypto_ope_encrypt(ope,-100));
+  tt_u64_op(UINT64_MAX, OP_EQ, crypto_ope_encrypt(ope,0));
+  tt_u64_op(UINT64_MAX, OP_NE, crypto_ope_encrypt(ope,1));
+  tt_u64_op(UINT64_MAX, OP_NE, crypto_ope_encrypt(ope,7000));
+  tt_u64_op(UINT64_MAX, OP_NE, crypto_ope_encrypt(ope,OPE_INPUT_MAX));
+  tt_u64_op(UINT64_MAX, OP_EQ, crypto_ope_encrypt(ope,OPE_INPUT_MAX+1));
+  tt_u64_op(UINT64_MAX, OP_EQ, crypto_ope_encrypt(ope,INT_MAX));
+ done:
+  crypto_ope_free(ope);
+}
+
+static const char OPE_TEST_KEY[] =
+  "19e05891d55232c08c2cad91d612fdb9cbd6691949a0742434a76c80bc6992fe";
+
+/* generated by a separate python implementation. */
+static const struct {
+  int v;
+  uint64_t r;
+} OPE_TEST_VECTORS[] = {
+  { 121132, UINT64_C(3971694514) },
+  { 82283, UINT64_C(2695743564) },
+  { 72661, UINT64_C(2381548866) },
+  { 72941, UINT64_C(2390408421) },
+  { 123122, UINT64_C(4036781069) },
+  { 12154, UINT64_C(402067100) },
+  { 121574, UINT64_C(3986197593) },
+  { 11391, UINT64_C(376696838) },
+  { 65845, UINT64_C(2161801517) },
+  { 86301, UINT64_C(2828270975) },
+  { 61284, UINT64_C(2013616892) },
+  { 70505, UINT64_C(2313368870) },
+  { 30438, UINT64_C(1001394664) },
+  { 60150, UINT64_C(1977329668) },
+  { 114800, UINT64_C(3764946628) },
+  { 109403, UINT64_C(3585352477) },
+  { 21893, UINT64_C(721388468) },
+  { 123569, UINT64_C(4051780471) },
+  { 95617, UINT64_C(3134921876) },
+  { 48561, UINT64_C(1597596985) },
+  { 53334, UINT64_C(1753691710) },
+  { 92746, UINT64_C(3040874493) },
+  { 7110, UINT64_C(234966492) },
+  { 9612, UINT64_C(318326551) },
+  { 106958, UINT64_C(3506124249) },
+  { 46889, UINT64_C(1542219146) },
+  { 87790, UINT64_C(2877361609) },
+  { 68878, UINT64_C(2260369112) },
+  { 47917, UINT64_C(1576681737) },
+  { 121128, UINT64_C(3971553290) },
+  { 108602, UINT64_C(3559176081) },
+  { 28217, UINT64_C(929692460) },
+  { 69498, UINT64_C(2280554161) },
+  { 63870, UINT64_C(2098322675) },
+  { 57542, UINT64_C(1891698992) },
+  { 122148, UINT64_C(4004515805) },
+  { 46254, UINT64_C(1521227949) },
+  { 42850, UINT64_C(1408996941) },
+  { 92661, UINT64_C(3037901517) },
+  { 57720, UINT64_C(1897369989) },
+};
+
+static void
+test_crypto_ope_vectors(void *arg)
+{
+  (void)arg;
+  uint8_t key[32];
+  crypto_ope_t *ope = NULL, *ope2 = NULL;
+
+  base16_decode((char*)key, 32, OPE_TEST_KEY, strlen(OPE_TEST_KEY));
+
+  ope = crypto_ope_new(key);
+  key[8] += 1;
+  ope2 = crypto_ope_new(key);
+  unsigned i;
+  for (i = 0; i < ARRAY_LENGTH(OPE_TEST_VECTORS); ++i) {
+    int val = OPE_TEST_VECTORS[i].v;
+    uint64_t res = OPE_TEST_VECTORS[i].r;
+
+    tt_u64_op(crypto_ope_encrypt(ope, val), OP_EQ, res);
+    tt_u64_op(crypto_ope_encrypt(ope2, val), OP_NE, res);
+  }
+ done:
+  crypto_ope_free(ope);
+  crypto_ope_free(ope2);
+}
+
+struct testcase_t crypto_ope_tests[] = {
+  { "consistency", test_crypto_ope_consistency, 0, NULL, NULL },
+  { "oob", test_crypto_ope_oob, 0, NULL, NULL },
+  { "vectors", test_crypto_ope_vectors, 0, NULL, NULL },
+  END_OF_TESTCASES
+};
diff --git a/src/test/test_hs_common.c b/src/test/test_hs_common.c
index f17cc8aeb3..c1001ee5c4 100644
--- a/src/test/test_hs_common.c
+++ b/src/test/test_hs_common.c
@@ -1344,6 +1344,10 @@ run_reachability_scenario(const reachability_cfg_t *cfg, int num_scenario)
                       &mock_service_ns->fresh_until);
   voting_schedule_recalculate_timing(get_options(),
                                      mock_service_ns->valid_after);
+  /* Check that service is in the right time period point */
+  tt_int_op(hs_in_period_between_tp_and_srv(mock_service_ns, 0), OP_EQ,
+            cfg->service_in_new_tp);
+
   /* Set client consensus time. */
   set_consensus_times(cfg->client_valid_after,
                       &mock_client_ns->valid_after);
@@ -1353,10 +1357,7 @@ run_reachability_scenario(const reachability_cfg_t *cfg, int num_scenario)
                       &mock_client_ns->fresh_until);
   voting_schedule_recalculate_timing(get_options(),
                                      mock_client_ns->valid_after);
-
-  /* New time period checks for this scenario. */
-  tt_int_op(hs_in_period_between_tp_and_srv(mock_service_ns, 0), OP_EQ,
-            cfg->service_in_new_tp);
+  /* Check that client is in the right time period point */
   tt_int_op(hs_in_period_between_tp_and_srv(mock_client_ns, 0), OP_EQ,
             cfg->client_in_new_tp);
 
@@ -1367,7 +1368,8 @@ run_reachability_scenario(const reachability_cfg_t *cfg, int num_scenario)
   mock_service_ns->sr_info.previous_srv = cfg->service_previous_srv;
 
   /* Initialize a service to get keys. */
-  service = helper_init_service(time(NULL));
+  update_approx_time(mock_service_ns->valid_after);
+  service = helper_init_service(mock_service_ns->valid_after+1);
 
   /*
    * === Client setup ===
diff --git a/src/test/test_hs_service.c b/src/test/test_hs_service.c
index 8074d260a4..ee6cbc2ac1 100644
--- a/src/test/test_hs_service.c
+++ b/src/test/test_hs_service.c
@@ -1044,7 +1044,7 @@ static void
 test_rotate_descriptors(void *arg)
 {
   int ret;
-  time_t next_rotation_time, now = time(NULL);
+  time_t next_rotation_time, now;
   hs_service_t *service;
   hs_service_descriptor_t *desc_next;
 
@@ -1068,6 +1068,9 @@ test_rotate_descriptors(void *arg)
   tt_int_op(ret, OP_EQ, 0);
   voting_schedule_recalculate_timing(get_options(), mock_ns.valid_after);
 
+  update_approx_time(mock_ns.valid_after+1);
+  now = mock_ns.valid_after+1;
+
   /* Create a service with a default descriptor and state. It's added to the
    * global map. */
   service = helper_create_service();
@@ -1106,6 +1109,9 @@ test_rotate_descriptors(void *arg)
   tt_int_op(ret, OP_EQ, 0);
   voting_schedule_recalculate_timing(get_options(), mock_ns.valid_after);
 
+  update_approx_time(mock_ns.valid_after+1);
+  now = mock_ns.valid_after+1;
+
   /* Note down what to expect for the next rotation time which is 01:00 + 23h
    * meaning 00:00:00. */
   next_rotation_time = mock_ns.valid_after + (23 * 60 * 60);
@@ -1168,6 +1174,9 @@ test_build_update_descriptors(void *arg)
   tt_int_op(ret, OP_EQ, 0);
   voting_schedule_recalculate_timing(get_options(), mock_ns.valid_after);
 
+  update_approx_time(mock_ns.valid_after+1);
+  now = mock_ns.valid_after+1;
+
   /* Create a service without a current descriptor to trigger a build. */
   service = helper_create_service();
   tt_assert(service);
@@ -1309,6 +1318,9 @@ test_build_update_descriptors(void *arg)
                            &mock_ns.fresh_until);
   tt_int_op(ret, OP_EQ, 0);
 
+  update_approx_time(mock_ns.valid_after+1);
+  now = mock_ns.valid_after+1;
+
   /* Create a service without a current descriptor to trigger a build. */
   service = helper_create_service();
   tt_assert(service);
@@ -1363,7 +1375,7 @@ static void
 test_upload_descriptors(void *arg)
 {
   int ret;
-  time_t now = time(NULL);
+  time_t now;
   hs_service_t *service;
 
   (void) arg;
@@ -1382,6 +1394,10 @@ test_upload_descriptors(void *arg)
   ret = parse_rfc1123_time("Sat, 26 Oct 1985 14:00:00 UTC",
                            &mock_ns.fresh_until);
   tt_int_op(ret, OP_EQ, 0);
+  voting_schedule_recalculate_timing(get_options(), mock_ns.valid_after);
+
+  update_approx_time(mock_ns.valid_after+1);
+  now = mock_ns.valid_after+1;
 
   /* Create a service with no descriptor. It's added to the global map. */
   service = hs_service_new(get_options());
@@ -1416,66 +1432,6 @@ test_upload_descriptors(void *arg)
   UNMOCK(get_or_state);
 }
 
-/** Test the functions that save and load HS revision counters to state. */
-static void
-test_revision_counter_state(void *arg)
-{
-  char *state_line_one = NULL;
-  char *state_line_two = NULL;
-
-  hs_service_descriptor_t *desc_one = service_descriptor_new();
-  hs_service_descriptor_t *desc_two = service_descriptor_new();
-
-  (void) arg;
-
-  /* Prepare both descriptors */
-  desc_one->desc->plaintext_data.revision_counter = 42;
-  desc_two->desc->plaintext_data.revision_counter = 240;
-  memset(&desc_one->blinded_kp.pubkey.pubkey, 66,
-         sizeof(desc_one->blinded_kp.pubkey.pubkey));
-  memset(&desc_two->blinded_kp.pubkey.pubkey, 240,
-         sizeof(desc_one->blinded_kp.pubkey.pubkey));
-
-  /* Turn the descriptor rev counters into state lines */
-  state_line_one = encode_desc_rev_counter_for_state(desc_one);
-  tt_str_op(state_line_one, OP_EQ,
-            "QkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkJCQkI 42");
-
-  state_line_two = encode_desc_rev_counter_for_state(desc_two);
-  tt_str_op(state_line_two, OP_EQ,
-            "8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PDw8PA 240");
-
-  /* Now let's test our state parsing function: */
-  int service_found;
-  uint64_t cached_rev_counter;
-
-  /* First's try with wrong pubkey and check that no service was found */
-  cached_rev_counter =check_state_line_for_service_rev_counter(state_line_one,
-                                                 &desc_two->blinded_kp.pubkey,
-                                                               &service_found);
-  tt_int_op(service_found, OP_EQ, 0);
-  tt_u64_op(cached_rev_counter, OP_EQ, 0);
-
-  /* Now let's try with the right pubkeys */
-  cached_rev_counter =check_state_line_for_service_rev_counter(state_line_one,
-                                                 &desc_one->blinded_kp.pubkey,
-                                                               &service_found);
-  tt_int_op(service_found, OP_EQ, 1);
-  tt_u64_op(cached_rev_counter, OP_EQ, 42);
-
-  cached_rev_counter =check_state_line_for_service_rev_counter(state_line_two,
-                                                 &desc_two->blinded_kp.pubkey,
-                                                               &service_found);
-  tt_int_op(service_found, OP_EQ, 1);
-  tt_u64_op(cached_rev_counter, OP_EQ, 240);
-
- done:
-  tor_free(state_line_one);
-  tor_free(state_line_two);
-  service_descriptor_free(desc_one);
-  service_descriptor_free(desc_two);
-}
-
 /** Global vars used by test_rendezvous1_parsing() */
 static char rend1_payload[RELAY_PAYLOAD_SIZE];
 static size_t rend1_payload_len = 0;
@@ -1629,8 +1585,6 @@ struct testcase_t hs_service_tests[] = {
     NULL, NULL },
   { "upload_descriptors", test_upload_descriptors, TT_FORK,
     NULL, NULL },
-  { "revision_counter_state", test_revision_counter_state, TT_FORK,
-    NULL, NULL },
   { "rendezvous1_parsing", test_rendezvous1_parsing, TT_FORK,
     NULL, NULL },
 
diff --git a/src/test/test_shared_random.c b/src/test/test_shared_random.c
index b0a9da0033..d2defdf680 100644
--- a/src/test/test_shared_random.c
+++ b/src/test/test_shared_random.c
@@ -259,8 +259,7 @@ test_get_start_time_of_current_run(void *arg)
                                 &current_time);
     tt_int_op(retval, OP_EQ, 0);
     voting_schedule_recalculate_timing(get_options(), current_time);
-    run_start_time =
-      sr_state_get_start_time_of_current_protocol_run(current_time);
+    run_start_time = sr_state_get_start_time_of_current_protocol_run();
 
     /* Compare it with the correct result */
     format_iso_time(tbuf, run_start_time);
@@ -272,8 +271,7 @@ test_get_start_time_of_current_run(void *arg)
                                 &current_time);
     tt_int_op(retval, OP_EQ, 0);
     voting_schedule_recalculate_timing(get_options(), current_time);
-    run_start_time =
-      sr_state_get_start_time_of_current_protocol_run(current_time);
+    run_start_time = sr_state_get_start_time_of_current_protocol_run();
 
     /* Compare it with the correct result */
     format_iso_time(tbuf, run_start_time);
@@ -285,8 +283,7 @@ test_get_start_time_of_current_run(void *arg)
                                 &current_time);
     tt_int_op(retval, OP_EQ, 0);
     voting_schedule_recalculate_timing(get_options(), current_time);
-    run_start_time =
-      sr_state_get_start_time_of_current_protocol_run(current_time);
+    run_start_time = sr_state_get_start_time_of_current_protocol_run();
 
     /* Compare it with the correct result */
     format_iso_time(tbuf, run_start_time);
@@ -308,8 +305,7 @@ test_get_start_time_of_current_run(void *arg)
                                 &current_time);
     tt_int_op(retval, OP_EQ, 0);
     voting_schedule_recalculate_timing(get_options(), current_time);
-    run_start_time =
-      sr_state_get_start_time_of_current_protocol_run(current_time);
+    run_start_time = sr_state_get_start_time_of_current_protocol_run();
 
     /* Compare it with the correct result */
     format_iso_time(tbuf, run_start_time);
@@ -342,7 +338,7 @@ test_get_start_time_functions(void *arg)
 
   voting_schedule_recalculate_timing(get_options(), now);
   time_t start_time_of_protocol_run =
-    sr_state_get_start_time_of_current_protocol_run(now);
+    sr_state_get_start_time_of_current_protocol_run();
   tt_assert(start_time_of_protocol_run);
 
   /* Check that the round start time of the beginning of the run, is itself */