Some draft notes on migrating Tor's ciphersuites

[Nick Mathewson]

On Fri, Dec 31, 2010 at 4:17 PM, Robert Ransom <rransom.8774 at gmail.com> wrote:
> On Sun, 19 Dec 2010 08:46:13 -0500
> Watson Ladd <watsonbladd at gmail.com> wrote:
>
>> On Sat, Dec 18, 2010 at 10:34 PM, Nick Mathewson <nickm at freehaven.net> wrote:
>
>> > You're right that it's important to limit partitioning opportunities
>> > in any protocol revision; I tried to go over that in section 2, but we
>> > shouldn't assume that I've said the last word on this.  We should
>> > continue to look for ways to revise and improve whatever we come up
>> > with to get the partitioning and other undesirable things down to a
>> > minimum.
>
> My current plan to minimize partitioning of the client anonymity set is:
>
> * The directory authorities should specify lists of cryptographic
>  primitives (identity key signature systems, circuit-extension
>  handshakes, circuit ciphersuites, etc.) that relays are permitted to
>  support in the consensus.

This should probably incorporate allowable key sizes.  We don't want
some twit generating 16384-bit identity keys just to slow down all the
clients, but we also don't want somebody using 512-bit RSA keys.

> * The directory authorities should specify lists of cryptographic
>  primitives that clients should consider using in the consensus.
>
> * Each relay should specify lists of cryptographic primitives that it
>  is willing to use in its descriptor, ordered by the relay's
>  preference (e.g. the relay puts its favorite primitive in a list
>  first).

Hm.  If this involves multiple onion keys, this can potentially bloat
server descriptor sizes; we should consider carefully how we can avoid
that.  Perhaps there should be an upper bound on how many onion keys
you can advertise.

> * A client should select the first cryptographic primitive in a relay's
>  list that (a) the consensus recommends that clients use, and (b) the
>  client supports.

Hm. This puts the onus on relay operators of picking the best
primitives.  I'm not sure that's such a great idea.  Perhaps the
client should pick whichever method supported by both the client and
the relay that the *consensus* recommends first.

> * The Tor developers should not introduce new cryptographic primitives
>  between two stable releases in the same branch.
>
> The Tor client will need to support torrc options that override the
> lists of recommended cryptographic primitives in the consensus in order
> to allow testing of not-yet-recommended primitives on the public Tor
> network, but the manual page will need to warn explicitly that setting
> those options will harm a Tor user's anonymity.

One thing we will need to think about here is the risk of having
seldom-used code.  Remember the time that GPG had broken ElGamal keys
for ages, and it went unnoticed since almost nobody used ElGamal keys?
(CVE-2003-0971)  More code does come with more risk.


> This plan relies on the directory authorities not recommending a new
> cryptographic primitive until a large fraction of Tor clients support
> it.
>
>
>> One way is to be very conservative in suite choices so we don't have
>> to change them that often. I'm going to also go out on a limb and say
>> that we also want a crypto API like NaCL that lets us just say
>> enciphered=encrypt(key, unenciphered) and doesn't force us to worry
>> about padding or modes because this is a much simpler abstraction
>> layer and so offers less opportunity for mistakes that could threaten
>> security.
>
> I think that if we follow the plan above, we don't need to limit the
> number of cryptographic primitives of each type in order to preserve
> the client anonymity set.  It's more important to have at least two
> cryptographic primitives of each type implemented, even if we expect
> that few relays will prefer one of them, in order to ensure that we get
> the APIs for each primitive right.

I am a little skeptical that it will turn out to be quite this simple
once we design it, but at this point I think the easiest way to see
whether we can get away with a good design with all the properties we
want is to just try to make one, and see how it works out.

peace & happy new year,
-- 
Nick