May 15, 1999
by Bruce Schneier
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 Internationalization of Cryptography
- Federal Appeals Court Agrees that Encryption Export Rules are Unconstitutional
- The Doghouse -- Novell NetWare's Remote Passwords
- U.S. Crypto Legislation News
- Counterpane Systems News
- Factoring with TWINKLE
- Comments from Readers
- About "CRYPTO-GRAM"
The Internationalization of Cryptography
One of the stranger justifications of U.S. export controls is that they prevent the spread of cryptographic expertise. Years ago, the Administration argued that there were no cryptographic products available outside the U.S. When several studies proved that there were hundreds of products designed, built, and marketed outside the U.S., the Administration changed its story. These products were all no good, they argued. Export controls prevent superior American products from getting into foreign hands, forcing them to use inferior non-U.S. products.
Cryptography is an international science. Most of the cryptographic conferences are held outside the U.S. Most of the cryptography researchers are at universities outside the U.S., and most cryptographic papers presented at conferences are written outside the U.S. There are more advanced degree programs in cryptography outside the U.S. than there are inside. Researchers outside the U.S. tend to be better funded, and there is more interest in their work. Some of the most important cryptographic research ideas in the past ten years have come from outside the U.S. The U.S. not only does not have a lock on cryptographic research, it does not even have the majority.
In 1997, NIST solicited algorithms for the Advanced Encryption Standard, to replace DES as a government encryption standard. Of the fifteen submissions received, ten were from companies and universities outside the U.S: Australia, Belgium, Canada, Costa Rica, England, France, Germany, Israel, Japan, Korea. Of the five submissions likely to be chosen for the next round, about half will be from outside the U.S. It is very possible that the next U.S. government encryption standard will have been designed outside the U.S.
The Internet Engineering Task Force has created a series of cryptographic standards for the Internet: secure e-mail, encrypted and authenticated IP packets, secure socket-level communications, key exchange and certificate formats, etc. These meetings are held several times a year, mostly in the U.S. but also outside. Attendees are from companies all over the world, and the standards are written by international consensus. The U.S. has no lock on the content of the standards, nor the evaluation process. These standards are implemented in products built all over the world, not just in the U.S. For example, a Finnish company called SSH has one of the best IPSec -- a standard for IP security -- implementations in the world.
Other non-U.S. technology has been integrated into U.S. companies. A Swedish company called COST built a comprehensive cryptographic toolkit. The company was acquired by Entegrity Solutions, Inc., a U.S. startup. Algorithmic Research, and its cryptographic products, was acquired by Cylink Corp. ELVIS+, a Russian company, is now part of the U.S. company TrustWorks, Inc. RSA Data Security, now owned by Security Dynamics Inc., recently purchased the rights to a cryptographic product created in Australia. This list goes on and on. Again and again, U.S. companies have realized that cryptographic expertise is available outside the U.S., and have taken steps to secure that expertise.
Cryptography does not stop at national borders. Research, standards, and products are international. Expertise is international. For the U.S. Administration to believe that there are "national secrets" about cryptography that export controls somehow keep inside the U.S. is sheer folly. There is no evidence that this is true, and considerable evidence that the reverse is true.
Cyberwar is becoming real, maybe. It seems that hackers in Belgrade have attacked NATO's public Web server. Now there's a big difference between attacking a Web site and attacking actual war-fighting computers, but still... http://www.pcworld.com/cgi-bin/pcwtoday?ID=10358
And hackers have done damage in protest to to NATO's accidental bombing of the Chinese embassy in Belgrade. A number of U.S. government sites were hacked, including those of the Department of the Interior, the Department of Energy, and the U.S. embassy in China.
This item is more interesting, if it's true. According to this news report, which I can't confirm anywhere, the Serbs used a CIA mobile phone and security identification codes to call in a NATO air strike on a civilian convoy.
More credible is the story that the Serbs are eavesdropping on NATO unencrypted radio links.
http://www.washingtonpost.com/wp-srv/WPlate/1999-05/... [link dead as of 1999-09-01; available for a fee in the Washington Post Archves]
A cat lost an English bus company a pounds 20,000 contract after falling asleep on a fax machine and sending confidential information to a rival firm.
KeyNote v2, a toolkit for handling trust management issues, has been released in beta. KeyNote is a small, flexible trust management system designed by Matt Blaze, Joan Feigenbaum, and others, suitable for Internet-style applications.
Beta release of the KeyNote toolkit: http://www.cis.upenn.edu/~angelos/keynote.html
Crypto++ 3.1, a free C++ crypto class library, has just been released. This version fixes some bugs and adds more AES candidates as well as a couple of MAC constructions based on block ciphers.
Starium will soon be selling voice encryption add-ons for telephones. They'll be using 2048-bit Diffie-Hellman for key exchange, and triple-DES for voice encryption. Price will be around $100. And unlike AT&T, these guys probably won't bend to government pressure to add key escrow to their protocols (remember Clipper).
This is a terrifying one. A U.S.-led international organization of police and security agencies is trying to push through laws to mandate eavesdropping points for Web sites and other forms of digital communication. The plans require the installation of a network of tapping centers throughout Europe, operating almost instantly across all national boundaries, providing access to every kind of communications including the net and satellites. A German tapping center could intercept Internet messages in Britain, or a British detective could listen to Dutch phone calls. There could even be several tapping centers listening in at once.
The full story:
Another story: http://www.newsunlimited.co.uk/The_Paper/Weekly/... [link dead; try http://www.guardianunlimited.co.uk/online/story/...]
The document is Enfopol 19, a restricted document leaked to the London-based Foundation for Information Policy Research:
Cool Internet Explorer security bugs:
Someone else using your computer can see where you've been browsing. http://www.nwnetworks.com/iesecurity.htm
Someone else using your computer can access your password-protected Web sites.
Think computer privacy is a problem? Here's how it works in the real world. This was originally published in the 14 March 1999 New York Times magazine section.
http://archives.nytimes.com/archives/search/fastweb?... [link dead as of 2000-02-18; try searching the NY Times Archives for "fiber optic confessional"]
Visa has issued a draft of the "Visa Smart Card Protection Profile," as part of the Common Criteria. It contains a very nice list of smart card attacks. The document is a draft, and they want comments.
http://www.visa.com/nt/chip/accept.html [link dead; see http://www.international.visa.com/fb/paytech/...]
The Visa document references the Common Criteria:
The IC2000 report on communications interception and ECHELON, the U.S. satellite surveillance network, was approved as a working document by the Science and Technology Options Assessment Panel of the European Parliament (STOA) at their meeting in Strasbourg on 6 May 1999. The document is public, and very interesting. Report:
News story: http://www.wired.com/news/politics/0,1283,19602,00.html
A man has been sentenced to seven and one half years for hacking $6M out of slot machines.
The story so far: Dan Bernstein wanted to publish the details and source code to Snuffle, an algorithm of his. Export rules prevented him from doing so. He took this to court. About a year and a half ago, Judge Patel agreed with him and ruled the export rules unconstitutional. The government requested a stay, which was granted. The case was appealed to the Federal Ninth Circuit Court of Appeals...
...which just agreed with Judge Patel's decision.
Briefly, 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) is a prior restraint on free speech. While such things can be legal, they bear a heavy burden; EAR does not meet that burden, 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 their reasoning was narrowly focused on expressive source code, they struck down the entire rule on crypto export because the rule doesn't distinguish between expressive source, functional source, and object code, and they can't (and shouldn't) do a line-by-line rewrite of the EAR. They 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 speach, and the right to informational privacy.
This does not mean that it is suddenly legal to export cryptography out of the U.S. Judge Patel issued declaratory and injunctive relief, but it was almost immediately stayed. The Ninth Circuit Court of Appeals affirmed her decision, but that Court's mandate does not issue until the time for petitioning for rehearing runs (14 days). This will almost undoubtedly be stayed, as the government asks the Supreme Court to hear the case. The conservative among us will wait before exporting source code.
An excellent summary and analysis:
Novell NetWare 5 (and 4.11 and 4.2) has a feature that allows administrators to remotely manage Novell servers. These administrative accounts are protected by passwords, and the password are encrypted on the servers. Unfortunately, the encryption algorithm doesn't work.
According to a hacker named TheRuiner, the password file is only protected with some obfuscation, bit realignment, subtraction, value substitution, and an XOR cipher. It's pretty trivial to break, and all it really took was for someone to reverse-engineer the code and see exactly how it worked.
This isn't rocket science, guys. Password protection is a solved problem: use a strong hash function. I'm not sure why Novell wasn't paying attention.
Details are at: http://oliver.efri.hr/~crv/security/bugs/Others/...
Once again, the U.S. Congress is trying to enact legislation to relax export controls on computer hardware and software that include encryption. The hope is that actual laws will eventually replace the ITAR regulations, which are not laws and have never been voted on.
On March 24, the House Judiciary Committee approved H.R. 850, the "Security And Freedom through Encryption" (SAFE) Act. We like this bill; it generally relaxes export controls on encryption software. On the minus side, it also includes a controversial provision that creates a new criminal offense for using encryption during a crime. But on the plus side, the Committee rejected an attempt by Rep. Bill McCollum (R-FL) to introduce an amendment that would have limited relaxation to those encryption products that have key-escrow (or whatever they are calling it these days).
The bill is sponsored by Congressman Robert Goodlatte (R-VA) and Congresswoman Zoe Lofgren (D-CA) (both great people who deserve our support) and currently has 251 co-sponsors, including the Republican and Democrat leaders. Republican leaders sent a "Dear Colleague" letter to all members of Congress last week urging passage of the bill. Unfortunately, it has now been referred to the Commerce, International Relations, Armed Services, and Intelligence Committees for further review. If you remember back to 1997, the House Armed Services and Intelligence Committees both revised a similar bill -- at the request of the FBI -- to impose restrictions on crypto products; their efforts to pass that gutted bill were defeated with help from industry and public interest groups. Majority Leader Dick Armey has told Rep. Goodlatte that he expects the legislation to be voted on by the House by summer; we'll have to wait and see.
There is also some progress in the Senate this year. In a surprising turnaround, Senator John McCain (R-AZ) has reversed his previous support for domestic encryption restrictions and introduced a bill to slightly relax export controls. His new bill, S. 798, "Promote Reliable On-Line Transactions to Encourage Commerce and Trade" (PROTECT) Act of 1999 relaxes export controls on products with 64-bit keys or less. Restrictions are also relaxed on publicly traded companies, regulated or regularly audited companies (such as banks or insurance companies), subsidiaries of U.S. companies and strategic partners, online merchants, and governments in NATO, OECD and ASEAN (a weird choice).
Products that have longer keys than 64 bits can be exported if a new Encryption Export Advisory Board and the Secretary of Commerce approve the exports after finding that "the product or service is...generally available, publicly available; or an encryption product utilizing the same or greater key length or otherwise providing comparable security is, or will be within the next 12 months generally or widely available outside the United States from a foreign supplier." Decisions will be subject to judicial review.
The bill requires the National Institute of Standards and Technology to finish the Advanced Encryption Standard (AES) selection by January 1, 2002. After the AES is selected, products that incorporate the AES or have an equivalent strength may be exportable without a license in most cases.
The bill also prohibits mandatory access to encryption keys or key recovery information by the United States government or the government of any state. However, it also contains provisions that require NIST to assist law enforcement in enhancing access to cryptography and intrusion detection systems.
The bill has been referred to the Senate Commerce Committee, where Senator McCain is Chairman. It is also co-sponsored by Senators Leahy (D-VT), Burns (R-MT), Kerry (D-MA), Abraham (R-MI), and Wyden (D-OR).
It promises to be an interesting year in Congress.
PROTECT ACT: http://thomas.loc.gov/cgi-bin/query/z?c106:S.798.IS:
(This article was co-written with David Banisar.)
Rootfest '99. Bruce Schneier will be speaking at RootFest, a hackers' convention on 21-23 May 1999, in Minneapolis.
NetSec '99. At 8:00 AM on 15 June, Bruce Schneier will give the keynote speech at NetSec '99 in St. Louis. Schneier will also be speaking about securing legacy applications at 2:00 that afternoon. http://www.gocsi.com/conf.htm
At Eurocrypt '99, Adi Shamir presented a new machine that could increase our factoring speed by about 100-1000 times. Called TWINKLE (The Weizmann INstitute Key Locating Engine), this device brings 512-bit keys within the realm of our ability to factor.
The best factoring algorithms known to date all work on similar principles. First, there is a massive parallel search for equations with a certain relation. This is known as the sieving step. Then, after a certain number of relations are found, there is a massive matrix operation to solve a linear equation and produce the prime factors. The first step can easily be paralleled -- recently, 200 computers worked in parallel for about four weeks to find relations to help factor RSA-140 -- but the second has to be done on a single supercomputer: it took a large Cray about 100 hours and 810 Mbytes of memory to factor RSA-140.
Shamir conceptualized a special hardware device that uses electro-optical techniques to sieve at speeds much faster than normal computers. He encodes various LEDs with values corresponding to prime numbers, and then uses it to factor numbers. The machine reminds me of the famous Difference Engine of the 1800s. Once the engineering kinks are worked out -- and there are considerable ones -- this machine will be as powerful as 100-1000 PCs for about $5000. The basic idea is not new; a mechanical-optical machine built by D.H. Lehmer in the 1930s did much the same thing (although quite a bit more slowly).
As far as we know, Shamir's machine is never been built. (I can't speak for secret organizations.) As I said, Shamir presented a conceptualization and a sketch of a design, not a full set of engineering blueprints. There are all sorts of details still to be figured out, but none of them seem impossible. If I were running a multi-billion-dollar intelligence organization, I would turn my boffins loose at the problem.
The important thing to note is that this new machine does not affect the matrix step at all. And this step explodes in complexity for large factoring problems; its complexity grows much faster than the complexity of the sieving step. And it's not just the time, it's the memory requirements. With a 1024-bit number, for example, the matrix step requires something like ten terabytes of memory: not off-line storage, but real computer memory. No one has a clue how to solve that kind of problem.
This technique works just as well for discrete-logarithm public-key algorithms (Diffie-Hellman, ElGamal, DSA, etc.) as it does for RSA, although it is worth noting that the matrix problem is harder for discrete-log problems than it is for factoring. The technique does not apply to elliptic-curve-based algorithms, as we don't know how to use the sieving-based algorithms to solve elliptic-curve problems.
In "Applied Cryptography," I talked about advances in factoring coming from four different directions. One, faster computers. Two, better networking. Three, optimizations and tweaks of existing factoring algorithms. And four, fundamental advances in the science of factoring. TWINKLE falls in categories one and three; there is no new mathematics in this machine, it's just a much faster way of doing existing mathematics.
Shamir's contribution is obvious once you understand it (the hallmark of a brilliant contribution, in my opinion), and definitely changes the landscape of what public-key key sizes are considered secure. The moral is that it is prudent to be conservative -- all well-designed security products went beyond 512-bit moduli years ago -- and that advances in cryptography can come from the strangest places.
The RSA Data Security opinion:
From: pgut001cs.auckland.ac.nz (Peter Gutmann)
Subject: Attacking Certificates with Computer Viruses
>So if you're a paranoid computer-security professional, >the obvious question to ask is: can a rogue piece of >software replace the root-level certificates in my browser >and trick me into trusting someone? Of course it can.
You don't even need rogue software, all you need is Internet Explorer. Try this: Using your favorite certificate toolkit, create a CA root certificate which is identical to an existing one (except for the key) and stick it in a web page. Click on the link with MSIE. You'll be presented with a dialog telling you you're about to accept a new certificate from, for example, "Verisign Class 1 Public Primary Certification Authority." Once you've clicked OK (as virtually all users will), you've replaced the standard CA root with your own one, and can use it to certify rogue servers, CA's, email, viruses, and whatever else you feel like. There's no warning presented by MSIE, it just quietly replaces the existing cert.
(Hint: You may want to test this with one of the lesser-used CA's rather than Verisign, because even ignoring the security implications it's a significant denial-of-service attack. This hole may have been fixed in newer versions of MSIE, but it worked fine in 3.02, which is the last version which doesn't try to take over your machine when you install it).
From: Ed Gerck <egerckmcg.org.br>
Subject: Re: Smart Card Threats
I enjoyed reading your paper on smart-card security issues (Cryptogram Apr/15/1999). I find it specially useful since it provides yet more examples where trust cannot be seen as an objective property of a system, not even for some of its parts. I believe the same applies to all systems, though -- however unperceived in most cases. Smart-cards are thus IMO no better and no worse in principle than a computer on the Net. Trust is essentially subjective and thus any recognizable part of any system can operate within its own and different trust truth-conditions -- potentially leading to different trust-values when in interaction with other parts, perhaps from other systems and also differently for each other part, history, and time. At the end, the main question is thus not whether it is a smart-card or a computer on your desk -- but whether you can rely upon it for your decisions (i.e., trust it within a specific extent and epoch, for specific trust-points). Which may be easier to accept for a smart-card that you always carry with you in contrast to a computer that you never see, such as a server -- but not necessarily, as your paper exemplifies.
I would like to comment also on another part of your newsletter, where you have the title "Trusting the Known" -- since, of course, no one can trust the unknown. IMO, the gist of your text is "Trusting with Qualification" which introduces the discussion on the *degree* of such qualification as you then proceed to do. I also note that it is possible to trust without qualification on the trusted matter itself, even though you must know it -- and that such may even apply to what you analyzed, as when a spy in a spy-ring trusts the key handed down by the spymaster, in an objective way as an "authorization" and entirely based on his trust on the spymaster... not on the key's qualifications.
From: email@example.com (John Macdonald)
Subject: "In cryptography, there is security in following the crowd"
Careful how you phrase that. As written, it could easily be used to justify choosing Microsoft PPP rather than IPSec because that is where "the crowd" has led.
Nobody who reads and understands the article would consider the masses generally unknowledgeable about cryptography to be the right "crowd" to follow of course, but I shudder to think of this article being read by a marketing droid looking for the catch-phrases for his next ad campaign, or a purchasing agent being challenged about an all-Microsoft buying policy.
From: firstname.lastname@example.org (Frank Hecker)
Subject: Re: CRYPTO-GRAM, April 15, 1999
>Other Internet protocols -- S/MIME, SSL, etc. -- take a more >hierarchical approach. You probably got your public key >signed by a company like Verisign. A Web site's SSL public >key might have been signed by Netscape.
>This attack isn't without problems. If a virus replaces the >root Netscape certificate with a phony one....
For the record, Netscape does not sign web sites' public keys (i.e., act as a Certificate Authority for them); I don't believe Netscape has ever performed this service. Thus there is no "root Netscape certificate" included in the Netscape Navigator and Netscape Communicator products, if by that you mean a certificate for a hypothesized Netscape CA. Netscape Navigator and Netscape Communicator as shipped do include root CA certificates for a number of public CA services, and we recommend that our customers use those services (unless they wish to act as their own CA).
This doesn't of course change the underlying argument of your article, concerning the vulnerability to replacement of the include root certificate list; I just wanted to correct a minor error of fact.
From: "hansnetman.se" <email@example.com>
Subject: Smart-Card Flaws
For the last 2.5 years I've been responsible for the security issues when implementing a large Smart Card based authorization concept for Windows NT 4.0 here in Sweden and here are 3 major flaws I've encountered when dealing with smart cards:
1) When connecting to a NT server your user name, password and X509v3 certificate are sent to the server. The server starts a challenge response using the public key in the certificate and encrypts a random value. The encrypted random value and the server certificate are then sent to the smart card and decrypted with the corresponding private key. Then the smart card encrypts the random value with the server's public key in the server certificate and sends it back to the server, which compares the two values. Since there is no connection between the value in the X509 certificate (subject field and Common Name) and the user ID you may enter some other person's ID and password which are sent with your certificate. So the strong authentication will begin using your Public and private RSA keys but you will get the other person's privileges and access rights!
2) On an RSA based smart card you usually store the user id and password on the data area (SSO table = Single Sign On Table) -- the problem lies in the fact that the smart cards offered today are limited in storage data, such as certificates and user IDs and passwords, to 8K maximum. (You may find cards on the market that can store more than 8K data but you can't buy them yet.) So if we use certificates with RSA based keys stored in them, which are 1024 bits long, you may only have 2 certificates and 2 corresponding private keys. If we use RSA based keys stored in a smart card that are 512 bits long, we can store 3 certificates in them. And since 512 bit RSA keys are in the Wassenaar agreement and you may export them, you can't trust them :-). So we used 1024 bits keys instead and used them for authentication and encryption. So the following will then happen. You enter the PIN that opens the card AND opens for usage of the certificate and private key for authentication/encryption since we want to do a strong authentication of the user. I can then decrypt anything that the user of the smart card has encrypted since the usage of the private key is opened by the user when he enters his PIN! If I can get the user to execute a Trojan horse program the user will not even know that I'm decrypting something he encrypted with his private key! Therefore you can't encrypt the user id and the password stored on the smart card! So I can read this from the smart card and get user id and the corresponding password and email it to me! (I've done this once using just Visual Basic for Application and a macro stored in the normal.dot)
3) If we do a challenge response in a NT environment the server needs to know which work station/server he is talking to. So in your case the server program used WINS to get the IP-address from the workstation name. This opened to a nice attack:
The user logged in on a NT workstation using his smart card and was authenticated by challenge response. We sent a email to the user that included a macro in the normal.dot and got the workstation's name from the workstation, and user id and password from the smart card. We then got another NT workstation and named it as the user's workstation name and tried to get a connection to a disk on the NT server. We were prompted for user ID and password, which we entered and voila! We got access to the disk! The server in this case got the workstation name, the user id and password and used WINS to find the corresponding IP address for that workstation name. Then the server did a strong authentication on the IP address that the server got from WINS. That IP address was not our machine's IP address, it was the user's IP address! In the NT security log we could read that the user logged in to that disk and that he was authenticated by the use of strong authentication.
So the question is: Can you rely on Smart Cards? And my answer is: Yes, if you know what they can do and what they can't!
To subscribe, visit http://www.schneier.com/crypto-gram.html or send a blank message to firstname.lastname@example.org. 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 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.