Crypto-Gram

January 15, 1999

by Bruce Schneier
President
Counterpane Systems

schneier@schneier.com
http://www.counterpane.com

A free monthly newsletter providing summaries, analyses, insights, and commentaries on cryptography and computer security.

Copyright (c) 1999 by Bruce Schneier

In this issue:

The 1998 Crypto Year-in-Review

1998 was an exciting year to be a cryptographer, considering all the developments in algorithms, attacks and politics. At first glance, the important events of the year seem completely unrelated: done by different people, at different times, and for different reasons. But when we step back and reflect on the year-that-was, some common threads emerge—as do important lessons about the evolution and direction of cryptography.

New Algorithms

In June, the NSA declassified KEA and Skipjack. KEA is a public-key Key Exchange Algorithm <http://www.schneier.com/crypto-gram-9808.html#kea>, while Skipjack is a block cipher first used in the ill-fated Clipper Chip <http://www.schneier.com/crypto-gram-9807.html#skip>. The NSA wanted Fortezza in software, and the only way they could get that was to declassify both algorithms.

This marks the first time that an NSA-developed algorithm has been declassified and released into the public domain, and also the first time that the U.S. military has used a public algorithm to encrypt classified traffic. More importantly, the release of Skipjack marks a watershed event in public cryptanalysis. Like DES, a reference algorithm by which all attacks were measured, Skipjack is an example of a “reference good algorithm.” Think of it as alien technology: for the next decade researchers will pick Skipjack apart, looking for clues on how to design and analyze block ciphers.

And there are lots of block ciphers to analyze. In June, candidates for the Advanced Encryption Standard (AES), the replacement to DES, were submitted to NIST <www.nist.gov/aes>. NIST’s goal is to replace DES with another block cipher, one with a 128-bit block size and a key size of 128, 192 or 256 bits. Fifteen groups (companies, universities, individuals) submitted algorithms from the United States and abroad.

The process is a long one. Currently, all 15 algorithms are being reviewed by the crypto community. NIST will host a public workshop in Rome this March, with the public comment period ending this June. After that, NIST will pick about five candidates for a second round. Another workshop and public comment period will follow, after which NIST will pick a single winner sometime in 2000. Following that, they will take the algorithm through the FIPS process, and it will hopefully become an ANSI, ISO, and IETF standard as well.

The AES review process is important for several reasons. First, DES is just too weak for modern use (see below). Second, since there’s no emergency, NIST can take its time and do this correctly. And third, if everyone plays fair, there will be an encryption standard that is endorsed by the cryptographic community, one not subject to NSA tampering.

New Attacks

1998 also saw several important developments in the flip side of cryptology: cryptanalysis. Quite simply, a lot of things were broken last year.

In July, the Electronic Frontier Foundation (EFF) built Deep Crack, a hardware DES cracker that can break DES in an average of four-and-a-half days <http://www.eff.org/descracker>. The $220,000 machine was not built to steal secrets or embezzle money, but to inarguably demonstrate that DES’s 56-bit key is too short for any real security.

The news here is not that DES is insecure, that hardware algorithm-crackers can be built, or that a 56-bit key length is too short. We already knew this; cryptographers have been saying it for years (I said it in my book, Applied Cryptography, back in 1994). Technological predictions about the declining costs of such a machine—predictions made from the late 1970s onward—turned out to be dead-on.

