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