Subject: Diffie-Hellman Choices

From: Russ Housley <[email-masked]>
Date: Fri, 02 Oct 1998 08:28:20 -0400

The S/MIME WG needs to select one mandatory to implement variant of
Diffie-Hellman.  This not presents the two alternatives that have
been proposed.  I would like the WG to discuss these alternatives
and then select the one that will be included in CMS.  Both
alternatives were presented at the face-to-face session in Chicago.

The criteria for selecting the most appropriate choice include security,
performance, and patents.

The two alternatives are both variants of X9.42, the ANSI Draft
Diffie-Hellman (D-H) standard.

Static-Static D-H is the first alternative.

Certicom has a pending patent that covers a check to avoid the small
subgroup attack.  Certicom has offered royalty-free lisence for CMS
and PKIX implemntations if this is chosen as the mandatory to implement
algorithm.

Static-Static D-H requires one exponentiation per recipient when
sending encrypted messages.

Static-Static D-H provides data origin authuthentication.  This
is due to the originator public key being contained in a
certificate.

Static-Static D-H would have a shorter certificate than the
Ephemeral-Static D-H alternative.

The originator certerficate is carried in message.  The public
key in the certificate is used by all recipients.

Static-Static D-H requires a common set of D-H parameters (p,q,g) for
the entire community.

Sample processing:

- Certificate contains Ya = ( g ** Xa ) mod p

- Originator certificate transferred in the header

- Originator generates random, R, that is transferred in
plaintext in the header

- Key = SHA1 [ ( g ** XaXb ) mod p || algorithm ID || counter
|| R ]

Ephemeral-Static D-H is the second alternative.

No patents known patents.  If there are any (including pending
patents), please make us aware of them now.

Ephemeral-Static D-H requires two exponentiations per recipient when
sending encrypted messages.

Ephemeral-Static D-H provides no authentication.  The originator
uses an ephemeral public/private key pair for each recipient, so there is
not originator certificate.

The recipient certificate must contain the D-H paramters (p,q,g), so
the certificate is longer than the Static-Static D-H alternative.

Neither the originator nor the recipient certificate is carried in
the message.

When generating the ephemeral public/private key pair, the originator
uses the recipient's D-H parmaters (p,q,g) obtained from the recipient
certificate.  Thus, the community does not need to agree on a common
set of D-H paramters (p,q,g).

Sample processing:

- No originator certificate; Recipient certificate contains Yb
= ( g ** Xb ) mod p

- Originator generates D-H key pair for each recipient, using
the recipient p,q,g values

- Originator Yr = ( g ** Xr ) mod p transferred in header for
each recipient

- Key = SHA1 [ ( g ** XrXb ) mod p || algorithm ID || counter
]

Which alternative do you prefer?  Why?

Russ

---

From: Dr Stephen Henson <[email-masked]>
Date: Fri, 02 Oct 1998 17:19:27 +0100

My thanks to Russ for presenting the two alternatives.

I would want the Ephemeral-Static D-H to be included. I'll abbreviate
this as ES and the alternative as SS.

Let me outline my reasons.

1. ES does not force authentication. With SS there is an implied
signature which would make such messages traceable: effectively forcing
the originator to sign everything. Personally I don't want to be forced
to sign everything I send. 

There was a requirement to add anon DH to the current CMS for this
reason. Jim Schaad wrote in a message on 28 May:

> At the December working group meeting, this was expressed as a desire from
> the S/MIME side of CMS.  People working for groups like Amnesty
> International wanted to be able to send anonymous mail which could not be
> traced back to them without having decrypted the message.
> 

2. SS requires a fixed set of parameters. What happens if, in future,
some weakness is found in the chosen common parameter set? This could
prove painful to modify.

3. As I understand it SS has some additional security concerns. In
particular the originator's private key needs to be accessed: this can
cause considerable problems for automated systems (e.g. encrypted
mailing lists). Systems which need to be restartable without the
operator entering a password may be forced to either store the private
key unencrypted, rely on fixed "security by obscurity" keys or use some
additional hardware. 

In ES all that is needed is the recipient's public keys. A one time key
pair is generated in each case but it is discarded after use. This does
not require access to any sensitive information and it is much more
secure in automated environments.

In the SS case if an attacker obtains the private key while the process
is taking place then all future messages involving the originator can be
decrypted. In the ES case only the one message can be read.

4. The ES properties are very similar to those of the RSA equivalent for
key transport, which many are more familiar with.

Steve.
-- 
Dr Stephen N. Henson. UK based freelance Cryptographic Consultant. 
For info see homepage at http://www.drh-consultancy.demon.co.uk/
Email: [email-masked]
PGP key: via homepage.