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

From: "Don Johnson" <[email-masked]>
Date: Mon, 22 Nov 1999 14:06:17 -0500

Russ,

Yes, the ASN.1 for X9.30 is/was in X9.57 Certificate Management, DSA was the
only public key ANSI X9 had at that time.
Don Johnson

Russ Housley <[email-masked]> on 11/22/99 01:50:56 PM

To:   Don Johnson/Certicom@Certicom
cc:   "John C. Kennedy" <[email-masked]>, [email-masked],
      [email-masked], [email-masked], [email-masked],
      [email-masked], [email-masked], [email-masked], [email-masked],
      [email-masked], Elaine Barker <[email-masked]>, Sharon
      Keller <[email-masked]>, Simon Blake-Wilson/Certicom@Certicom, "Phil
      Griffin" <[email-masked]>

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

Don:

At 09:36 AM 11/22/99 -0500, Don Johnson wrote:
>2. The order of the parameters in the domain parameters should be made
>consistent with X9.30 DSA, I think.  If this is not the way it is, it
>should be
>changed in X9.42.

I find no ASN.1 in X9.30 part 1.

Russ

---

From: "Don Johnson" <[email-masked]>
Date: Mon, 22 Nov 1999 15:17:00 -0500

John,

1. ANSI X9.42 is supposed to go shortly to final ballot.
2. Yes, it looks like the different orders of parms are now cast in concrete.
3. A duplicate private key can be detected by checking for a duplicate public
key, if this is a concern.  For example, if an ephemeral public key repeats,
then the forward secrecy property may fail.  But this is often handled as being
a event so rare it does not need to be checked.  If it is a concern, it can be
checked.
Don Johnson

"John C. Kennedy" <[email-masked]> on 11/22/99 03:08:47 PM

To:   Don Johnson/Certicom@Certicom
cc:   [email-masked], [email-masked], [email-masked],
      [email-masked], [email-masked], [email-masked],
      [email-masked], [email-masked], [email-masked],
      [email-masked], "Elaine Barker" <[email-masked]>,
      "Sharon Keller" <[email-masked]>, Simon Blake-Wilson/Certicom@Certicom,
      "Phil Griffin" <[email-masked]>

Don,

1. I truly hope it is ready for final ballot.  Many people have been
patiently waiting for it and respectfully referencing and including
placeholders in code and other standards in anticipation of it.  It is not
ANSI X9F1's responsibility to supply IETF with algorithm standards in a
timely fashion.  By the same token, IETF security working groups must be
vigilant to not delay important work by continuing to hitch its wagon to a
Diffie-Hellman draft that the ANSI committee continues to revise and which
is *still* not ratified.  My first post gave valid evidence of the results
of this decision thus far.

2. IMHO, the order of the parameters is irrelevant as long as they are
labeled and encoded correctly.

3. Is the private key now called 'd' instead of 'x'? <sigh>
As for the range of the private key, the checks to be performed during
generation should be unambiguous.  Whether or not the receiver of the
corresponding public number can verify that these checks were done is
somewhat meaningless.  For example, can the receiver tell whether or not
the sender's private number was generated with a robust PRNG that won't
repeat itself every tenth time it is accessed?

-John

-----Original Message-----
From: Don Johnson [mailto:[email-masked]]
Sent: Monday, November 22, 1999 6:36 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]; Elaine Barker; Sharon Keller; Simon
Blake-Wilson; Phil Griffin
Subject: RE: FIPS 186 and X9.42: One of these things is not like the
other

John,

A few comments on X9.42.
1. Elaine Barkey and Sharon Keller of NIST are the editors of ANSI X9.42.
I am
copying them on your note.  It should be ready for final ballot.
2. The order of the parameters in the domain parameters should be made
consistent with X9.30 DSA, I think.  If this is not the way it is, it
should be
changed in X9.42.
3. The private key d should be a value from 1 to q-1 in X9.42.  It is
allowed to
chop off the ends and make it 2 to q-2.  Any further reduction risks
reducing
the keysize and therefore aiding the adversary.  The reason that "low"
values
are allowed sometimes is that it is not known how to detect such a
situation.
In fact, if it were, then DH would unravel anyway.

Don Johnson

"John C. Kennedy" <[email-masked]> on 11/21/99 04:17:21 AM

To:   [email-masked], [email-masked], [email-masked],
      [email-masked]
cc:   [email-masked], [email-masked], Don
      Johnson/Certicom@Certicom, [email-masked], [email-masked],
      [email-masked], [email-masked]

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

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

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: [email-masked] (Peter Gutmann)
Date: Tue, 23 Nov 1999 11:39:10 (NZDT)

[Recipient list trimmed somewhat, I hope this is going to appropriate people]

Russ Housley <[email-masked]> writes:

>Both of these parameter structures are included in RFC 2459.  Concerns about
>alignment of the two structures should have been raised many months ago.
>
>While it might have been nice to have the two parameter definitions use the
>same order for p, q, and g, this is not a show stopper.  People have
>implemented with against the current specifications, and I am strongly
>opposed to changes at this late date.

I had the impression that for an outsider to influence ANSI standards was close
to impossible (if it wasn't for P1363 I'd never even have seen X9.42), which is
why I never commented on it.  Besides, I can't go around nitpicking *every*
standard around, there are only so many hours in the day :-).  That's why, in
my original message, I merely suggested that any new work which uses X9.42 and
FIPS 186/X9.30/whatever other standard it appears in point out that although
the keys look the same and quack the same, they have two of the parameters
(with names which look almost identical) reversed in the ASN.1 form.  This is a
trap just waiting to catch the unwary.

[Having said that, I'd certainly like to see the ASN.1 fixed so the two match
 up, but I guess that's unlikely to happen at this stage].

Peter.