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

[isis]

Nick Mathewson transcribed 3.1K bytes:
> 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.

I should take a closer look at using AEZ w.r.t. leaky pipes and loose-source
routing.  However, my inclination is to say that, when using the leaky pipe
feature, you can still talk to any node in the circuit simply by ensuring
that, when that node decrypts it, the 16(ish) zeros come out as expected.

Similarly, for loose-source routed circuits, since (essentially) all cells
arriving (in either direction) at a node which is utilising the loose-source
feature are processed as "unrecognised" — regardless of whether or not they
are actually recognised — also nothing should change (except for the increased
forgery resistance that Nick mentioned).

Ex. 1: Alice is building her circuit through Bob the Bridge, and Bob uses
Bridge Guards.  Alice would like to extend to Charlie, and so she sends an
EXTEND2 inside a RELAY_EARLY to Bob which says so.  Bob recieves this, does
AEZ_Decrypt([…]) on the RELAY_EARLY cell, notices that the 16(ish) bytes at
the end are zeros, and consequently updates the circuit's digest.  Finally Bob
forwards the cell through the the leaky pipe towards the Bridge Guard (mostly)
regardless of whether the cell was "recognised".  (Cf. proposal #188 §3.1.1
steps 6.a. and 6.c., but nothing should really change with the switch to AEZ
as far as I can tell.)

-- 
 ♥Ⓐ isis agora lovecruft
_________________________________________________________
OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35
Current Keys: https://blog.patternsinthevoid.net/isis.txt
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 1240 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20151018/4fde7078/attachment.sig>