December 15, 1998

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) 1998 by Bruce Schneier

---

In this issue:

• The Fallacy of Cracking Contests
• How to Recognize Plaintext
• News
• The Doghouse: Iomega Zip Disks
• Counterpane Systems News
• Final Report from the Commerce Department Technical Advisory Committee on Key Recovery
• Comments From Readers
• About “CRYPTO-GRAM”

---

The Fallacy of Cracking Contests

You see them all the time: “Company X offers $1,000,000 to anyone who can break through their firewall/crack their algorithm/make a fraudulent transaction using their protocol/do whatever.” These are cracking contests, and they’re supposed to show how strong and secure the target of the contests are. The logic goes something like this: We offered a prize to break the target, and no one did. This means that the target is secure.

It doesn’t.

Contests are a terrible way to demonstrate security. A product/system/protocol/algorithm that has survived a contest unbroken is not obviously more trustworthy than one that has not been the subject of a contest. The best products/systems/protocols/algorithms available today have not been the subjects of any contests, and probably never will be. Contests generally don’t produce useful data. There are three basic reasons why this is so.

1. The contests are generally unfair.

Cryptanalysis assumes that the attacker knows everything except the secret. He has access to the algorithms and protocols, the source code, everything. He knows the ciphertext and the plaintext. He may even know something about the key.

And a cryptanalytic result can be anything. It can be a complete break: a result that breaks the security in a reasonable amount of time. It can be a theoretical break: a result that doesn’t work “operationally,” but still shows that the security isn’t as good as advertised. It can be anything in between.

Most cryptanalysis contests have arbitrary rules. They define what the attacker has to work with, and how a successful break looks. Jaws Technologies provided a ciphertext file and, without explaining how their algorithm worked, offered a prize to anyone who could recover the plaintext. This isn’t how real cryptanalysis works; if no one wins the contest, it means nothing.

Most contests don’t disclose the algorithm. And since most cryptanalysts don’t have the skills for reverse-engineering (I find it tedious and boring), they never bother analyzing the systems. This is why COMP128, CMEA, ORYX, the Firewire cipher, the DVD cipher, and the Netscape PRNG were all broken within months of their disclosure (despite the fact that some of them have been widely deployed for many years); once the algorithm is revealed, it’s easy to see the flaw, but it might take years before someone bothers to reverse-engineer the algorithm and publish it. Contests don’t help.

(Of course, the above paragraph does not hold true for the military. There are countless examples successful reverse-engineering—VENONA, PURPLE—in the “real” world. But the academic world doesn’t work that way, fortunately or unfortunately.)

Unfair contests aren’t new. Back in the mid-1980s, the authors of an encryption algorithm called FEAL issued a contest. They provided a ciphertext file, and offered a prize to the first person to recover the plaintext. The algorithm has been repeatedly broken by cryptographers, through differential and then linear cryptanalysis and by other statistical attacks. Everyone agrees that the algorithm was badly flawed. Still, no one won the contest.

2. The analysis is not controlled.

Contests are random tests. Do ten people, each working 100 hours to win the contest, count as 1000 hours of analysis? Or did they all try the same things? Are they even competent analysts, or are they just random people who heard about the contest and wanted to try their luck? Just because no one wins a contest doesn’t mean the target is secure…it just means that no one won.

3. Contest prizes are rarely good incentives.

Cryptanalysis of an algorithm, protocol, or system can be a lot of work. People who are good at it are going to do the work for a variety of reasons—money, prestige, boredom—but trying to win a contest is rarely one of them. Contests are viewed in the community with skepticism: most companies that sponsor contests are not known, and people don’t believe that they will judge the results fairly. And trying to win a contest is no sure thing: someone could beat you, leaving you nothing to show for your efforts. Cryptanalysts are much better off analyzing systems where they are being paid for their analysis work, or systems for which they can publish a paper explaining their results.

