[tor-dev] RFC: AEZ for relay cryptography, v2

[Nick Mathewson]

[This is an improvement over my last draft in this area; it makes
concrete proposals about forward secrecy and chaining, and tries to
start getting performance numbers for some platforms. I still need to
compute plausible performance numbers on non-aesni platforms, but I
might not get to that immediately.  For the last draft, see
https://www.mail-archive.com/tor-dev@lists.torproject.org/msg07104.html
.]

Filename: xxx-aez-relay.txt
Title: AEZ for relay cryptography
Author: Nick Mathewson
Created: 13 Oct 2015
Last-changed: 29 Nov 2015
Status: Draft

0. History

   I wrote the first draft of this around October.  This draft takes a
   more concrete approach to the open questions from last time around.

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 use SHAKE128 to derive the
   following output:

 struct hkdf_output {
 u8 aez_key[48];
 u8 chain_key[32];
 u8 chain_val_forward[16];
 u8 chain_val_backward[16];
 };

   The first two two fields are constant for the lifetime of the
   circuit.

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:

   Let Chain denote chain_val_forward if this is a forward cell
  or chain_forward_backward otherwise.

   tau = 0

   # We set tau=0 because 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.

   Define CELL_CHAIN_BYTES = 32

   AD = [ XOR(prev_plaintext[:CELL_CHAIN_BYTES],
  prev_ciphertext[:CELL_CHAIN_BYTES]),
  Chain ]

   # Using the previous cell's plaintext/ciphertext as additional data
   # guarantees that any corrupt ciphertext received will corrupt the
   # plaintext, which will corrupt all future plaintexts.

   Set Chain = AES256(chain_key, Chain) xor Chain.

   # This 'chain' construction is meant to provide forward
   # secrecy.  Each chain value is replaced after each cell with a
   # (hopefully!) hard-to-reverse construction.

   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, and far better
   than what we're doing now.  See performance appendix.

   It seems secure-ish too.  Several cryptographers I know seem to
   think 

Re: [tor-dev] Graphs - Estimated Traffic Capacity

[David Fifield]

On Fri, Nov 20, 2015 at 01:38:56PM -0500, David Goulet wrote:
> Anyway, if you think this algorithm could be improved, please respond. If you
> think this algorithm is wrong, please respond. If you can reproduce the result
> on your own with this algo, omg please respond! :) The above could be totally
> wrong but hopefully we did a fairly good job. Please remember, this is an
> estimate. :)

I would be interested to see the capacity by pluggable transport: how
much headroom each PT has and which ones need more bridges.

I tried it a few months ago but I didn't have the idea of looking at the
read/write bytes history. I tried using measured/advertised bandwidth
and using the speed of consensus downloads from the
dirreq-v3-tunneled-dl line.

[tor-dev] Per-transport bridge bandwidth and bridge counts
https://lists.torproject.org/pipermail/tor-dev/2015-July/009136.html
Using measured bandwidth:
https://people.torproject.org/~dcf/graphs/pt-bandwidth-2015-07-20/pt-bandwidth.png
Using median dirreq-v3-tunneled-dl rate:
https://people.torproject.org/~dcf/graphs/pt-bandwidth-2015-07-20/pt-dl.md.png
Source code:
https://people.torproject.org/~dcf/graphs/pt-bandwidth-2015-07-20.tar.gz
___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

Re: [tor-dev] RFC: AEZ for relay cryptography, v2

[Nick Mathewson]

On Sun, Nov 29, 2015 at 7:06 PM, Tim Wilson-Brown - teor
 wrote:
>
> On 30 Nov 2015, at 09:13, Nick Mathewson  wrote:
> ...
> 2.2. New relay cell payload
> ...
>   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:
>
>   Let Chain denote chain_val_forward if this is a forward cell
>  or chain_forward_backward otherwise.
>
>
> chain_val_backward?

Yes, whoops.

> ...
>
> 3.3. Why _not_ AEZ?
>
>   ...
>
>   THIRD, it's really horrible to try to do it in hardware.
>
>
> This may be considered an advantage against an adversary with the resources
> to employ custom hardware to attempt to break AEZ-based encryption.

Ooh.  Interesting.

> ...
>
> ...
> 4.3. A forward-secure variant.
>
>
> How is this different to what you've specified in the main body of the
> proposal?
>
>
>   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.

Whoops; it's leftover text from an earlier version of the proposal.

-- 
Nick
___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

Re: [tor-dev] RFC: AEZ for relay cryptography, v2

[Tim Wilson-Brown - teor]

> On 30 Nov 2015, at 09:13, Nick Mathewson  wrote:
> ...
> 2.2. New relay cell payload
> ...
>   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:
> 
>   Let Chain denote chain_val_forward if this is a forward cell
>  or chain_forward_backward otherwise.

chain_val_backward?

> ...
> 
> 3.3. Why _not_ AEZ?
> 
>   ...
> 
>   THIRD, it's really horrible to try to do it in hardware.

This may be considered an advantage against an adversary with the resources to 
employ custom hardware to attempt to break AEZ-based encryption.

> ...
> 
> ...
> 4.3. A forward-secure variant.

How is this different to what you've specified in the main body of the proposal?

> 
>   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.
> 
>   …

Tim

Tim Wilson-Brown (teor)

teor2345 at gmail dot com
PGP 968F094B

teor at blah dot im
OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F



signature.asc
Description: Message signed with OpenPGP using GPGMail
___
tor-dev mailing list
tor-dev@lists.torproject.org
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev