[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: Some draft notes on migrating Tor's ciphersuites



Just throwing in my two cents here.

If there is talk about going back to the design board, and while you're about crypto, I was wondering if this would be a good time to also think about a UDP transport vs TCP.

Just wondering,

Kyle

On Tue, Dec 14, 2010 at 8:31 PM, Nick Mathewson <nickm@xxxxxxxxxxxxxx> wrote:
Here's something I've worked up, with fixes from Robert Ransom.  It's
currently in doc/spec/proposals/ideas/xxx-crypto-migration.txt.  Once
it's more discussed and worked out, it should turn into a real
proposal, but I'd like to kick the ball off here.

Robert has also written up a couple of documents I'll be forwarding in
my next email.

=====
Title: Initial thoughts on migrating Tor to new cryptography
Author: Nick Mathewson
Created: 12 December 2010

1. Introduction

 Tor currently uses AES-128, RSA-1024, and SHA1.  Even though these
 ciphers were a decent choice back in 2003, and even though attacking
 these algorithms is by no means the best way for a well-funded
 adversary to attack users (correlation attacks are still cheaper, even
 with pessimistic assumptions about the security of each cipher), we
 will want to move to better algorithms in the future.  Indeed, if
 migrating to a new ciphersuite were simple, we would probably have
 already moved to RSA-1024/AES-128/SHA256 or something like that.

 So it's a good idea to start figuring out how we can move to better
 ciphers.  Unfortunately, this is a bit nontrivial, so before we start
 doing the design work here, we should start by examining the issues
 involved.  Robert Ransom and I both decided to spend this weekend
 writing up documents of this type so that we can see how much two
 people working independently agree on.  I know more Tor than Robert;
 Robert knows far more cryptography than I do.  With luck we'll
 complement each other's work nicely.

 A note on scope: This document WILL NOT attempt to pick a new cipher
 or set of ciphers.  Instead, it's about how to migrate to new ciphers
 in general.  Any algorithms mentioned other than those we use today
 are just for illustration.

 Also, I don't much consider the importance of updating each particular
 usage; only the methods that you'd use to do it.

 Also, this isn't a complete proposal.

2. General principles and tricks

 Before I get started, let's talk about some general design issues.

2.1. Many algorithms or few?

 Protocols like TLS and OpenPGP allow a wide choice of cryptographic
 algorithms; so long as the sender and receiver (or the responder and
 initiator) have at least one mutually acceptable algorithm, they can
 converge upon it and send each other messages.

 This isn't the best choice for anonymity designs.  If two clients
 support a different set of algorithms, then an attacker can tell them
 apart.  A protocol with N ciphersuites would in principle split
 clients into 2**N-1 sets.  (In practice, nearly all users will use the
 default, and most users who choose _not_ to use the default will do so
 without considering the loss of anonymity.  See "Anonymity Loves
 Company: Usability and the Network Effect".)

 On the other hand, building only one ciphersuite into Tor has a flaw
 of its own: it has proven difficult to migrate to another one.  So
 perhaps instead of specifying only a single new ciphersuite, we should
 specify more than one, with plans to switch over (based on a flag in
 the consensus or some other secure signal) once the first choice of
 algorithms start looking iffy.  This switch-based approach would seem
 especially easy for parameterizable stuff like key sizes.

2.2. Waiting for old clients and servers to upgrade

 The easiest way to implement a shift in algorithms would be to declare
 a "flag day": once we have the new versions of the protocols
 implemented, pick a day by which everybody must upgrade to the new
 software.  Before this day, the software would have the old behavior;
 after this way, it would use the improved behavior.

 Tor tries to avoid flag days whenever possible; they have well-known
 issues.  First, since a number of our users don't automatically
 update, it can take a while for people to upgrade to new versions of
 our software.  Second and more worryingly, it's hard to get adequate
 testing for new behavior that is off-by-default.  Flag days in other
 systems have been known to leave whole networks more or less
 inoperable for months; we should not trust in our skill to avoid
 similar problems.

 So if we're avoiding flag days, what can we do?

 * We can add _support_ for new behavior early, and have clients use it
   where it's available.  (Clients know the advertised versions of the
   Tor servers they use-- but see 2.3 below for a danger here, and 2.4
   for a bigger danger.)

 * We can remove misfeatures that _prevent_ deployment of new
   behavior.  For instance, if a certain key length has an arbitrary
   1024-bit limit, we can remove that arbitrary limitation.

 * Once an optional new behavior is ubiquitous enough, the authorities
   can stop accepting descriptors from servers that do not have it
   until they upgrade.

 It is far easier to remove arbitrary limitations than to make other
 changes; such changes are generally safe to back-port to older stable
 release series.  But in general, it's much better to avoid any plans
 that require waiting for any version of Tor to no longer be in common
 use: a stable release can take on the order of 2.5 years to start
 dropping off the radar.  Thandy might fix that, but even if a perfect
 Thandy release comes out tomorrow, we'll still have lots of older
 clients and relays not using it.

 We'll have to approach the migration problem on a case-by-case basis
 as we consider the algorithms used by Tor and how to change them.

2.3. Early adopters and other partitioning dangers

 It's pretty much unavoidable that clients running software that speak
 the new version of any protocol will be distinguishable from those
 that cannot speak the new version.  This is inevitable, though we
 could try to minimize the number of such partitioning sets by having
 features turned on in the same release rather than one-at-a-time.

 Another option here is to have new protocols controlled by a
 configuration tri-state with values "on", "off", and "auto".  The
 "auto" value means to look at the consensus to decide wither to use
 the feature; the other two values are self-explanatory.  We'd ship
 clients with the feature set to "auto" by default, with people only
 using "on" for testing.

 If we're worried about early client-side implementations of a protocol
 turning out to be broken, we can have the consensus value say _which_
 versions should turn on the protocol.

2.4. Avoid whole-circuit switches

 One risky kind of protocol migration is a feature that gets used only
 when all the routers in a circuit support it.  If such a feature is
 implemented by few relays, then each relay learns a lot about the rest
 of the path by seeing it used.  On the other hand, if the feature is
 implemented by most relays, then a relay learns a lot about the rest of
 the path when the feature is *not* used.

 It's okay to have a feature that can be only used if two consecutive
 routers in the patch support it: each router knows the ones adjacent
 to it, after all, so knowing what version of Tor they're running is no
 big deal.

2.5. The Second System Effect rears its ugly head

 Any attempt at improving Tor's crypto is likely to involve changes
 throughout the Tor protocol.  We should be aware of the risks of
 falling into what Fred Brooks called the "Second System Effect": when
 redesigning a fielded system, it's always tempting to try to shovel in
 every possible change that one ever wanted to make to it.

 This is a fine time to make parts of our protocol that weren't
 previously versionable into ones that are easier to upgrade in the
 future.  This probably _isn't_ time to redesign every aspect of the
 Tor protocol that anybody finds problematic.

2.6. Low-hanging fruit and well-lit areas

 Not all parts of Tor are tightly covered.  If it's possible to upgrade
 different parts of the system at different rates from one another, we
 should consider doing the stuff we can do easier, earlier.

 But remember the story of the policeman who finds a drunk under a
 streetlamp, staring at the ground?  The cop asks, "What are you
 doing?"  The drunk says, "I'm looking for my keys!"  "Oh, did you drop
 them around here?" says the policeman.  "No," says the drunk, "But the
 light is so much better here!"

 Or less proverbially: Simply because a change is easiest, does not
 mean it is the best use of our time.  We should avoid getting bogged
 down solving the _easy_ aspects of our system unless they happen also
 to be _important_.

2.7. Nice safe boring codes

 Let's avoid, to the extent that we can:
   - being the primary user of any cryptographic construction or
     protocol.
   - anything that hasn't gotten much attention in the literature.
   - anything we would have to implement from scratch
   - anything without a nice BSD-licensed C implementation

 Sometimes we'll have the choice of a more efficient algorithm or a
 more boring & well-analyzed one.  We should not even consider trading
 conservative design for efficiency unless we are firmly in the
 critical path.

2.8. Key restrictions

 Our spec says that RSA exponents should be 65537, but our code never
 checks for that.  If we want to bolster resistance against collision
 attacks, we could check this requirement.  To the best of my
 knowledge, nothing violates it except for tools like "shallot" that
 generate cute memorable .onion names.  If we want to be nice to
 shallot users, we could check the requirement for everything *except*
 hidden service identity keys.

3. Aspects of Tor's cryptography, and thoughts on how to upgrade them all

3.1. Link cryptography

 Tor uses TLS for its link cryptography; it is easy to add more
 ciphersuites to the acceptable list, or increase the length of
 link-crypto public keys, or increase the length of the DH parameter,
 or sign the X509 certificates with any digest algorithm that OpenSSL
 clients will support.  Current Tor versions do not check any of these
 against expected values.

 The identity key used to sign the second certificate in the current
 handshake protocol, however, is harder to change, since it needs to
 match up with what we see in the router descriptor for the router
 we're connecting to.  See notes on router identity below.  So long as
 the certificate chain is ultimately authenticated by a RSA-1024 key,
 it's not clear whether making the link RSA key longer on its own
 really improves matters or not.

 Recall also that for anti-fingerprinting reasons, we're thinking of
 revising the protocol handshake sometime in the 0.2.3.x timeframe.
 If we do that, that might be a good time to make sure that we aren't
 limited by the old identity key size.

3.2. Circuit-extend crypto

 Currently, our code requires RSA onion keys to be 1024 bits long.
 Additionally, current nodes will not deliver an EXTEND cell unless it
 is the right length.

 For this, we might add a second, longer onion-key to router
 descriptors, and a second CREATE2 cell to open new circuits
 using this key type.  It should contain not only the onionskin, but
 also information on onionskin version and ciphersuite.  Onionskins
 generated for CREATE2 cells should use a larger DH group as well, and
 keys should be derived from DH results using a better digest algorithm.

 We should remove the length limit on EXTEND cells, backported to all
 supported stable versions; call these "EXTEND2" cells.  Call these
 "lightly patched".  Clients could use the new EXTEND2/CREATE2 format
 whenever using a lightly patched or new server to extend to a new
 server, and the old EXTEND/CREATE format otherwise.

 The new onion skin format should try to avoid the design oddities of
 our old one.  Instead of its current iffy hybrid encryption scheme, it
 should probably do something more like a BEAR/LIONESS operation with a
 fixed key on the g^x value, followed by a public key encryption on the
 start of the encrypted data.  (Robert reminded me about this
 construction.)

 The current EXTEND cell format ends with a router identity
 fingerprint, which is used by the extended-from router to authenticate
 the extended-to router when it connects.  Changes to this will
 interact with changes to how long an identity key can be and to the
 link protocol; see notes on the link protocol above and about router
 identity below.

3.2.1. Circuit-extend crypto: fast case

 When we do unauthenticated circuit extends with CREATE/CREATED_FAST,
 the two input values are combined with SHA1.  I believe that's okay;
 using any entropy here at all is overkill.

3.3. Relay crypto

 Upon receiving relay cells, a router transforms the payload portion of
 the cell with the appropriate key appropriate key, sees if it
 recognizes the cell (the recognized field is zero, the digest field is
 correct, the cell is outbound), and passes them on if not.  It is
 possible for each hop in the circuit to handle the relay crypto
 differently; nobody but the client and the hop in question need to
 coordinate their operations.

 It's not clear, though, whether updating the relay crypto algorithms
 would help anything, unless we changed the whole relay cell processing
 format too.  The stream cipher is good enough, and the use of 4 bytes
 of digest does not have enough bits to provide cryptographic strength,
 no matter what cipher we use.

 This is the likeliest area for the second-system effect to strike;
 there are lots of opportunities to try to be more clever than we are
 now.

3.4. Router identity

 This is one of the hardest things to change.  Right now, routers are
 identified by a "fingerprint" equal to the SHA1 hash of their 1024-bit
 identity key as given in their router descriptor.  No existing Tor
 will accept any other size of identity key, or any other hash
 algorithm.  The identity key itself is used:
   - To sign the router descriptors
   - To sign link-key certificates
   - To determine the least significant bits of circuit IDs used on a
     Tor instance's links (see tor-spec §5.1)

 The fingerprint is used:
   - To identify a router identity key in EXTEND cells
   - To identify a router identity key in bridge lines
   - Throughout the controller interface
   - To fetch bridge descriptors for a bridge
   - To identify a particular router throughout the codebase
   - In the .exit notation.
   - By the controller to identify nodes
   - To identify servers in the logs
   - Probably other places too

 To begin to allow other key types, key lengths, and hash functions, we
 would either need to wait till all current Tors are obsolete, or allow
 routers to have more than one identity for a while.

 To allow routers to have more than one identity, we need to
 cross-certify identity keys.  We can do this trivially, in theory, by
 listing both keys in the router descriptor and having both identities
 sign the descriptor.  In practice, we will need to analyze this pretty
 carefully to avoid attacks where one key is completely fake aimed to
 trick old clients somehow.

 Upgrading the hash algorithm once would be easy: just say that all
 new-type keys get hashed using the new hash algorithm.  Remaining
 future-proof could be tricky.

 This is one of the hardest areas to update; "SHA1 of identity key" is
 assumed in so many places throughout Tor that we'll probably need a
 lot of design work to work with something else.

3.5. Directory objects

 Fortunately, the problem is not so bad for consensuses themselves,
 because:
   - Authority identity keys are allowed to be RSA keys of any length;
     in practice I think they are all 3072 bits.
   - Authority signing keys are also allowed to be of any length.
     AFAIK the code works with longer signing keys just fine.
   - Currently, votes are hashed with both sha1 and sha256; adding
     more hash algorithms isn't so hard.
   - Microdescriptor consensuses are all signed using sha256.  While
     regular consensuses are signed using sha1, exploitable collisions
     are hard to come up with, since once you had a collision, you
     would need to get a majority of other authorities to agree to
     generate it.

 Router descriptors are currently identified by SHA1 digests of their
 identity keys and descriptor digests in regular consensuses, and by
 SHA1 digests of identity keys and SHA256 digests of microdescriptors
 in microdesc consensuses.  The consensus-flavors design allows us to
 generate new flavors of consensus that identity routers by new hashes
 of their identity keys.  Alternatively, existing consensuses could be
 expanded to contain more hashes, though that would have some space
 concerns.

 Router descriptors themselves are signed using RSA-1024 identity keys
 and SHA1.  For information on updating identity keys, see above.

 Router descriptors and extra-info documents cross-certify one another
 using SHA1.

 Microdescriptors are currently specified to contain exactly one
 onion key, of length 1024 bits.

3.6. The directory protocol

 Most objects are indexed by SHA1 hash of an identity key or a
 descriptor object.  Adding more hash types wouldn't be a huge problem
 at the directory cache level.

3.7. The hidden service protocol

 Hidden services self-identify by a 1024-bit RSA key.  Other key
 lengths are not supported.  This key is turned into an 80 bit half
 SHA-1 hash for hidden service names.

 The most simple change here would be to set an interface for putting
 the whole ugly SHA1 hash in the hidden service name.  Remember that
 this needs to coexist with the authentication system which also uses
 .onion hostnames; that hostnames top out around 255 characters and and
 their components top out at 63.

 Currently, ESTABLISH_INTRO cells take a key length parameter, so in
 theory they allow longer keys.  The rest of the protocol assumes that
 this will be hashed into a 20-byte SHA1 identifier.  Changing that
 would require changes at the introduction point as well as the hidden
 service.

 The parsing code for hidden service descriptors currently enforce a
 1024-bit identity key, though this does not seem to be described in
 the specification.  Changing that would be at least as hard as doing
 it for regular identity keys.

 Fortunately, hidden services are nearly completely orthogonal to
 everything else.