- tor-dev - lists.torproject.org

Re: [tor-dev] tor-dev Digest, Vol 60, Issue 2
by Flipchan 04 Jan '16

04 Jan '16

How would u add quantum-safe crypto? I havent seen anyone puttin a pub lib that anyone can import tor-dev-request(a)lists.torproject.org skrev: (2 januari 2016 13:00:02 CET) >Send tor-dev mailing list submissions to > tor-dev(a)lists.torproject.org > >To subscribe or unsubscribe via the World Wide Web, visit > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev >or, via email, send a message with subject or body 'help' to > tor-dev-request(a)lists.torproject.org > >You can reach the person managing the list at > tor-dev-owner(a)lists.torproject.org > >When replying, please edit your Subject line so it is more specific >than "Re: Contents of tor-dev digest..." > > >Today's Topics: > > 1. Re: Quantum-safe Hybrid handshake for Tor (Ryan Carboni) > 2. Re: Quantum-safe Hybrid handshake for Tor (Yawning Angel) > > >---------------------------------------------------------------------- > >Message: 1 >Date: Fri, 1 Jan 2016 19:33:31 -0800 >From: Ryan Carboni <ryacko(a)gmail.com> >To: tor-dev(a)lists.torproject.org >Subject: Re: [tor-dev] Quantum-safe Hybrid handshake for Tor >Message-ID: > <CAO7N=i2MspE1N5eOczCyT9RCPORgUJboSOY3vUMGKL5FSzAPnw(a)mail.gmail.com> >Content-Type: text/plain; charset="utf-8" > >The first step should be replacing the long-term keys with quantum-safe >crypto. >

5 6

Go version in Gitian descriptors
by Jeremy Rand 04 Jan '16

04 Jan '16

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 Hello, I noticed that it looks like Tor Project is using Go 1.4.2 to build the pluggable transports in Gitian. I'm curious why a newer version of Go isn't used. My understanding is that Go 1.4.2 (or earlier) is needed to build Go 1.5 because 1.5's source code is itself in Go. Would using Go 1.5 be as simple as building 1.4.2 in Gitian (as is done now), and then using 1.4.2 to build 1.5, and then placing 1.5 in PATH instead of 1.4.2 as is done now? Have obstacles been identified in such a configuration, or is it just that no one tried it? Cheers, - -Jeremy Rand -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iQIcBAEBCAAGBQJWifxjAAoJEAHN/EbZ1y0686cP/3kdRz3va8dZ056j4x9k+sd7 XJsfsj9eWJ/tPxdpppPsBIoseTVNrPSCOB/cJ/bc0Xl75KGQkHFsmGusnUp6kg9L bwJK8wcNoO+s5EjjiY/Rk39UQTNJ3YKOaanvUnGXolYy4LtgUTTI7jdSWcpyZmd7 zxQVzvIXQEawgbu9SjTzXFkBQVHkZzkCDmTPcQNEPtIZambj7fFU0EMBWSmrYkVa /Lzz0bq2wMcZBpdMR07JT0WcrXNgkun48gJlBCV2SuScgs+FycmQi1dVCapwptrQ H0WeCv61XnhXTlens60gfhjrXMcUf4Xud2p71pG0N3OYrF8eOJGpSzTdnBnOFNGw IA2B+CB8u6l8PoZAqeJg0qhFjwm/BoG9o8b8WI9WJOvqDsSfo9Mjmr2lfuoxEGI7 /Uu7aZgRboFI899/xfKJUjzZpQs3hVrtpgukjNEShDBBhsZDOQUkbfzw097NttxB Nst6RW8WmRpbvFMGMrLiYrUKxGKJkzOUVaexU2C9y6y5asq3i2qotTmXpzEHkcP0 XL4KR9/JC6MeuBqSszEb2gpcQsHVsPxk7Wo1cJwLDSeS2YniZnxlpre5DjF2Exez H54PqwtXTezThc8TZuTzfJZrkOA/X5ggL7/wnpUaDrF8T9r4fn1rosP6m8PdUeOL RhVNDX3NeTjV6KywVJX4 =ELuw -----END PGP SIGNATURE-----

5 4

Re: [tor-dev] Quantum-safe Hybrid handshake for Tor
by Ryan Carboni 04 Jan '16

04 Jan '16

Wasn't there a transition period in migrating from RSA to ECC? Maybe I'm just confused. Or you are confused. But I think it is best plan for a five or ten year transition period.

1 0

Re: [tor-dev] Quantum-safe Hybrid handshake for Tor
by Ryan Carboni 04 Jan '16

04 Jan '16

> > We had a GSOC project to produce "consensus diffs", so that clients could download the differences between each consensus each hour, rather than downloading a full consensus (~1.5MB). > > It showed some great results, but still needs a little work before we merge it.https://trac.torproject.org/projects/tor/ticket/13339 <https://trac.torproject.org/projects/tor/ticket/13339> > > Still, one doesn't need to download the full consensus. 3/16ths of the consensus could work and would be more beneficial for low bandwidth clients. If Tor became popular, it wouldn't be usable. Right now it consumes the bandwidth of several colleges. If Tor got anywhere near consuming the bandwidth and popularity of a major datacenter (such as the five million user botnet spike of 2013), Tor wouldn't work too well. Facebook has hundreds of millions of active users. A few billion people live under a dictatorship. How well would Tor work if it's infrastructure and usage was scaled up a hundred times? It's not an immediate issue, but if one was to add quantum cryptography, this would be one of the issues that needs to be addressed (as it is one of many long-term issues). nb: Migrating to X448 would possibly hold up longer than Curve25519 > would since it requires a bigger quantum computer. But performance > isn't that great without using vectorization. > > Given the slow time it takes to roll things out, a timeline which begins with trusted directory keys include post-quantum crypto first, and which ends in enabling clients to use post-quantum crypto would be best.

3 2

Re: [tor-dev] Quantum-safe Hybrid handshake for Tor
by Ryan Carboni 03 Jan '16

03 Jan '16

And yet the NSA is moving to prime numbers. A large public key isn't a very good reason to not adopt quantum-safe crypto, it just means that it requires having the Tor project to be able to scale to a larger degree. I suggest hash tables, a percentage of which are pseudorandomly downloaded. Otherwise the Tor project won't scale to 10x the relays ... even ignoring quantum cryptography.

4 4

trac account 'proper' - Full Disclosure
by Patrick Schleizer 02 Jan '16

02 Jan '16

Hi, I've learned that using the trac account 'proper' [1] has lead to some confusion and/or curiosity. That account name is really old, it's been created while I was still anonymous. Tickets created by the trac account are created by me, Patrick Schleizer, nickname adrelanos. The arguments made in these tickets should stand or fall independently of my identity. Those are either of interest for me personally, for my general contribution to Libre Software and/or for the Whonix project. >From now, I will be using my new trac account 'adrelanos'. Cheers, Patrick [1] https://trac.torproject.org/projects/tor/query?reporter=proper&col=id&col=s…

2 1

Re: [tor-dev] Quantum-safe Hybrid handshake for Tor
by Ryan Carboni 02 Jan '16

02 Jan '16

The first step should be replacing the long-term keys with quantum-safe crypto.

2 1

Proposal 262: Re-keying live circuits with new cryptographic material
by Nick Mathewson 29 Dec '15

29 Dec '15

