Some draft notes on migrating Tor's ciphersuites
kyle.kwilliams at gmail.com
Sat Dec 18 03:27:14 UTC 2010
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.
On Tue, Dec 14, 2010 at 8:31 PM, Nick Mathewson <nickm at torproject.org>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
> - 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
> 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
> 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,
> - 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
> 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
> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the tor-dev