Just throwing in my two cents here.<div><br></div><div>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.</div>
<div><br></div><div>Just wondering,</div><div><br></div><div>Kyle<br><br><div class="gmail_quote">On Tue, Dec 14, 2010 at 8:31 PM, Nick Mathewson <span dir="ltr"><<a href="mailto:nickm@torproject.org">nickm@torproject.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Here's something I've worked up, with fixes from Robert Ransom. It's<br>
currently in doc/spec/proposals/ideas/xxx-crypto-migration.txt. Once<br>
it's more discussed and worked out, it should turn into a real<br>
proposal, but I'd like to kick the ball off here.<br>
<br>
Robert has also written up a couple of documents I'll be forwarding in<br>
my next email.<br>
<br>
=====<br>
Title: Initial thoughts on migrating Tor to new cryptography<br>
Author: Nick Mathewson<br>
Created: 12 December 2010<br>
<br>
1. Introduction<br>
<br>
Tor currently uses AES-128, RSA-1024, and SHA1. Even though these<br>
ciphers were a decent choice back in 2003, and even though attacking<br>
these algorithms is by no means the best way for a well-funded<br>
adversary to attack users (correlation attacks are still cheaper, even<br>
with pessimistic assumptions about the security of each cipher), we<br>
will want to move to better algorithms in the future. Indeed, if<br>
migrating to a new ciphersuite were simple, we would probably have<br>
already moved to RSA-1024/AES-128/SHA256 or something like that.<br>
<br>
So it's a good idea to start figuring out how we can move to better<br>
ciphers. Unfortunately, this is a bit nontrivial, so before we start<br>
doing the design work here, we should start by examining the issues<br>
involved. Robert Ransom and I both decided to spend this weekend<br>
writing up documents of this type so that we can see how much two<br>
people working independently agree on. I know more Tor than Robert;<br>
Robert knows far more cryptography than I do. With luck we'll<br>
complement each other's work nicely.<br>
<br>
A note on scope: This document WILL NOT attempt to pick a new cipher<br>
or set of ciphers. Instead, it's about how to migrate to new ciphers<br>
in general. Any algorithms mentioned other than those we use today<br>
are just for illustration.<br>
<br>
Also, I don't much consider the importance of updating each particular<br>
usage; only the methods that you'd use to do it.<br>
<br>
Also, this isn't a complete proposal.<br>
<br>
2. General principles and tricks<br>
<br>
Before I get started, let's talk about some general design issues.<br>
<br>
2.1. Many algorithms or few?<br>
<br>
Protocols like TLS and OpenPGP allow a wide choice of cryptographic<br>
algorithms; so long as the sender and receiver (or the responder and<br>
initiator) have at least one mutually acceptable algorithm, they can<br>
converge upon it and send each other messages.<br>
<br>
This isn't the best choice for anonymity designs. If two clients<br>
support a different set of algorithms, then an attacker can tell them<br>
apart. A protocol with N ciphersuites would in principle split<br>
clients into 2**N-1 sets. (In practice, nearly all users will use the<br>
default, and most users who choose _not_ to use the default will do so<br>
without considering the loss of anonymity. See "Anonymity Loves<br>
Company: Usability and the Network Effect".)<br>
<br>
On the other hand, building only one ciphersuite into Tor has a flaw<br>
of its own: it has proven difficult to migrate to another one. So<br>
perhaps instead of specifying only a single new ciphersuite, we should<br>
specify more than one, with plans to switch over (based on a flag in<br>
the consensus or some other secure signal) once the first choice of<br>
algorithms start looking iffy. This switch-based approach would seem<br>
especially easy for parameterizable stuff like key sizes.<br>
<br>
2.2. Waiting for old clients and servers to upgrade<br>
<br>
The easiest way to implement a shift in algorithms would be to declare<br>
a "flag day": once we have the new versions of the protocols<br>
implemented, pick a day by which everybody must upgrade to the new<br>
software. Before this day, the software would have the old behavior;<br>
after this way, it would use the improved behavior.<br>
<br>
Tor tries to avoid flag days whenever possible; they have well-known<br>
issues. First, since a number of our users don't automatically<br>
update, it can take a while for people to upgrade to new versions of<br>
our software. Second and more worryingly, it's hard to get adequate<br>
testing for new behavior that is off-by-default. Flag days in other<br>
systems have been known to leave whole networks more or less<br>
inoperable for months; we should not trust in our skill to avoid<br>
similar problems.<br>
<br>
So if we're avoiding flag days, what can we do?<br>
<br>
* We can add _support_ for new behavior early, and have clients use it<br>
where it's available. (Clients know the advertised versions of the<br>
Tor servers they use-- but see 2.3 below for a danger here, and 2.4<br>
for a bigger danger.)<br>
<br>
* We can remove misfeatures that _prevent_ deployment of new<br>
behavior. For instance, if a certain key length has an arbitrary<br>
1024-bit limit, we can remove that arbitrary limitation.<br>
<br>
* Once an optional new behavior is ubiquitous enough, the authorities<br>
can stop accepting descriptors from servers that do not have it<br>
until they upgrade.<br>
<br>
It is far easier to remove arbitrary limitations than to make other<br>
changes; such changes are generally safe to back-port to older stable<br>
release series. But in general, it's much better to avoid any plans<br>
that require waiting for any version of Tor to no longer be in common<br>
use: a stable release can take on the order of 2.5 years to start<br>
dropping off the radar. Thandy might fix that, but even if a perfect<br>
Thandy release comes out tomorrow, we'll still have lots of older<br>
clients and relays not using it.<br>
<br>
We'll have to approach the migration problem on a case-by-case basis<br>
as we consider the algorithms used by Tor and how to change them.<br>
<br>
2.3. Early adopters and other partitioning dangers<br>
<br>
It's pretty much unavoidable that clients running software that speak<br>
the new version of any protocol will be distinguishable from those<br>
that cannot speak the new version. This is inevitable, though we<br>
could try to minimize the number of such partitioning sets by having<br>
features turned on in the same release rather than one-at-a-time.<br>
<br>
Another option here is to have new protocols controlled by a<br>
configuration tri-state with values "on", "off", and "auto". The<br>
"auto" value means to look at the consensus to decide wither to use<br>
the feature; the other two values are self-explanatory. We'd ship<br>
clients with the feature set to "auto" by default, with people only<br>
using "on" for testing.<br>
<br>
If we're worried about early client-side implementations of a protocol<br>
turning out to be broken, we can have the consensus value say _which_<br>
versions should turn on the protocol.<br>
<br>
2.4. Avoid whole-circuit switches<br>
<br>
One risky kind of protocol migration is a feature that gets used only<br>
when all the routers in a circuit support it. If such a feature is<br>
implemented by few relays, then each relay learns a lot about the rest<br>
of the path by seeing it used. On the other hand, if the feature is<br>
implemented by most relays, then a relay learns a lot about the rest of<br>
the path when the feature is *not* used.<br>
<br>
It's okay to have a feature that can be only used if two consecutive<br>
routers in the patch support it: each router knows the ones adjacent<br>
to it, after all, so knowing what version of Tor they're running is no<br>
big deal.<br>
<br>
2.5. The Second System Effect rears its ugly head<br>
<br>
Any attempt at improving Tor's crypto is likely to involve changes<br>
throughout the Tor protocol. We should be aware of the risks of<br>
falling into what Fred Brooks called the "Second System Effect": when<br>
redesigning a fielded system, it's always tempting to try to shovel in<br>
every possible change that one ever wanted to make to it.<br>
<br>
This is a fine time to make parts of our protocol that weren't<br>
previously versionable into ones that are easier to upgrade in the<br>
future. This probably _isn't_ time to redesign every aspect of the<br>
Tor protocol that anybody finds problematic.<br>
<br>
2.6. Low-hanging fruit and well-lit areas<br>
<br>
Not all parts of Tor are tightly covered. If it's possible to upgrade<br>
different parts of the system at different rates from one another, we<br>
should consider doing the stuff we can do easier, earlier.<br>
<br>
But remember the story of the policeman who finds a drunk under a<br>
streetlamp, staring at the ground? The cop asks, "What are you<br>
doing?" The drunk says, "I'm looking for my keys!" "Oh, did you drop<br>
them around here?" says the policeman. "No," says the drunk, "But the<br>
light is so much better here!"<br>
<br>
Or less proverbially: Simply because a change is easiest, does not<br>
mean it is the best use of our time. We should avoid getting bogged<br>
down solving the _easy_ aspects of our system unless they happen also<br>
to be _important_.<br>
<br>
2.7. Nice safe boring codes<br>
<br>
Let's avoid, to the extent that we can:<br>
- being the primary user of any cryptographic construction or<br>
protocol.<br>
- anything that hasn't gotten much attention in the literature.<br>
- anything we would have to implement from scratch<br>
- anything without a nice BSD-licensed C implementation<br>
<br>
Sometimes we'll have the choice of a more efficient algorithm or a<br>
more boring & well-analyzed one. We should not even consider trading<br>
conservative design for efficiency unless we are firmly in the<br>
critical path.<br>
<br>
2.8. Key restrictions<br>
<br>
Our spec says that RSA exponents should be 65537, but our code never<br>
checks for that. If we want to bolster resistance against collision<br>
attacks, we could check this requirement. To the best of my<br>
knowledge, nothing violates it except for tools like "shallot" that<br>
generate cute memorable .onion names. If we want to be nice to<br>
shallot users, we could check the requirement for everything *except*<br>
hidden service identity keys.<br>
<br>
3. Aspects of Tor's cryptography, and thoughts on how to upgrade them all<br>
<br>
3.1. Link cryptography<br>
<br>
Tor uses TLS for its link cryptography; it is easy to add more<br>
ciphersuites to the acceptable list, or increase the length of<br>
link-crypto public keys, or increase the length of the DH parameter,<br>
or sign the X509 certificates with any digest algorithm that OpenSSL<br>
clients will support. Current Tor versions do not check any of these<br>
against expected values.<br>
<br>
The identity key used to sign the second certificate in the current<br>
handshake protocol, however, is harder to change, since it needs to<br>
match up with what we see in the router descriptor for the router<br>
we're connecting to. See notes on router identity below. So long as<br>
the certificate chain is ultimately authenticated by a RSA-1024 key,<br>
it's not clear whether making the link RSA key longer on its own<br>
really improves matters or not.<br>
<br>
Recall also that for anti-fingerprinting reasons, we're thinking of<br>
revising the protocol handshake sometime in the 0.2.3.x timeframe.<br>
If we do that, that might be a good time to make sure that we aren't<br>
limited by the old identity key size.<br>
<br>
3.2. Circuit-extend crypto<br>
<br>
Currently, our code requires RSA onion keys to be 1024 bits long.<br>
Additionally, current nodes will not deliver an EXTEND cell unless it<br>
is the right length.<br>
<br>
For this, we might add a second, longer onion-key to router<br>
descriptors, and a second CREATE2 cell to open new circuits<br>
using this key type. It should contain not only the onionskin, but<br>
also information on onionskin version and ciphersuite. Onionskins<br>
generated for CREATE2 cells should use a larger DH group as well, and<br>
keys should be derived from DH results using a better digest algorithm.<br>
<br>
We should remove the length limit on EXTEND cells, backported to all<br>
supported stable versions; call these "EXTEND2" cells. Call these<br>
"lightly patched". Clients could use the new EXTEND2/CREATE2 format<br>
whenever using a lightly patched or new server to extend to a new<br>
server, and the old EXTEND/CREATE format otherwise.<br>
<br>
The new onion skin format should try to avoid the design oddities of<br>
our old one. Instead of its current iffy hybrid encryption scheme, it<br>
should probably do something more like a BEAR/LIONESS operation with a<br>
fixed key on the g^x value, followed by a public key encryption on the<br>
start of the encrypted data. (Robert reminded me about this<br>
construction.)<br>
<br>
The current EXTEND cell format ends with a router identity<br>
fingerprint, which is used by the extended-from router to authenticate<br>
the extended-to router when it connects. Changes to this will<br>
interact with changes to how long an identity key can be and to the<br>
link protocol; see notes on the link protocol above and about router<br>
identity below.<br>
<br>
3.2.1. Circuit-extend crypto: fast case<br>
<br>
When we do unauthenticated circuit extends with CREATE/CREATED_FAST,<br>
the two input values are combined with SHA1. I believe that's okay;<br>
using any entropy here at all is overkill.<br>
<br>
3.3. Relay crypto<br>
<br>
Upon receiving relay cells, a router transforms the payload portion of<br>
the cell with the appropriate key appropriate key, sees if it<br>
recognizes the cell (the recognized field is zero, the digest field is<br>
correct, the cell is outbound), and passes them on if not. It is<br>
possible for each hop in the circuit to handle the relay crypto<br>
differently; nobody but the client and the hop in question need to<br>
coordinate their operations.<br>
<br>
It's not clear, though, whether updating the relay crypto algorithms<br>
would help anything, unless we changed the whole relay cell processing<br>
format too. The stream cipher is good enough, and the use of 4 bytes<br>
of digest does not have enough bits to provide cryptographic strength,<br>
no matter what cipher we use.<br>
<br>
This is the likeliest area for the second-system effect to strike;<br>
there are lots of opportunities to try to be more clever than we are<br>
now.<br>
<br>
3.4. Router identity<br>
<br>
This is one of the hardest things to change. Right now, routers are<br>
identified by a "fingerprint" equal to the SHA1 hash of their 1024-bit<br>
identity key as given in their router descriptor. No existing Tor<br>
will accept any other size of identity key, or any other hash<br>
algorithm. The identity key itself is used:<br>
- To sign the router descriptors<br>
- To sign link-key certificates<br>
- To determine the least significant bits of circuit IDs used on a<br>
Tor instance's links (see tor-spec §5.1)<br>
<br>
The fingerprint is used:<br>
- To identify a router identity key in EXTEND cells<br>
- To identify a router identity key in bridge lines<br>
- Throughout the controller interface<br>
- To fetch bridge descriptors for a bridge<br>
- To identify a particular router throughout the codebase<br>
- In the .exit notation.<br>
- By the controller to identify nodes<br>
- To identify servers in the logs<br>
- Probably other places too<br>
<br>
To begin to allow other key types, key lengths, and hash functions, we<br>
would either need to wait till all current Tors are obsolete, or allow<br>
routers to have more than one identity for a while.<br>
<br>
To allow routers to have more than one identity, we need to<br>
cross-certify identity keys. We can do this trivially, in theory, by<br>
listing both keys in the router descriptor and having both identities<br>
sign the descriptor. In practice, we will need to analyze this pretty<br>
carefully to avoid attacks where one key is completely fake aimed to<br>
trick old clients somehow.<br>
<br>
Upgrading the hash algorithm once would be easy: just say that all<br>
new-type keys get hashed using the new hash algorithm. Remaining<br>
future-proof could be tricky.<br>
<br>
This is one of the hardest areas to update; "SHA1 of identity key" is<br>
assumed in so many places throughout Tor that we'll probably need a<br>
lot of design work to work with something else.<br>
<br>
3.5. Directory objects<br>
<br>
Fortunately, the problem is not so bad for consensuses themselves,<br>
because:<br>
- Authority identity keys are allowed to be RSA keys of any length;<br>
in practice I think they are all 3072 bits.<br>
- Authority signing keys are also allowed to be of any length.<br>
AFAIK the code works with longer signing keys just fine.<br>
- Currently, votes are hashed with both sha1 and sha256; adding<br>
more hash algorithms isn't so hard.<br>
- Microdescriptor consensuses are all signed using sha256. While<br>
regular consensuses are signed using sha1, exploitable collisions<br>
are hard to come up with, since once you had a collision, you<br>
would need to get a majority of other authorities to agree to<br>
generate it.<br>
<br>
Router descriptors are currently identified by SHA1 digests of their<br>
identity keys and descriptor digests in regular consensuses, and by<br>
SHA1 digests of identity keys and SHA256 digests of microdescriptors<br>
in microdesc consensuses. The consensus-flavors design allows us to<br>
generate new flavors of consensus that identity routers by new hashes<br>
of their identity keys. Alternatively, existing consensuses could be<br>
expanded to contain more hashes, though that would have some space<br>
concerns.<br>
<br>
Router descriptors themselves are signed using RSA-1024 identity keys<br>
and SHA1. For information on updating identity keys, see above.<br>
<br>
Router descriptors and extra-info documents cross-certify one another<br>
using SHA1.<br>
<br>
Microdescriptors are currently specified to contain exactly one<br>
onion key, of length 1024 bits.<br>
<br>
3.6. The directory protocol<br>
<br>
Most objects are indexed by SHA1 hash of an identity key or a<br>
descriptor object. Adding more hash types wouldn't be a huge problem<br>
at the directory cache level.<br>
<br>
3.7. The hidden service protocol<br>
<br>
Hidden services self-identify by a 1024-bit RSA key. Other key<br>
lengths are not supported. This key is turned into an 80 bit half<br>
SHA-1 hash for hidden service names.<br>
<br>
The most simple change here would be to set an interface for putting<br>
the whole ugly SHA1 hash in the hidden service name. Remember that<br>
this needs to coexist with the authentication system which also uses<br>
.onion hostnames; that hostnames top out around 255 characters and and<br>
their components top out at 63.<br>
<br>
Currently, ESTABLISH_INTRO cells take a key length parameter, so in<br>
theory they allow longer keys. The rest of the protocol assumes that<br>
this will be hashed into a 20-byte SHA1 identifier. Changing that<br>
would require changes at the introduction point as well as the hidden<br>
service.<br>
<br>
The parsing code for hidden service descriptors currently enforce a<br>
1024-bit identity key, though this does not seem to be described in<br>
the specification. Changing that would be at least as hard as doing<br>
it for regular identity keys.<br>
<br>
Fortunately, hidden services are nearly completely orthogonal to<br>
everything else.<br>
</blockquote></div><br></div>