On Tue, Dec 14, 2010 at 11:35 PM, Nick Mathewson <[email protected]> wrote:
I'm going to try to kick off discussion here in hopes of moving the design effort forward. I don't have the crypto chops of Robert, so I'm hoping that people with more experience in formal cryptography can have a look here too. > === > Title: Requirements for Tor's circuit cryptography This document might morph into a larger "requirements for Tor's cryptography" document, or one of a set of such documents. Unless I'm forgetting something, the other areas of cryptography Tor has are: * link cryptography * directory authentication * hidden-service protocol * hidden-service directory protocol > Author: Robert Ransom > Created: 12 December 2010 > > Overview > > This draft is intended to specify the meaning of 'secure' for a Tor > circuit protocol, hopefully in enough detail that > mathematically-inclined cryptographers can use this definition to > prove that a Tor circuit protocol (or component thereof) is secure > under reasonably well-accepted assumptions. > > Tor's current circuit protocol consists of the CREATE, CREATED, RELAY, > DESTROY, CREATE_FAST, CREATED_FAST, and RELAY_EARLY cells (including > all subtypes of RELAY and RELAY_EARLY cells). So as written, this would make the circuit protocol consist of all hidden service cells too, since they are also RELAY_* cells. Can we exclude them from consideration here? The rendezvous protocol is pretty complicated, and almost wholly orthogonal from the rest of the circuit protocol. (At first I wanted to say that the circuit protocol should consist only of the crypto done to transmit relay cells, and not their contents, but saying that would exclude the contents of RELAY EXTEND cells, which would be silly.) > Tor currently has two > circuit-extension handshake protocols: one consists of the CREATE and > CREATED cells; the other, used only over the TLS connection to the > first node in a circuit, consists of the CREATE_FAST and CREATED_FAST > cells. > > Requirements > 1. Every circuit-extension handshake protocol must provide forward > secrecy -- the protocol must allow both the client and the relay to > destroy, immediately after a circuit is closed, enough key material > that no attacker who can eavesdrop on all handshake and circuit cells > and who can seize and inspect the client and relay after the circuit > is closed will be able to decrypt any non-handshake data sent along > the circuit. > > In particular, the protocol must not require that a key which can be > used to decrypt non-handshake data be stored for a predetermined > period of time, as such a key must be written to persistent storage. It would also be nice if we could do better here: if for example we could re-key an existing circuit and drop the old keys so that the nodes long-lived circuit didn't need to keep the key material needed to decrypt all the stuff they had already received. > 2. Every circuit-extension handshake protocol must specify what key > material must be used only once in order to allow unlinkability of > circuit-extension handshakes. > > 3. Every circuit-extension handshake protocol must authenticate the relay > to the client -- an attacker who can eavesdrop on all handshake and > circuit cells and who can participate in handshakes with the client > must not be able to determine a symmetric session key that a circuit > will use without either knowing a secret key corresponding to a > handshake-authentication public key published by the relay or breaking > a cryptosystem for which the relay published a > handshake-authentication public key. > > 4. Every circuit-extension handshake protocol must ensure that neither > the client nor the relay can cause the handshake to result in a > predetermined symmetric session key. I think you want something a little stronger here; by the literal reading of 4, it's okay if the relay can force _one of two_ keys, but of course that's not okay. Also, what is the problem if the *client* can force a particular session key? If the client is hostile to her own anonymity, then the system is not expected to work. > 5. Every circuit-extension handshake protocol should ensure that an > attacker who can predict the relay's ephemeral secret input to the > handshake and can eavesdrop on all handshake and circuit cells, but > does not know a secret key corresponding to the > handshake-authentication public key used in the handshake, cannot > break the handshake-authentication public key's cryptosystem, and > cannot predict the client's ephemeral secret input to the handshake, > cannot predict the symmetric session keys used for the resulting > circuit. > > 6. The circuit protocol must specify an end-to-end flow-control > mechanism, and must allow for the addition of new mechanisms. > > 7. The circuit protocol should specify the statistics to be exchanged > between circuit endpoints in order to support end-to-end flow control, > and should specify how such statistics can be verified. > > > 8. The circuit protocol should allow an endpoint to verify that the other > endpoint is participating in an end-to-end flow-control protocol > honestly. I note that this doesn't actually say much about the content of RELAY cells themselves. IMO, that's a little cart-before-the-horseish, since the whole point of establishing circuits is to use them to send RELAY cells back and forth. I don't have a complete list, but here's a sketch: * The point of the circuit crypto protocol is to transmit data between the client and the nodes in the circuit so they can handle it appropriately. This data is sent in RELAY cells. Each RELAY cell originated by the client goes to exactly one node on the circuit; each RELAY cell originated by a node on the circuit goes to the client. * Relay cells should get encrypted with one layer of cryptography per node in the circuit. We want a property here something like, "A cell sent by the client cannot be read by anybody but the relay it is intended for; a cell sent by the relay cannot be read by anybody but the client." There's probably more to say here, though we could probably also just incorporate the appropriate part of the design paper by reference and say "it works like that". We might also want to mention some properties that you get for free from the rest of the Tor design, including: * Link crypto exists. * Clients know circuit-establishment public keys (a.k.a onion keys) for all relays they want to use. Also, here are a few more nice-to-have properties that might be worth considering if they can be done without too much trouble. I realize that all of these probably fall under the heading of "Second System" desiderata, but I feel unable to keep myself from writing them down *somewhere*. * It would be nice to make it a little harder for end-to-end bitwise tagging attacks to work. This isn't a huge priority, though, since these are already outside our threat model (as noted in the Tor design paper), and there are plenty of other and less detectable ways to do active and passive end-to-end correlation. * Some work in resisting traffic analysis relies on an ability for _all_ nodes in the circuit to introduce long-range padding in both directions. In our current protocol, only the client can add outbound padding, while each node can only add inbound padding. I'm not putting a high priority on this one personally, since it's only a building block for future work and not actually applicable to anything solid today. * There shouldn't be any high-multiplier DoS attacks against the protocol. In particular, maybe an attacker shouldn't be able to force a node to do an expensive secret-key operation just by sending some undecodable junk data. Proof-of-work might be one way to do this. * The protocol should not be very hard to implement; hard things are error-prone. In particular, it shouldn't require any particular cryptographic algorithm not commonly available in Free/Open Source crypto libraries. > =========== > NOTES: > > > > > All circuit handshake protocols must provide forward security. This > requires that the client send a public key for some asymmetric > protocol that can provide secrecy (RSA, ElGamal, DH, McEliece, > Ajtai-Dwork, Lyubashevsky-Palacio-Segev, etc.) to each node in each > circuit. > > The public keys and public parameters used in different handshakes > must be unlinkable. This will restrict different cryptosystems in > different ways: > > * An RSA or LPS key must be used only once, and then the entire secret > key must be destroyed. > > * An ElGamal or DH key must be used only once, and then the secret > exponent must be destroyed. In addition, if the client generated > the public parameters used by the key, the public parameters must > also be destroyed. (Public parameters published by a third party > may be used multiple times.) To be clear, the above applies only to keys used for forward-secrecy, right? IOW, our current CREATE/CREATED format uses a long-term RSA public key for authentication and encryption of the DH handshake, and a short-term DH handshake to generate the actual key material used for encrypting cells. > special wants to make it impossible for a node in the hidserv > directory DHT to determine the address a hidserv descriptor describes > unless it already knows the address. The problem here is that the > following are absolutely required: > > * Each client must be able to compute, from the hidserv's address and > a public nonce, the DHT retrieval key needed to retrieve the > hidserv's descriptor and any decryption key needed to use the > descriptor. > > * Each hidserv must give each DHT node responsible for its retrieval > key the DHT retrieval key and a descriptor, and must prove to the > DHT node that it knows a secret key which ‘owns’ a hidserv address > which currently ‘owns’ the retrieval key. > > The proof of knowledge of a hidserv secret key is needed not to keep > jerks from crapflooding a DHT node (they can still do that by > generating lots of hidserv secret keys), but to prevent a censor from > overwriting someone else's hidserv descriptor and thereby blocking > access to the hidserv. I want to call all of this hidden service stuff orthogonal for now, but we should come up for it when we're writing requirements and nice-to-haves for > Other questions: > > * What types of attackers should Tor's crypto protect against? > > * What types of attacks should Tor's crypto protect against? My rule of thumb is: attacking the crypto should never be the easiest way to attack Tor users for any attacker. So for attackers and attacks that Tor currently defeats, has a reasonable prospect of evolving to defeat, or aspires to defeat (see the paper and other work on the threat model), the cryptography should be hard enough to attack that they cannot link or trace users. Even for attackers we currently *don't* know how to defeat with today's low-latency anonymity net designs (e.g., those who can do end-to-end correlation attacks against users), the cryptography should be strong enough that attacking it is far more expensive than all their current plausible attacks. (My rationale here is that today's cryptography research can give far more impressive results than today's anonymity research, so we might as well get them.) > * How do we transition relay identity key cryptosystems, now and in > the future? > > * How do we transition directory identity key cryptosystems, now and > in the future? My other proposal draft starts to answer these, I hope. Comments welcome and invited! peace, -- Nick