Just look at the economics. Taken at a conservative $125 an hour for a competent cryptanalyst, a $10K prize pays for two weeks of work, not enough time to even dig through the code. A $100K prize might be worth a look, but reverse-engineering the product is boring and that’s still not enough time to do a thorough job. A prize of $1M starts to become interesting, but most companies can’t afford to offer that. And the cryptanalyst has no guarantee of getting paid: he may not find anything, he may get beaten to the attack and lose out to someone else, or the company might not even pay. Why should a cryptanalyst donate his time (and good name) to the company’s publicity campaign?

Cryptanalysis contests are generally nothing more than a publicity tool. Sponsoring a contest, even a fair one, is no guarantee that people will analyze the target. Surviving a contest is no guarantee that there are no flaws in the target.

The true measure of trustworthiness is how much analysis has been done, not whether there was a contest. And analysis is a slow and painful process. People trust cryptographic algorithms (DES, RSA), protocols (Kerberos), and systems (PGP, IPSec) not because of contests, but because all have been subjected to years (decades, even) of peer review and analysis. And they have been analyzed not because of some elusive prize, but because they were either interesting or widely deployed. The analysis of the fifteen AES candidates is going to take several years. There isn’t a prize in the world that’s going to make the best cryptanalysts drop what they’re doing and examine the offerings of Meganet Corporation or RPK Security Inc., two companies that recently offered cracking prizes. It’s much more interesting to find flaws in Java, or Windows NT, or cellular telephone security.

The above three reasons are generalizations. There are exceptions, but they are few and far between. The RSA challenges, both their factoring challenges and their symmetric brute-force challenges, are fair and good contests. These contests are successful not because the prize money is an incentive to factor numbers or build brute-force cracking machines, but because researchers are already interested in factoring and brute-force cracking. The contests simply provide a spotlight for what was already an interesting endeavor. The AES contest, although more a competition than a cryptanalysis contest, is also fair.

Our Twofish cryptanalysis contest offers a $10K prize for the best negative comments on Twofish that aren’t written by the authors. There are no arbitrary definitions of what a winning analysis is. There is no ciphertext to break or keys to recover. We are simply rewarding the most successful cryptanalysis research result, whatever it may be and however successful it is (or is not). Again, the contest is fair because 1) the algorithm is completely specified, 2) there are no arbitrary definition of what winning means, and 3) the algorithm is public domain.

Contests, if implemented correctly, can provide useful information and reward particular areas of research. But they are not useful metrics to judge security. I can offer $10K to the first person who successfully breaks into my home and steals a book off my shelf. If no one does so before the contest ends, that doesn’t mean my home is secure. Maybe no one with any burgling ability heard about my contest. Maybe they were too busy doing other things. Maybe they weren’t able to break into my home, but they figured out how to forge the real-estate title to put the property in their name. Maybe they did break into my home, but took a look around and decided to come back when there was something more valuable than a $10,000 prize at stake. The contest proved nothing.

Gene Spafford has written against hacking contests. http://www.itd.nrl.navy.mil/ITD/5540/ieee/cipher/… [link moved to http://www.ieee-security.org/Cipher/PastIssues/1996/…]

Matt Blaze has too, but I can’t find a good URL.

---

How to Recognize Plaintext

A brute-force cracking machine tries every possible key until it finds the right one. If the machine has a chunk of ciphertext and decrypts it with one key after the other, how does it know when it found the correct plaintext?

It seems obvious to me, but I get this question often enough to address it in these pages. The machine knows that it found the plaintext because it looks like plaintext.

Plaintext tends to look like plaintext. It’s an English-language message, or a data file from a computer application (programs like Microsoft Word have large known headers; even PK-ZIP files have known headers), or a database in a reasonable format. When you look at a decrypted file, it looks like something understandable. When you look at a ciphertext file, or a file decrypted with the wrong key, it looks like gibberish.

In the 1940s, Claude Shannon invented a concept called the unicity distance. Among other things, the unicity distance measures the amount of ciphertext required such that there is only one reasonable plaintext. This number depends both on the characteristics of the plaintext and the key length of the encryption algorithm.

For example, RC4 encrypts data in bytes. Imagine a single ASCII letter as plaintext. There are 26 possible plaintexts out of 256 possible decryptions. Any random key, when used to decrypt the ciphertext, has a 26/256 chance of producing a valid plaintext. The analyst has no way to tell the wrong plaintext from the correct plaintext.

Now imagine a 1K e-mail message. The analyst tries random keys, and eventually a plaintext emerges that looks like an e-mail message: words, phrases, sentences, grammar. The odds are infinitesimal that this is not the correct plaintext.

Everything else is in the middle. The unicity distance determines when you can think like the second example instead of the first.

For a standard English message, the unicity distance is K/6.8, where K is the key length. (The 6.8 is a measure of the redundancy of English in ASCII. For other plaintexts it will be more or less, but not that much more or less.) For DES, the unicity distance is 8.2 bytes. For 128-bit ciphers, it is about 19 bytes.

This means that if you are trying to brute-force DES you need two ciphertext blocks. (DES’s block length is 8 bytes.) Decrypt the first ciphertext block with one key after another. If the resulting plaintext looks like English, then decrypt the second block with the same key. If the second plaintext block also looks like English, you’ve found the correct key.

The unicity distance grows as the redundancy of the plaintext shrinks. For compressed files, the redundancy might be 2.5, or three blocks of DES ciphertext. For a 256-bit-key cipher, that would be 105 plaintext bytes. If the plaintext is a random key, the redundancy is zero and the unicity distance reaches infinity: it is impossible to recognize the correct plaintext from an incorrect plaintext.

But that’s a special case. Most of the time, it is easy to recognize plaintext.

---

News

Okay, I finally got the story right about Network Associates Inc. and the Key Recovery Alliance. (Last month I pointed to a Wired News story that they quietly rejoined.) The story is wrong. They never left the KRA. Since its inception, Trusted Information Systems was a big mover and shaker in the KRA. When NAI bought TIS in May 1998, TIS’s membership transferred to NAI. NAI resigned the leadership posts that TIS had held in the Alliance and stopped attending its meetings, but never left the KRA. So, NAI is a member of the KRA, and has been since it bought TIS. http://www.wired.com/news/technology/…

A federal judge has issued a temporary restraining order (TRO) against enforcement of the Child Online Protection Act (COPA). (That’s the so-called CDA II.) This is a big deal, and a cause for celebration. The judge’s decision is at: http://www.aclu.org/court/acluvrenoII_order.html. The full text of the plaintiffs’ brief is available at: http://www.epic.org/free_speech/copa/tro_brief.html To follow this story, subscribe to EPIC Alert: http://www.epic.org/alert/blog/crypto-gram/subscribe.

This is a fascinating web security hole: http://www.securexpert.com/framespoof/index.html [dead link as of 1999-08-27; see http://bugnet.com/alerts/bugalert_122398.html]

Attorneys for Liquid Audio, a company promoting secure music distribution on the net, pressured someone to remove information on how to defeat copy protection. You’d think they still taught the First Amendment in law school. http://www.mp3.com/news/122.html

A good C++ library: NTL provides data structures and algorithms for manipulating signed, arbitrary-length integers; and for vectors, matrices, and polynomials over the integers and finite fields. Version 3.1b has just been released. http://www.shoup.net/ntl/

The Clinton Administration isn’t satisfied with trying to destroy personal privacy in the U.S.; for years they’ve been taking their arguments abroad. Now, according to the administration, the 33 Wassenaar Arrangement signatories have agreed to implement the same bizarre export controls on mass market encryption software as the U.S. has. Now I don’t know if this is true—the administration has lied before about the international reception of its policies—but if it is, it’s a major step backwards. I’m not sure why the administration believes that making sure that sensitive information is encrypted poorly so that criminals can read it will help the world, but I’m sure they’ve got it figured out. http://www.nytimes.com/library/tech/98/12/biztech/… http://jya.com/wass-au.htm http://jya.com/wass-de2.htm http://biz.yahoo.com/rf/981203/3l.html

