Challenge-response passwords (Was: big word listing)

At 06:59 PM 7/25/95 +0100, Andrew Spring wrote:
>Free-after-1997 example:
>        g is a generator of a prime p.
>        password is X (0<X<p);
>        password file has g^X mod p.
>        login server generates Y, issues challenge g^Y.
>        expected response is g^XY mod p
>        login client has X, generates (g^Y)^X = g^XY mod p.
>        J. Random SuperHacker can get g^X, and g^Y, but not g^XY.

It's _not_ free after 1997!  I thought of it last fall, was surprised I couldn't
find it anywhere in the literature, given that it's pretty obvious,
but eventually found that a guy from Siemens had patented it in Germany
and then gotten a US patent in ~1994.  Unfortunately, he phrased it in terms of
"commutative hash functions", with g^X mod p as an example, so it's more
general.
He also extended it to do two-way authentication (obviously the process can be
symmetrical if the user has a stored g^W from the server and can send a
challenge,
but he found a way to save a step or two.)

I developed it because I was looking for a way to do authentication-only
public key stuff so the code would be exportable - this approach doesn't
generate a shared secret (since the otherwise-secret g^XT is exposed
as the response to the challenge.)  However, it's possible to extend it to
preserve the shared secret - instead of sending response g^XY mod p, send
        Hash(g^XY mod p)
and have the login server validate that.  One advantage is that the hash
can be much shorter than the whole g^XY mod p, e.g. 32-64 bits instead of
512-1024.

And you can now use (g^XY mod p) as a session key (for encrypted sessions)
or an authenticator (e.g. send Hash(Data,sequence#,sessionkey) as a MAC for
each packet.
#---
#                                Thanks;  Bill
# Bill Stewart, Freelance Information Architect, stewarts@ix.netcom.com
# Phone +1-510-247-0664 Pager/Voicemail 1-408-787-1281
#---
# Export PGP three lines a time --> http://dcs.ex.ac.uk/~aba/export/
M0V]N9W)E<W,@<VAA;&P@;6%K92!N;R!L87<@+BXN(&%B<FED9VEN9R!T:&4@
M9G)E961O;2!O9B!S<&5E8V@L(&]R(&]F('1H92!P<F5S<SL-"F]R('1H92!R
M:6=H="!O9B!T:&4@<&5O<&QE('!E86-E86)L>2!T;R!A<W-E;6)L92P@( T*

Bill Stewart writes:
> It's _not_ free after 1997!  I thought of it last fall, was
> surprised I couldn't find it anywhere in the literature, given that
> it's pretty obvious, but eventually found that a guy from Siemens
> had patented it in Germany and then gotten a US patent in ~1994.
> Unfortunately, he phrased it in terms of
> "commutative hash functions", with g^X mod p as an example, so it's more
> general.

Given all the prior art, I have a solid suspicion that the patent
wouldn't hold up. The existance of the publically published Diffie
Hellman patent, for instance, makes it rather hard to patent the
more general case.

Perry

Reply-To: perry@imsi.com
   X-Reposting-Policy: redistribute only with permission
   Date: Wed, 26 Jul 1995 15:52:36 -0400
   From: "Perry E. Metzger" <perry@imsi.com>

   Given all the prior art, I have a solid suspicion that the patent
   wouldn't hold up. The existance of the publically published Diffie
   Hellman patent, for instance, makes it rather hard to patent the
   more general case.

   Perry

Does anyone know if that patent on distributed file systems that was
filed in '82 and granted sometime recently held up in court?

The last I heard the guy was going around collecting royalty payments
from large companies unwilling to go to court anyway.

Is this the sort of thing it's easier for a small company to challenge
than a big company?

Phil