A new technique called differential cryptanalysis can break even DES quickly
Peter Wayner
How secure is your encrypted data? Advances in mathematics and increased computing power mean you need longer keys and stronger algorithms if you still want to keep your secrets. Both private-key encryption (which uses a single key for coding and decoding) and public-key systems (which use separate keys for encryption and decryption) are increasingly vulnerable to determined attack. But do these weaknesses represent a real threat to encrypted data, or are they still just intriguing research results?
Unfortunately, when we try to assess the effectiveness of today's popular cryptographic systems, we run into a problem of mathematical ignorance. Most people who are familiar with mathematics can work in two direc
tions, forward and backward, like the simple algebraic equation a = b + 1. We can determine the value of the first variable from that of the second and vice versa. Crypto systems, however, generally rely on mathematics that works only in one direction. People assume these systems are secure because no one has yet shown how to work the mathematics backward and break open the message. In general, we determine the strength of most cryptographic systems by seeing how well they avoid the attacks we know have been used on other systems. If none of the past attacks seems to work, then we deem a system secure. For now.
Let's look at how today's codebreakers work, the resources and time they need, and what we require in the way of new systems and longer keys. Recent assessments of the strength of private-key crypto systems involve looking for theoretical holes and measuring the time needed for a brute-force attack. Finding the holes can be devilishly hard, calling for deep mathematical insights. Brute-force atta
cks are easier to mount if enough computational hardware is available, but they're also easy to defend against.
The most important development in the realm of data encryption in recent years is Eli Biham and Adi Shamir's
differential cryptanalysis
. They showed how to mount a limited attack on today's most widely used cryptosystem, DES (the federal Data Encryption Standard), which is also the basis for Unix's password system.
Imagine that you had access to your victim's DES cipher "box" (the common term for an enciphering system) with preloaded keys. Your goal is to determine the 56-bit key, so that you can decrypt the other messages your victim had encrypted with the box. Biham and Shamir showed that you could infer the hidden key if you could pass 2(47) messages through the box and observe what came out. This
chosen plaintext attack
builds up a statistical model of the cipher, and it needs this many plaintexts to produce an answer with confidence.
Most intriguing, this wor
k exposed flaws in many DES substitutes. Because the U.S. government classified the details behind DES's design, many assumed that there might be a trapdoor through which the government could eavesdrop. To circumvent these potential trapdoors, some folks designed their own variations of DES. Most of these new ciphers, however, fall even faster to Biham and Shamir's mathematical machinery. FEAL-4, a faster replacement, for example, takes only four well-chosen plaintexts.
Recently, the IBM scientists who originally designed DES revealed that they anticipated Biham and Shamir's attack and optimized DES to resist it. Because other nongovernment cryptographers didn't know about this attack, they couldn't design their software to resist it. Now the information is public, and there are new ciphers that hold up well against these attacks. Ralph Merkle's Khufu and Bruce Schneier's Blowfish are two private-key ciphers that are similar to DES but resist differential cryptography. They do this by creating new S-box
es for each encryption, using the key to randomize them. (S-boxes are the essential scrambling elements of DES-like ciphers. Think of them as lookup tables or nonlinear functions; their outputs should be as random as possible.) Differential cryptanalysis works only if the attacker knows what's in the S-boxes.
This work also revealed some stunning counterintuitive results. Key length is usually taken as a rough measure of a system's security. DES uses 56-bit keys; a brute-force attacker might need to try all 2(56) keys to find the right one. A longer key would mean a longer brute-force attack. However, Biham and Shamir showed that even if DES used longer keys, it would hardly be any stronger against differential cryptanalysis. The statistical model would still be solvable if DES used the maximum of 768 bits.
Applying this knowledge to other types of ciphers is tricky. RSA Data Security markets a proprietary algorithm called RC-4 that accepts a variable-length key; this algorithm is used in many pro
ducts. The flexible key length can be an advantage in some situations. For example, the government allows general export of software using RC-4 with a 40-bit key, but similar software using a longer key must stay within the U.S. While we don't know if differential cryptanalysis can be applied to RC-4 directly, because of the algorithm's proprietary nature, the results with DES suggest that more key is not necessarily stronger.
Men and Machines
Mathematical tools like differential cryptanalysis can be the most powerful attack against a cipher system. Brute-force attacks are normally a last resort, rare in practice because cipher designers routinely use long key lengths specifically to preclude them. But times are changing. We're reaching a point at which a large machine can quickly search the entire keyspace of DES. DES is still in wide use; it's been the commercial and governmental standard for nearly two decades. Replacing such standards can be a painfully slow process. DES use
rs should be thinking about what can be done with off-the-shelf hardware.
Brute-force attacks simply use large machines that try all possible passwords in parallel. It's even possible to produce native chips that run DES. Michael Wiener of Bell Northern Research described how to build a $1 million machine using a pipelined DES processor that could cruise through all possible keys in about 7 hours.
Massively parallel machines can also attack the problem. Some of the most promising emerging machines distribute small, 1-bit processors directly onto the memory chips. Some have 1024 processors on a chip with 42 bits of memory per processor. (Before it entered Chapter 11, Cray Computer was building for the National Security Agency a special Cray 3 with such processor-embedded memory.) In 1992 I designed a machine using 1 million associative processor memory chips (standard DRAM densities) from Coherent Research (Syracuse, NY) that could attack all of DES in one day. This machine could be reprogrammed to
attack other DES-like ciphers. Linden Technology (Austin, TX) is currently exploring manufacturing new 4-Mb DRAMs with the 1024 associative processors built onto the chip.
The effect of brute-force attacks on DES is also important for Unix security, which stores each password after passing it through DES 25 times. At log-in, you type your password; it's encrypted 25 times and the result compared against the password file. If it matches, the system grants you access. Because the password file doesn't contain the passwords themselves, unauthorized users can't use the file to recover them directly. They must use a brute-force machine. However, the brute-force attack can be relatively successful against Unix, because the keyspace is smaller. Most users limit their passwords to alphabetic characters, occasionally adding numbers. This makes searching for passwords much faster; it could be done quite quickly with an associative-memory parallel processor. One estimate suggests that a computer using 512 of Lind
en's chips could test all six-character alphanumeric passwords in 15 minutes. Clearly, the Unix password structure needs to be rethought in light of today's machines and code-breaking techniques.
Because of this new vulnerability, you may want to explore other, newer ciphers, such as Merkle's Khufu or Schneier's Blowfish. The classified Skipjack algorithm buried inside the U.S. government's Clipper and Capstone encryption chips also uses S-boxes, but little is known about their design. There's little reliable public information about RSA Data Security's RC-4. Anyone who uses these algorithms must be prepared to trust the wits of the designers, because the algorithms have not undergone the intensely thorough and long-time public scrutiny given to DES.
Many organizations have opted to continue with DES, but the current state of the art is triple-DES -- three passes of the algorithm with either 112- or 168-bit keys. This effectively guards against both brute-force and differential analysis attacks. T
hese users can rest assured that, paradoxically, all the attacks focused on DES continues to keep it strong.
WHERE TO FIND
RC-4
RSA Data Security, Inc.
Redwood City, CA 94065
(415) 595-8782
fax: (415) 595-1783
Strengths and Weaknesses of Crypto Algorithms
ALGORITHM COMMENT STRENGTHS WEAKNESSES
==========================================================================
DES Standard, Long-tested Has yielded to DC
widely accepted
FEAL-4 DES substitute Easily broken by DC
GDES, NewDES DES-like Easily broken by DC
Khufu DES-like Secure against DC New, unknown
Blowfish DES-like Secure against DC New, unknown
RC-4 Proprietary Variable-length key Unknown
RSA Public Key Widely used
Long-tested Vulnerable to
advances in
factoring
Skipjack Classified Considered strong Algorithm must
remain secret
to preserve
law-enforcement
trapdoor
DC = differential cryptanalysis
Peter Wayner is a BYTE consulting editor living in Baltimore, MD. You can reach him on the Internet at
pcw@access.digex.net
, on BIX as
pwayner@bix.com
, or on the World Wide Web at
http://access.digex.net/pcw/pcwpage.html
.
Picking the Crypto Locks
