Comparing Cryptographic Key Sizes II

[Adam Back <aba@dcs.ex.ac.uk>]

I got quite a few useful comments on the key comparison summary I
posted earlier.  Even some people said they found it useful.  Mark
Grant improved the readability, plus other suggestions.  Peter Trei
urged me to actually re-read the Wiener paper to quote the figures
correctly rather than from memory.  Also Peter raised issues to do
with how to compare hardness to break DES against 512 bit RSA.  There
is now an aside more technical note explaining the issues.  I think I
stand by my original comparison of "roughly equal", because depending
on how you view it, it'll come out 10x cheaper, or 10x harder.
(Memory being one hurdle each participating workstation needing of the
order of 128 Mb; the other hurdle being the existance of a machine
large enough to reduce the matrix which results from all the
relations).

I don't think we can explain it any more technically and expect it to
be useful to a journalist.  We need a gross generalisation: is it
approx as hard, is it 100x harder.  They don't want to hear about
space complexity, the matrix reduction phase (RSA) nor known plaintext
memory trade offs (DES).  If we don't supply the gross generalisation,
they will do it themselves to make it palatable for their readers.
With less understanding of the subject, their generalisation is likely
to be even wildly inaccurate than the generous error bars on ours.
This is not an insult to journalists.  Crypto is a technical,
complicated field.  I wouldn't contemplate making estimates in other
peoples fields.

Further discussion of course still sought (rip it apart pessimists on
crypto estimates).  Here's the new improved version.

Adam
-- 
Have *you* exported RSA today? --> http://www.dcs.ex.ac.uk/~aba/rsa/

print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`


======================================================================

Comparing Cryptographic Key Sizes

There are two types of cryptographic keys; public keys -- sometimes
called asymmetric key -- and symmetric keys. RSA and Diffie-Hellman
are common public key algorithms and RC4, DES and IDEA common
symmetric key algorithms. You cannot directly compare public key
lengths (for example RSA keys) with symmetric key lengths (DES, RC4);
this is an important point which confuses many people.

For example, 40 bit RC4 (a symmetric key cipher) can be broken in a
few hours with a few hundred workstations but 40 bit RSA (a public key
cipher) can be broken in a fraction of a second on one PC. A 350 bit
RSA key is roughly equivalent in strength to 40 bit RC4, and 512 bit
RSA key is thought to cost roughly the same to break as a 56 bit DES
key.

(That last comparison (DES vs 512 bit RSA) glosses over many issues.
Here's a summary if you're interested: no one's broken a 512 RSA bit
key yet, and you need lots of memory to break RSA at that key size, a
PC with 128 Mb would be required to participate.  In contrast, you
need hardly any memory to break DES, any PC will do.  The internet
based breaking of a DES key in answer to RSA DSI's challenge involved
many participants, and included some participants with low end 486 PCs
with 1Mb of memory.  Theoretically 512 bit RSA could be broken more
quickly than DES, but, as you need more memory than typical
workstations have, a distributed internet attack with the same group
of participants as for the DES break would clearly take longer.  There
are a number of other factors also.)

Symmetric keys sizes are easy to understand; for any particular
algorithm, adding one bit to the key length doubles the
difficulty. Estimating the difficulty of breaking a public key (say
RSA) is harder because the increase in strength is not
straightforward, but typically adding ten bits to the size of an RSA
key doubles the strength.  This is why public key systems require
longer keys to provide the same security.

Most systems use a mixture of public and symmetric key ciphers,
because public key ciphers are _slow_ but dramatically simplify key
management.  Symmetric key ciphers are fast, so they are used in
conjunction with public key systems to speed up the combined
system. Such a system using two ciphers -- one public key and one
symmetric key -- is only as strong as the weakest link.

For example, consider the export version of SSL, as shipped in the
export version of Netscape browsers and servers; it uses 512 bit RSA,
and 40 bit RC4.  Cracking 40 bit RC4 is easier than cracking 512 bit
RSA, so export SSL can be broken by breaking the 40 bit RC4 component.
Ian Goldberg recently broke a 40 bit RC5 key himself with Berkeley
univ machines in 3.5 hours.  40 bit RC4 could be broken in a similar
time.

512 bits RSA is not enough either, and you can rest assured that the
NSA, other governments' secret services, and any corporation or
organised crime group with sufficient funds can break it.  512 bits is
likely within reach of a distributed internet effort, or soon will be.

There is a further problem. Each session uses a different, randomly
chosen, RC4 key, so breaking one RC4 key only allows you to read a
single message. However, every message is encrypted with the _same_
512 bit RSA key, so if you can break that key you can immediately read
any message sent to or from the server. As a consequence, the public
key size should be chosen to be much harder to break than the
symmetric key. In this case although the key is thousands of times
harder to break it would be worth attacking if the server is
processing thousands or millions of transactions.

56 bit DES is harder to break than 40 bit RC4 (SSL); you would expect
that the extra sixteen bits would increase the difficulty 65536 times,
but DES is faster than RC4. In software it's about 5 times faster, so
breaking DES in software is about 10000 times harder than breaking 40
bit RC4 (as used in export SSL).

But if the Russian Mafia or a corporation involved in industrial
espionage wanted to break 56 bit DES they would not use software but
would build a special purpose piece of hardware which was designed
only to break DES.  DES was designed to be fast in hardware, and is a
relatively slow cipher in software.

In 1993 Michael Wiener designed such a DES breaking machine.  His
estimated cost for a machine capable of breaking 56 bit DES in a 3.5
hours hours was $1,000,000. The machine was scalable, so that by
spending more or less money you could reduce or increase the time
taken to break the key.  He estimated that building a machine to break
DES in 21 minutes would cost $10,000,000.

That was 10 years ago; 10 years is a long time in the computer
industry.  Today the machine would be much cheaper because chip
technology has progressed and computers are much faster per
$. Estimates are around $20,000 to build a machine to break a DES key
within a day (neglecting hardware engineers consultancy fees).  When
you consider the sorts of uses DES is being used for by banks, ATM
card PINs, wire transfers, interbank exchanges, DES is clearly
out-of-date.

Everyone expects that NSA, GCHQ, SCSSI have built one or more machines
for $20,000+; this is considered obvious because the NSA and SCSSI
allow export of 56 bit DES.  $20,000 is not much money for a secret
service, or for many less scrupulous individuals.

Algorithms using 40 bit keys are insecure against all but trivial
cracking attempts. Systems using DES (such as SET) are only secure
against organisations who can't raise $20,000 and can't find people
who know lots about crypto and hardware design; $20,000 is not much
money for the Rusian Mafia either. Even worse, once you have built
such a machine the cost of cracking each key is only a few hundreds or
thousands of dollars, so any DES key protecting information of greater
value is a tempting target.

US export controls used to restrict exports to 40 bit RC4.  When the
cypherpunks broke several 40 bit RC4 systems the rules were relaxed to
56 bits.  Now that a distributed internet group has broken 56 bit DES,
the US government's claim that 56 bit is "good enough" is being
demonstrated to be patently false.  The US government's other ploy has
been to allow larger key lengths, but to keep a master key to all
communications for themselves.  When full strength encryption systems
with 128 bit symmetric keys are widely available from foreign
competitors, this firstly makes no sense: why can't the US software
industry export when every one has strong crypto anway.  And secondly
the US software industry is losing billions each year in lost sales to
their european competitors. 

128 bit encryption is unbreakable for all practical purposes.  You
will recall in the discussion above that each bit of key size doubles
the work required to break a symmetric cipher.  A 128 bit cipher is
4,722,366,482,869,645,213,696 times harder to break than DES.  That is
a very large number.  Messages encrypted with such keys aren't likely
to be breakable for 30-100 years from now.

Similarly 1024, to 4096 bit public key systems are in use, and
available outside the US.  These systems are of roughly comparable
hardness to break to 128 bit symmetric keys, the larger the key, the
more secure.

One final point: things are getting better for cryptography.  The
attackers job is getting harder.  With each doubling of machine speed
it is possible to use larger keys, and still encrypt and decrypt
instantly when you have the key.  When PGP was first released back in
1991, 1024 bit RSA keys were slow to use on the state of the art PC
then, a lowly '286.  Nowadays an entry level PC, a Pentium 133
whistles through 4096 bit keys.  If we say that a P133 is 50x faster
than a 20Mhz '286 you can see that the same person using encryption
now can use key sizes which before were too slow.  I can assure you
that in moving from a 1024 bit key to a 4096 bit key, the attackers
job is well in excess of 50x harder.  Greatly in excess of a trillion
trillion times harder.