[tor-dev] Request for comment: AEZ for relay cryptography
Mike Perry
mikeperry at torproject.org
Tue Oct 13 12:05:00 UTC 2015
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.)
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?
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.
> 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?
--
Mike Perry
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20151013/a052531e/attachment.sig>
More information about the tor-dev
mailing list