Draft document and notes from rransom: requirements for circuit crypto

[Nick Mathewson]

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.

(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