[1130] in cryptography@c2.net mail archive
SPEKE with selected modulus
daemon@ATHENA.MIT.EDU (David P. Jablon)
Tue Jul 1 12:30:21 1997
Date: Tue, 01 Jul 1997 10:26:12 -0400
To: coderpunks@toad.com, cryptography@c2.net
From: "David P. Jablon" <dpj@world.std.com>
Here's a proposed variant of password-authenticated key
exchange, with modifications in light of several concerns raised
by about an earlier version. It incorporates a form of SPEKE
exchange with a password-selected modulus.
It's also sort of a collaborative Internet work-in-progress.
A primary goal is to increase the difficulty of an
eavesdropper brute-force attack on a (suspected)
low-entropy shared secret S, as compared to a standard
challenge/response method, without relying on additional keys.
Another goal is to reduce the amount of large integer arithmetic,
as compared to an ordinary SPEKE or DH-EKE exchange.
The essential idea is to combine a standard challenge/response
password hash method with a small Diffie-Hellman exchange.
Here the DH modulus is a Germain prime, based on a hash
of S, but smaller than is typical for Diffie-Hellman.
The DH base is also selected as a hash of S.
The proof of S is a combined hash of the classical
form, h(r, S), plus the negotiated DH key K -- that is,
h(h(r, S), K).
The method
----------
Let S = a low-entropy secret shared by Alice and Bob.
Alice chooses p, an n-bit prime modulus based on S as follows:
Pmax = 2^n, Pmin = Pmax - 2^(n-16)
Pmax > p > Pmin (the high 16-bits of p all 1s)
p = 2q+1, for a prime q.
The low bits of q are chosen based on an iterative
search for the first suitable value >= (n-15) bits
from SHA1("p", S).
Alice chooses g, as follows:
g is a primitive root of p.
g is chosen by using an iterative search starting
with n bits of SHA1("g", S).
Bob stores {"Alice", g, p} secretly as the verifier.
Alice performs the calculation of p and g before login,
to avoid needing secure long-term storage.
Alice proves knowledge of S to Bob as follows.
Alice->Bob: "Alice"
Bob looks up g and p based on "Alice".
Bob chooses random numbers Rb < 2^n and Rc < 2^160.
Bob computes Qb = g^Rb mod p.
If Qb >= Pmin, he tries again with another Rb.
Bob->Alice: Rc, Qb
Alice aborts if Qb >= Pmin, or if Qb < 2.
Alice chooses random Ra < 2^n and computes:
Qa = g^Ra mod p
K = Qb^Ra mod p
V = SHA1(SHA1(Rc, p), K)
Alice->Bob: Qa, V
Bob aborts if Qa >= Pmin, or if Qa < 2.
Bob computes:
K' = Qa^Rb mod p
V' = SHA1(SHA1(Rc, p), K')
Bob compares V to V', and if they match,
he knows that Alice knows S.
Analysis and concerns
---------------------
1) Setting several high bits of p insures that the values of
Qa and Qb do not leak significant information about p.
2) Since the calculation of p for large n is slow, we are motivated
to use a small n. However, the slow calculation only
affects Alice, as Bob need not compute either p or g.
3) A subtle property distinguishes this method from
ordinary SPEKE or DH-EKE. The cost of eavesdropper
attack seems to be the product of the entropy of the
password-space and the cost of the discrete log computation
for the n-bit modulus. However, this comes at a price.
This method doesn't seem practical when scaled to the
full strength of SPEKE using a large group.
4) A timing attack would be possible if one can test how
long it takes Alice to compute p and g. This can be easily
avoided. One way is to avoid using the small subset of
potential passwords that require more than a certain
threshhold of time to compute.
5) An earlier version used a fixed g = 2, but Lewis
McCarthy noted that when Bob sends an unreduced
power of g as Qb, this permitted a dictionary attack
after a single bad exchange. This problem is fixed here by
choosing g as a function of S, forcing each party
to fully "commit" to a specific choice for S in their
calculation of Qa or Qb. An alternate cure may be to
use a fixed g, and abort if an (unreduced) power of 2 is
received.
6) It seems doubtful that Qb > Pmin is a threat, and if we're
convinced of this, we can omit Bob's check, and just make Alice
insure that Qb < Pmax.
7) Worst case: Even if most of our analysis is wrong, or if
discrete log somehow turns out to be cheaper than
a run of the protocol, we still are left with a method that's
at least as strong as the challenge/response we're trying to replace.
The benefit
-----------
The DH exchange here multiplies the work factor for
eavesdropper attack. In classic challenge/response,
each eavesdropper guess requires (by definition) the
same effort as an run of the protocol, which has to be small to
make the protocol tolerable. By introducing the
small DH exchange, each guess here requires solving
a small discrete log problem, which we presume
takes significantly longer than a single run of the protocol.
------------------------------------
David Jablon
web: http://world.std.com/~dpj/
email: dpj@world.std.com
