[tor-dev] Proposal 262: Re-keying live circuits with new cryptographic material

[Nick Mathewson]

[Proposal 261 probably needs this.]

Filename: 262-rekey-circuits.txt
Title: Re-keying live circuits with new cryptographic material
Author: Nick Mathewson
Created: 28 Dec 2015
Status: Open

1. Summary and Motivation

   Cryptographic primitives have an upper limit of how much data should
   be encrypted with the same key.  But currently Tor circuits have no
   upper limit of how much data they will deliver.

   While the upper limits of our AES-CTR crypto is ridiculously high
   (on the order of hundreds of exabytes), the AEZ crypto we're
   considering suggests we should rekey after the equivalent in cells
   after around 280 TB.  280 TB is still high, but not ridiculously
   high.

   So in this proposal I explain a general mechanism for rekeying a
   circuit.  We shouldn't actually build this unless we settle on

2. RELAY_REKEY cell operation

   To rekey, the circuit initiator ("client") can send a new RELAY_REKEY cell
   type:

        struct relay_rekey {
          u16 rekey_method IN [0, 1];
          u8 rekey_data[];
        }

        const REKEY_METHOD_ACK = 0;
        const REKEY_METHOD_SHAKE128_CLIENT = 1;

   This cell means "I am changing the key." The new key material will be
   derived from SHAKE128 of the aez_key concatenated with the rekey_data
   field, to fill a new shake_output structure.  The client should set
   rekey_data at random.

   After sending one of these RELAY_REKEY cells, the client uses the new
   aez_key to encrypt all of its data to this hop, but retains the old
   aez_key for decrypting the data coming back from the relay.

   When the relay receives a RELAY_REKEY cell, it sends a RELAY_REKEY
   cell back towards the client, with empty rekey_data, and
   relay_method==0, and then updates its own key material for all
   additional data it sends and receives to the client.

   When the client receives this reply, it can discard the old AEZ key, and
   begin decrypting subsequent inbound cells with the new key.


   So in summary: the client sends a series of cells encrypted with the
   old key, and then sends a REKEY cell, followed by relay cells
   encrypted with the new key:

     OldKey[data data data ... data rekey] NewKey[data data data...]

   And after the server receives the REKEY cell, it stops sending relay
   cells encrypted with the old keys, sends its own REKEY cell with the
   ACK method, and starts sending cells encrypted with the new key.

       REKEY arrives somewhere in here
                   I
                   V
     OldKey[data data data data rekey-ack] NewKey[data data data ...]

2.1. Supporting other cryptography types

   Each relay cipher must specify its own behavior in the presence of a
   REKEY cell of each type that it supports.  In general, the behavior
   of method 1 ("shake128-client") is "regenerate keys as if we were
   calling the original KDF after a CREATE handshake, using SHAKE128 on
   our current static key material and on a 32-byte random input."

   The behavior of any unsupported REKEY method must be to close the
   circuit with an error.

   The AES-CTR relay cell crypto doesn't support rekeying. See 3.2 below
   if you disagree.

2.2. How often to re-key?

   Clients should follow a deterministic algorithm in deciding when to
   re-key, so as not to leak client differences.  This algorithm should
   be type-specific.  For AEZ, I recommend that clients conservatively
   rekey every 2**32 cells (about 2 TB).  And to make sure that this
   code actually works, the schedule should be after 2**15 cells, and
   then every 2**32 cells thereafter.

   It may be beneficial to randomize these numbers.  If so, let's try
   subtracting between 0 and 25% at random.

2.3. How often to allow re-keying?

   We could define a lower bound to prevent too-frequent rekeying.  I'm
   not sure I see the point here; the process described above is not
   that costly.

3.  Alternative designs

3.1. Should we add some public key cryptography here?

   We could change the body of a REKEY cell and its ack to be more like
   CREATE/CREATED.  Then we'd have to add a third step from the client
   to the server to acknowledge receipt of the 'CREATED' cell and
   changing of the key.

   So, what would this added complexity and computational load buy us?
   It would defend against the case where an adversary had compromised
   the shared key material for a circuit, but was not able to compromise
   the rekey process.  I'm not sure that this is reasonable; the
   likeliest cases I can think of here seem to be "get compromised, stay
   compromised" for a circuit.

3.2. Hey, could we use this for forward secrecy with AES-CTR?

   We could, but the best solution to AES-CTR's limitations right now is
   to stop using our AES-CTR setup.  Anything that supports REKEY will
   also presumably support AEZ or something better.

3.3. We could upgrade ciphers with this!

   Yes we could.  We could define this not only to change the key, but
   to upgrade to a better ciphersuite.  For example, we could start by
   negotiating AES-CTR, and then "secretly" upgrade to AEZ.  I'm not
   sure that's worth the complexity, or that it would really be secret
   in the presence of traffic analysis.