Crypto '95 report

[Hal <hfinney@shell.portal.com>]

This was the first year I attended a Crypto conference (although for the
last two years I have "crashed" the evening rump session, where less
formal 5-10 minute presentations are given).  A number of list members
were present and it was good to meet a lot of new people.

I was a bit disappointed that few of the technical sessions were in areas
that I am interested in or that seem to have bearing on CP issues.  I
have read many of the Crypto proceedings and this year the pickings
seemed to be unusually slim.

Richard Schroeppel gave a very clear presentation on an implementation
of elliptic curve cryptography for a diffie-hellman-like key exchange.
This is a two-dimensional variation from the regular integers that are
used in most of the number theory based crypto, and has some
advantages.  This new implementation is actually faster than regular DH
for apparently the same security level.  It looks like elliptic curve
crypto is on the threshold of coming into widespread use.  I believe the
patent situation is one of the main reasons.

There were several papers on secret sharing, something we have discussed
here as an alternative to escrow for handling lost keys.  Amir Herzberg
et al had a method for "resharing" a shared secret periodically and
securely, so that if an adversary was stealthily sneaking in and learning
shares occasionally, he would be put back to square one when the secret
resharing phase occured.  Only the trustees are involved, not the
original secret holder, and the secret does not have to be reconstructed
during the resharing.

Bruce Dodson presented some results on using the Number Field Sieve
factoring algorithm.  Their implementation looks to be the fastest
available now, considerably better than the Quadratic Sieve that was used
for RSA-129.  I belive they estimated 1000 MIPS years would have been
enough for NFS to do RSA-129 compared to the 6000 MIPS years for QS.
They are now going to try another challenge number, RSA-130.  (RSA has
challenge numbers every 10 digits in size (or maybe it was 5): RSA-140,
RSA-150, etc.)

