Comparing Cryptographic Key Sizes

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

Below is a explanation of the meaning of cryptographic key sizes which
started as an explanation I wrote for a journalist friend of mine, on
being asked about how relatively secure a system using DES and RSA
(SET) was as compared to netscapes export version of SSL.

I've re-written it to make it more general in scope.

One of the most common errors I see in news stories about
cryptographic breaks is to (say) compare 1024 bit RSA keys with 56 bit
symmetric keys as if the two key sizes are directly comparable.

This new document is intended to be simple and understandable to give
people a handle on how to describe and compare cryptographic systems
strengths.

This document by design glosses over some details, where I think this
is reasonable.

It could use some criticism.  If you are not that crypto aware, does
it make sense to you?  If you are crypto aware, what do you think of
my off the cuff estimates of hardness?

I wrote it with journalists in mind.  If you are a journalist and find
it useful, feel free to quote parts/all of it without attribution.

Adam


Comparing Cryptographic Key Sizes

There are two types of key sizes: public key (sometimes called
asymmetric key) and symmetric keys.  Examples of public key algorithms
are RSA, and Diffie-Hellman.  Examples of symmetric key algorithms are
RC4, DES, IDEA.  You can not 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.  40 bit RSA (a public key
cipher) can be broken in a fraction of a second on one PC.  RSA keys
need to be I'd guess around 350 bits to be equivalent in strength to
40 bit RC4.

56 bit DES is probably roughly similar to 512 bit RSA in hardness to
break.

Symmetric keys sizes are easy to reason with: one more bit in key
length is twice as hard to break, for the same algorithm.  It is more
complicated estimating the hardness to break of public key (say RSA)
keys of varying sizes as they get harder more gradually than symmetric
keys.  This is why public key systems have longer keys, you need more
bits to get the same security level.

Most systems use a mixture of public and symmetric key ciphers.  This
is because public key ciphers are _slow_.  Symmetric key ciphers are
fast, and so are used in combination with public key systems to speed
up the combined system.  Public key systems are used because of the
advantages of public key management they make possible.

When considering the strength of a system using two ciphers one public
key and one symmetric key, the strength of the system is equal to the
strength of 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.  It is easier to crack 40 bit RC4 than it is to crack
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 amount of 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, of similar or
smaller scale than the recent DES breaking.

56 bit DES is harder to break than 40 bit RC4 (SSL), from the number
bits you might think it would be 65536 times harder, but it's less
than that because DES is faster than RC4.  In software it's about 5
times faster, so that means breaking DES in software is about 10000
times harder than breaking 40 bit RC4 (as used in export SSL) in
software.

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

About 10 years ago now Michael Wiener made a design for such a DES
breaking machine.  He estimated it would cost $10,000,000 to build a
machine which would break a 56 bit DES encrypted message a few hours.
His machine was scalable, pay more money, break the key faster, pay
less take longer.  The estimate was that could build one with enough
DES key searching units to break it in a day for $1,000,000.  That was
10 years ago.  10 years is a long time in the computer industry.
Nowadays you build the machine more cheaply as chip technology has
progressed, and computers are much faster per $.  Estimates are around
$100,000 to build the machine (neglecting hardware engineers
consultancy fees).

Everyone expects that NSA, GCHQ, SCSSI have built such a machine for
$100,000+.  This is obvious because the NSA and SCSSI allow export of
56 bit DES.

$100,000 is not much money for a secret service.

Algorithms using 40 bit keys aren't secure at all, past a very
superficial casual level of protection.  Systems using DES, such as
SET are only secure against organisations who can't raise $100,000 and
can't find people who know lots about crypto and hardware design.
$100,000 is not much money for a secret service.  It's not much for
the Rusian Mafia either.

END