Rather, the news is how long the government has been denying that these machines were possible. As recently as June 8, 1998, Robert Litt, principal associate deputy attorney general at the U.S. Department of Justice, denied that it was possible for the FBI to crack DES. “[It is a myth that] we have supercomputers that can crack anything that is out there,” Litt said at an EPIC conference. “Let me put the technical problem in context: It took 14,000 Pentium computers working for four months to decrypt a single message…. We are not just talking FBI and NSA [needing massive computing power], we are talking about every police department.” Litt looked foolish at the time, and he looks even more foolish now. (See also: <http://www.schneier.com/…>)

What Litt was talking about was another achievement of 1998: the cracking of the DES-II-1 challenge in February. This was a software-only search of DES’s 56-bit keyspace using spare cycles on computers connected to the Internet. This break was a monumental distributed processing effort—yet another piece of evidence that 56-bit keys are just too short.

Not So Smart Cards

Cryptanalysts gave smart cards a good whack when researchers invented power analysis. In June, Paul Kocher and others demonstrated that secrets could be extracted from a smart card by watching the card’s power usage <http://www.cryptography.c om/dpa/index.html>. Researchers have demonstrated this attack in several laboratories, extracting secret keys, bank balances, and everything else from supposedly secure smart cards.

The important concept here is that there’s another way of looking at a cryptographic algorithm. We’re used to treating algorithms as mathematics, but they can also be looked at as systems. It’s a biological approach: What are its inputs and outputs? How does it move? How does it respond to different stimuli? By looking at a smart card as a concrete device with timing, power, radiation and other characteristics, it’s possible to attack many systems that were previously believed to be secure. By combining these techniques with fault analysis—another “biological” attack that measures how a smart card responds to randomly induced faults—the result is even more devastating <http://www.schneier.com/crypto-gram-9806.html#side>.

What these attacks are telling us is not that we have to spend more effort making smart cards resistant—that’s probably not possible—but that we need to rethink how data is stored on smart cards. A system in which a device is owned by one party and the secrets within the device are owned by another is, fundamentally, a badly designed system. Well-designed systems don’t care about these attacks, because there are no secrets on the card that the cardholder wants.

No Substitutes

Some pretty lousy cryptography was exposed in 1998. In April, University of California Berkeley researchers found flaws in the GSM digital cellular encryption algorithm, used in about 90 million cell phones worldwide <http://www.isaac.cs.berkeley.edu/isaac/gsm.html>. And in an unrelated incident, in June researchers found flaws in Microsoft’s PPTP protocol, used as a virtual private network (VPN) security protocol by many companies <http://www.schneier.com/pptp.html>.

The moral from these two attacks is not that it’s hard to do cryptography right and it’s easy to make mistakes: we already knew that. The moral is that there is no substitute for the public review process when it comes to security. Both the GSM cellular system and Microsoft’s PPTP system were designed by a closed group and remained proprietary. No one person or group can be expert in all things, and as a result both systems had major flaws. But because they were proprietary, the flaws were only discovered after the systems had been fielded.

Contrast this approach with that for IPSec, a protocol for secure Internet traffic. This protocol was developed in a public working group, and every step of the process has been available for public review. As with GSM and PPTP, the group designing IPSec was not expert in all things, and, to be sure, there were flaws. But these flaws were discovered by others involved in the process while the process was going on. The system has been broken, fixed, broken again, fixed again and so on. In the end we have a very robust system, the result of many people examining and commenting on drafts. This kind of expertise simply cannot be purchased by a single organization, and it’s foolish to believe otherwise.

High-Profile Cracks

In July, a Bell Labs researcher broke the RSA implementation in PKCS #1 <http://www.schneier.com/crypto-gram-9807.html#rsa>. PKCS #1 is a padding scheme used in many products (SSL is probably the most widely known), and the attack worked in an operational setting against these products. Vendors scrambled to fix the problem—the fix was easy, once you knew the problem—but the attack showed that even if the underlying algorithm is secure (RSA, in this example), the implementation may not be.

In August, two French cryptographers described an attack against SHA-0. For those who don’t remember, SHA is a NIST-standard hash function. It was invented by the NSA in 1993, and is largely inspired by MD4. In 1995, the NSA modified the standard (the new version is called SHA-1; the old version is now called SHA-0). The agency claimed that the modification was designed to correct a weakness, although no justification was given. Well, we now understand the attack against SHA-0 and how the modification prevents it.

Also in August, a group of Israeli cryptographers presented “impossible differential cryptanalysis.” This is an esoteric mathematical cryptanalytic attack, applicable against several academic ciphers and one high-profile fielded one. Surprisingly enough, impossible differentials work against a Skipjack variant with 31 rounds (the real cipher has 32 rounds). (See <http://www.schneier.com/…>.)

The implications of this attack are major. There are two possible explanations: (1) The NSA didn’t know about this attack, in which case academic cryptographers have scored a major win over our military counterparts; or (2) the NSA did know about this attack, in which case they have some kind of mathematical model that permits them to field algorithms that are just marginally above the break point. Either explanation is fascinating, and points to some interesting research to come.

Old News

Some of the news in 1998 wasn’t really news at all, since we all knew what was coming.

In fall 1997, the first public-key patents expired. These patents had prevented people from implementing all public-key cryptographic algorithms (not just RSA) without paying royalties. So, in 1998 free public-key algorithms were used in standards for the first time; now, people can implement Diffie-Hellman key exchange, ElGamal encryption and ElGamal signatures without paying royalties to anyone.

Finally, serious doubts were again raised about feasibility of key escrow <http://www.schneier.com/paper-key-escrow.html>. Again, this isn’t “new” news. Researchers have long argued that the kind of key escrow the FBI wants causes more problems than it solves. In June, a distinguished group of cryptographers released a report explaining just how insecure such a system would be. The report looked at several new vulnerabilities that key escrow can introduce, including new ways of breaking messages, loss of security control, abuse by insiders, single points of attack and failure, loss of secrecy assumptions and complicated system design. The amazing thing about this analysis is not that it echoes the NSA’s own internal analysis (which it does), but that the more we learn about how to design and attack systems the harder this problem is to solve.

What About ’99?

Looking back, most of the highlights from 1998 were completely unpredictable in December 1997. Similarly, we have no idea what cryptographic success 1999 will bring. Some predictions are obvious: NIST will choose finalists for the AES selection process; the RSA patent won’t expire—that will happen in September 2000; and key escrow won’t get any more secure. For sure, there will be some interesting cryptanalytic results against some interesting algorithms. And some products we all use will be found to be weak, and hopefully they will be corrected.

But beyond these general observations, no one knows. Cryptography is a unique science because research can go backwards in time. A new compression algorithm might be better, but it won’t make the old algorithms compress any less efficiently. A new cryptographic technique can make already fielded algorithms, protocols, and products less secure. There are a lot of very clever people working in cryptography, and it is unlikely they will have a dry year. Stay tuned for more information—as people invent it.

(This originally appeared in the January 1998 issue of Information Security: <http://www.infosecuritymag.com>.)

Counterpane Systems—Featured Research

“Environmental Key Generation towards Clueless Agents”

J. Riordan and B. Schneier, Mobile Agents and Security, G. Vigna, ed., Springer-Verlag, 1998, pp. 15-24.

This paper discusses the notion of “clueless agents,” pieces of encrypted mobile code that cannot be decrypted until some external event occurs. The idea is to build the computer equivalent of sleeper agents, who don’t even know their own function and hence cannot be compromised. (Think of “The Manchurian Candidate.”) As mobile code becomes more common, we see clueless agents becoming more important.

http://www.schneier.com/paper-clueless-agents.html

News

Human Rights watch has issued a report about restrictions on Internet speech around the world. The full report, “Freedom of Expression on the Internet,” is at:
http://www.hrw.org/hrw/worldreport99/special/…
A summary can be found at:
http://www.nytimes.com/library/tech/98/12/cyber/…

The Congressional comedy of Speakers resigning and new ones being chosen will have a negative effect on the fight for free cryptography in the U.S. Livingston supported the industry’s version of SAFE, the crypto decontrol bill that died in Congress last session. Hastert (the front-runner for Speaker of the House at this time) has shown strong solidarity with the FBI on encryption issues as a member of the House Commerce Committee. Hastert supported the Oxley-Manton Amendment that would have turned the SAFE Act of 1997 into a mandate for domestic regulation of encryption. And when Oxley-Manton was rejected by the Committee in favor of the Markey-White Amendment, Hastert voted against the SAFE Act.

“The Inevitability of Failure: The Flawed Assumption of Security in Modern Computing Environments.” This paper is by six NSA employees, and argues for secure operating systems in order to adequately address current and future security needs:
http://www.jya.com/paperF1.htm

Netscape 4.X can be used to read a file on a remote machine without the permission of the owner of that machine. The initial posting on the topic can be found at:
http://lwn.net/1998/1203/netscape.html
Additional postings can be found in the Bugtraq archives at:
http://geek-girl.com/bugtraq/ [link moved to http://www.securityfocus.com/archive/1/-1]

I’m not sure what to make of this next story. Security Computing Corporation <http://www1.securecomputing.com/index.cfm?skey=85> [link dead], sells a content filter (“SmartFilter”) that is used to restrict web access from within corporations and other organizations. Lauren Weinstein, the moderator of the widely respected Privacy Forum, a mailing list and web site on the Internet at <http://www.vortex.com>, recently reported that for over a year corporate employees at sites that use SCC’s SmartFilter have typically been restricted from accessing the Privacy Forum web site or archives because of the Privacy Forum’s occasional discussion of cryptography. These discussions—high-level discussions of civil and ethical values, policy, and crypto politics—were apparently enough to define the Privacy Forum web site as a repository of “criminal skill.”

In September, the National Academy of Sciences issued “Trust in Cyberspace,” a 243-page survey of all security issues and technologies associated with the Internet and computer networks. The report reviews prior studies such as the CRISIS report on cryptography, the PCCIP report on protecting US infrastructure, the DoD report on Information Warfare-Defense, and several others. It assesses those findings in greater depth, looks at technology and research needed, and recommends what government (NSA and DARPA) and private industry/education should do to assure security. NSA is upbraided for its opposition to strong cryptography and culture of over-controlling secrecy. NSA’s R2 research unit is singled out as needing to find ways to compete with industry for the best talent so that the agency’s skills and tools do not lag behind the world market.

Introduction only:
http://jya.com/tic-intro.htm (Introduction only, 58K)
Full report:
http://cryptome.org/tic.htm or http://cryptome.org/tic.zip

Crypto++ 3.0 has just been released. This is a fine, free crypto source code library. You can find download instructions on the Crypto++ home page at:
http://www.eskimo.com/~weidai/cryptlib.html
http://cryptography.org/cgi-bin/crypto.cgi/…

Electronic Frontiers Australia has posted an uncensored copy of the “Review of Policy relating to Encryption Technologies” (the Walsh Report) on its web site. The originally censored parts are highlighted in red. The report was prepared in late 1996 by Gerard Walsh, former deputy director of the Australian Security Intelligence Organisation (ASIO). It was supposed to be released to the public, but it wasn’t. Eventually, a censored version was released. Officially, this uncensored version has not been released. It’s worth reading, especially the censored parts.
http://www.efa.org.au/Issues/Crypto/Walsh/index.htm

The press is buzzing about an Irish teenager creating a brilliant new public-key scheme called Cayley-Purser, supposedly much better than RSA. “Even when high security levels are required, her code can encrypt a letter in just one minute—a widely used encryption standard called RSA would take 30 minutes. ‘But she has also proven that her code is as secure as RSA,’ says Dr Flannery. ‘It wouldn’t be worth a hat of straw if it was not.'” Leaving aside the incredibly quaint Irish metaphor, this is what I do know: The system is based on RSA, but I have not seen it. It is believed to be as strong as RSA, but there is no proof. The key and the ciphertext are about eight times the length of the modulus, rather than more-or-less the length of the modulus as with RSA. It is faster, but I don’t know by how much and under what assumptions. Is this going to change the world, no. Might it be interesting, yes. We’ll have to wait and see. In any case, it is cool to see serious cryptography out of a new researcher.
http://news.bbc.co.uk/hi/english/sci/tech/…
http://www.msnbc.com/news/231690.asp [dead link as of 1999-08-31]
http://jya.com/flannery.htm

The Indian Defence Research and Development Organisation (DRDO) has issued a “red alert” against all network security software developed in the US. The government is concerned that all U.S. software is weak and may contain government back doors.
http://www.economictimes.com/120199/lead2.htm [dead link as of 1998-08-25]

Furbys have been banned from the NSA, due to the possibility of them mimicking what they hear. The fear is “that people would take them home and they’d start talking classified.”
http://news.bbc.co.uk/hi/english/world/americas/…

Counterpane Systems News

Counterpane Systems will be featured in several panels at the 1998 RSA Conference in San Jose next week:

Mon, 3:00 PM. Securing Audit Trails in Electronic Commerce. Bruce Schneier will talk about how to secure audit trails so that they can be used as a forensics tool. This is a continuation of the research found in <http://www.schneier.com/paper-secure-logs.html>.

Tue, 4:00 PM. The Twofish Encryption Algorithm. Twofish design team member Doug Whiting will explain the algorithm and its implementation options.

Tue, 6:30 PM. Extending PKI to Legacy Applications. One of the companies we’re working with, LockStar <http://www.lockstar.com>, will debut at the RSA Conference next week. Bruce Schneier will speak on the above topic. It’s in the Santa Clara room at the Hilton. There’ll be food.

Wed, 2:00 PM. A Hacker Looks at Cryptography. Bruce Schneier will speak at the Valicert booth. It’s a cheap trick to get into their booth, but I’ll be entertaining and their booth is actually pretty cool.

Wed, 4:00 PM. Pseudorandom Number Generation & Testing. Counterpane cryptographer John Kelsey will discuss Yarrow, our free random number generator: <http://www.schneier.com/yarrow.html>.

The big Twofish news is that we’ve got the encryption speed down to 258 clocks, or 16 clocks per byte. Twofish was already the fastest algorithm on the Pentium, but now it is only 3% (7 clocks) slower than RC6 on the Pentium Pro/II.

Comments From Readers

From: Reinhard Wobst <R.Wobst@ifw-dresden.de>
Subject: plaintext recognition

Your article about plaintext recognition is important. I think people don’t recognize that *any* plaintext format which obeys deterministic or probabilistic rules can be easily tested. An example: Take a file generated by “compress” (which uses Ziv-Level compression) and cut off the 3 magic bytes (otherwise the task would be too easy). Then divide the bitstream into 9 bit words. The nth word can have a value not greater than 257+n. So 7 ciphertext blocks should be enough to determine a 56-bit DES key uniquely.

If you have GIF, JPEG or other graphic formats, then they must be expandable to pictures. A picture can be defined by “most significant bits 1…8 should not be white noise”. This should theoretically suffice to detect plaintext. The practical problem is the computation time. One has to find fast tests to drop the bad samples. My idea is to write several rough and fast tests: the first (fastest) excludes 90% of bad samples, the second 80% of the rest and so on. In practice, the speed of the first tests determines the speed of the whole procedure.

Any data format with some *deterministic* relation between the bits and/or bytes should be even easier to test than an ASCII text which could contain some odd characters. The most trivial example are word processors which produce lots of fixed bytes in fixed positions. (The first KB of my WordPerfect files contain about 40% of zero bytes, for example.)

Almost nobody in the “civil world” cares about such tests. For demonstration purposes, I wrote a C program that cracks Vigenere enciphered compressed files (not using the magic bytes!). It is contained on the CD in my book “Abenteuer Kryptologie.” I found up to 64 byte long passwords within dozens of seconds.

CRYPTO-GRAM is a free monthly newsletter providing summaries, analyses, insights, and commentaries on cryptography and computer security.

To subscribe, visit http://www.schneier.com/crypto-gram.html or send a blank message to crypto-gram-subscribe@chaparraltree.com. Back issues are available at http://www.schneier.com. To unsubscribe, visit http://www.schneier.com/crypto-gram-faq.html.

Please feel free to forward CRYPTO-GRAM to colleagues and friends who will find it valuable. Permission is granted to reprint CRYPTO-GRAM, as long as it is reprinted in its entirety.

CRYPTO-GRAM is written by Bruce Schneier. Schneier is president of Counterpane Systems, the author of Applied Cryptography, and an inventor of the Blowfish, Twofish, and Yarrow algorithms. He served on the board of the International Association for Cryptologic Research, EPIC, and VTW. He is a frequent writer and lecturer on cryptography.

Counterpane Systems is a five-person consulting firm specializing in cryptography and computer security. Counterpane provides expert consulting in, design and analysis, implementation and testing, threat modeling, product research and forecasting, classes and training, intellectual property, and export consulting. Contracts range from short-term design evaluations and expert opinions to multi-year development efforts.

Sidebar photo of Bruce Schneier by Joe MacInnis.