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

[Tim Wilson-Brown - teor]

> On 23 Dec 2015, at 03:59, Nick Mathewson <nickm at alum.mit.edu> wrote:
> 
> 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:

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.

Tim

Tim Wilson-Brown (teor)

teor2345 at gmail dot com
PGP 968F094B

teor at blah dot im
OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20151229/5ebcb9ff/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 842 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20151229/5ebcb9ff/attachment-0001.sig>