[Proposal 261 probably needs this.] Filename: 262-rekey-circuits.txt Title: Re-keying live circuits with new cryptographic material Author: Nick Mathewson Created: 28 Dec 2015 Status: Open 1. Summary and Motivation Cryptographic primitives have an upper limit of how much data should be encrypted with the same key. But currently Tor circuits have no upper limit of how much data they will deliver. While the upper limits of our AES-CTR crypto is ridiculously high (on the order of hundreds of exabytes), the AEZ crypto we're considering suggests we should rekey after the equivalent in cells after around 280 TB. 280 TB is still high, but not ridiculously high. So in this proposal I explain a general mechanism for rekeying a circuit. We shouldn't actually build this unless we settle on 2. RELAY_REKEY cell operation To rekey, the circuit initiator ("client") can send a new RELAY_REKEY cell type: struct relay_rekey { u16 rekey_method IN [0, 1]; u8 rekey_data[]; } const REKEY_METHOD_ACK = 0; const REKEY_METHOD_SHAKE128_CLIENT = 1; This cell means "I am changing the key." The new key material will be derived from SHAKE128 of the aez_key concatenated with the rekey_data field, to fill a new shake_output structure. The client should set rekey_data at random. After sending one of these RELAY_REKEY cells, the client uses the new aez_key to encrypt all of its data to this hop, but retains the old aez_key for decrypting the data coming back from the relay. When the relay receives a RELAY_REKEY cell, it sends a RELAY_REKEY cell back towards the client, with empty rekey_data, and relay_method==0, and then updates its own key material for all additional data it sends and receives to the client. When the client receives this reply, it can discard the old AEZ key, and begin decrypting subsequent inbound cells with the new key. So in summary: the client sends a series of cells encrypted with the old key, and then sends a REKEY cell, followed by relay cells encrypted with the new key: OldKey[data data data ... data rekey] NewKey[data data data...] And after the server receives the REKEY cell, it stops sending relay cells encrypted with the old keys, sends its own REKEY cell with the ACK method, and starts sending cells encrypted with the new key. REKEY arrives somewhere in here I V OldKey[data data data data rekey-ack] NewKey[data data data ...] 2.1. Supporting other cryptography types Each relay cipher must specify its own behavior in the presence of a REKEY cell of each type that it supports. In general, the behavior of method 1 ("shake128-client") is "regenerate keys as if we were calling the original KDF after a CREATE handshake, using SHAKE128 on our current static key material and on a 32-byte random input." The behavior of any unsupported REKEY method must be to close the circuit with an error. The AES-CTR relay cell crypto doesn't support rekeying. See 3.2 below if you disagree. 2.2. How often to re-key? Clients should follow a deterministic algorithm in deciding when to re-key, so as not to leak client differences. This algorithm should be type-specific. For AEZ, I recommend that clients conservatively rekey every 2**32 cells (about 2 TB). And to make sure that this code actually works, the schedule should be after 2**15 cells, and then every 2**32 cells thereafter. It may be beneficial to randomize these numbers. If so, let's try subtracting between 0 and 25% at random. 2.3. How often to allow re-keying? We could define a lower bound to prevent too-frequent rekeying. I'm not sure I see the point here; the process described above is not that costly. 3. Alternative designs 3.1. Should we add some public key cryptography here? We could change the body of a REKEY cell and its ack to be more like CREATE/CREATED. Then we'd have to add a third step from the client to the server to acknowledge receipt of the 'CREATED' cell and changing of the key. So, what would this added complexity and computational load buy us? It would defend against the case where an adversary had compromised the shared key material for a circuit, but was not able to compromise the rekey process. I'm not sure that this is reasonable; the likeliest cases I can think of here seem to be "get compromised, stay compromised" for a circuit. 3.2. Hey, could we use this for forward secrecy with AES-CTR? We could, but the best solution to AES-CTR's limitations right now is to stop using our AES-CTR setup. Anything that supports REKEY will also presumably support AEZ or something better. 3.3. We could upgrade ciphers with this! Yes we could. We could define this not only to change the key, but to upgrade to a better ciphersuite. For example, we could start by negotiating AES-CTR, and then "secretly" upgrade to AEZ. I'm not sure that's worth the complexity, or that it would really be secret in the presence of traffic analysis.

2 1

Proposal 261: AEZ for relay cryptography
by Nick Mathewson 29 Dec '15

29 Dec '15

