Is there any writeup on the current status of Tor crypto? doc or issue list.
Thanks, Weidong On Tue, Dec 14, 2010 at 8:31 PM, Nick Mathewson <ni...@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 > 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. >
