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

[Lluís <2015.msl@xxxxxxxxx>]

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@xxxxxxxxxxxxxxxxxxxx
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
> 
_______________________________________________
tor-dev mailing list
tor-dev@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev