Subject: [ietf-tls] PKCS #3 vs. ANSI X9.42 Diffie-Hellman in TLS

From: [email-masked]
Date: Tue, 13 Mar 2001 10:50:05 -0500

Hi everyone,

I am not sure if this issue has been discussed previously on the TLS mailing
list, but here it is.

While reviewing the suggested text to incorporate the TLS master key
derivation for Diffie-Hellman in the upcoming revision to PKCS #11 standard,
I have noted that it seems to refer to the PKCS #3 flavour of Diffie-Hellman
instead of the ANSI X9.42 flavour of Diffie-Hellman.  The major difference
with the ANSI X9.42 flavour of Diffie-Hellman is the fact that X9.42
Diffie-Hellman domain parameters similarly to DSA domain parameters MUST
also include the value of "q" for the subprime.

So I look further in RFC 2246 and noted that Section 7.4.2 indicates that
"All certificate profiles, key and cryptographic formats are defined by the
IETF PKIX working group [PKIX]" (i.e. RFC 2459).  RFC 2459 has since been
split into two Internet Drafts and PKIX algorithms are now specified in the
Internet Draft <draft-ietf-pkix-ipki-pkalgs-02.txt>, which specifies in
Section 2.3.3 that only the ANSI X9.42 flavour of Diffie-Hellman is
supported and not the PKCS #3 flavour.

However, I have also noted that the Server Key Exchange Message in Section
7.4.3 of RFC 2246 does not include the subprime "q" needed for the X9.42
Diffie-Hellman operations.  The subprime "q" would also be required for the
validation of domain parameters as specified in Sections 7.4.6, 7.4.7 and
A.5 of RFC 2246.

Does TLS mandate the ANSI X9.42 flavour of Diffie-Hellman or the PKCS #3
flavour of Diffie-Hellman?

If the ANSI X9.42 flavour of Diffie-Hellman is mandated, why is the subprime
"q" not included the Server Key Exchange Message in Section 7.4.3 of RFC
2246?

Cheers,

Francois
___________________________________
Francois Rousseau
Director of Standards and Conformance
Chrysalis-ITS
One Chrysalis Way
Ottawa, Ontario, CANADA, K2G 6P9
[email-masked]    Tel. (613) 723-5076 ext. 3419
http://www.chrysalis-its.com   Fax. (613) 723-5078

---
You are currently subscribed to ietf-tls as: [email-masked]
To unsubscribe send a blank email to [email-masked]

---

From: Eric Rescorla <[email-masked]>
Date: 13 Mar 2001 09:14:10 -0800

> flavour of Diffie-Hellman?
There are really two issues here:

(1) how the domain parameters and key are generated
(2) how ZZ is computed.

TLS is agnostic on how the domain parameters are generated, so they
may be of the form p=jq+1 or not. Obviously if they were of this form
you'd still only be able to send p and g, so the client wouldn't be
able to detect that the primes were of a special form.

X9.42 describes a large number of different algorithms for generating
ZZ. In at least one variant (the one documented in RFC 2631), q is not
used and ZZ=g^(XaXb) mod p. I don't have a current copy of X9.42 in
front of my so I can't tell you what they call it.) It's widely
understood that this is the algorithm used in TLS, though I admit that
the standard falls short of saying so.

The end result is that the server knows if his prime is of special
form but the client does not. Thus the server can use a private
key of order q but the client must use a private key of order p.

Cheers,
-Ekr

[Eric Rescorla                                   [email-masked]]
Author of "SSL and TLS: Designing and Building Secure Systems"
                  http://www.rtfm.com/

---

---

From: [email-masked]
Date: Tue, 13 Mar 2001 12:47:39 -0500

Hi Eric,

How can a ANSI X9.42 conformant client validate the server's ephemeral
Diffie-Hellman domain parameters if not all parameters are transmitted by
the server through the Server Key Exchange Message from Section 7.4.3 of RFC
2246?

Since as you have indicated below, the server can use a private key of order
q but the client must use a private key of order p, how can a ANSI X9.42
conformant server validate that the client's Diffie-Hellman public key if
the client did not use the same parameters to generate its public key?

Cheers,

Francois

-----Original Message-----
From: Eric Rescorla [mailto:[email-masked]]
Sent: Tuesday, March 13, 2001 12:14
To: IETF Transport Layer Security WG
Subject: [ietf-tls] Re: PKCS #3 vs. ANSI X9.42 Diffie-Hellman in TLS

Cheers,
-Ekr

---

---

From: Eric Rescorla <[email-masked]>
Date: 13 Mar 2001 15:33:14 -0800

> the server through the Server Key Exchange Message from Section 7.4.3 of RFC
They can't.

> the client did not use the same parameters to generate its public key?
They can't.

