ietf-smime
[Top] [All Lists]

RE: FIPS 186 and X9.42: One of these things is not like the other

1999-11-22 09:06:04
John:

You have been out of the loop for over two years, and your observation are simply incorrect!

The people that have been working on the PKIX and S/MIME standards that refer to X9.42 have been given every version of the document as it became available to the X9F1 working group participants. And, X9F1 has worked to ensure that they did not change the parts of X9.42 that were adopted by the IETF.

Peter may not like the minor differences between X9.42 and DSA. But the IETF documents are aligned with the X9.42 (just as they claim). By the way, FIPS 186 contains no ASN.1; it only contains the algorithm specification.

Russ


At 01:17 AM 11/21/99 -0800, John C. Kennedy wrote:
(A long but hopefully illuminating follow-up regarding ANSI X9.42)

(**Summary: The use or referencing of the ANSI X9.42 (Diffie-Hellman) drafts
in IETF standards has resulted in the propagation of a number of errors and
inconsistencies within IETF drafts and RFCs.  IMHO, it is questionable
whether the still unratified ANSI X9.42 draft should be used as a basis or
even a reference for ongoing IETF Diffie-Hellman protocol standardization
work.)

Peter,

I was the editor of the ANSI X9.42 Diffie-Hellman draft up until about April
of 1997 when I changed employers and passed the X9.42 editing torch.  Since
my current work has given me a reason to wade back into the IETF process, I
wanted to share a few comments and provide some additional data on the
apparent state of Diffie-Hellman in IETF work.  As I revisit things 2.5
years later it seems to still be a bit of a mess in need of some tidying up.

(1) RFC 2459 (PKIX) references a December 1997 draft of ANSI X9.42.  I
believe this may be a draft that I "strategically distributed" to a few
select people working in IPSEC, PKIX, and other IETF working groups around
that time.  ANSI X9F has never had a lot of interest in seeing X9.42
reviewed or adopted by IETF.  [In fact, it is ridiculous that after almost
five years of work and innumerable rewrites, neither ANSI or NIST have
published an authoritative interoperability standard for one the most
fundamental and powerful public key techniques for key agreement we have.
(Hint: It is not because of patents or because it is too difficult to
communicate.)]

(2) RFC 2631 (Diffie-Hellman Key Agreement Method) references a 1998 draft
of X9.42.  This X9.42 draft is probably the one made available by ANSI to
IEEE P1363 members at
http://grouper.ieee.org/groups/1363/private/x9-42-10-02-98.doc (You will
need an IEEE P1363 password to get at this.)  This draft is better than the
1997 draft, but still has problems.  Since I have not been involved with
ANSI for about 3 years, I can't comment on where the X9.42 draft currently
stands.  Since the X9.42 draft document is (still!) not public, it is not
clear whether it is relevant to the IETF's work anyway.  RFC 2631 is
currently a proposed standard in IETF.  Since RFC 2631 propagates errors
that existed in the 1998 X9.42 draft, a second look at it is probably called
for. (These errors are noted below)

(3) RFC 2412 (OAKLEY Key Agreement) doesn't reference any Diffie-Hellman
standards.  While the techniques given in this document are mathematically
accurate and certainly filled a gap in the IPSEC work at the time, the
OAKLEY RFC doesn't quite provide all the pieces needed to link up with PKIX
and some other security standards.

(4) The following drafts contain relevant references to Diffie-Hellman or
related protocols.  The first two reference RFC 2631 and the second
specifies a new DH variant altogether:
draft-ietf-smime-small-subgroup-02.txt
draft-ietf-pkix-dhpop-02.txt
draft-ietf-secsh-transport-06.txt

(5) Both of the ANSI documents currently referenced were drafts and probably
weren't the best basis for IETF standards.  Given the lack of anything else
to point to, I can't say I blame the authors, however.  They certainly meant
well.  What is also unfortunate is that IETF community has not been provided
with access to more current X9.42 drafts.  This is, IMHO, probably related
to the situation I pointed out in (1).

Now, in reponse to your observations:

(6) RFC 2631 states "X9.42 requires that the private key x be in the
interval [2, (q - 2)]"
In other words, (1 < x < q-1).  **It is quite clear that the referenced
X9.42 draft is not only wrong but inconsistent**.  And in a number of
places.  The Diffie-Hellman private key x should be chosen in the closed
interval [2^(m-1), q-1], where m is the minimum length in bits acceptable
for the private key.  (Typically m>=160, but your mileage may vary...)  This
is consistent with security recommendations in the current IEEE P1363
documents as well as definitions in draft-ietf-smime-small-subgroup-02.txt,
draft-ietf-pkix-dhpop-02.txt.  (If there is a mathematical subtlety I have
forgotten and x should be in [2^(m-1), q-2], I hope someone speaks up to
correct me.)

Note that choosing x in [1, q-1] will work just fine mathematically, but
does not reflect or enforce the minimum key size requirement.  Note that if
the size of q is at least a few bit greater than m and you are using a good
RNG to pick x, the point is probably moot anyway.  If you are using a
long-term (aka "static") DH keys, however, it probably not a bad idea to put
the minimum keysize check in your keygen routine as a "belt and suspenders"
type measure.

(7) The domain parameter generation routines in X9.42 were in fact derived
from those in the FIP 186 spec to allow re-use of DSA parameters (p, q, and
g) with X9.42 if desired.  I can't say I am a big fan of this because it
forces q to 160 bits which is probably not appropriate if you intend to
enforce a minimum DH private key size greater than 160.

