Draft document and notes from rransom: requirements for circuit crypto
nickm at torproject.org
Wed Dec 15 04:35:03 UTC 2010
Here's a slightly reformatted version of Robert Ransom's current notes
on circuit crypto requirements. If I understand his goals here, he
wants to work out a set of requirements for any revised circuit crypto
protocol s.t. it can be called "secure" for Tor's purposes. With
permission, I'm posting it here and putting it in
I'm also attaching, but not putting in the repo, some additional notes
that Robert's been keeping as he worked along with these. I don't
know that they belong in the tor repo yet, but they've got some neat
thoughts that could be well integrated into some of the other
Title: Requirements for Tor's circuit cryptography
Author: Robert Ransom
Created: 12 December 2010
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). 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
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
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.
2. Every circuit-extension handshake protocol must specify what key
material must be used only once in order to allow unlinkability of
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.
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
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
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
The public keys and public parameters used in different handshakes
must be unlinkable. This will restrict different cryptosystems in
* 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.)
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
* 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.
* What types of attackers should Tor's crypto protect against?
* What types of attacks should Tor's crypto protect against?
* How do we transition relay identity key cryptosystems, now and in
* How do we transition directory identity key cryptosystems, now and
in the future?
More information about the tor-dev