Re: Dr. Dobbs Dev. Update 1/5 July 94 & Schneier

[schneier@chinet.chinet.com (Bruce Schneier)]

                    EUROCRYPT '94 CONFERENCE


In the cryptographic world--at least, the cryptographic world
outside the military--there are two major annual conferences:
Crypto and Eurocrypt.  Eurocrypt '94 was held in Perugia, Italy,
on May 9-12.  There were about 300 people in attendance,
representing the best in academic cryptography from five
continents (I didn't notice anyone from South America or
Antarctica).  A total of 37 papers were presented at the main
session, and another twenty or so at an informal "rump session"
one evening.

Much of what was presented was very theoretical, and only of
marginal interest to front-line programmers actually implementing
this stuff.  Here is a list of what I found 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 that were 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 development to dramatically change the development
of stream ciphers.

     Synthesis of Public-Key Algorithms:  There are a lot of
public-key digital signature algorithms in the literature based
on the problem of taking discrete logarithms in a finite field: 
ElGamal, Schnorr, and the Digital Signature Standard (DSS) are
three examples.  Nyberg and Rueppel presented a paper which
unified all of these algorithms (108 in total) into one unified
family.  They also showed how to do encryption with all of them. 
What this does it allow further research to proceed on the entire
family of algorithms, and not just on one particular one.  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 on this general algorithm.

     The Digital Signature Standard:  Naccache, M'Raihi,
Raphaeli, and Vaudenay presented enhancements to the DSS: one
that increases speed, one that reduces storage requirements
(important for smart-card implementations), etc.  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 that is 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.  Applications
include sending an encrypted message via fax: the receiver can
carry the key transparency with him and can 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. 
Applications include 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 only wants
his signature to be verifiable 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, but
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 is just as strong.

     Formal Protocol Design:  One of the problems with
authentication protocols, like 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.

Several interesting papers were presented at the rump session.  
Biham presented a paper showing that triple-DES in cipher
feedback mode, with triple-DES as the bock 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.  There is 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.
Also interesting were the side discussions.  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 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 to watch for them.

RSA-129 was recently factored.  This is the 129-digit number, the
product of two large primes, that was featured in Martin
Gardner's original Scientific American column about the RSA
algorithm.  Although this doesn't affect the security of the
1024-bit numbers used in programs like PGP, it does show how far
we've come in fifteen 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), discussed in the Apr 94 DDJ.  The cryptographers
at NSA have found a problem with the algorithm.  They won't tell
anyone what it is, or even how serious it is, but they promise a
fix soon.  Everyone is waiting with baited breath.

From owner-cypherpunks  Fri Jul  1 19:51:37 1994
Return-Path: <owner-cypherpunks>
Received: by toad.com id AA19692; Fri, 1 Jul 94 19:51:37 PDT