May 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 Secret Story of Non-Secret Encryption
- Research: Conditional Purchase Orders
- Advanced Encryption Standard (AES)
- About “CRYPTO-GRAM”
The Secret Story of Non-Secret Encryption
On Dec 16, 1997 the GCHQ, the British equivalent of the NSA, released a document stating that they had invented public key cryptography several years before it was discovered by the research community. According to the paper, they had discovered both RSA and Diffie-Hellman, and had kept their discoveries secret.
During World War II, some unknown researcher at Bell Telephone Labs had the idea that a receiver could inject noise onto a communications circuit and effectively drown out any signal. An eavesdropper would only hear the noise, but the receiver could subtract the noise and recover the signal. The interesting idea here is that the sender doesn’t have to know any encryption “key” in order to send a secret message to the receiver; the receiver does all the work. (This is essentially what echo-canceling modems do; they scream at each other along the same line, and subtract out their own signal when they listen for the other.) The research was promptly classified by the US Government.
Fast forward to 1960 in the U.K. Intrigued by this idea, James Ellis wrote a classified paper providing an existence proof of “non-secret encryption.” It’s a thoroughly impractical scheme, with large tables and other pre-computer cryptographic ideas, but there it was.
In 1973 Clifford Cocks (another British spook) published a classified paper where he described (essentially) RSA. And in 1974, M.J. Williamson invented another classified algorithm, remarkably similar to Diffie-Hellman.
Those who pay attention to such things believe that the GCHG claims are valid, and that the mathematics of public-key cryptography were discovered within the intelligence community several years before they were discovered by academic cryptographers. But while they may have discovered the mathematics, it is clear that they never understood its significance.
Public-key cryptography is not used to encrypt data directly. It is used for key exchange, key distribution, and digital signatures. Its primary benefit is allowing people who have no pre-existing security arrangement to exchange messages securely, or for a sender to authenticate a message to a random receiver.
The military world is a fixed hierarchy. Key distribution works through the chain of command, and units trust their superiors. Soldiers don’t need to communicate with people they don’t have pre-existing arrangements with; those people are either civilians or the enemy. The problems that are immediately obvious to someone trying to secure the nutty world of business and personal communications just didn’t occur to those trying to secure a military.
So the British didn’t envision their non-secret encryption as a solution to the key management problem, and the notion of digital signatures didn’t occur to them. It took Ralph Merkle and Martin Hellman and Whitfield Diffie to invent public-key cryptography, and Ron Rivest, Adi Shamir, and Len Adelman to invent RSA. (The British did not invent knapsack encryption or the ElGamal algorithm before it was published in the academic community.)
This announcement by GCHQ doesn’t mean that we’re going to start calling RSA “Cocks” and Diffie-Hellman “Williamson,” but it is an interesting footnote to the history of modern cryptography. And we still don’t know if the NSA developed public-key cryptography before learning about it from the British or the press, as they have sometimes claimed. But we do know that the first military device that used public-key cryptography, the STU-III telephone, was not built until the mid 1980s, long after the academic community expounded on the technology.
http://www.cesg.gov.uk/pkc.htm [dead link as of 1999-08-23; see http://www.cesg.gov.uk/publications/ for documents on non-secret encryption]
Counterpane Systems—Featured Research
“Conditional Purchase Orders”
J. Kelsey and B. Schneier, 4th ACM Conference on Computer and Communications Security, ACM Press, April 1997, pp. 117-124.
This paper describes a system of commerce based on the Conditional Purchase Order (CPO). This system is buyer-driven: individual buyers issue CPOs, which are evaluated and fulfilled by sellers. There are mechanisms to bind the buyer to the transaction once a seller meets the conditions. Additional enhancements include the ability to add anonymity, and assurances of product quality by trusted third parties.
The Advanced Encryption Standard (AES)
In 1972 and 1974, the National Bureau of Standards (now the National Institute of Standards and Technology, or NIST) issued the first public request for an encryption standard. The result was DES, arguably the most widely used and successful encryption algorithm in the world.
In response to a growing desire to replace DES (too-short key, too slow, too clunky), NIST announced the Advanced Encryption Standard (AES) program in 1997. NIST solicited comments from the public on the proposed standard, and eventually issued a call for algorithms to satisfy the standard. The intention is for NIST to make all submissions public and eventually, through a process of public review and comment, choose a new encryption standard to replace DES. Think of it as a giant demolition derby: people submit algorithms and then beat on each other. The last one standing wins.
NIST’s call requested a block cipher. They wanted it to have a 128-bit block size (which effectively ruled out almost all existing algorithms), and key sizes of 128-, 192-, and 256-bits. They wanted it to be efficient and flexible (whatever that means). And they wanted it to be free, either unpatented or with patent right given away.
About a dozen groups are working on a submission. IBM has already submitted something, as did Cylink and RSADSI. An Australian submission has appeared on the WWW, and Serpent was published at a conference in March. I expect submissions from Katholieke Universiteit in Belgium, NTT in Japan, Entrust Technologies in Canada, and L’Ecole Normale Superieur in France.
The NSA will not submit an algorithm. They claim that NIST asked them not to submit, so they could be an impartial assistant judge rather than a participant.
http://csrc.nist.gov/encryption/aes/aes_home.htm
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 on http://www.schneier.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 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.