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.