[tor-dev] Proposal 222: Stop sending client timestamps

[Nick Mathewson]

Filename: 222-remove-client-timestamps.txt
Title: Stop sending client timestamps
Authors: Nick Mathewson
Created: 22 August 2013
Target: 0.2.5.x
Status: Open

0. Summary

   There are a few places in Tor where clients and servers send
   timestamps.  I list them and discuss how to eliminate them.

1. Introduction

   Despite this late date, many hosts aren't running NTP and
   don't have very well synchronized clocks. Even more hosts
   aren't running a secure NTP; it's probably easy to
   desynchronize target hosts.

   Given all of this, it's probably a fingerprinting opportunity
   whenever clients send their view of the current time.
   Let's try to avoid that.

   I'm also going to list the places where servers send their
   view of the current time, and propose that we eliminate some
   of those.

   Scope: This proposal is about eliminating passive timestamp
   exposure, not about tricky active detection mechanisms where
   you do something like offering a client a large number of
   about-to-expire/just-expired certificates to see which ones
   they accept.

2. The Tor link protocol

2.1. NETINFO (client and server)

   NETINFO cells specify that both parties include a 4-byte
   timestamp.

   Instead, let's say that clients should set this timestamp to
   0.  Nothing currently looks at a client's setting for this
   field, so this change should be safe.

2.2. AUTHENTICATE (server)

   The AUTHENTICATE cell is not ordinarily sent by clients. It
   contains an 8-byte timestamp and a 16-byte random value.
   Instead, let's replace both with a 24-byte (truncated) HMAC of
   the current time, using a random key.

   This will achieve the goal of including a timestamp in the
   cell (preventing replays even in the presence of bad entropy),
   while at the same time not including the time here.

2.3. TLS

2.3.1. ClientRandom in the TLS handshake

   See TLS proposal in appendix A.

   This presents a TLS fingerprinting/censorship opportunity. I
   propose that we investigate whether "random " or "zero" is
   more common on the wire, choose that, and lobby for changes to
   TLS implementations.

2.3.2. Certificate validity intervals

   Servers use the current time in setting certificate validity
   for their initial certificates.  They randomize this value
   somewhat.  I propose that we don't change this, since it's a
   server-only issue, and already somewhat mitigated.

3. Directory protocol

3.1. Published

  This field in descriptors is generated by servers only; I
  propose no change.

3.2. The Date header

  This HTTP header is sent by directory servers only; I propose
  no change.

4. The hidden service protocol

4.1. Descriptor publication time

  Hidden service descriptors include a publication time.  I
  propose that we round this time down to the nearest N minutes,
  perhaps for N=30.

4.2. INTRODUCE2 cell timestamp

  INTRODUCE2 cells once limited the duration of their replay
  caches by including a timestamp in the INTRODUCE2 cells.  Since
  0.2.3.9-alpha, this timestamp is ignored, and key lifetime is
  used instead.

  When we determine that no hidden services are running on
  0.2.2.x (and really, no hidden services should be running on
  0.2.2.x!), we can simply send 0 instead.  (See ticket #7803).

  This might be a good place to use a consensus parameter, so
  that a large number of clients switch at the same time.

  I claim this would be suitable for backport to 0.2.4.

5. The application layer

  The application layer is mostly out of scope for this proposal,
  except:

  TorBrowser already (I hear) drops the timestamp from the
  ClientRandom field in TLS.  We should encourage other TLS
  applications to do so.  (See Appendix A.)



=================================================================
APPENDIX A:  "Let's replace gmt_unix_time in TLS"

PROBLEM:

The gmt_unix_time field in the Random field in the TLS handshake
provides a way for an observer to fingerprint clients.

Despite the late date, much of the world is still not
synchronized to the second via an ntp-like service. This means
that different clients have different views of the current time,
which provides a fingerprint that helps to track and distinguish
them.  This fingerprint is useful for tracking clients as they
move around.  It can also distinguish clients using a single VPN,
NAT, or privacy network.  (Tor's modified firefox avoids this by
not sending the time.)

Worse, some implementations don't send the current time, but the
process time, or the computer's uptime, both of which are far
more distinguishing than the current time() value.

The information fingerprint here is strong enough to uniquely
identify some TLS users (the ones whose clocks are hours off).
Even for the ones whose clocks are mostly right (within a second
or two), the field leaks a bit of information, and it only takes
so many bits to make a user unique.


WHY gmt_unix_time IN THE FIRST PLACE?

According to third-hand reports -- (and correct me if I'm wrong!)
it was introduced in SSL 3.0 to prevent complete failure in cases
where the PRNG was completely broken, by making a part of the
Random field that would definitely vary between TLS handshakes.

I doubt that this goal is really achieved: on modern desktop
environments, it's not really so strange to start two TLS
connections within the same second.

WHY ELSE IS gmt_unix_time USED?

The consensus among implementors seems to be that it's unwise to
depend on any particular value or interpretation for the field.
The TLS 1.2 standard, RFC 5246, says that "Clocks are not
required to be set correctly by the basic TLS protocol;
higher-level or application protocols may define additional
requirements."

Some implementations set the entire field randomly; this appears
not to have broken TLS on the internet.

At least one tool (tlsdate) uses the server-side value of the
field as an authenticated view of the current time.



PROPOSAL 1:

Declare that implementations MAY replace gmt_unix_time either
with four more random bytes, or four bytes of zeroes.

Make your implementation just do that.

(Rationale: some implementations (like TorBrowser) are already
doing this in practice.  It's sensible and simple.  You're
unlikely to mess it up, or cause trouble.)



PROPOSAL 2:

Okay, if you really want to preserve the security allegedly
provided by gmt_unix_time, allow the following approach instead:

Set the Random field, not to 32 bytes from your PRNG, but to the
HMAC-SHA256 of any high resolution timer that you have, using 32
bytes from your PRNG as a key.  In other words, replace this:

   Random.gmt_unix_time = time();
   Random.random_bytes = get_random_bytes(28)

with this:

   now = hires_time(); // clock_gettime(), or concatenate time()
                       // with a CPU timer, or process
                       // uptime, or whatever.
   key = get_random_bytes(32);
   Random = hmac_sha256(key, now);

This approach is better than the status quo on the following
counts:

   * It doesn't leak your view of the current time, assuming that
     your PRNG isn't busted.

   * It actually fixes the problem that gmt_unix_time purported to
     fix, by using a high-resolution time that's much less likely to
     be used twice.  Even if the PRNG is broken, the value is still
     nonrepeating.

It is not worse than the status quo:

   * It is unpredictable from an attacker's POV, assuming that the
     PRNG works.  (Because an HMAC, even of known data, with an
     unknown random key is supposed to look random).


CONSIDERATIONS:

I'd personally suggest proposal 1 (just set the field at random) for
most users.  Yes, it makes things a little worse if your PRNG can
generate repeat values... but nearly everything in cryptography
fails if your PRNG is broken.


You might want to apply this fix on clients only.  With a few
exceptions (like hidden services) the server's view of the current
time is not sensitive.


Implementors might want to make this feature optional and
on-by-default, just in case some higher-level application protocol
really does depend on it.
==================================================================