March 15, 1999
by Bruce Schneier
President
Counterpane Systems
schneier@counterpane.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:
In this issue:Imagine this situation: An engineer builds a bridge. It stands for a day, and then collapses. He builds another. It stands for three days, and then collapses. Then, he builds a third, which stands for two weeks but collapses during the first rainstorm. So he builds a fourth. It's been standing for a month, and has survived two rainstorms. Do you believe this fourth bridge is strong, secure and safe? Or is it more likely just another accident waiting to happen?
As bizarre as it may seem, this kind of design process happens all the time in cryptography, a field that is full of people who love to design their own algorithms and protocols. With so many aspiring cryptanalysts out there, however, there's bound to be a lot of weak designs. The problem is this: Anyone, no matter how unskilled, can design an algorithm that he himself cannot break. Though a competent cryptanalyst can break most of this stuff after a short review, the rest of it survives, and in most cases is never looked at again (especially outside the military world). But just because an algorithm survives an initial review is no reason to trust it. I had a client once who desperately wanted to design his own encryption algorithm. He had no cryptographic training, no experience analyzing other algorithms. He was a designer, he said, not an analyst. So Counterpane did his analysis for him, and we broke his algorithm in a day. He fixed it and sent it back, and we broke it in two days. He fixed it and sent it back again, and we broke it again. Finally, the fourth version of his algorithm resisted our attempts at cryptanalysis...at least for the full 40 hours our contract specified. The client was happy; finally, he had a secure algorithm.
In a way, the client is worse off than he was before he started. At first, he had an algorithm that was obviously flawed. If he included it in a product, he would have no analysis to show potential buyers and no responses to questions about its security. If a competent cryptographer looked at the algorithm -- either because it was made public or by reverse-engineering the code -- he could easily break it.
But after we went through the break-fix-break cycle a few times, he ended up with an algorithm that was not obviously flawed. He had a written analysis showing that we could not break it within 40 hours. Even if a competent cryptographer looked at the algorithm for a few days, he probably would not find a problem. Unless the algorithm was being used in some high-profile application -- cellular telephony, a Microsoft product, an Internet standard -- it might never be looked at any more closely. But that doesn't mean that it's not still flawed, or that it can't be broken given enough time and resources.
This is not to say that the break-fix-break cycle is completely flawed. It's not. In fact, it's how most good cryptographic systems got to be good. Consider IPSec, the Internet IP security protocol. It was designed by committee, out in the open and in public, and from the start has been the subject of considerable public scrutiny. Everyone knew it was an important protocol, and people spent a lot of effort trying to get it right. Things were proposed, broken and then modified. Versions were codified and analyzed. Debates raged over its security merits, performance, ease-of-implementation, upgradability and use. Then, in November 1998, a pile of RFCs were published, the next in a series of steps to make IPSec an Internet standard. It is impossible to mimic this kind of analysis with a proprietary system. Still, many companies try, which begs the question: Why try to develop new algorithms and protocols at all? They're generally not faster, or smaller, or more efficient. They're just different.
Unfortunately, in the world of cryptography, different is bad. Cryptography is at its best when it is conservative, and the conservative approach is to choose an algorithm that has already been analyzed. The admonition not to put all your eggs in one basket does not apply in this case. The security of a system is the security of its weakest component, since the weakest component breaks the entire system. In cryptography, there is security in following the crowd. A home-grown algorithm can't possibly be subjected to the hundreds of thousands of hours of analysis that DES and triple-DES have been subjected to. A company just can't mobilize the resources that are being brought to bear against the AES candidates, or the IPSec Internet security protocol. No one can duplicate the confidence that RSA offers after 20 years of cryptanalytic review. A standard security review, even by competent cryptographers, can only prove insecurity; it can never prove security. By following the pack you can leverage the cryptanalytic expertise of the worldwide community, not just a handful of hours of a consultant's time.
This article originally appeared in the March 1999 issue of Information Security magazine <http://www.infosecuritymag.com>.
B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall, and N. Ferguson 2nd AES Candidate Conference, March 1999, to appear.
In this paper, we compare the performance of the leading AES candidates on a variety of common platforms: 32-bit CPUs, 64-bit CPUs, cheap 8-bit smart card CPUs, and dedicated hardware. For each platform, we first make some general observations on the performance issues of the platform, then compare the various AES candidates, and finally look at the specific issues for each of the candidates.
http://www.counterpane.com/aes-performance.htmlThere's a Windows program that decodes the police car mobile data terminal transmissions. If you thought listening in on police radio frequencies was interesting, you should see what comes over on those data transcripts.
Motorola's "encryption" wasn't designed for privacy, it's more like a checksum for transmission integrity. Basically, it's XOR.
The software is free, although there is this helpful notice on the Web site: "Decoding MDT transmissions may be illegal in some countries, you may want to check the laws for your country before using this program."
http://www.geocities.com/ResearchTriangle/Facility/7646/Here's further proof, if you needed it, that Microsoft prefers to treat security holes as a public relations problem, rather than fixing the actual problem. Microsoft recently announced a prompt fix for a security hole in IE4.0 and Word 97. Turns out, it wasn't so prompt after all.
In December 1997, David Foster discovered a security hole in Office 97. This bug allows any Web page to contain executable code that will run without warning on the user's machine. For anyone who knows Word and VBA (Word 97's macro language), the problem is obvious.
Foster went to the bug reporting Web pages for Internet Explorer and Word, and reported the problem. There was no response from Microsoft. In late 1998, he discovered that not only had MS still not fixed the problem in Word 97, but the bug also existed in the beta version of Word 2000. He posted a further message to Microsoft, and received the following: "Microsoft appreciates your input regarding this issue, however in lieu of modern technology being what it is, we all need to be personally responsible for knowing what we are downloading off the internet." In case it's not immediately obvious, this is arrant nonsense.
It wasn't until Woody Leonhard, Word guru and Office 97 iconoclast, heard about the problem and threatened to publish particulars of the security hole in the next issue of "Woody's Office Watch," with a readership of 140,000, that Microsoft finally did something. With that incentive, Microsoft had a patch available on their Web site within days.
Patch URLs:
http://officeupdate.microsoft.com/downloaddetails/wd97sp.htm
http://officeupdate.microsoft.com/downloaddetails/fm2paste.htm
David Foster's story of the bug: http://www.panix.com/~dfoster/sec/chrono.html
Woody's Office Watch article:
http://www.wopr.com/wow/wowv4n3.html
For those who haven't been paying attention, the AES (Advanced Encryption Standard) will be the eventual replacement for DES. It's a 128-bit block cipher with key lengths of 128, 192, and 256 bits. And there's a competition going on right now to determine what it is. (For details, see: http://www.counterpane.com/crypto-gram-9805.html#aes.)
Step 1 was the submission of algorithms: NIST received 15 last June. Step 2 is the solicitation of public comments on the algorithms. To that end, NIST is hosting an AES Candidate Conference in Rome the week of March 22nd. NIST received 28 submissions to present at the conference, and they accepted most of them.
The papers are available on the NIST Web site. No real suprises, but if you can't get to Rome and are interested, take a look.
http://csrc.nist.gov/encryption/aes/round1/conf2/aes2conf.htm
The Palm VII (the on-line capable version of the PalmPilot) will come with
public-key cryptography built in. Certicom managed to convince them that
elliptic curve public-key cryptography is the way to go. I haven't seen
this yet, but I'm hopeful it will be good.
http://www.zdnet.com/pcweek/stories/jumps/0,4270,383613,00.html
NIST exports strong crypto. Cool! NIST went and did it; they exported
strong cryptography to the world electronically. See the appendix to:
http://csrc.nist.gov/encryption/aes/round1/conf2/papers/baudron2.pdf
It's sort-of good news. On March 4th, Tony Blair told a bunch of computer
executives that the government will not tie key escrow requirements with
the licensing of CAs. At least some countries are listening. But then he
gave everyone three weeks to come up with a better alternative -- whatever
"better" means in this context -- or he just might do it anyway.
http://news.bbc.co.uk/hi/english/business/the_economy/newsid_290000/290902.stm
http://news.bbc.co.uk/hi/english/sci/tech/newsid_290000/290964.stm
While the debate rages over Intel's unique ID and its plans to use it for
identification over the Internet, the New York Times reports that Microsoft
uses the unique ID on the network card (or generates a substitute) and
secretly inserts it into MS Word and Excel documents for purposes of
identification.
http://www.nytimes.com/library/tech/99/03/biztech/articles/03privacy.html
Microsoft announced that they will fix it.
http://www.zdnet.com/zdnn/stories/news/0,4586,2221330,00.html
http://www.wired.com/news/news/technology/story/18315.html
Hey, the U.S. has a privacy czar! The question is whether or not he'll do
anything useful.
http://www.zdnet.com/zdnn/stories/news/0,4586,2221341,00.html
All right, so I think it's funny.
http://www.nottingham.ac.uk/~ppzmajoc/filks/customs.html
The UK Consultation Document on the proposed e-commerce legislation is now
available on the Web at http://www.dti.gov.uk/CII/elec/consfn1.pdf.
Summary document: http://www.dti.gov.uk/CII/elec/elec_com.html
Comments are required by Thursday 1 April.
The Pentagon is claiming that cyber terrorists are launching sophisticated,
coordinated attacks -- as many as 100 per day -- on military computers.
Honestly, this sounds like a bid for more funding to me.
http://www.zdnet.com/zdnn/stories/news/0,4586,2220773,00.html
Meanwhile, Computer Security Institute and the FBI last week released
survey results showing cyber crooks caused more than $100 million in losses
last year.
http://www.gocsi.com/prelea990301.htm
If this keeps up I won't have to do any more marketing.
Bruce Schneier is going to give the keynote speech at the fifth annual
Public-Key Solutions (PKS) conference in Toronto. The conference is April
12-14 1999 at the Four Seasons hotel, and Bruce's talk will be given at
9:00 AM on the 12th.
http://www.certicom.com/pks99/index2.htm
Slides from the talk are available in Powerpoint format at:
http://www.counterpane.com/crypto-flaws.ppt
New Results on the Twofish Encryption Algorithm http://www.counterpane.com/twofish-aes.html
Performance Comparison of the AES Submissions http://www.counterpane.com/aes-performance.html
Cryptanalysis of FROG http://www.counterpane.com/frog.html
Key Schedule Weakness in SAFER+ http://www.counterpane.com/safer.html
and one talk at the Fast Software Encryption conference:
Mod n Cryptanalysis, with Applications against RC5P and M6 http://www.counterpane.com/mod3.html
This is all happening in Rome, the week of March 22nd.
A new factoring record has been set. Herman J.J. te Riele, and his group at CWI in Amsterdam, announced that they have factored a 140-digit (465-bit) number. This number was one of the RSA challenge numbers (RSA-140): the product of two large primes and the kind of number used in the RSA cryptosystem.
The amount of work is estimated to be about 2000 mips years. (A "mips year" is the computing power of a one mips computer running for a year. A DEC 11/780 is a one mips machine. A top-of-the-line Pentium II is about a 200 mips machine. The ASCI Red TFLOPS supercomputer, recently installed in Sandia National Laboratory -- presumably for nuclear blast simulations -- with its 9216 Pentium Pro processors, is about a 1.8-million mips machine.)
They used an algorithm called the Number Field Sieve, the same algorithm used to factor the 130-digit RSA challenge number in 1000 mips years. And given what they learned on this project, if they had to start over again they estimate that they could have factored RSA-150 in 1500 mips years, and RSA-130 in 500 mips years.
What does this mean for the security of RSA? How does it affect 512-bit keys? 1024-bit keys? No one is sure. It's tricky to extrapolate these work efforts to larger key sizes. Theoretically, increasing the number of decimal digits by three or four doubles the computing effort required to factor the number by the method they used). So RSA-150 would require about six times as much computing effort as we spent on RSA-140.
Larger numbers are much harder to extrapolate. Arjen Lenstra often points out that the various steps used in the Number Field Sieve don't scale as you'd expect, and that many of these techniques just won't work for larger number sizes. It's not simply a matter of raw mips, you need enough memory to hold the intermediate results. While this is true, I am more optimistic about the ability to tweak algoritms. Just based on this one project, they estimate that they could have cut the work to factor RSA-140 by 25%. Who knows what they will learn next time, or the time after that.
Factoring has been getting easier. It's been getting easier faster than anyone has anticipated. I see four reasons why this is so:
Using current mathematics and technology, it is impossible to even consider factoring a 1024-bit number. I'm not willing to make any hard predictions about tomorrow.
Menewhile, the group's next project is a 155 digit (512-bit) RSA number. They expect to finish by the end of the year.
Some info on the factoring research at CWI can be found at:Another intersting URL is Paul Zimmermann's:
http://www.loria.fr/~zimmerma/records/factor.html
who has also contributed to the RSA-140 record. (Note that this is NOT
Phil Zimmerman.)
From: John Washburn johnwashburn@usa.net
Subject: UL for Crypto?
I very much enjoyed my February 1999 Crypto-Gram. Your statement that Cryptography as a commercial product is like pharmaceuticals at the the turn of the century is true. Commercial cryptography is also similar to electrical power and electrical appliance industries at the turn of the century. One industry went the route of Underwriter's Laboratory. The other industry lobbied for the FDA. Another industry (telephone) simply went for the monopoly. Now with at least 75 years of data (FDA), I would argue the UL route has proven the best.
The incidence of accidental (or deliberate) electrocution is statistically insignificant. The standards for electrical appliances have steadily increased. I.e. a product that passed the UL standards in 1945 would likely fail the 1995 standards.
The FDA kills (or more precisely allows to die) more than 25,000 people per year. This does not include drug overdoses, misfilled prescriptions, incorrect prescriptions or unforseen drug interactions. The 25,000 is the most conservative estimate of people who die from unavailable (non FDA approved) medical treatment. This is simply because the FDA does not care how you die, as long as death is not by an FDA approved method.
Given the fork in the road faced by the cryptography industry how can the cryptographic industry opt for the Underwriter's Laboratory model. The only way I see is insurance / bonding.
For example: I sell crypto and submit my crypto to Wausau Insurance for bonding. Wausau Insurance inspects my system. If I balk at their inspection requirements I get no bond. After inspection Wausau Insurance quotes me a premium. If the premium is too high (system is too risky for Wausau Insurance), I balk. After I pay my premium, I can now add to my sales pitch, "an insured cryptographic product from a bonded crytographic company".
The bond is a variation of liability insurance. I picked Wausau Insurance because it specializes in business liability insurance and is close to you in Wausau Wisconsin. Wausau Insurance does not provide such a product at this time. Any liability company would have done for my example.
My point is an insurance company is cautious enough to issue a bonding (liability) policy only after review by third parties or internal experts. In turn, the insurance company's reputation and finacial stake would make the claim of strong crypto easier to believe. This would be true even if the review of the commercial crypto was done complete under NDA's. Also an insurance company would be far more sensitive to implementation, use and system integration issues. Netscape is a prime example where the crypto was good, but the system as a whole sucked (poor PRNG for session key generation).
Also having a multi-billion dollar industry that is already adept at lobbying in many countries lobbying for strong crypto as well is not a Bad Thing. For the insurance company bonding weak crypto is equivalent to writing a series of claim checks.
Note from Bruce: For a contrary point of view, see Tan's essay on why the Underwriter's Laboratory model would NOT work for cryptography and computer security products: http://www.l0pht.com/cyberul.html. I agree with Tan.
CRYPTO-GRAM is a free monthly newsletter providing summaries, analyses, insights, and commentaries on cryptography and computer security.
To subscribe, visit http://www.counterpane.com/crypto-gram.html or send a blank message to crypto-gram-subscribe@chaparraltree.com. To unsubscribe, visit http://www.counterpane.com/unsubform.html. Back issues are available on http://www.counterpane.com.
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 six-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.
Copyright © 1999 by Bruce Schneier