(8) The parameter order switch was not a deliberate booby trap, although
these types of things do help to keep crypto engineers on their toes. :)  As
I recall, the parameters q and j were added when concerns about small
subgroup attacks on Diffie-Hellman surfaced.  It is more of a coincidence
that the DSA algorithm exploits the use of a subgroup also defined by a
prime called q.  In other words, DSA included q from the beginning while
X9.42 added q as a security enhancement.  The ASN.1 encoding choices are an
artifact of the development process, not a deliberate reversal.  If you feel
like lobbying ANSI X9F to change the ordering to make everyone's life
easier, have at it.  I wouldn't hold my breath however. :)

(9) RFC 2459 (PKIX) shows ASN.1 encoding of the DH parameters as:
 DomainParameters ::= SEQUENCE {
              p       INTEGER, -- odd prime, p=jq +1
              g       INTEGER, -- generator, g
              q       INTEGER, -- factor of p-1
              j       INTEGER OPTIONAL, -- subgroup factor
              validationParms  ValidationParms OPTIONAL }

        ValidationParms ::= SEQUENCE {
              seed             BIT STRING,
              pgenCounter      INTEGER }

whereas the 1998 X9.42 draft shows them as:

DomainParameters ::= SEQUENCE {  -- Galois field group parameters
   p                INTEGER,        -- odd prime, p = jq + 1
   g                INTEGER,        -- generator, g
   q                INTEGER,        -- prime factor of p-1
   j                INTEGER,        -- subgroup factor, j >= 2
   validationParms  ValidationParms OPTIONAL
(**Note q is no longer optional.** JK)

if you can find a copy of the 1997 draft (which I happen to have) we see the
original version:

DomainParameters ::= SEQUENCE {  -- Galois field group parameters
   p                INTEGER,        -- odd prime, p = jq + 1
   g                INTEGER,        -- generator, g
   q                INTEGER OPTIONAL,        -- prime factor of p-1
   j                INTEGER OPTIONAL,        -- subgroup factor, j >= 2
   validationParms  ValidationParms OPTIONAL

(This early draft reflects my admitted ignorance of proper ASN.1 at the
time. You cannot have multiple optional INTEGERS without tags on them.)

My guess is that the middle version (i.e., with only ValidationParms
optional) is the preferred version, which means RFC 2459 should probably be
changed.  I do not know what the current X9.42 draft gives.

****Conclusion****
(10) Because of the aforementioned errors and inconsistencies, I have
serious reservations about the continued use or referencing of ANSI X9.42 in
IETF drafts or standards.  The use or referencing of the ANSI X9.42 draft in
IETF standards has resulted in the propagation of a number of errors and
inconsistencies within IETF drafts and RFCs.  IMHO, it is questionable
whether the apparently still unratified and possibly unstable ANSI X9.42
draft should be used as a basis or reference for ongoing IETF Diffie-Hellman
protocol standardization efforts.  Because of this, I respectfully submit
that the IETF should consider whether RFC 2631 should be deprecated and
rewritten in a manner which removes unnecessary references to the mysterious
and forever-unpublished ANSI X9.42 draft.


-John Kennedy
jkennedy(_at_)trustpoint(_dot_)com



-----Original Message-----
From: pgut001(_at_)cs(_dot_)auckland(_dot_)ac(_dot_)nz 
[mailto:pgut001(_at_)cs(_dot_)auckland(_dot_)ac(_dot_)nz]
Sent: Sunday, November 21, 1999 1:58 PM
To: ietf-pkix(_at_)imc(_dot_)org; ietf-smime(_at_)imc(_dot_)org
Subject: FIPS 186 and X9.42: One of these things is not like the other


FIPS 186/X9.30 and X9.42 (and by extension RFC 2631) share the same key
generation algorithm, and have domain parameters which look identical,
however
there are two subtle differences between them, one of which is really
annoying.

The annoying difference is that when writing the domain parameters, the
order
of q and g is reversed for FIPS 186 and X9.42 keys, so that while DSA domain
parameters are written (p, q, g), exactly the same domain parameters when
viewed as X9.42 values are written (p, g, q).  This isn't helped by the fact
that in many fonts lowercase q and g look very similar.  Apart from the fact
that it's a booby-trap for implementors, it also means that if the domain
parameters are identified in the traditional way (SHA-1 hash), identical
parameters will appear to be different depending on whether you're
interpreting
them as DSA/KEA or DH parameters.

The second difference is in the allowed range for x:

  FIPS 186: 0 < x < q (ie x = 1...q-1)
  X9.42: 1 < x <= q-2 in one place, [2...q-2] in another (ie x = 2..q-2)

This looks like a transcription error from FIPS 186, given that using any
x < ~2^160 is unsound I can't see why there'd be any difference between 1
and 2
as a lower bound.

Perhaps new RFC's which cover this (eg son-of-RFC2459) could include
warnings
to the effect that although the parameters are the same internally, their
external representations differ.

Does anyone know why X9.42 decided to reverse the parameter order?

(The motivation for this post is that ages ago I solved the problem of the
 reversed parameters by swapping the pointers for the X9.42 g and q values
so
 they were read and written in the correct order, recently I was looking
 through the code and wondered why it was working fine for both
interpretations
 of parameter ordering.  There's now a big comment block by the code
explaining
 the Bug which Isn't)

Peter.