Draft document and notes from rransom: requirements for circuit crypto

[Nick Mathewson <nickm@xxxxxxxxxxxxxx>]

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?