[tor-dev] Request for comment: AEZ for relay cryptography

[Nick Mathewson]

On Tue, Oct 13, 2015 at 8:05 AM, Mike Perry <mikeperry at torproject.org> wrote:
> Nick Mathewson:
 [...]
>>      (How fast is it?
>>
>>      To encrypt a 509-byte relay cell with a 16 byte nonce and 32 bytes
>>      of additional data, AEZ only uses 360 aes rounds.  This is the same
>>      number of aes rounds as we'd need to CTR encrypt a 512-byte cell
>>      with 11.25 rounds per block.  AES128 uses 10 rounds per block;
>>      AES256 uses 14 rounds per block.
>>
>>      We could chop out 4 of the AES rounds by optimizing the code
>>      for the tau=0 case, or with AD shenenegans, but that's probably
>>      unwise.
>>
>>      Additionally, we would no longer need to maintain a running SHA-1
>>      of cells.)
>
> Can you explain how the 'recognized' behavior will work in more detail
> with AEZ then? In the current circuit crypto, the shorter recognized
> field is used just as a hint to check the larger SHA-1 hash. But with
> what you specified above, it sounds like there is now only 55 bits with
> which to check for 'recognized' at a hop, before causing some kind of
> (unpredictable?) error condition due to other, later protocol checks
> failing?

Sure!

Currently, the 2-byte 'recognized' field tells us whether to check a
4-byte, truncated SHA1 hash.  That gives 32 bits of resistance vs
forgery, and a one-in-65536 chance of checking the the SHA1 hash when
we don't need to.  (The recognized field doesn't provide any forgery
resistance, since AES-CTR is malleable.)

So the current pseudocode is:
    P_cell = CTR_Decrypt(Key, Ctr, Enc_cell)
    If (P_cell.recognized == 0 &&
           SHA1(sha_state + P_cell)[:4] == P_cell.digest) {
      // Cell is recognized and valid; add P_cell to sha_state and handle it.
    } else {
       // Cell is not recognized or not valid; forward it to the next
hop in the circuit
   }

With this AEZ proposal, we have 55 bits of forgery resistance, since
any attempt to meddle with any bit in the ciphertext will have an
unpredictable affect on all bits on the plaintext.  (It's an SPRP).
So the algorithm is:

    P_cell = AEZ_decrypt(Key, State, Enc_cell)
    If (P_cell.zero_16 == 0 && P_cell.zero_32 == 0 &&
           P_cell.length <= 498) {
      // Cell is recognized and valid; add P_cell to state and handle it.
    } else {
       // Cell is not recognized or not valid; forward it to the next
hop in the circuit.
   }

This represents an _increase_ in our security, since we now have a
much better chance of rejecting random or tampered cells.

> In general, it would also be nice to specify in detail how leaky-pipe
> circuits could still be used without breaking the construction,
> especially as we get closer to chosing which one of these options to
> take. It sounds like some of the options in 4.2 and 4.3 may break it, if
> we're not careful with the implementation.

Sounds good; I'll try to specify how it works.  It's important to add
provisos like "processed at this hop" to most of the descriptions
there, so I should really add pseudocode as appropriate.

best,
-- 
Nick