For the record, the Wassenaar Arrangement countries are: Argentina, Australia, Austria, Belgium, Bulgaria, Canada, Czech Republic, Denmark, Finland, France, Germany, Greece, Hungary, Ireland, Italy, Japan, Republic of Korea, Luxembourg, The Netherlands, New Zealand, Norway, Poland, Portugal, Romania, Russia, Slovakia, Spain, Sweden, Switzerland, Turkey, Ukraine, United Kingdom, United States. Some of these countries are presently the major sources for the international distribution of cryptographic software. http://www.wassenaar.org/

Visit the Free Crypto website and send a message of support. http://www.freecrypto.org

---

The Doghouse: Iomega Zip Disks

The following instructions describe a hack around the read/write protection on IOMEGA ZIP-100 disks. This isn’t my work; I received it anonymously. If anyone knows who discovered this, please have him or her contact me.

The password protection feature involves having a password and security flag stored on the ZIP disk (in the boot sector?). This password and security status are read by the firmware in the ZIP drive and it refuses to allow access to a disk it believes to be read/write protected.

The ZIP drive supports a “power down” feature that literally stops the drive spinning (and parks the drive’s read/write head?) after 15 minutes of inactivity. Drives automatically restart as needed.

The firmware does not currently (28 May 1998) notice a disk change via the manual disk eject hole on the back of the device. If, after spin-down, a known protected disk is manually ejected and a different protected disk is then inserted, the password for the first disk is still considered current by the firmware, and is thus valid for the second disk. The second disk can then be “unprotected” by using the password of the first disk.

To implement this hack, perform the following steps:

1. You need a new blank ZIP-100 disk. Call this disk the KNOWN disk.
2. Insert the KNOWN disk into the ZIP drive.
3. Give the KNOWN disk a read/write password using the IOMEGA toolset. Remember the password.
4. Using the IOMEGA toolset startup preferences, set the SLEEP TIME of the ZIP drive to 1 minute.
5. Let the drive, with the KNOWN disk still inserted, spin down. (You can hear the obvious difference in noise output.)
6. Take an unfolded paper clip.
7. Poke it into the small hole at the back of the ZIP drive, and manually eject the KNOWN disk. (The hole is located at the back of the drive casing above the printer or second SCSI connector.)
8. Insert the UNKNOWN disk.
9. The drive may spin up to speed again or may remain silent.
10. Using the IOMEGA toolset, REMOVE the protection on this disk. Use the KNOWN PASSWORD from step (3) above.
11. Using the normal eject button on the front of the device, eject the UNKNOWN disk.
12. Reinsert the UNKNOWN disk a second time (to prepare for directory and file access).
13. Double-click on the disk drive icon in your Explorer/File Manager window.

Done.

---

Counterpane Systems News

