Picking the Crypto Locks

Byte, October, 1995, pp. 77, 80. Picking the Crypto Locks A new technique called differential cryptanalysis can break even DES quickly By 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 directions, 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 attacks 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 247 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 work 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. _______________________________________________________ Strengths and Weakness of Crypto Algorithms _______________________________________________________ Algorithm Comment Strengths Weaknesses _______________________________________________________ DES Standard, Long-tested Has yielded Widely to DC Accepted _______________________________________________________ FEAL-4 DES Easily broken substitute by DC _______________________________________________________ GDES, DES-like Easily broken New DES by DC _______________________________________________________ Khufu DES-like Secure New, unknown against DC _______________________________________________________ Blowfish DES-like Secure New, unknown against DC _______________________________________________________ RC-4 Proprietary Variable- Unknown length key _______________________________________________________ RSA Widely used Long-tested Vulnerable to Public Key advances in factoring _______________________________________________________ Skipjack Classified Considered Algorithm must strong remain secret to preserve law-enforcement trapdoor _______________________________________________________ DC = differential cryptanalysis _______________________________________________________ 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-boxes 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 products. 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 users 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 promismg emergmg 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 densihes) 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 Linden'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. These users can rest assured that, paradoxically, all the attacks focused on DES continues to keep it strong. ----- 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. ----- Byte, October, 1995, p. 78. Factoring in Public-Key's Future Long thought nearly unbreakable, public-key cryptogratphy is yielding to attack. The secret of security here is key length. By Bruce Schneier Factoring large numbers is hard but not as hard as it used to be. This has grave implications for the effectiveness of public key cryptocraphy, which relies on the difficulty of factoring long keys for its security. But how long is long enough'? In 1976, Richard Guy wrote: "I shall be surprised if anyone regularly factors numbers of size 10^80 without special form during the present century." In 1977, Ron Rivest said that factoring a 125-digit number would take 40 quadrillion years. In 1994, a 129-digit number was factored. The lesson here is that making predictions is foolish. Today, 512-bit keys are common. Factoring them, thus destroying their security, is well within the range of possibility for today's computing resources. A weekend- long worm on the Internet could do it. Computing power is measured in MIPS-years: a million-instructions-per-second computer running for one year, or about 3 x 10^13 instructions. A 100-MHz Pentium is about a 50-MIPS machine; a 1600-node Intel Paragon is about 50,000 MIPS. In 1983, a Cray X-MP supercomputer factored a 71-digit number in 0.1 MIPS-years, using 9.5 CPU hours. That's expensive. Factoring the 129-digit number in 1994 required 5000 MlPS-years and used the idle time on 1600 computers around the world over an eight-month period. Although it took longer, it was essentially free. Those two computations used what's called the *quadratic sieve*, but a newer, more powerful algorithm has arrived. The *general number filed sieve* is faster than the quadratic sieve for numbers well below 116 digits and can factor a 512-bit number over 10 times faster -- it would take less than a year to run on an 1800-node Intel Paragon. And the process gets still faster. Mathematicians keep coming up with new tricks, new optimizations, and new techniques. A related algorithm, the special number field sieve, can already factor numbers of a specialized form (not generally used for cryptography) much faster. So we can probably optimize the general number field sieve to run that fast. For all we know, the National Security Agency is already doing it. The figure "MIPS Years Needed to Factor" gives the number of MlPS-years required to factor "special" and "general" numbers of different lengths. How Big Is Big Enough? The wise cryptographer is ultraconservative when choosing key lengths for a public-key system. You must consider the intended security, the key's expected lifetime, and the current state of the factoring art. Now you need a 1024-bit number to get the same security you got from a 512-bit number in the early 1980s. If you want your keys to remain secure for 20 years, 1024 bits is probably too short. Consider these assumptions from the mathematicians who factored RSA-129: We believe we could acquire 100,000 machines without superhuman or unethical efforts and without an Internet womm or virus. Many organizations have several thousand machines on the Net. Using their facilities would require diplomacy but should not be impossible. Assuming an average power of 5 MIPS and one year elapsed time, we could reasonably embark on a project that would require half a million MIPS-years. The project to factor the 129-digit number harnessed an estimated 0.03 percent of the Internet's total computing power. A well-publicized project might be able to harness 2 percent of the world's computing power for a year. My recommendations for public-key lengths are given in the figure "Recommended Public-Key Key Lengths" according to how long you require the key to be secure. There are three key lengths given for each period -- one secure against an individual cryptanalyst who can get his hands on 10,000 MlPS-years, one against a major corporation that could harness 10^7 MIPS-years, and the third secure against a major govemment and 10^9 MIPS-years. These figures assume that computing power will increase by a factor of 10 every five years and that mathematical advances will let us factor numbers at the speeds of the special number field sieve. Not everyone will agree with these final recommendations. The National Institute of Standards and Technology has mandated 512- to 1024-bit keys for its Digital Signature Standard. PGP has a maximum RSA key length of 1280 bits. Aljen Lenstra, the world's most successful factorer, refuses to predict beyond 10 years. There's always the possibility that an advance in factoring will surprise me as well, though I tried to factor everything into my calculations. But why trust me? I just proved my own foolishness by making predictions. _______________________________________________________ MIPS Years Needed to Factor _______________________________________________________ Ascending Line of General Number Field Sieve Ascending Line Special Number Field Sieve Y-axis: MIPS-years 10^0, 10^3, 10^6, 10^9, 10^12, 10^15, 10^18, 10^21 X-axis: Bits 512, 768, 1024, 1280, 1536, 2048 _______________________________________________________ _______________________________________________________ Recommended Public-Key Key Lengths _______________________________________________________ Ascending bars for: Individual, Company, Government Y-axis: Bits 0, 500, 1000, 1500, 2000, 2500 X-axis: Year 1995 2000 2005 2010 2015 _______________________________________________________ ----- Bruce Schneier is the author of Applied Cryptography (John Wiley), the second edition of which is due out in December. He can be reached on the Internet as schneier@winternet.com, or on BIX c/o editors@bix.com. -----