[tor-dev] Request for comment: AEZ for relay cryptography
Lluís
2015.msl at gmail.com
Wed Oct 21 08:12:16 UTC 2015
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
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
>
More information about the tor-dev
mailing list