There is another Twofish technical report (#3) on the website. This one is called “Improved Twofish Implementations,” and gives better performance numbers for 32-bit computers, smart cards, and hardware.

http://www.schneier.com/paper-twofish-speed.html

There is also a Twofish implementation in Delphi:

http://www.scramdisk.clara.net/d_crypto.html

And finally, we have published a paper that compares the performance of all fifteen AES candidates on 32-bit processors, smart cards, and hardware.

http://www.schneier.com/paper-aes-performance.html

---

Final Report from the Commerce Department Technical Advisory Committee on Key Recovery

The Technical Advisory Committee to Develop a Federal Information Processing Standard for the Federal Key Management Infrastructure was established by the Department of Commerce in July 1996. The Committee, which was formally chartered on July 24, 1996, held its first meeting on December 5-6, 1996. The goal, near as I can tell, was to get industry to agree on rules for key recovery.

Its final meeting was held November 17-19, 1998. The meeting was more of a fizzle than a finale. Although the committee concluded all of its work, their final document continues to undergo editing and will continue to do so for the next several weeks. The document is far more coherent than it was at the end of their June “finale”; however, it has still not been thoroughly reviewed.

Here are some points which may be of interest.

Although it may be described as such, the committee’s final document was hardly the product of “a 22-member commission.” Participation dwindled to such an extent that members who were not present at the final meeting were asked to resign so that a quorum could be achieved. By the end of the final meeting, the fewer than half a dozen remaining participants were still making substantive changes to the document. Changes continued to be made by the chair and other individuals even after the conclusion of the committee’s final meeting.

The commission did not “conclude” anything. The committee never voted on or addressed any issues about whether key recovery made sense, where it could/should be deployed, or even if it is possible, safe, or makes economic sense.

The commission did not make any recommendations. The work of the committee is a matter of public record and will presumably be continued by NIST. However, the committee did not recommend that its work go forward.

The document produced by the committee does not give a blueprint for how to do key recovery. It lists over two hundred things that key recovery products should and should not do without ever saying how to do them.

There is no reason to believe that the committee’s document is consistent or complete. As an example, most of the document’s 200+ requirements are contained in a section that was completely rewritten by a single member shortly before the final meeting. During the last day of the final meeting and before this section had been reviewed by what remained of the committee, this individual left saying that since the group had already dropped below quorum, his presence was no longer necessary. The section was later reviewed only superficially by the few remaining members.

The document was written at least as much by NIST and NSA as by the committee. Although the only voting members of the committee were from the private sector, this was certainly not a product of (or at the initiative of) the private sector.

You can read the document yourself at: http://csrc.nist.gov/tacdfipsfkmi/

---

Comments from Readers

From Chris Smith <smith@interlog.com>:

You write about Canada’s new crypto policy. However, the new policy is not, as you have described, about “export policy,” but about domestic policy. This is about cryptography in Canada. My understanding is that Canada will continue to abide by the Wassenaar Arrangement, which currently limits the export of strong encryption.

From George Foot <georgefoot@oxted.demon.co.uk>:

Schneier wrote:

“The electronic world moves too fast for this cycle. A serious flaw in an electronic commerce system could bankrupt a company in days. Today’s systems must anticipate future attacks. Any successful electronic commerce system is likely to remain in use for ten years or more. It must be able to withstand the future: smarter attackers, more computational power, and greater incentives to subvert a widespread system. There won’t be time to upgrade them in the field.”

I read every issue of the CRYPTO-GRAM with great interest. If I may as a simple subscriber be permitted an observation, I would say that there is a great need to learn from the warning in the above paragraph.

But what principles should be adopted to guard against the danger which is predicted? My criterion is simplicity. Discard the complex algorithms which at every convolution open a crack through which their inner working may be examined exhaustively without limit of time.

Choose instead a simple system which has unique parameters for every two stations desiring to intercommunicate and for every message passed, which publishes no keys and which has no association whatever with a third party.

From Illuminatus Primus <vermont@gate.net>:

I see that the main reason automation poses a new risk is because the system increasingly depends on dumb (comparatively speaking) components, rather than humans. A small, isolated program will usually not recognize when cash flow trends suddenly change because small, isolated programs will not teach themselves how to recognize fraud. However, humans sometimes unreasonably expect them to. The cure is for more people to spend the time translating warning systems that humans are accustomed to into machine-friendly language. For example, Visa warns me every time a sharp change in my spending patterns is noticed. It’s almost like I have a friendly banker keeping a watch over my money, but in reality it’s just a few checks completed in a fraction of a second by a computer somewhere.

Automation also brings a great benefit: new holes in the system can be squashed in very little time. Centralized systems benefit the moment that the hole is repaired, and decentralized systems benefit the moment that the fix propagates. I think a good argument could be made about how the current human-dependent systems might actually be worse off than the digital ones. For example, look at the problems involved with introducing new US currency to stop counterfeiting. Humans often times can take longer to adapt to a new situation than the time it takes to transmit a new piece of authentication code across the world millions of times.

Perhaps there is a larger issue underneath all of this: the need for individual nodes to become more intelligent. If my credit card was actually a small terminal that allowed me to clear requests to charge to it, perhaps fraud against my card would be more difficult to accomplish. Perhaps if cars had meters at the gasoline intake, gas stations couldn’t fraudulently overcharge people so easily. And perhaps, if merchants exchanged digital money instead of paper money, counterfeiting wouldn’t take decades to stamp out.

---

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.