On Sat, 18 Dec 2010 01:23:49 -0500 Nick Mathewson <nickm@xxxxxxxxxxxxxx> wrote: > On Tue, Dec 14, 2010 at 11:35 PM, Nick Mathewson <nickm@xxxxxxxxxxxxxx> 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. A client which has opened a circuit to a node with fingerprint KEY-TYPE$FINGERPRINT should be able to use the same command to open a stream at that node to any of the following services: * KEY-TYPE$FINGERPRINT/directory * KEY-TYPE$FINGERPRINT/dns * KEY-TYPE$FINGERPRINT/exit/127.0.0.1/80 * KEY-TYPE$FINGERPRINT/exit/example.com/80 * KEY-TYPE$FINGERPRINT/exit/::1/80 * KEY-TYPE$FINGERPRINT/persistent-circuit * KEY-TYPE$FINGERPRINT/establish-introduce-v0 * HS-EPHEMERAL-KEY-TYPE$HS-EPHEMERAL-FINGERPRINT/introduce-v0 * KEY-TYPE$FINGERPRINT/establish-rendezvous-v0 * rendezvous$RENDEZVOUS-COOKIE/rendezvous-v0 * KEY-TYPE$FINGERPRINT/establish-rendezvous-v1 * HS-EPHEMERAL-KEY-TYPE$HS-EPHEMERAL-FINGERPRINT/rendezvous-v1 A new hidden service protocol should reuse circuit-handshake protocols for the new introduction point mechanism, and should reuse circuit ciphersuites for the new rendezvous point mechanism. > (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.) I have been using the term "circuit ciphersuite" for the layer of cryptography used on RELAY cells, and the term "circuit-extension handshake protocol" for the protocol currently performed using CREATE, CREATED, EXTEND, and EXTENDED cells. A circuit protocol relies on both a circuit ciphersuite and a circuit-extension handshake protocol. > > 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. I agree, but that is not part of the handshake protocol or its cryptographic primitives. That goal relates to the circuit ciphersuite. > > Â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. Indeed. > 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. Some parts of the current Tor protocol (at least the ESTABLISH_INTRO relay cell in the rendezvous protocol) use KH (a value derived from the shared session key produced by the circuit-extension handshake protocol) as a nonce to prevent an attacker from replaying a cell on a later circuit. > > Â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." Circuit ciphersuites also must provide some amount of integrity protection and replay prevention. > 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. This applies to all ephemeral forward-secrecy public keys sent by a *client*. It does not apply to hidden-service identity public keys, or to forward-secrecy keys sent by a relay. > > 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! Robert Ransom
Attachment:
signature.asc
Description: PGP signature