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 doc/spec/proposals/ideas/xxx-crypto-requirements.txt.
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 documents. === Title: Requirements for Tor's circuit cryptography 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). 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. 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. 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. =========== 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.) 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. Other questions: * 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 the future? * How do we transition directory identity key cryptosystems, now and in the future?