There was one paper on electronic cash, by Okamoto.  His technology is
distinguished by allowing divisibility - you can take a $10 and divide
it into 2 $5's without going back to the bank.  However he has always
had a problem that your various pieces of cash are linkable, although
not traceable to the user who withdrew them.  His new method uses
smaller amounts of data.  I was encouraged to see some progress on the
linkability issue: for the first time (that I have seen) he admits it
as a problem; he now has it so that theoretically the linkability is
only within a single divided piece of cash (so that if you didn't
divide you wouldn't have linkability).  Actually the overheads are too
large for this to by quite true, but it is a step in the right
direction.  He also included elimination of linkability as a future
goal.  Unfortunately his oral presentation was extremely shallow,
mostly describing what electronic cash was.

There was also a paper on "fingerprinting", the encoding of hidden
information into a document so that if the doc is leaked it can be traced
to the leaker.  The talk wasn't very clear but I was able to glean enough
that I now believe that this is possible whereas I didn't before.

I was discouraged to see a whole session on key escrow.  One presenter
described key escrow as a whole new area of cryptography, analogous to
the discovery of public key crypto when all that was known previously was
conventional key.  Now there are three areas.  The academic crypto
community seems to be greeting key escrow enthusiastically as a new
technical challenge.

The rump session had some good stuff, I thought.  Matt Blaze et al had a
paper on "Master Key" cryptosystems, a variation on escrow where the
government can read all the messages using a certain cryptosystem.  They
pointed out the similarity to the trap door concept used in public key
cryptography and concluded that an efficient master key system would be
an efficient public key system.  If you believe that the latter can't
exist then it follows that the master key versions can't exist either.

Bruce Schneier gave a talk summarizing the sketchy information known
about Skipjack (the cipher in Clipper), including some FOIA'd docs.
These included some comments from design reviews by Mycotronix on
earlier versions, which included references to F and G boxes or
tables.  This is the first I had heard of this and helps explain why
people thought S-1 was Skipjack or a hoax, since it had F and G
tables.  (I hadn't felt that the number of rounds and key/block sizes
were sufficient coincidence to preclude independent invention.)

A new crypto library was announced from AT&T.  It is written in C and
has a bignum lib (arbitrary size) and the usual crypto suspects,
although I think not RSA presuambly due to patent issues.  On a
reasonably modern PC it could do an RSA 1024 bit signature in 900
milliseconds.  Email to lacy@research.att.com with subject CRYPTOLIB to
be informed on when it will be released and how to get it.

Dhem and Quisquiter described CASCADE, a smart card system with voice
recognition for ID rather than the PIN usually used.
http://www.dice.ucl.ac.be/~dhem/cascade/.  This talk was hard to
understand due to the language differences.

Eric Hughes, co-founder of the cypherpunks, announced the formation of
Cypherpunk Laboratories, a California non-profit corporation.  It is
intended to be a common resource for people motivated by freely available
strong cryptography tools.  Among other things it will offer scholarships
and prizes to students who create relevant work and papers, consider
establishing an online journal focusing on implementations of crypto, and
work on software development.  One project Eric mentioned was to create a
replacement for PGP.

Ron Rivest proposed probabilisitic key escrow, which he described as
"translucent" crypto.  The idea is that with every message you send
there is a Law Enforcement Access Field, but there is only some
probability p that it is readable, and you can't tell if it will be
readable or not.  This way you don't lose as much privacy but criminals
can't take the risk that maybe they'll be unlucky and this particular
message will be readable.

Shamir had an interesting paper on preventing "flooding" attacks.  A
server may check for signatures on incoming messages to reject bogus ones
(only certain sigs are valid) but just doing a signature check may take
too long if it is really being flooded.  Shamir came up with a kind of
signature which can be quickly probabilistically checked, based on a
variation on the Rabin cryptosystem.  You can do almost all the work
using single precision and it should be very fast.  I will write this up
if anyone is interested.

Our own Wei Dai, at 19 the youngest author, has spent his summer
vacation developing with Josh Benaloh at Microsoft an improved modular
reduction algorithm, which unfortunately will be patented (or at least
they will try).  BTW a number of people from Microsoft were in attendance
at Crypto, including other list members.  Obviously this crypto stuff
is considered very important at MS.

One of the more interesting talks I thought was from cypherpunk Doug
Barnes, on "identity agnostic" electronic cash.  This is basically an
idea for creating a Magic-Money-type electronic cash server without
violating Chaum's cash patent.  What you do is to run the server and
publish a spec it will follow.  All the server does is do an RSA
signature on the raw data it receives and decrement the user's account
accordingly.  The user has a choice of doing blinding or not on the
signature.

Chaum's patent covers the blinding, so if the user wants to do that he
should be sure to license the patent or live somewhere it doesn't apply
(or ignore it if he figures he's too small potatoes for them to care
about).  But the server isn't responsible for checking all this.  It just
does RSA sigs, which is prior art as far as Chaum's patent goes.  Users
can blind or not, it doesn't care.  It is "identity agnostic" as Doug
says.

The implication is that with an RSA license you could run this kind of
bank (online cash) and ignore Chaum's patents, while a horde of end users
violate the patents but take safety in numbers and get anonymity.
Lawyers like to go after big targets but the servers aren't violating
anything.

The other things I enjoyed in the conference were the non technical talks
by Bob Morris (senior), retired NSA, and later Adi Shamir.  Morris said,
with what I thought was peculiar emphasis, "never underestimate the
amount of time, money, and effort your opponent will put into breaking
your encryption."  He was supposedly speaking in the context of the
German (and Allied) mistakes during WWII, but I got the impression he was
talking about today, and in fact warning of NSA efforts to spy on people.
He went on to describe the many ways mikes and antennas can be planted or
used - he looks at a telephone and sees a microphone, and the hand cord
is an antenna.  All in all a rather chilling talk from someone who
obviously can't say as much as he would like to.

Shamir had some interesting anecdotes about the invention of RSA.  He
emphasized what amateurs the three of them were, claiming this was
probably an advantage.

Some of the other talks I enjoyed without following all the details were
the cryptanalysis ones.  A lot of systems were broken or weaknesses
found.  Most were not ones I was familiar with but it just emphasizes how
hard it is to really come up with something strong.  All those bozos on
sci.crypt with their "break this" challenges would benefit from seeing
some of these results.

All in all there were several interesting results even if the percentage
seemed smaller than usual.

Hal Finney