That said, when I last checked domain parameter validation was not required
by X9.42. On the other hand, if you're not going to check the parameters
AND you're not using ephemeral keys you need to follow the guidelines
in RFC 2785 for avoiding small subgroup attacks.

-Ekr

---

---

From: David Hopwood <[email-masked]>
Date: Wed, 14 Mar 2001 00:14:17 +0000

-----BEGIN PGP SIGNED MESSAGE-----

[email-masked] wrote:
> Diffie-Hellman domain parameters if not all parameters are transmitted
> by the server through the Server Key Exchange Message from Section 7.4.3
> of RFC 2246?

TLS clients and servers are not X9.42 conformant; the TLS key exchange
algorithm was designed independently of X9.42. Validation of either the
client or server's DH public value is not necessary in TLS, because
the server's public value is signed (either in the ServerKeyExchange message
for the DHE_{DSA,RSA} ciphersuites, or in the server's certificate for
DH_{DSA,RSA}), and the client's public value is also signed when client
auth is used. Therefore there is no attack involving changing these
public values, because that would be detected when the signatures are
verified (or when the Finished messages are checked, in the case of an
attacker changing an anonymous client's public value).

Validation of the server's long-term *signature* public key is possible
for the DHE_DSA ciphersuites, as is validation of the client's long-term
signature public key in a DSA client cert, but it isn't really necessary
for clients and servers to do this, because:

1. The CA should be doing it.
2. More importantly, it is not possible to obtain any information about
   the other party's long-term key by publishing an invalid signature
   public key (unlike the situation for static DH, which is the main
   reason why validation is required in X9.42).

> Since as you have indicated below, the server can use a private key
> of order q but the client must use a private key of order p, how can a
> ANSI X9.42 conformant server validate that the client's Diffie-Hellman
> public key if the client did not use the same parameters to generate
> its public key?

The client's private exponent will effectively be reduced mod q in this
case, which is harmless. There is no need for the client to know q, or
for the server to validate the client's public value. (Note that this
depends on the server not reusing private exponents, otherwise a
dishonest client would be able to perform a small subgroup attack of
the type described in [LimLee].)

In any case, the only applicable standard is TLS, not X9.42 or PKCS#3.
Unfortunately, the description of DH in RFC 2246 is not really adequate;
it should be described in much more detail when the RFC is next revised.

[LimLee] Chae Hoon Lim, Pil Joong Lee,
         "A Key Recovery Attack on Discrete Log-Based Schemes using a
          Prime Order Subgroup,"
         Advances in Cryptology - Crypto '97.

- -- 
David Hopwood <[email-masked]>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5  0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip

---

---

From: Eric Rescorla <[email-masked]>
Date: 13 Mar 2001 16:35:23 -0800

> the type described in [LimLee].)
An alternative to not reusing the private exponent is to make p
a Sophie-Germain prime.

-Ekr

---

---

From: David Hopwood <[email-masked]>
Date: Wed, 14 Mar 2001 00:24:16 +0000

-----BEGIN PGP SIGNED MESSAGE-----

>    reason why validation is required in X9.42).

I should have said "why validation is included in X9.42"; it isn't required.

> the type described in [LimLee].)

Also, the client should never reuse exponents between different servers.

- -- 

---

---

From: Dr S N Henson <[email-masked]>
Date: Wed, 14 Mar 2001 00:46:04 +0000

> An alternative to not reusing the private exponent is to make p

I was going to mention parameter selection myself. In a typical
scenario, due to the slow speed of parameter generation, a server will
reuse a set of precomputed parameters (for example loading them from a
file when the server starts). As such the various techniques of
parameter selection mentioned in RFC2785 and elsewhere for avoiding the
small subgroup attack will typically be performed.

Validating the client ephemeral public key (even if it was possible)
would be detrimental to server performance in any case.

Steve.
-- 
Dr Stephen N. Henson.   http://www.drh-consultancy.demon.co.uk/
Personal Email: [email-masked] 
Senior crypto engineer, Celo Communications: http://www.celocom.com/
Core developer of the   OpenSSL project: http://www.openssl.org/
Business Email: [email-masked] PGP key: via homepage.

---

---

From: David Hopwood <[email-masked]>
Date: Wed, 14 Mar 2001 00:33:20 +0000

-----BEGIN PGP SIGNED MESSAGE-----

> An alternative to not reusing the private exponent is to make p

Or, more efficiently, a Lim-Lee prime (2qr + 1 where r has no factors
smaller than q). I'm pretty sure this is OK for the ephemeral DH
ciphersuites, although I haven't looked at the static DH ones. Anyway,
make sure you understand small subgroup attacks thoroughly before
doing this.

Each exponent should still only be used for a limited time, of course,
to avoid degrading the forward secrecy property.

- -- 

---