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

From: [email-masked] (Peter Gutmann)
Date: Sun, 21 Nov 1999 13:58:14 (NZDT)

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.

---

From: "John C. Kennedy" <[email-masked]>
Date: Sun, 21 Nov 1999 01:17:21 -0800

(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
[email-masked]

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
Sent: Sunday, November 21, 1999 1:58 PM
To: [email-masked]; [email-masked]
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.

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.

(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.

---

From: Ben Laurie <[email-masked]>
Date: Sun, 21 Nov 1999 10:44:17 +0000

>               validationParms  ValidationParms OPTIONAL }

I was perusing the OpenSSL DH code recently, and I noticed that DH was
using a Germain prime for p (miscommented as a strong prime, btw),
which, of course, makes j=2. But q and j are not kept - what are they
actually used for? (Answers in the form "read XXX" are welcome)

BTW, why the redundancy? If you have any two of p, j and q, you don't
need the other, and surely the work involved to recover the third one is
minimal in comparison to anything else you'd need to do, sumswise?

Cheers,

Ben.

--
http://www.apache-ssl.org/ben.html

"My grandfather once told me that there are two kinds of people: those
who work and those who take the credit. He told me to try to be in the
first group; there was less competition there."
     - Indira Gandhi

---

From: "John C. Kennedy" <[email-masked]>
Date: Sun, 21 Nov 1999 13:43:23 -0800

As I recall, I argued the same point and lost.  I believe the prevailing
argument was that including both j and q saved a parameter validator the
cost of doing a division to derive the other value.  If j=2, the most common
case, the division is simply a right-shift, and the argument is moot.  If
you are using a q of 160 and j>>2, say in the case where DSA parameters are
being overloaded for use as DH parameters, the p/q calculation is more
expensive.  If you are doing the calculation on a memory/CPU limited smart
card the inclusion of p,q,j may be useful.

The values q and j are made available for verification of domain parameters
and for guiding selection of appropriately sized private keys.

-John
[email-masked]

-----Original Message-----
From: Ben Laurie [mailto:[email-masked]]
Sent: Sunday, November 21, 1999 2:44 AM
To: John C. Kennedy
Cc: [email-masked]; [email-masked]; [email-masked];
[email-masked]; [email-masked]; [email-masked];
[email-masked]; [email-masked]; [email-masked]; [email-masked];
[email-masked]
Subject: Re: FIPS 186 and X9.42: One of these things is not like the
other

Cheers,

Ben.

---

From: Russ Housley <[email-masked]>
Date: Mon, 22 Nov 1999 11:00:16 -0500

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

---

From: "John C. Kennedy" <[email-masked]>
Date: Mon, 22 Nov 1999 12:57:13 -0800

Russ,

1. With all due respect, saying that I have been "out of the loop" is not
quite correct.  I have continued to track the output of both X9F1 and IETF
with regards to X9.42 and DH for the last couple of years. I have copies
of X9.42 drafts up through February 1999.  One does not have to be "in the
loop" to see the inconsistencies I have pointed out.

2. The PKIX "son-of-2459" work, of which mostly only the ASN.1 portion of
X9.42 is relevant, is probably correct.  What is a bigger problem is that
RFC 2631 (Diffie-Hellman Key Agreement Method) by Eric Rescorla references
a 1998 draft. The related drafts, <draft-ietf-smime-small-subgroup-02.txt>
and <draft-ietf-pkix-dhpop-02.txt>, reference RFC 2631.  Is there proper
alignment in these works with the current state of X9.42?  I don't think
so.  How would the larger IETF community know if they were?  Is ANSI
keeping all these authors "in the loop"?

3. FIPS 186-1 on DSA and rDSA is a good example.  If the X9.42
specification had been kept as simple as FIPS 186 we wouldn't be where we
are now.  It is unfortunate that crypto-politics and other machinations
did not allow NIST to handle this work independent of ANSI from the
beginning.

-John
[email-masked]

> From: Russ Housley [mailto:[email-masked]]