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

Small subgroups and ISAKMP/Oakley



All,

David is right that this problem should be addressed in a DH standard.

In X9.42, the following checks are mandatory for an implementation:

1) Received public numbers are checked to insure that they are not equal to 1 or -1.
(note -1 = (p-1) mod p)

2) The shared-secret number Z=g(xy) mod p is checked to make sure that
(Z ^j)) mod p <> 1, where j=(p-1)/q.  I.e. j is the "co-factor" used to multiply q: p = jq+1.
Typically, j is fairly small so this is a quick operation to detect the small sub-group attack.

3) Finally, the generation of the prime modulus p may be optionally checked because X9.42 specifies a repeatable method for prime generation similar to that specified in the DSS standard.  Also, the order of the generator g may be check to make sure the order is q.

Since I haven't gotten around to the new and improved OAKLEY draft, I don't know how much of this is there or not.

During X9.42 development discussion it was not necessarily a man-in-the-middle that was feared with regards to the small sub-group attack.  Conceivably, one of the communicating parties could send a "bad" public number on purpose.  Is this a realistic scenario?  Whatever your opinion it makes since to do the relatively inexpensive checks outlined above.

Finally, with regards to elliptic curve DH I think it would be best to refer to the work being done by IEEE P1363.  You might want to consider deferring to P1363 for the GF(P) DH stuff too. ANSI X9.42 is much more application specific than the work in P1363.  (P1363 can be profiled into something X9.42 compliant however.) 

Also, the P1363 drafts are all freely-avaliable on-line and not as subject to US-centric interests. See http://stdsbbs.ieee.org/groups/1363/ .  IMHO, the P1363 work is the most comprehensive and up-to-date standards work on public-key technology available right now and deserves to be a primary reference for all IETF standards on crypto.  With regards to elliptic curve PK it is unparalled.

-John Kennedy

>>> "David P. Jablon" <dpj@world.std.com> 04/16/97 09:59AM >>>
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: