September 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:
- Cramer-Shoup Cryptosystem
- Impossible Cryptanalysis and Skipjack
- Counterpane Systems – Featured Research
- News
- Private Doorbell
- Corrections to 15 August 1998 CRYPTO-GRAM
- More on Biometrics
- About “CRYPTO-GRAM”
Cramer-Shoup Cryptosystem
So there I was, sitting in the audience at Crypto, listening to the various presentations. Crypto is the largest and most important annual cryptography research conference, and the papers were interesting.
Monday afternoon I checked my messages. Five reporters called me about some big IBM announcement at Crypto about their amazing new cryptographic algorithm. Nothing stood out from the day’s presentations. I looked through the proceedings, and only found one IBM paper that it could be. I skimmed it again, and it didn’t look like anything. So I started calling reporters back.
It seems that the IBM public relations department was working overtime. There was a story in The Wall Street Journal, and another in The Industry Standard. The news was glowing, and predicted that this new algorithm would replace SSL, save the Internet, and cure cancer. Hype was everywhere, and facts were few. Near as I can tell, the only reason this got out of hand so badly is that every cryptographer was at Crypto, and unreachable.
This is my attempt to inject some reality into the conversation.
What is the Cramer-Shoup Cryptosystem? It’s an academic paper (a good one) with an overly aggressive public relations department behind it.
Simply, Cramer-Shoup is a public-key cryptosystem that prevents adaptive chosen ciphertext attacks. This is an attack where a cryptanalyst is able to get the decryption of different ciphertexts related to the ciphertext he is interested in. The cryptanalyst might want to know the decryption of C. So the cryptanalyst gets the decryptions of several other ciphertexts, C’, C”, etc., and uses that information to decrypt C. The attack against RSA in PKCS #1 by Bleichenbacher, discussed in the 15 July 1998 CRYPTO-GRAM, is an example of an adaptive chosen ciphertext attack: a cryptanalyst can learn how to decrypt C by sending the system several related C’s, and seeing if the system can decrypt those.
This resistance is a nice feature of the Cramer-Shoup algorithm, and there are some nice security proofs to back the claims up. The algorithm is a little more annoying than some others: ciphertext is about four times plaintext (not a big deal in most applications) and takes about twice as much computation as ElGamal. But it’s not new. It’s not earth-shattering. It’s not going to change the world. Or even reduce itching.
The cryptographic community hasn’t been bemoaning the problem, utterly lost in how to defend against the attacks, and desperately hoping for some company (like IBM) to come swooping down out of the sky with the answer. RSA’s vulnerability to adaptive chosen ciphertext attacks was pointed out soon after the algorithm was invented. In most cases, the attacks are not possible within the application. And solutions have been devised for dealing with the attacks when they are possible. They are usually dealt with in the protocol; PKCS #1 was vulnerable to an adaptive chosen ciphertext attack, but version 2 of the protocol uses a message packing protocol called OAEP that makes the attack infeasible. And not leaking related plaintexts is another good defense.
Cramer-Shoup is good work and a good academic paper. The results are suprising: provable security against adaptive chosen ciphertexts and only twice as slow and four times the data expansion. But the proofs are based on something called the Diffie-Hellman Decision Problem (not the Diffie-Hellman Problem), which is much weaker. And IBM’s provably secure algorithm from last year’s Crypto, Atjai-Dwork, has at least three different breaks. The breaks don’t attack the proofs, but the assumptions surrounding the proofs.
If, in a few years, Cramer-Shoup still looks secure, cryptographers may look at using it instead of other defenses they are already using. But since IBM is going to patent Cramer-Shoup, probably not. (There have been some reports that IBM will give the patent away, but I have seen nothing conclusive.) But we have many other solutions to the problem of adaptive chosen ciphertext attacks.
excite news: http://nt.excite.com:80/news/bw/980824/…
BBCNews: http://news.bbc.co.uk:80/hi/english/sci/tech/…
Nando (Reuters): http://www2.nando.net:80/newsroom/ntn/info/082498/…
ABCNews: http://www.abcnews.com:80/sections/tech/DailyNews/…
MSNBC: http://www.msnbc.com:80/news/190053.asp [dead link]
news.com (Reuters): http://www.news.com:80/News/Item/0,4,25598,00.html?owv
Wired: http://www.wired.com:80/news/technology/…
PCWeek: http://www8.zdnet.com:80/pcweek/news/0824/24eibm.html
Impossible Cryptanalysis and Skipjack
Eli Biham, Alix Biryukov, and Adi Shamir invented something called “impossible cryptanalysis,” which they presented at the rump session (the informal session where recent results are briefly described) of Crypto ’98. (Biham and Shamir are two Israeli cryptographers who independently invented differential cryptanalysis in 1991, setting the foundations for pretty much every general cryptanalytic technique since then.)
The basic idea is that they look for differentials (differences between pairs of plaintexts that have some percentage of holding true for the corresponding differences between pairs of ciphertexts) that are impossible; i.e., that cannot happen. It turns out that in many cases these impossible differentials are more powerful than normal differentials, and can be used to attack encryption algorithms.
The group presented an attack against 31-round Skipjack that is faster than brute force. Skipjack has 32 rounds, so their attack is just shy of being better than brute force. On the other hand, I can’t imagine that the NSA would field an algorithm with 32 rounds when they could break 31, so I believe that the NSA did not know about this attack. And the cryptanalysts are still working on improving their attack, so it is possible that they will get to 32 rounds.
Since none of the AES submissions have been designed with impossible cryptanalysis in mind (with the possible exception of Biham’s own Serpent), it will be interesting to see how the algorithms fare against this new form of attack. My guess is that all will be strongly resistant to it, with a couple of exceptions.
http://www.cs.technion.ac.il/~biham/Reports/SkipJack/
Counterpane Systems—Featured Research
“Electronic Commerce and the Street Performer Protocol”
J. Kelsey and B. Schneier, The Third USENIX Workshop on Electronic Commerce Proceedings, USENIX Press, September 1998.
Copyright will be increasingly difficult to enforce in the future. The barriers to making high-quality pirated copies of digital works are getting lower and lower, and solutions such as hardware tamper-resistance and watermarking just don’t work. We introduce the Street Performer Protocol, an electronic-commerce mechanism to facilitate the private financing of public works. Using this protocol, people would place donations in escrow, to be released to an author in the event that the promised work is put in the public domain. This protocol has the potential to fund alternative or “marginal” works.
http://www.schneier.com/paper-street-performer.html
News
A U.S. programmer has posted encryption software on his website, just daring the government to pick him off. He’s looking to be a test case. Good for him.
http://www.zdnet.com/intweek/print/980824/346609.html
http://www.mercurycenter.com/premium/business/docs/… [dead link; available for a fee in the Mercury Center Archives—search in 1998 for Charles Booher]
Fifteen algorithms are lined up as potential replacements for DES. Counterpane’s Twofish is one of them. On 20-23 August, NIST held the First AES Conference. Twofish is now one of twelve remaining.
http://www.fcw.com/pubs/fcw/1998/0831/…
Congressman Tauzin takes a hard line against the FBI’s access to encryption keys. Tauzin chairs the House Commerce Committee’s subcommittee on telecommunications, so this matters.
http://www.zdnet.com/zdnn/stories/…
PGP adds support for X.509 certificates. This will probably help them get accepted as mainstream, but they still are not compatible with S/MIME.
http://www.techweb.com/wire/story/TWB19980904S0010
Pegging the Clueless Meter…. “With PCs 1,000 times more powerful than they used to be, our encryption keys can and should be 1,000 times bigger too. That means cryptokeys of at least 56,000 bits.”
Toni Patti, “Available right now: Uncrackable encryption, Dirt Cheap”
http://www.developer.com/journal/ITfocus/…
Private Doorbell
Last month I posted a quick reaction to Private Doorbell, a Cisco key-recovery program, which was that it was the same old key-escrow repackaged with a new name. It seems my analysis was a bit hasty.
Private Doorbell is an attempt to hack the government’s key-escrow export policy. The goal is to export existing, unmodified, encrypting routers, while at the same time satisfying the letter of the regulations. What the export regulations require is that there be an access point for eavesdropping, not necessarily that the access be provided by releasing keys. Now by definition, encrypting routers have an unencrypted side and an encrypted side. If you want to eavesdrop, you can already eavesdrop on the unencrypted side. Administration functions are already built into these routers; a network administrator can certainly respond to a court order. Hence, encrypting routers should be exportable, no modifications required.
Of course there’s nothing stopping users from pre-encrypting with PGP or S/MIME; that, Private Doorbell supporters argue, is not their problem. And there’s no “key escrow”; the keys are already in the routers, encrypting and decrypting traffic as before.
This is actually pretty clever. There are no modifications to the routers, no special key-collection features or additional key management infrastructure; the routers are doing what encrypted routers do anyway. The FBI gets what it asked for (although not the no-warrant no-block wiretaps Louis Freeh really wants), and it already can produce a warrant and wiretap an ISP. The only group that is pissed is NSA.
The whole deal is a “policy initiative” based on the wording in Section 740.8(d)(1)(ii) of the EAR (Export Administration Regulations), which says that “other recoverable encryption products” shall receive “favorable consideration” for export. The products all promise to provide a configurable interface that lets encryption be controlled based on source and destination addresses, and provide means to route plaintext traffic of interest to a port that law enforcement can tap. This is to address law enforcement’s concerns. For NSA, they offer restrictions on their proposed export licensing arrangements that would prevent sales (without an ordinary BXA license review) to military and diplomatic agencies in a list of countries.
Cisco got a pile of companies to submit similar applications simultaneously, including Sun, 3Com, HP, and Bay Networks. These were filed July 12; the government has 90 days to respond. It remains to be seen how the Commerce Department (actually, the FBI, State Department, and NSA) will respond, or what the companies will do if it doesn’t.
Cisco has been working on this since October 1997, and went public because they felt that their export paperwork was being stalled by the NSA. This “stalling” seems to have been done in secret; Cisco says that no one in any agency has questioned the legitimacy of their original filing.
This is a legal/political strategy that we hadn’t thought of: Split the law enforcement and national security communities by offering to satisfy law enforcement’s problem (after pushing its desires back into the box defined by the Constitution). Then national security has to step out from behind the FBI’s skirts and acknowledge itself. And the initiative tries to offer what a national intelligence agency that’s only concerned with diplomatic and military traffic would need, so if they need more, they have to expose those needs.
This won’t work for all encryption products (file encryptors, for example), but it does work for a lot of communications products, especially network-layer encryption products. Depending on how they are implemented, IPSec systems could sneak through this same loophole. And that’s without the addition of any key-escrow functionality.
http://www.cisco.com/warp/public/146/july98/2.html [dead link as of 2000-01-10]
Corrections to 15 August 1998 CRYPTO-GRAM
In my lead story on Deep Crack, I said that follow-on machines would cost only $50K. This turns out not to be true. John Gilmore attributes the incorrect fact to someone at EFF, who got the story wrong. It has been repeated ever since, so I am taking this opportunity to correct the record: A second Deep Crack machine will cost about the same as the first. Of course, if someone were to spend time researching the efficiencies of brute force machines, costs could probably come down significantly.
http://www.eff.org/descracker/
Last month I mentioned a Wired News story where “the Pentagon’s top civil servant believes that no two people in the world have a ‘God-given right’ to communicate in total secrecy.” Wired has since changed the news story. This is the new lead paragraph:
The Pentagon’s top civil servant said that no company has a “God-given right” to export powerful American data scrambling technology that would allow foreign nationals to communicate in total secrecy, according to information made public this week.
The article contains the following retraction:
Editor’s Note: The headline and first paragraph of this story have been corrected to better reflect the context of John Hamre’s remarks regarding the export of powerful US encryption technology. In the original story, Hamre’s comments regarding “no God-given right” were misrepresented as suggesting that no two people in the world had the right to communicate in total secrecy. Wired News regrets the error.
Apologies for promulgating an error.
http://www.wired.com/news/technology/…
More on Biometrics
This comment is from Tom Rowley, CEO of Veridicom:
As always, your analysis is impeccable. But I think it misses the real value that biometrics offer. I’ve noticed that most people trained in security tend to ignore this value but it’s very real.
People like biometrics because they believe in them. And, therefore, use them. And it’s certainly true that a poor security system used all the time is better than a “perfect” security system never used.
When I think about people’s attitudes to biometrics, I tend to draw conclusions from signatures, as opposed to fingerprints, because signatures have the most extensive use in real “security” applications. People are willing to accept fingerprints as valid authorization for very high value transactions, even life and death, because they believe in them. All of the security flaws which you pointed out about signatures are true. Nevertheless, they pervade the authorization infrastructure. Their non-repudiation character, which you correctly rebut, is nonetheless a fact because users want it to be.
I observe that this hunger for an understandable authentication mechanism is so strong that a variety of higher level infrastructures are added by the world to deal with improving the legitimacy of signatures, e.g. notary public. (I’ve always thought that the value of someone that neither of you know certifying that you are who you say you are is fascinating.)
Or the insistence on “originals” of signed documents on the presumption that these will be more difficult to forge than copies. Or a raised seal over a signed passport photograph.
This sort of psychological analysis of the value of signatures (and by extension, fingerprints) for authentication may seem bizarre from a crypto science standpoint but it’s very acceptable to users.
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.