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

Once again DDDU has an encryption News Brief re the Standards & clipper,
and Bruce Schneier has an article on Eurocrypt '94 with some highlights
from the same.  As he is on the list (yes?) perhaps he might upload it
here...


-NetSurfer

#include standard.disclaimer

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
==  =    = |James D. Wilson        |V.PGP 2.4:   512/E12FCD 1994/03/17 >
 "  "    " |P. O. Box 15432        |     finger for full PGP key        >
 "  " /\ " |Honolulu, HI  96830    |====================================>
\"  "/  \" |Serendipitous Solutions|    Also NetSurfer@sersol.com      >
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

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

On Fri, 1 Jul 1994, Bruce Schneier wrote:

>      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. 

Hrm...  As far as I recall they showed how to do _message_recovery_ (not 
encryption) with the discrete log signature functions.  Message recovery 
and encryption are two quite different things for assymetric schemes such as 
the discrete log ones (as opposed to RSA).  Correct me if I'm wrong...

>      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.

Yea, cool stuff, especially if the fax doesen't shrink the transmitted 
picture :-)  This is also great for demonstrating crypto to newbies by 
showing that noise+noise=picture.

-- Rolf



----------------------------------------------------------------------
Rolf Michelsen                           "Standards are wonderful --     
Email: rolf.michelsen@delab.sintef.no      everyone should have one"
Phone: +47 73 59 87 33                       -- Ancient FORTH proverb
----------------------------------------------------------------------

> 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.

   Yea, cool stuff, especially if the fax doesen't shrink the transmitted 
   picture :-)  

Shamir's comment on this at his talk at MIT was that the accuracy of a
fax machine in the horizontal direction was much better than the
accuracy in the vertical direction.  If the visually encrypted
document is a text file, you can adjust it so that it's correctly
registered for a few lines, read those lines, slide the key
transparancy by a small fraction of an inch, read the next few lines,
and repeat until you're done with the message.

							- Bill

-----BEGIN PGP SIGNED MESSAGE-----

>     Feedback with Carry Shift Registers (FCSRs):  Linear
>Feedback Shift Registers (LFSRs) have been the workhorse of
>military cryptography for years.  Goresky and Klapper have

An interesting thought hit me when reading this.  The "classic"
Cray series (Cray-1, X-MP, Y-MP) all have a rather curious instruction
generally known as population count.  All it does is to take a register
and count the number of one bits in it, and return that count.  Originally
I could never figure out a use for this, but later was told that it was the
"canonical NSA instruction", and was consistently demanded by almost all
military SIGINT operations.

On reading this, I realised that one possible use was to implement a
vectorized version of a LFSR.  Take a vector register (the shift register),
AND it with a mask of the taps into another vector register, and then
do a population count to determine the carry in.

Just a thought.  It's the only plausable use that I have yet thought of
for this instruction.  Has anyone else got any ideas?

As for military ciphers having been "the workhorse of military
cryptography for years", I am reminded (with some amusement) of the
structure of A5.  I wonder if all of the fuss about secrecy was not
about the almost non-existant security of the cipher, but simply it's
similarity to more sophisticated military ciphers?

						Ian.

-----BEGIN PGP SIGNATURE-----
Version: 2.3

iQCVAgUBLhX/qtCZASdT8NoBAQF8SAP/V5FKgEaCk1GQXV9rrK+AMry2Bzb9Xlyu
bYMqjN94mAqqkNOe1r2ChmUF4kleTUMxdx1Krje3xhLDPL31HH4lvJ386sm6Ogrm
/iu/TgjoSnGbMYtoq+C2ZJacA/NBDzItTeUaZgkWRS62Emo/cFIGarT130clL8/x
HnNbtdGtSOE=
=VVZZ
-----END PGP SIGNATURE-----

>An interesting thought hit me when reading this.  The "classic"
>Cray series (Cray-1, X-MP, Y-MP) all have a rather curious instruction
>generally known as population count.  All it does is to take a register
>and count the number of one bits in it, and return that count.  Originally
>I could never figure out a use for this, but later was told that it was the
>"canonical NSA instruction", and was consistently demanded by almost all
>military SIGINT operations.

>On reading this, I realised that one possible use was to implement a
>vectorized version of a LFSR.  Take a vector register (the shift register),
>AND it with a mask of the taps into another vector register, and then
>do a population count to determine the carry in.

>Just a thought.  It's the only plausable use that I have yet thought of
>for this instruction.  Has anyone else got any ideas?

This operation is ideal for computing the "hamming distance" between
two binary words, an important operation in the encoding and decoding
of forward error correcting codes. It's also used when correlating
binary streams, eg, searching for frame synchronization vectors or
despreading spread spectrum signals. All these operations are
fundamental to modern digital radio communications.

I've written software that implements a correlator, a convolutional
coder and a sequential decoder. All three make heavy use of this
operation, so I know first hand how useful it would be to have such an
instruction. The best I can do on the 386/486 when is to add the
results of table lookups on manageable pieces of the word (e.g., 8
bits at a time).

People keep assuming that NSA spends most (or even all) of its CPU
cycles on cryptanalysis. They forget that before you can attack a
cipher, you need some ciphertext. Usually this comes by radio. This
means analyzing, demodulating and decoding (as opposed to deciphering)
the digital RF modulation being used by your target. A Cray with a
library of signal analysis and demodulation programs would be ideal
for this purpose.

I would make an educated guess that this, and not cryptanalysis, is
NSA's biggest use for their Crays.  A Cray is not especially
cost-effective for cryptanalysis, at least compared with special
purpose hardware that could, say, attack DES far more cheaply.

And then there's this friend of mine who works for IDA/CRD, the NSA
think-tank in Princeton. His specialty is digital signal processing,
often using Crays. As a lark, he once demodulated some amateur packet
radio signals that were used in "Star Trek IV" as background sound
effects. Great fun.  Another time he helped the Russians demodulate
some telemetry signals from their "Vega" Venus balloon probe. Sucked
the bits right out of the noise.

Phil