Eurocrypt '94

Bruce Schneier

In the cryptographic world--at least, the cryptographic world outside the military--there are two major annual conferences: Crypto and Eurocrypt. Eurocrypt '94, held in Perugia, Italy, in mid-May, had an attendance of approximately 300, representing the best in academic cryptography from five continents. A total of 37 papers were presented at the main session, with another 20 or so at an informal "rump session" one evening.

Much of what was presented was very theoretical and only of marginal use to front-line programmers actually implementing such things. Still, I found the following both useful and important:

• Feedback with Carry-Shift Registers (FCSRs). Linear-Feedback Shift Registers (LFSRs) have been the workhorse of military cryptography for years. Goresky and Klapper have discovered a new class of shift registers which should prove to be just as useful. There are analogues for most of the LFSR theory that apply to FCSRs. Algorithms implemented with LFSRs can be implemented with FCSRs, possibly with different degrees of security. Even more interesting should be cryptographic algorithms, which use a mixture of LFSRs and FCSRs. I expect this to dramatically change the development of stream ciphers.
• Synthesis of Public-Key Algorithms. Numerous public-key, digital-signature algorithms are based on the problem of taking discrete logarithms in a finite field: El Gamal, Schnorr, and the Digital-Signature Standard (DSS) are three such examples. Nyberg and Rueppel presented a paper which unified all of these algorithms (108 total) into one family. They also showed how to encrypt with all of them. This allows for further research on the entire family of algorithms, not just on one in particular. It also lays to rest Schnorr's claim that the DSS infringed on his patent; it is now clear that both Schnorr and DSS are specific cases in this general algorithm.
• The Digital-Signature Standard. Naccache, M'Raihi, Raphaeli, and Vaudenay presented enhancements to the DSS--one that increases speed and another that reduces storage requirements (important for smart-card implementations). Their most interesting enhancement is the ability to verify multiple signatures in a single operation. A complaint against DSS is that signature verification is slow. The batch-verification method in this paper should silence that complaint once and for all.
• Visual Cryptography. Shamir developed a one-time-pad cryptosystem suitable for encrypting visual images. The key is a pattern of black and white pixels on a transparency; the ciphertext is another pattern of black and white pixels. Overlay the key on the ciphertext, and the message appears. This is unconditionally secure; even alien civilizations with undreamed-of computing power cannot break this cryptosystem. One application is sending an encrypted message via fax: The receiver can carry the key transparency with him and receive the encrypted fax from an insecure machine. Cool stuff.
• Designated Confirmer Signatures. Undeniable signatures are signatures which need permission from the signer to verify. One application is computer publication of data. The recipient of the data wants to be able to verify the publisher's signature, so he knows that the data is authentic. The publisher wants his signature to be verifiable only by people who have paid for the data and not by people who have pirated it. Undeniable signatures do that. Chaum's extension allows the publisher to designate an agent who can help receivers verify the signatures.
• Differential and Linear Cryptanalysis. Both of these techniques were further refined by several people. Two papers, one by Biham and another by Chabaud and Vaudenay, looked at similarities between the two. Matsui found an alternate order for the S-boxes that is resistant to linear cryptanalysis; unfortunately, it is weak against differential cryptanalysis.
• Self-Shrinking Generator. The shrinking generator was a big hit at Crypto '93. Basically, a LFSR is decimated by another LFSR. This stream algorithm is simple to implement and looks very strong. Meyer and Staffelbach developed a variant of this generator, which uses a single LFSR. The even bits of the generator are used to decimate the odd bits. This is even simpler to implement and just as strong.
• Formal Protocol Design. One of the problems with authentication protocols, such as Kerberos is proving that they are correct. There's nothing more embarrassing than fielding a protocol and finding a security problem two years later. Syverson and Meadows have developed an expert system that helps detect security problems in protocols.

Among the interesting papers presented at the rump session were Biham's, showing that triple-DES in cipher-feedback mode, with triple-DES as the block cipher, is more secure than a large number of variant possibilities. Knudsen found a class of "weak" keys for DES and LOKI when those algorithms are used as one-way hash functions. However, there is really nothing to worry about; the odds of picking such a key at random is very small. Charnes and O'Connor presented some initial comments on the GOST algorithm, an encryption algorithm from the Soviet Union.

The side discussions were also interesting. At least two cryptographers are working on something called "higher-order differential cryptanalysis." Although this technique has had great success against DES with only 5 rounds, no one knows how to extend it to a full 16-round DES. One cryptographer has developed an alternate set of DES S-boxes that is resistant to both differential and linear cryptanalysis, while another has developed a method for generating key-dependent S-boxes that increase the effective key size of DES beyond 56 bits. If there are going to be any more attacks against DES, this--and Hellman's attempts to combine differential and linear cryptanalysis--is where you'll want to be watching.

RSA-129 was recently factored. This is the 129-digit number, the product of two large primes, that was featured in Martin Gardner's seminal Scientific American column (August 1977) about the RSA algorithm. Although this doesn't affect the security of the 1024-bit numbers used in programs such as PGP, it does show how far we've come in 15 years. Gardner was sure this number would not be factored for millions of years.

The other big news is a security problem with the Secure Hash Algorithm (SHA); see "The Secure Hash Algorithm" by William Stallings, DDJ, April 1994. NSA cryptographers acknowledge they've found a problem with the algorithm, but they won't tell anyone what, or even how serious, it is. Still, they promise a fix really soon now. Expect that fix to be secret, too. We're all waiting with bated breath.