[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: Draft document and notes from rransom: requirements for circuit crypto

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,
> > Â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/exit/example.com/80
* KEY-TYPE$FINGERPRINT/persistent-circuit
* KEY-TYPE$FINGERPRINT/establish-introduce-v0
* KEY-TYPE$FINGERPRINT/establish-rendezvous-v0
* rendezvous$RENDEZVOUS-COOKIE/rendezvous-v0
* KEY-TYPE$FINGERPRINT/establish-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.


> 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

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