What DESCHALL Means

With all of the press that DESCHALL has gotten, lots of people are asking "what does this mean?" What follows is an explanation, written for the nontechnical reader. This is important for all of us, because regardless of whether you like it, information about you is protected with DES.

For a more technical consideration of the DESCHALL project, please see "A Brute Force Search of DES Keyspace".

What's a cryptosystem?

Cryptosystems are locks for data. By using mathematical functions (called algorithms), 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. (In computers, we use "bits" instead of tumblers, but for our purposes here, it means the same thing.)

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) -- 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³ = 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:

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.

DES is a 56-bit cryptosystem, first pronounced a standard in 1977. At that time, it was infeasible for someone to try each of more than 72 quadrillion possibilities and find the contents of the encrypted file. At that time, it was safe. We've proven that this is no longer the case.

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 (called a client) on their computer that has no noticeable effect on their systems' performance.

It is noteworthy that this is the first time that a message encrypted with DES has been broken "in public." It's been widely believed that large governments' intelligence agencies (such as the NSA in the US) have been able to do this for quite a few years now.

That client 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 every possible key until the right one is found. This is the computer equivalent of turning the tumblers of a bicycle lock to

0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000

and pulling the chain to see if it unlocks. If not, we turn it to

0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000001

and try again. We do this until we find the right combination, which, by the way, was

1000010 0101100 1000100 0001101 1011000 1100100 0101000 1011011

Which means that we tried 37,350,551,110,358,107 of 72,057,594,037,927,936 possible keys.

(Mathematicians, please forgive the following oversimplification. We can compensate for the extra work needed to compute RC5 by adding more computers to the project, so this comparison is possible.)

For comparison, Hawking[1] notes that the age of the universe is probably "only" 20,000,000,000 (or perhaps 10,000,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 72 years[2].)

If we were interested in going after a real target, with real value, then we would certainly have a budget with which we could build a machine specifically for the purpose of cracking keys. Here's a chart from [3] that shows how quickly DES-encrypted messages could be broken with machines of various costs. Keep in mind that this is already a year and a half old, and that with the falling cost of hardware, and the increasingly available power, we could actually do more for less money now. (Also note that we have proven that what is labeled "infeasible" here can be done using scavanged computer time in about three months.)

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?)

What's the Solution? (How Do We Address this Problem?)

It doesn't "cost" us much more, in terms of computer 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.

2 U.S. Census Bureau. http://www.census.gov/genealogy/www/

3 M. Blaze, W. Diffie, R. Rivest, B. Schneier, T. Shimomura, E. Thompson, M. Wiener. Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security. January 1996.