Seems a great challenge !!! Lluís
Nick Mathewson: > [This is a draft proposal; I'm not giving it a number yet. I'm hoping > it'll receive some good advice.] > > Filename: xxx-aez-relay.txt > Title: AEZ for relay cryptography > Author: Nick Mathewson > Created: 13 Oct 2015 > Status: Draft > > 1. Summary and preliminaries > > This proposal describes an improved algorithm for circuit > encryption, based on the wide-block SPRP AEZ. I also describe the > attendant bookkeeping, including CREATE cells, and several > variants of the proposal. > > For more information about AEZ, see > http://web.cs.ucdavis.edu/~rogaway/aez/ > > For motivations, see proposal 202. > > 2. Specifications > > 2.1. New CREATE cell types. > > We add a new CREATE cell type that behaves as an ntor cell but which > specifies that the circuit will be created to use this mode of > encryption. > > [TODO: Can/should we make this unobservable?] > > The ntor handshake is performed as usual, but a different PROTOID is > used: > "ntor-curve25519-sha256-aez-1" > > To derive keys under this handshake, we still use HKDF_SHA256, but we > produce 96 bytes of output: > > struct hkdf_output { > u8 key_forward[48]; > u8 key_backward[48]; > }; > > These two fields are constant for the lifetime of the circuit. (But > see section 4.3 below.) > > (Also see 4.1 for a variant that uses less storage key material.) > > 2.2. New relay cell payload > > We specify the following relay cell payload format, to be used when > the exit node circuit hop was created with the CREATE format in 2.1 > above: > > struct relay_cell_payload { > u32 zero_1; > u16 zero_2; > u16 stream_id; > u16 length IN [0..498]; > u8 command; > u8 data[498]; // payload_len - 11 > }; > > Note that the payload length is unchanged. The fields are now > rearranged to be aligned. The 'recognized' and 'length' fields are > replaced with zero_1, zero_2, and the high 7 bits of length, for a > minimum of 55 bits of unambigious verification. (Additional > verification can be done by checking the other fields for > correctness; AEZ users can exploit plaintext redundancy for > additional cryptographic checking.) > > When encrypting a cell for a hop that was created using one of these > circuits, clients and relays encrypt them using the AEZ algorithm > with the following parameters: > > Key = Kf for forward cells, Kb for backward cells. > > # In theory, we are allowed to use a single key here, but I'm > # > > tau = 0 > > # We want no per-hop ciphertext expansion. Instead we use > # redundancy in the plaintext to authenticate the data. > > Nonce = > struct { > u64 cell_number; > u8 is_forward; > u8 is_early; > } > > # The cell number is the number of relay cells that have > # traveled in this direction on this circuit before this cell. > # ie, it's zero for the first cell, two for the second, etc. > # > # is_forward is 1 for outbound cells, 0 for inbound cells. > # is_early is 1 for cells packaged as RELAY_EARLY, 0 for > # cells packaged as RELAY. > # > # Technically these two values would be more at home in AD > # than in Nonce; but AEZ doesn't actually distinguish N and AD > # internally. > > AD = [ The last 32 bytes of the previous cell's plaintext, > if this is not the first cell sent in this direction on > this circuit ] > > # Using this as additional data guarantees that any corrupt > # ciphertext received will corrupt the plaintext, which will > # corrupt all future plaintexts. Using the last 32 bytes of the > # ciphertext would not have the same property. > > This instantiates a wide-block cipher, tweaked based on the cell > index and direction. It authenticates part of the previous cell's > plaintext, thereby ensuring that if the previous cell was corrupted, > this cell will be unrecoverable. > > > 3. Design considerations > > 3.1. Wide-block pros and cons? > > See proposal 202, section 4. > > 3.2. Given wide-block, why AEZ? > > It's a reasonably fast probably secure wide-block cipher. In > particular, it's performance-competitive with AES_CTR. > > (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.) > > It seems secure-ish too. Several cryptographers I know seem to > think it's likely secure enough, and almost surely at least as > good as AES. > > [There are many other competing wide-block SPRP constructions if > you like. Many require blocks be an integer number of blocks, or > aren't tweakable. Some are slow. Do you know a good one?] > > 3.3. Why _not_ AEZ? > > There are also some reasons to consider avoiding AEZ, even if we do > decide to use a wide-block cipher. > > FIRST it is complicated to implement. As the specification says, > "The easiness claim for AEZ is with respect to ease and versatility > of use, not implementation." > > SECOND, it's still more complicated to implement well (fast, > side-channel-free) on systems without AES acceleration. We'll need > to pull the round functions out of fast assembly AES, which is > everybody's favorite hobby. > > THIRD, it's really horrible to try to do it in hardware. > > FOURTH, it is comparatively new. Although several cryptographers > like it, and it is closely related to a system with a security proof, > you never know. > > FIFTH, something better may come along. > > > 4. Alternative designs > > 4.1. Only one key > > We already use different nonces for the forward and reverse > direction; according to the AEZ design, this is sufficient to > give security, even if K_b and K_f are the same. We could > generate and store only half as much key material by using only a > single key per circuit. > > 4.2. Authenticating things differently > > Adding only _a part of the plaintext_ of the previous cell seems > a little screwy: that's usually easy information to predict. I > believe this is secure, however, since the only purpose here is > to ensure that _if_ the previous cell was corrupted, subsequent > cells will be corrupted too. > > We could authenticate more stuff, however. We could, for > example, authenticate the _entire_ previous ciphertext cell. Or > we could authenticate the last 8 bytes of ciphertext and the > last 24 bytes of plaintext. > > > (Another thing we might dislike about the current proposal is > that it appears to requires us to remember 32 bytes of plaintext > until we get another cell. But that part is fixable: note that > in the structure of AEZ, the AD is processed in the AEZ-hash() > function, and then no longer used. We can compute the AEZ-hash() > to be used for the next cell after each cell is en/de crypted.) > > 4.3. A forward-secure variant. > > We might want the property that after every cell, we can forget > some secret that would enable us to decrypt that cell if we saw > it again. > > One way to do this, at a little extra expense, is to keep a 16 or > 32 byte 'chaining' value that changes after each cell. The > initial chaining value in each direction would be another output > of the HKDF. We could use it as an extra AD for the AEZ > encryption. > > To update the chaining value, we need a one-way function. One > option would be your-favorite-hash-function; blake2b isn't _that_ > bad, right? > > We could also try to XOR it with a function of some hidden value > from AEZ: E(S,-1,?) is promising, but it would require that we > get our hands inside of our AEZ implementation. Also it would > require a real cryptographer to come up with it. :) > > A more severe option is to update the entire key after each > cell. This would conflict with 4.1 above, and cost us a bit more. > > A positively silly option would be to reserve the last X bytes of > each relay cell's plaintext for random bytes, if they are not > used for payload. This would help forward secrecy a little, in a > really doofy way. > > Any other ideas? > > 4.4. SHA256 is stupid > > We could update the ntor definition used in this to use blake2b as > its tweakable hash and for its KDF as well. > > (This would be faster _and_ more secure, not only because blake2b > is lots faster than SHA256, but also because we could use the > personalization and salt and key features of blake2b to avoid > HMAC.) > > Or there's sha3 I guess if you want to do that. > _______________________________________________ > tor-dev mailing list > [email protected] > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev > _______________________________________________ tor-dev mailing list [email protected] https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
