- tor-dev - lists.torproject.org

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

Scaling Tor Metrics, Round 2
by Karsten Loesing 28 Dec '15

28 Dec '15

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi everyone, I posted some thoughts on Scaling Tor Metrics [0] almost two weeks ago and received very useful feedback from George, David, Thomas, and Letty. Thanks for that! In fact, this is such a big topic and this was so much feedback that I decided not to respond to every idea individually but instead start over and suggest a new plan that incorporates all feedback I saw. Otherwise, I'd be worried that we'd lose ourselves in the details and miss the big picture. Maybe this also makes this topic somewhat easier to follow and respond to, which I hope many people will do. The problem to solve is still that the Tor Metrics website has a huge product backlog and that we want it to remain "the primary place to learn interesting facts about the Tor network", either by making it better and bigger internally, or by adding more ways to let others contribute to it externally. - From the feedback in round 1, I observe three major areas where we need to improve Tor Metrics: 1 Metrics frontend 2 Metrics backend 3 External contributions There are low-hanging fruit in each area, but there are many fruit overall and some are hanging higher than we might think. I'll go through them area by area and assign numbers to the tasks. 1 Metrics frontend The frontend is the part of the Tor Metrics website that takes pre-aggregated data in the .csv format as input and produces somewhat interactive visualizations. The current frontend uses Java servlets/JSP as web framework and R/ggplot2 for graphs. This code is hard to extend, even for me, and the result isn't pretty, but therefore the website doesn't require any JavaScript. So, one task would be: #1 decide whether we can still ignore JavaScript and what it has to offer. I agree that D3.js is cool, I even used it myself in the past, though I know very little about it. This decision would mean that we develop new visualizations in D3.js and phase out the existing R/ggplot2 visualizations one by one. This is a tough decision, but one with a lot of potential. I understand how we're excited about this as developers, but I'd want to ask Metrics users about this first. Another task would be: #2 website redesign. In fact, what you see on the website right now is a redesign half-way through. Believe me, the website was even less readable a year or two ago, and this statement alone tells you how slow things are moving. But the remaining step is just to replace the start page with a gallery, well, and to apply a Bootstrap design to everything, because why not. One challenge here is that the current graphs all look quite similar making them hard to distinguish in a gallery, but that's probably still more useful than putting text there. It sounds like Letty and Thomas might be willing to help out with this, which would be great. Yet another task would be: #3 replace the website framework with something more recent. This can be something simple, as long as it supports some basic filtering and maybe searching on the start page. I'd say let's pick something Python-based here. However, maybe we should first replace the existing graphs that are deeply tied into the current website framework. If we switch to D3.js and have replaced all existing graphs, this switch to a new website framework will hurt a lot less. Another high-hanging fruit would be: #4 build something like Thomas' Visionion, where users can create generic visualizations on the fly. This is an exciting idea, really, but I think we have to accept that it's out of reach for now. 2 Metrics backend The backend of Tor Metrics consists of a bunch of programs that run once per day to fetch new data from CollecTor and produce a set of .csv files for the frontend. There are no strict requirements to languages and databases, as long as tools are available in Debian stable. Some programs use PostgreSQL, but most of them just use files. Ironically, it's the database-based tools that have major performance problems, whereas the file-based ones work just fine. Most programs are written in Java, very few in Python. One rather low-hanging fruit would be: #5 document backend programs and say what's required to add one more to the bunch. The biggest challenge in writing such a program is that it needs to stay reasonably fast even over the next couple of years and even if the network doubles or triples in size. I started documenting things a while ago, but got distracted by other things. I wouldn't mind help. Another rather low-hanging fruit would be: #6 use Big Data to produce pre-aggregated data for the frontend. As said before, it doesn't matter whether a backend program uses files or PostgreSQL or another database engine. What matters is that it reads data from CollecTor and produces a data that the frontend can use. This could be a CSV or JSON file. We should probably pick the next visualization project as test case for applying Big Data tools, or we could rewrite one that needs to be rewritten for performance reasons anyway. Here's a not-so-low-hanging fruit for the backend: #7 have the backend provide an API to the frontend. This is potentially more difficult. The part that I'm very much afraid of is performance. It's just too easy to build a tool that performs reasonable during testing but that can't handle the load of 10 or 100 people looking at a frontend visualization at once. In particular, it's easy to build an API that works just fine and then add another feature that looks harmless, which later turns out to hurt performance a lot. I'd say postpone. 3 External contributions Most of the discussion in round 1 circled around how external contributions are great, but that they need to be handled with care. I understand the risks here, and I think I'll postpone the part where we're including externally developed websites after "redressing" them. Let's instead try to either keep those contributions as external links or properly integrate them into Tor Metrics. The lowest-hanging fruit here is: #8 keep adding links to external websites as we already do, assuming that we clearly mark these contributions as external. Another low-hanging fruit is: #9 add static data or static graphs. I heard a single +1, but I guess once we have concrete suggestions what data or graphs to add, we'll have more discussion. That's fine. One important and still somewhat low-hanging fruit is: #10 give external developers more support when developing visualizations that could later be added to Metrics. This requires better documentation, but it also requires making it easier to install Tor Metrics locally and test new additions before submitting them. The latter is a good goal, but we're not there yet. The documentation part doesn't seem crazy though. David, if you don't mind being the guinea pig yet once more, I'd want to try this out with your latest visualizations. This is pending on the JavaScript decision though. Now to the higher-hanging fruit: #11 Build or adapt a tool like Munin to prototype new visualizations quickly. I didn't fully understand how Munin makes it easier to prototype a visualization than just writing a Python/Stem script for the data pre-processing and using any graphing engine for the visualization. But maybe there's something to learn here. Still, this seems like a quite high goal at the moment. Another one: #12 provide a public API like Onionoo but for Metrics data. This seems somewhat out of reach for the moment. It's a cool idea, but doing it right is not at all trivial. I'd want to put this to the lower end of the list. Another high-hanging fruit: #13 adapt the Gist idea where external contributors write some code that magically turn into new visualizations. I think that most new visualizations require writing backend code to aggregate different parts of the available data or to aggregate the same data differently. It's a neat idea that external contributors could simply write some code that then magically turns into new visualizations. But I think it's a long way until we're there. 4 Summary Here's the list of low-hanging fruit: #1 decide whether we can still ignore JavaScript #2 website redesign #5 document backend programs #6 use Big Data to produce pre-aggregated data #8 keep adding links to external websites #9 add static data or static graphs #10 give external developers more support And here are the tasks that I think we should postpone a bit longer: #3 replace the website framework #4 build something like Thomas' Visionion #7 have the backend provide an API to the frontend #11 Build or adapt a tool like Munin #12 provide a public API like Onionoo but for Metrics data #13 adapt the Gist idea How does this sound? What did I miss (sorry!), on a high level without going into all the details just yet? Who wants to help? All the best, Karsten [0] https://lists.torproject.org/pipermail/tor-dev/2015-November/009983.html -----BEGIN PGP SIGNATURE----- Comment: GPGTools - http://gpgtools.org iQEcBAEBAgAGBQJWZFnNAAoJEJD5dJfVqbCrowMIAIcx5kd7BfHN9HsgEj+JZ6e6 YsIUfrrCcTeMlZyHHG9amWodac+spE11fZCAkZ2B2gYf8I6KT23pex4w23WCVlxo 0qq5pZSADedAYBsocEhZLh2bZyzIhEPueGJW2/HeyW2Smd9T+YJ8hA1kkoebX/Xv xb/2051bc48sQW767gst3ClTv4va8+24pKytJxvfRYDrs3xv3VxPlyCvLsrgz9ji pnxd2C+Syo4sT3vHFb9JNhvd1ZaEmqjXBzywQ2SNnOqZNQE77zfvB766FFSJEg6a MMgwt0RcjElTnZRZR2utA2WLYzJDiof4ULfw51xoYYcT6kmGQw9IOqOuzgBvSr4= =Yo+I -----END PGP SIGNATURE-----

4 12