Re: 64bit or 1024bit - will it make a difference?

Nelson Minar (nelson@media.mit.edu)
Mon, 12 May 1997 12:28:36 -0400


>If it takes us using spare cycles a few months to crack a 64 (56
>really) bit by brute force, why in 10 years couldn't the same exact
>thing be done to a 1024 bit key?

You're mixing apples and oranges. "56 bit key" makes sense for
symmetric cyphers. "1024 bit key" makes sense for public key cyphers,
in particular RSA. It has different properties and you can't directly
compare key lengths. I vaguely remember a rule-of-thumb for comparing
key lengths one time. I think (but don't quote me) that 1024bit RSA is
roughly equivalent to 80 bit RC5 for brute force attacks.

As far as symmetric key cyphers (like DES or RC5) goes, if the cypher
is well designed then the effort of a brute force attack is
exponential in the key length. Ie: adding one bit to the key doubles
the amount of work to break the cypher. For example if 40 bit RC5
takes N amount of time to break, then 48 bit RC5 takes 256*N, 56 bit
takes 65536*N, etc.

Most symmetric cyphers tend to use 128 bit keys. That's so much harder
to break than a 56 bit cypher that unless there's some enormous,
fundamental breakthrough in computing I think we're safe for a few
centuries.

A lot of symmetric cyphers also have a fixed key length. DES is a 56
bit key cypher and will always be one (triple DES is a different
beast). RC5 is unusual in that its keylength (and hopefully, its
security) is adjustable. The other RSA challenge is about breaking RC5
with increasingly long keys.

There's a good article on key length titled "Minimal Key Lengths for
Symmetric Ciphers to Provide Adequate Commercial Security". Give it at
read. There's a copy at http://www.randomc.com/~llama/junk/keylengths.txt

Here's a quote relevant to the deschall effort:

A serious effort --- on the order of $300,000 --- by a legitimate or
illegitimate business could find a DES key in an average of 19 days
using off-the-shelf technology and in only 3 hours using a custom
developed chip. In the latter case, it would cost $38 to find each key
(again assuming a 3 year life to the chip and continual use). A
business or government willing to spend $10,000,000 on custom chips,
could recover DES keys in an average of 6 minutes, for the same $38
per key.

Sort of puts our 10,000 computers in perspective.

Their final recommendation:

*Bearing in mind that the additional computational costs of stronger
encryption are modest, we strongly recommend a minimum key-length of
90 bits for symmetric cryptosystems.*