[Okay, I'm pulling this out of draft stage. Still not sure this is the right primitive, but I'm pretty sure this would be about the right way to do it.] Filename: 261-aez-crypto.txt Title: AEZ for relay cryptography Author: Nick Mathewson Created: 28 Oct 2015 Status: Open 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 SHAKE256 to derive the following output: struct shake_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_val_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 = AES(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 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. Two keys. We could have a separate AEZ key for forward and backward encryption. This would use more space, however. 4.2. Authenticating things differently In computing the AD, we could replace xor with concat. In computing the AD, we could replace CELL_CHAIN_BYTES with 16, or 509. (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. Other hashes. We could update the ntor definition used in this to use a better hash than SHA256 inside. 4.4. Less predictable plaintext. 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 might help a little, in a really doofy way. A.1. Performance notes: memory requirements Let's ignore Tor overhead here, but not openssl overhead. IN THE CURRENT PROTOCOL, the total memory required at each relay is: 2 sha1 states, 2 aes states. Each sha1 state uses 96 bytes. Each aes state uses 244 bytes. (Plus 32 bytes counter-mode overhead.) This works out to 704 bytes at each hop. IN THE PROTOCOL ABOVE, using an optimized AEZ implementation, we'll need 128 bytes for the expanded AEZ key schedule. We'll need another 244 bytes for the AES key schedule for the chain key. And there's 32 bytes of chaining values. This gives us 404 bytes at each hop, for a savings of 42%. If we used separate AES and AEZ keys in each direction, we would be looking at 776 bytes, for a space increase of 10%. A.2. Performance notes: CPU requirements on AESNI hosts The cell_ops benchmark in bench.c purports to tell us how long it takes to encrypt a tor cell. But it wasn't really telling the truth, since it only did one SHA1 operation every 2^16 cells, when entries and exits really do one SHA1 operation every end-to-end cell. I expanded it to consider the slow (SHA1) case as well. I ran this on my friendly OSX laptop (2.9 GHz Intel Core i5) with AESNI support: Inbound cells: 169.72 ns per cell. Outbound cells: 175.74 ns per cell. Inbound cells, slow case: 934.42 ns per cell. Outbound cells, slow case: 928.23 ns per cell. Note that So for an n-hop circuit, each cell does the slow case and (n-1) fast cases at the entry; the slow case at the exit, and the fast case at each middle relay. So for 3 hop circuits, the total current load on the network is roughly 425 ns per hop, concentrated at the exit. Then I started messing around with AEZ benchmarks, using the aesni-optimized version of AEZ on the AEZ website. (Further optimizations are probably possible.) For the AES256, I used the usual aesni-based aes construction. Assuming xor is free in comparison to other operations, and CELL_CHAIN_BYTES=32, I get roughly 270 ns per cell for the entire operation. If we were to pick CELL_CHAIN_BYTES=509, we'd be looking at around 303 ns per cell. If we were to pick CELL_CHAIN_BYTES=509 and replace XOR with CONCAT, it would be around 355 ns per cell. If we were to keep CELL_CHAIN_BYTES=32, and remove the AES256-chaining, I see values around 260 ns per cell. (This is all very spotty measurements, with some xors left off, and not much effort done at optimization beyond what the default optimized AEZ does today.) A.3. Performance notes: what if we don't have AESNI? Here I'll test on a host with sse2 and ssse3, but no aesni instructions. From Tor's benchmarks I see: Inbound cells: 1218.96 ns per cell. Outbound cells: 1230.12 ns per cell. Inbound cells, slow case: 2099.97 ns per cell. Outbound cells, slow case: 2107.45 ns per cell. For a 3-hop circuit, that gives on average 1520 ns per cell. [XXXX Do a real benchmark with a fast AEZ backend. First, write one. Preliminary results are a bit disappointing, though, so I'll need to invetigate alternatives as well.]

2 1

RFC: AEZ for relay cryptography, v2
by Nick Mathewson 29 Dec '15

29 Dec '15

[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 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. Two keys. We could have a separate AEZ key for forward and backward encryption. This would use more space, however. 4.2. Authenticating things differently In computing the AD, we could replace xor with concat. In computing the AD, we could replace CELL_CHAIN_BYTES with 16, or 509. (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. Other hashes. We could update the ntor definition used in this to use a better hash than SHA256 inside A.1. Performance notes: memory requirements Let's ignore Tor overhead here, but not openssl overhead. IN THE CURRENT PROTOCOL, the total memory required at each relay is: 2 sha1 states, 2 aes states. Each sha1 state uses 96 bytes. Each aes state uses 244 bytes. (Plus 32 bytes counter-mode overhead.) This works out to 704 bytes at each hop. IN THE PROTOCOL ABOVE, using an optimized AEZ implementation, we'll need 128 bytes for the expanded AEZ key schedule. We'll need another 244 bytes for the AES key schedule for the chain key. And there's 32 bytes of chaining values. This gives us 404 bytes at each hop, for a savings of 42%. If we used separate AES and AEZ keys in each direction, we would be looking at 776 bytes, for a space increase of 10%. A.2. Performance notes: CPU requirements on AESNI hosts The cell_ops benchmark in bench.c purports to tell us how long it takes to encrypt a tor cell. But it wasn't really telling the truth, since it only did one SHA1 operation every 2^16 cells, when entries and exits really do one SHA1 operation every end-to-end cell. I expanded it to consider the slow (SHA1) case as well. I ran this on my friendly OSX laptop (2.9 GHz Intel Core i5) with AESNI support: Inbound cells: 169.72 ns per cell. Outbound cells: 175.74 ns per cell. Inbound cells, slow case: 934.42 ns per cell. Outbound cells, slow case: 928.23 ns per cell. Note that So for an n-hop circuit, each cell does the slow case and (n-1) fast cases at the entry; the slow case at the exit, and the fast case at each middle relay. So for 3 hop circuits, the total current load on the network is roughly 425 ns per hop, concentrated at the exit. Then I started messing around with AEZ benchmarks, using the aesni-optimized version of AEZ on the AEZ website. (Further optimizations are probably possible.) For the AES256, I used the usual aesni-based aes construction. Assuming xor is free in comparison to other operations, and CELL_CHAIN_BYTES=32, I get roughly 270 ns per cell for the entire operation. If we were to pick CELL_CHAIN_BYTES=509, we'd be looking at around 303 ns per cell. If we were to pick CELL_CHAIN_BYTES=509 and replace XOR with CONCAT, it would be around 355 ns per cell. If we were to keep CELL_CHAIN_BYTES=32, and remove the AES256-chaining, I see values around 260 ns per cell. (This is all very spotty measurements, with some xors left off, and not much effort done at optimization beyond what the default optimized AEZ does today.) A.3. Performance notes: what if we don't have AESNI? Here I'll test on a host with sse2 but no aesni instructions. [....XXXX writeme ....]

3 5