[tor-dev] RFC: AEZ for relay cryptography, v2

[Nick Mathewson]

On Mon, Nov 30, 2015 at 2:12 AM, Tim Wilson-Brown - teor
<teor2345 at gmail.com> wrote:
> Hi Nick,
>
> The AEZ paper says:
>
> "We impose a limit that AEZ be used for at most 2^48 bytes of data (about
> 280 TB); by that time, the user should rekey. This usage limit stems from
> the existence of birthday attacks on AEZ, as well as the use of AES4 to
> create a universal hash function."
>
> http://web.cs.ucdavis.edu/~rogaway/aez/rae.pdf
>
> Since we change the tweak for every cell, do we have to be worried about
> this limit?
> (Regardless of the tweak change, we are keeping the key constant, and using
> the same key forwards and backwards.)
>
> It seems to me that the 280 TB limit so large that we don't have to worry
> about it being reached in any real-world circuit.
> But I'm not sure of the maximum data volumes or lifetimes of current Tor
> circuits.
>
> Should we include a method of rekeying in the Tor AEZ specification, in case
> the recommended limit is reduced in future?

How's this:

2.3. Key rotation

   According to the AEZ paper, we should re-key after 280 TB.  Let's
   conservatively say that we should re-key every ~4 billion cells (about
   2 GB.

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

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

   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 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.

   I recommend that, to make sure this code works, clients be set up to
   rekey after e.g. the first 128Kb, and then every 2**32 cells thereafter.

   Note that the cell_number cell counter does not reset even when the key is
   rotated.