On 23 Dec 2015, at 03:59, Nick Mathewson <nickm@alum.mit.edu> wrote:

On Mon, Nov 30, 2015 at 2:12 AM, Tim Wilson-Brown - teor
<teor2345@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:

Looks good, I particularly like the way we test it on every (medium-term) connection.

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.

What is the minimum / recommended / set length of rekey_data?

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.

Do we want to randomise the number of cells before a rekey?

(I can imagine that rekeying might have a detectable timing / traffic pattern, but I'm not sure if that matters.)

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