[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Another pothole in ISAKMP/Oakley

Hilarie,

Regarding your comments on subgroup confinement ...

> If one is using new group mode, one might be advised to acquire some
> expertise in determining the size of largest subgroup.  One cannot
> simply pick a number at random and use it as a modulus.  Photuris had
> good practical advice on this score, and Oakley had a brief discussion
> of the problem, some words about Sophie-Germaine primes, Schnorr
> subgroups, etc.  But this is a piece of cake.  Solving the problem for
> elliptic curve groups is much harder.  That's why there are no new
> EC groups (it's not that they eat their young).

To clarify my concern, I am not referring to the problems with poorly-chosen
DH parameters, but rather to the subgroup attack on Diffie-Hellman
assuming the use of well-chosen parameters.  The attack is possible in
any ordinary DH groups as well as typical choices for EC groups.  Also, for
both ordinary and EC groups, the attack is easily prevented.

For any DH group where the order of the full group (m) is not prime,  DH
computations are restricted to a large subgroup of prime order (q), where q
divides m.  This leaves a co-factor t = m/q.  Small subgroups always exist in
Z_p*.  For Sophie-Germain primes, often called "safe-primes", where p = 2q+1,
the cofactor is 2.  Suitable elliptic curve groups also typically have a small
co-factor t, where t > 1.

A problem occurs when a man-in-the-middle forces each DH exponential into
a small subgroup, by raising each number to the power of q.  Both
legitimate parties
will derive the same key K, but it will be confined to one of "t" possible
values,
making it easy for the middleman to guess it.

Alice->Mary:  g^Ra	Mary->Bob:  (g^Ra)^q
Bob->Mary:  g^Rb	Mary->Alice:  (g^Rb)^q
K = g^(Ra Rb q q)

Two papers published last year describe these attacks, this one in a paper by
Wiener and vanOorschot, and a related attack relevant to authenticated-
Diffie-Hellman in a paper of mine.  The solution is to have each party make
sure
that the derived key K is in the proper subgroup, or at least not confined
to a
small subgroup.

One way to prevent the problem is to use K' = K^t, which "forces" K' 
into the group of order q, and then test to make sure that K' is not the
identity element.  Although discussion of this will be in the forthcoming
P1363 and X9.62 standards, given the current limited awareness of the
problem, I think this or some other solution or specific reference to a
solution
should be included in all standards that specify a DH exchange.

-- David
Follow-Ups: References: