The 1999 Crypto Year-in-Review
In 1999, the major developments in cryptography were more political than scientific. Of course, there were scientific conferences and scientific announcements, some of which were significant. But, by far, the most important events happened in the areas of law, court cases and regulation. As we move into the new millennium, these political and regulatory shifts could have resounding effects on the implementation of cryptography, especially in how it relates to balancing privacy concerns with the needs of government and law enforcement.
U.S. Export Control
One of this year’s more significant milestones was the Clinton administration’s announcement on Sept. 16 that it would change its long-derided export control rules. While changes haven’t yet been implemented, this decision represents a reversal of the administration’s long-standing hostility toward strong encryption. The devil is in the details, however, and the Clinton administration has a long record of promising export relief and then not delivering. Moreover, it has proposed legislation—the Cyberspace Electronic Security Act (CESA)—which supports key escrow and has some nasty anti-privacy provisions.
In September, the administration proposed that “retail” encryption hardware and software of unlimited strength could be exported without a license after a “one-time technical review” and some reporting on whom the products are sold to. “Custom” products will have some restrictions on sales to foreign governments and known terrorist or criminal organizations. Products with key lengths of 64 bits or less would be entirely decontrolled.
Again, these changes are not yet in effect. The administration has said they would be in force by Dec. 15, and, if it follows through on its promise, these new regulations will allow virtually any product to be exported more-or-less freely. It is important to note that there is nothing about key recovery in these new regulations, and there are no artificial limits based on key length. On the other hand, still missing are regulations about cryptographic research: The Karn, Junger and Bernstein court cases are still important (see below).
Now for the bad news: The Clinton administration’s proposed CESA bill spells out regulations for key escrow and the use of decryption as a police weapon. CESA requires third parties to disclose keys to government agents with a court order. More frightening is that the bill allows the government to refuse to disclose in court the methods used to recover plaintext. This means that law enforcement could present decrypted plaintext in open court, but refuse to reveal to the defendant how that plaintext was obtained. Moreover, if the government finds any back doors, or convinces manufacturers to put them in, they won’t have to be revealed in court.
Again, all of this is a proposal, and it’s yet to be official. So don’t think the deal is done. The debate over the use of encryption as a privacy tool continues.
Congressional Activity
Meanwhile, the House and Senate again moved forward with legislation to relax export controls on cryptography. In the House, more than 250 members of Congress have co-sponsored H.R. 850, the Security and Freedom through Encryption (SAFE) Act, introduced by Rep. Bob Goodlatte (R-Va.) and Rep. Zoe Lofgren (D-Calif.). The bill allows for the export of off-the-shelf crypto devices if a comparable product is available, and it bans mandatory key escrow. It also includes a controversial provision that creates a new federal crime for using crypto to “further a criminal act.” The bill has been approved by five committees. However, two of the five, the House Intelligence Committee and the House Armed Services Committee, have amended the bill to effectively retain export controls. The House Rules Committee has to decide which version will be voted on.
On the Senate side, Commerce Committee chair and presidential candidate John McCain (R-Ariz.) reversed his previous position opposing cryptography and introduced S. 798, the Promote Reliable OnLine Transactions to Encourage Commerce and Trade (PROTECT) Act of 1999. This bill allows for the free export of products of 64 bits or less. Stronger encryption can be exported to online merchants, major corporations that are publicly traded companies, government-regulated organizations, subsidiaries or affiliates of U.S. corporations, and governments in NATO, OECD and ASEAN. (Go figure that one: They want to sell strong crypto to Vietnam and Burma but not Brazil or Argentina.) An Encryption Export Advisory Board can recommend relaxing restrictions. And finally, products that adopt the AES or its equivalent will be freely exportable by January 2002. The bill was approved by the Commerce Committee in June and, at press time, was awaiting a vote by the Senate.
Crypto’s Day in Court
In 1999, there were three important cryptography-related court cases: Karn, Junger and Bernstein. The Bernstein case saw the most activity this year. In May, the federal Ninth Circuit Court of Appeals agreed with a lower court ruling that export laws constitute prior restraint, and are unconstitutional.
The court agreed that source code can be (though isn’t always) “expressive,” and thus qualifies as speech for the purpose of the First Amendment. Thus, the Export Administration Regulations (EAR) are a prior restraint on free speech. While this can be legal, such things bear a heavy burden. EAR does not meet that burden, the Court ruled, because (among other things) it grants unbridled discretion to the government, it provides no firm time limits for the process and it bars judicial review.
Despite the fact that the court’s reasoning was narrowly focused on expressive source code, it struck down the entire rule on crypto export because the rule doesn’t distinguish between expressive source, functional source and object code, and it can’t (and shouldn’t) do a line-by-line rewrite of the EAR. The court also said that government efforts to control cryptography, in addition to being a First Amendment issue, may also be in conflict with the Fourth Amendment, the right to speak anonymously, the right against compelled speech and the right to informational privacy.
At the government’s request, the Ninth Circuit Court of Appeals has recently agreed to a new hearing in the Bernstein case. This hearing was recently moved back due to U.S. government claims that rules regarding the export of source code will be changed. We’ll see. . . .
European Developments
Europe had its own privacy battles in 1999. A draft European Union (EU) regulation will extend export control of intangibles to Europe. This regulation was originally introduced in 1998 by the British government as a white paper (draft legislation for comment), but was retracted due to public outrage. Now it has been sneaked back in, and the U.S. is pressuring the EU to adopt it. This is about a lot more than cryptography: The regulation is so widely drafted that it will affect most of science, technology and medicine. There is no resolution yet, but it could be a disaster.
In the U.K., the Labor government, having pledged not to introduce key escrow when it was an opposition party, now proposes an electronic communications bill that does just the opposite. Just a few choice bits of the bill: It gives ministers power to regulate cryptography in arbitrary ways without further primary legislation. It allows police to force you to hand over cryptography keys and passwords on demand, with two years’ jail for noncompliance and the burden of proof reversed (if the police thinks you have a key, you must hand it over, prove you haven’t, or go to jail). And it prohibits people from discussing the facts of a key-seizure order with anyone but an attorney.
On the other hand, there have been some positive developments in France. In January 1999, France reversed its long-standing position as one of the most anti-cryptography countries in the world. Under the new policy, a key-escrow system of “trusted third parties” (read: “government-installed back-doors”) is no longer required for domestic use. Also, the 1996 law requiring trusted third parties will not be implemented, and users will be able to use up to 128-bit encryption without restrictions until a new law eliminating all restrictions is enacted.
Worldwide Crypto Control
If you want to know the state of cryptography restrictions in other countries, there’s finally a reference. The Electronic Privacy Information Center (EPIC) in June released a report called “Cryptography & Liberty 1999: An International Survey of Encryption Policy,” which is an excellent survey on international encryption policy. And for information on the worldwide availability of cryptographic products, there’s another reference: The Americans for Computer Privacy (ACP) in June released “Growing Development of Foreign Encryption Products in the Face of U.S. Export Regulations,” a study on the availability of international encryption.
All of the developments around export control are becoming more important as the need for communications privacy becomes apparent. Echelon, a secret U.S. satellite surveillance network that spies on U.S. allies as well as enemies, made the news this year in reports of secret pressure from the United States to extend the Wassenaar Arrangement (which limits export of critical military technologies) to mass market software. Other reports have exposed a U.S.-led international organization of police and security agencies that is trying to push through laws that mandate eavesdropping points for Web sites and other forms of digital communication.
The threats are out there. We’ve always known that we needed to protect our privacy from criminals, but more and more it’s becoming obvious that we need to protect our privacy from governments as well.
Intel X2
Intel made cryptography news this year for two reasons. First, it announced that it’s putting a hardware random-number generator in its processor chips, Pentium III and later. This is great news. Random numbers are required for almost all cryptographic protocols, and bad random-number generators are one of the easiest ways to break the security of a system.
Second, Intel announced a processor ID serial number in every CPU. Privacy groups have protested, but the ID remains. This illustrates an important point: Cryptography’s most obvious application is privacy, but often anonymity is more important. The attention that anonymous Web-browsing companies such as Zero Knowledge Systems are getting underscores this point.
Public-Key Crypto Under Attack
Also in the news in 1999 were the large-scale attacks on public-key cryptosystems. Early in the year, a group of cryptographers, led by Herman J. J. te Riele of CWI in Amsterdam, factored a 465-bit (140-digit) number. On the more theoretical side, cryptographer Adi Shamir described a special-purpose electro-optical computer called TWINKLE that could increase factoring speeds by a factor of 1,000. As far as anyone knows, the machine has not been built, but it certainly seems possible. And for mathematical reasons, it has a much greater effect on 512-bit keys than on 1024-bit keys. In fact, it really doesn’t speed up the 1024-bit factoring very much at all. What it really shows is that 512-bit keys are too short for operational use.
A more graphic demonstration of this fact happened later in the year, when the same group factored a 512-bit number. About 300 fast SGI (formerly known as Silicon Graphics Inc.) workstations and Intel Pentium PCs did the work, mostly on nights and weekends, over the course of seven months. The algorithm used was the General Number Field Sieve. The algorithm has two parts: a sieving step and a matrix reduction step.
The sieving step was the part that the 300 computers worked on for about 8,000 MIPS-years over 3.7 months. (This is the step that Shamir’s TWINKLE device would speed up.) The matrix reduction step took 224 CPU hours (and about 3.2 Gig of memory) on the Cray C916 at the SARA Amsterdam Academic Computer Center. If this were done over the Internet with resources comparable to what was used in the recent DES cracking efforts, it would take about a week calendar time.
The entire effort was 50 times easier than breaking DES. Factoring e-commerce keys is definitely very practical, and will become even more so in future years. It is certainly reasonable to expect 768-bit numbers to be factored within a few years, and so RSA Laboratories’ contention that RSA keys should be a minimum of 768 bits is much too optimistic.
The 512-bit factoring event is significant for two reasons. For one, most of the Internet security protocols use 512-bit RSA, which means that non-cryptographers will take notice of this—and probably panic a bit. And two, unlike other factoring efforts, this was done by one organization in secret. Most cryptographers didn’t even know this effort was going on, which shows that other organizations could already be breaking e-commerce keys regularly, and just not telling anyone.
As usual, the press is getting this story wrong. They say things like “512-bit keys are no longer safe.” That completely misses the point. Like many of these crypto-analysis stories, the real news is that there is no news. The complexity of the factoring effort was no surprise: There were no mathematical advances in the work. Factoring a 512-bit number took about as much computing power as people predicted. If 512-bit keys are insecure today, they were just as insecure last month. Anyone implementing RSA should have moved to 1028-bit keys years ago, and should be thinking about 2048-bit keys today.
Setting a Standard
In 1999, NIST chose five finalists for the Advanced Encryption Standard (AES): Mars, RC6, Rijndael, Serpent and Two-fish. AES is the encryption algorithm that will eventually replace DES. The next step is to choose among the finalists. NIST is again soliciting comments on the algorithms, and there will be a third AES Candidate Conference in New York in April 2000, held in conjunction with the 7th Fast Software Encryption workshop (FSE 2000). Comments are due by May 14, 2000, after which time NIST will propose a standard. The AES will then go through the formal government approval process, become a Federal Information Processing Standard (FIPS), and presumably become the standard encryption algorithm for all sorts of international applications. Expect all this to happen by the summer of 2001. The government moves slowly.
Categories: Computer and Information Security, Laws and Regulations