On Nov 3, 2011, at 9:08 PM, Watson Ladd wrote:

Dear all,

Recently Zooko forwarded an email asking why we have to migrate. I am outlining the reasons in this email why I believe Tor needs to use stronger cryptography very soon.

Tor currently uses RSA-1024 bit keys for OR public identities and 1024-bit Diffie Hellman for the negotiation of keys protecting circuits. It also uses SHA-1 for a hash in serveral applications, including key fingerprints. When deciding if these are adequate it is necessary to think about what compromise gives an attacker and what it costs to compromise Tor cryptography. We are aiming to protect users from TLAs with ASICs.

People should get off of 80-bit crypto as soon as is reasonably possible. This means RSA 1024, SHA-1, etc. NIST recommended doing this by the end of 2010, but are now holding their nose and saying that 2013 is the real new date.

This seems basically reasonable to me. No one has yet factored a 768-bit number, let alone a 1K one. SHA-1 actually looks safer today than it did in 2005. But still. Moving away is a Good Thing, so long as it doesn't make you do something stupid.

It's certainly laudable to worry about TLAs with ASICs. They probably can't break 80-bit crypto yet, but that's why you need to get off of it now.

On the other hand, no TLA worth their salt is buying ASICs to crack crypto. They are buying zero-day kernel 'sploits. That's how the Germans are beating Skype. Keep that in perspective. The half life of an ASIC is 18 months. Zero-days are much more effective and much cheaper.

Directory keys are 3024 bit RSA. Compromising a directory key is sufficient to generate directories containing fake entries, and thus break the anonymityof all users who see the fake directory. In the event of a compromise, Tor would be unusable until a new version is put out with a longer key length and new directory keys. But these are long keys.

However, the keys that actually sign the directories are 1024 bits, but rotate every 3 months.

OR keys are also 1024 bit RSA. Compromise of an OR key enables impersonation of the OR to an OP. Combined with fun and games with BGP it enables impersonation of an OR to other ORs, which can direct significant traffic to the fake OR. Detection is likely as the real OR will notice various refusals to connect by other OR to whom it is not connected. And if you can break the directory key why bother with ORs.

Hidden services are also identified by 1024 bit RSA keys. At the circuit level DH keys are 1024 bits. An attacker who compromises these can read data intended for further down in the circuit. In particular they can determine the rest of a circuit if they are the first node.

There is also the issue of keysize. A Tor cell is 512 bytes long. Thisis sufficent for only 4 keys, if we pack them very tightly. Smaller keys could enable fast circuit initiation or other cool tricks we cannot use today.

So, how strong or weak are RSA-1024 and DH-1024 currently? We are using DH over F_q* where q = a big prime. For DH the best known algorithm is the index calculus. This attack proceeds in 3 steps.

The first step, which can be spread over multiple keys is the collection of relations among a factor base, usually of small primes. The second step, again spread over multiple keys, is solving the linear system of equations from the first step. The third step is fast and key specific: given an element h,and generator g we attempt to factor g^s*h over the factor base. The general number field sieve is a very similar algorithm for factoring. It is more complicated but again relies on finding smooth numbers and factoring them with respect to a factor base of small primes.

Currently the complexity of these algorithms is L_n[1/3,\sqrt^3_{\frac{64}{9}}]for GNFS and L_n[1/2,c] for index calculus. (From wikipedia). Sadly the sieving stepscan be done very well on special hardware. TWIRL, a specialized hardwaredevice designed by Adi Shamir and Eran Tromer is believed by Shamir and Tromer to be capable of factoring a 1024-bit RSA key in a year at a cost of $10 million dollars. To break 10 directory keys in 3 months is 10 times as many keys, and 4 times the speed. That will be $400 million dollars.

That is half the cost of Golden Shield for a year: an amount of money that is not ludicrous. And such a machine once built can crack the next 10 keys for free. The cost is design and fabrication of this device: power is comparatively cheap. Of course, such a machine would be unsuited to other bit sizes.

And for $400 million, you can probably buy about a thousand zero days, if not more. You can buy a zero day for any OS in the world for between $50K and a million bucks, with the exception of iOS. For iOS, just Google "iPhone jailbreak" and they're free.

If the attacker instead decides to find a discrete logarithm base for DH over 1024, then they will have the ability to break DH-1024 fairly quickly. I haven't seen a good estimate for the time it would take to do this, but it will be a bit more. It will not be much more. And it will be a total break: once a factor basis is found discrete logs are very fast. So an adversary can spend more time and still be happy with the results.

So it isn't just directory signing that is an issue but the link protocol as well. And $400 million is a lot. But when you are the Golden Shield director and someone says "for $400 million we can break Tor for a long time" that is not entirely out of the picture. As technology for ASIC fabrication gets better, this price drops. As GNFS gets better it also drops. As index calculus gets better it drops. And as Balmol's cost disease drives up the cost and budget of Golden Shields regular activities, the price drops.

You're right on all of this, and you're right that the crypto needs to be upgraded, but software is still far weaker than the crypto.

On the other hand -- the crypto is something we can do something about. That's why we should. It would be truly embarrassing to have crypto weaker than the software.

Jon