Nick Mathewson transcribed 3.1K bytes:
On Tue, Oct 13, 2015 at 8:05 AM, Mike Perry mikeperry@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 nexthop 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.)