Draft document and notes from rransom: requirements for circuit crypto

Robert Ransom rransom.8774 at gmail.com
Mon Jan 10 09:49:40 UTC 2011


On Sat, 18 Dec 2010 01:23:49 -0500
Nick Mathewson <nickm at torproject.org> wrote:

> On Tue, Dec 14, 2010 at 11:35 PM, Nick Mathewson <nickm at torproject.org> 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 316 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20110110/602709cf/attachment.pgp>


More information about the tor-dev mailing list