What have we done? (Here's what.)

C Matthew Curtin (cmcurtin@research.megasoft.com)
Sat, 21 Jun 1997 02:34:11 -0400 (EDT)


Hi everyone. After the radio show, I sorta geeked-out here, and
started playing with numbers...

I apologize for the length of this message, but I think this will be
interesting, and possibly useful for press-types, or others who are
trying to understand the significance of what we've done.

Please send comments, and I'll HTML-ize this and park it up
someplace.

1. WHAT'S A CRYPTOSYSTEM?

Cryptosystems are locks for data. By using mathematical functions,
the data is turned into gibberish that can only be returned to a form
that makes sense by applying the appropriate key. It's easy to
understand how this works by envisioning a bicycle tumbler lock. In a
bicycle lock, there are a number of tumblers, each with numbers on it,
from 0 to 9. Because computers are binary -- only working with 0s and
1s -- at their most basic level, a cryptosystem is like a bicycle lock
that has only two numbers: 0 and 1.

On such a lock, there are two possible choices: 0 and 1. By putting
another tumbler with 0 and 1 on it, the number of possible
combinations increases exponentially from 2 to 4:

number of | possible
tumblers | combinations
----------|-------------
1 | 2 (0, 1)
2 | 4 (00, 01, 10, 11)
3 | 8 (000, 001, 010, 011, 100, 101, 110, 111)

So, not only does the lock have to be strong -- that is, function as
it was designed, without allowing a "shortcut" to solve the problem
(such as the application of boltcutters :-) -- but it has to have
enough possible combinations to make someone trying every single one
infeasible.

A cryptosystem with only a 3-bit keyspace would have 8 possible keys,
as shown in the chart above, or as we see mathematically: 2^3 = 8.
This would not be very secure, since to decrypt the message, I would
try to decrypt it using the key 000, then 001, then 010, etc., up
until 111, until I am looking at the contents of that message.

Let's catch up with our chart, by moving ahead to as many tumblers as
what some cryptosystems are using today:

number of | possible
tumblers | combinations
----------|-------------
40 | 1,099,511,627,776
56 | 72,057,594,037,927,936
64 | 18,446,744,073,709,551,616
128 | 340,282,366,920,938,463,463,374,607,431,768,211,456

For a cryptosystem to be secure, there have to be enough possible
keys to make it _practically_ impossible for someone to (on a regular
basis) try every possible key until they find the right one that
works.

2. WHAT WE DID

We took a message that had been encrypted with DES, and read the
contents of the message, as well as figured out which key was used to
encrypt the message in the first place. At the same time, we now have
more data that shows the kind of horsepower we can assemble by having
a bunch of people run a little piece of software on their machine that
has no noticeable effect on their systems' performance.

That little piece of software took the encrypted message, and
decrypted it using every possible key, until we found the one that
resulted in some output that made sense.

We were trying about 7 billion keys per second at the time that the
solution was found. If that computing power -- assembled using a
bunch of PCs, Macs, workstations, and some servers -- was applied to
the same cryptosystem of different key sizes, we can see how long it
would take to decrypt a message by trying everyone possible one until
the right one is found.

(Yes, the following is a slight oversimplification, but it's close
enough to what's going on to demonstrate the point well, and correctly
enough for comparison. There are differences in the internal
structure of various algorithms that would influence just how quickly
the keyspace can be searched, etc. But, algorithms that are slower to
compute can still be compared by throwing in some more clients, then
comparing. Humor me a moment.)

number of | time to crack the message
tumblers | (on the average, at DESCHALL Project speed)
----------|-------------
40 | 78 seconds
48 | 5 hours
56 | 59 days
64 | 41 years
72 | 10,696 years
80 | 2,738,199 years
88 | 700,978,948 years
96 | 179,450,610,898 years
128 | 770,734,505,057,572,442,069 years

For comparison, Hawking[1] notes that the age of the universe is
probably "only" 20,000,000 (or perhaps 10,000,000) years old.

So, while it's infeasible for DESCHALL to crack a 72 bit key, it seems
that 64 might be within reach, by adding more machines. (We probably
used between 15,000 and 20,000 machines.) Consider that the
RC5-32/12/5 (40 bits) key crack took three and a half hours. The
distributed computer we put together could do it in about 78 seconds.

The RC5-32/12/6 (48 bits) key crack took 13 days. A DESCHALL-sized
effort could do it in 5 hours.

Given Moore's Law, which states that computing power will double every
18 months, and the fact that the brute-force searches done for RC5 and
DES so far are written in _software_ on general-purpose computers (a
extremely slow method, by comparison to custom hardware), one can see
how it's useful to get keys up over that 80 bits mark, especially if
it's protecting data that has to be secret for any length of time.
(US Census data, by law, must remain secret for 99 years.)

Imagine not only trying to figure out how much money it would take to
build a machine to search a 96-bit keyspace today, but also in 99
years from now. Predicting what we'll be using next year is often
tricky enough, much less 10 years, 40 years, or 100 years down the
road. (See why we're paranoid?)

3. WHAT'S THE SOLUTION? (HOW DO WE FIX IT?)

It doesn't "cost" us much more, in terms of CPU cycles to encrypt
something with 128 bits, instead of 40 or 56. Yet, the level of
security that we enjoy as a result of that extra step is amazing.
We go from being able to trivially decrypt a message in seconds to
requiring more time than the age of the universe many times over.

The solution, then, is a simple matter of replacing our DES "locks"
with locks (cryptosystems) that use larger keys. Many such systems
exist: Triple-DES, IDEA, Blowfish, and RC5, to name just a handful of
the more well-known options. Data encrypted with DES must be
re-encrypted using the new cryptosystems, and applications must be
reprogrammed to stop using DES and begin using the new system for
their encryption.

To be "safe," then, the data that's been encrypted should be worthless
by the time someone is able to read it by using brute force. As an
example, a credit card that will expire in a year or two from now
might be OK to encrypt with a 64-bit cryptosystem. (Anyone who can
raise enough money to build a machine that will crack 64-bit-encrypted
messages would be able to find other means -- like bribing clerks --
to get the data he wants, so we'll only look at software-based attacks
like DESCHALL.) However, it would be stupid to encrypt census data
with a 64-bit algorithm, since DESCHALL could find the key in about 41
years (on the average). Factor in Moore's Law, and you're looking at
something that can probably be read in a decade with little-to-no
effort.

It's undesirable to change standards constantly, and be in a perpetual
process of upgrading the cryptographic modules of our software. It's
also unnecessary. Simply erring in favor of the paranoid and building
systems NOW with keys that seem ridiculously long, and re-encrypting
our small-key-encrypted data with these systems will adequately
address the problem.

...at least until someone gets a quantum or DNA computer working.
Then, all bets are off. :-)

References:
1 S.W.Hawking, _A_Brief_History_of_Time_. p.108. Published in 1988, by
Bantam.

-- 
Matt Curtin  Chief Scientist Megasoft Online  cmcurtin@research.megasoft.com
http://www.research.megasoft.com/people/cmcurtin/    I speak only for myself
Pull AGIS.NET's plug!  DES has fallen! http://www.frii.com/~rcv/deschall.htm