[tor-dev] The consequences of key compromise (or the reasons for changing)

[Watson Ladd]

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.

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.

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.

Sincerely,
Watson Ladd