Subject: Re: Diffie-Hellman Choices

From: [email-masked] (John Pawling)
Date: Fri, 2 Oct 1998 13:10:47 -0400

All,

I believe that the group should choose the Ephemeral-Static D-H algorithm as
the "mandatory-to-implement" key management algorithm to be included in CMS
for the following reasons:

1) I believe that if a user requires the security service of data origin
authentication, then the user should digitally sign the data and encapsulate
the signed data within a signedData object.  I don't believe that the data
origin authentication service needs to be provided by the key management
algorithm.  Therefore, I do not object to the fact that the E-S D-H
algorithm does not provide the data origin authentication service.  

2) Many organizations levy a requirement that each X.509 certificate must be
validated before the public key contained within that certificate is used
for cryptographic processing.  In the case of the S-S D-H algorithm, the
originator's D-H public key is conveyed in an X.509 certificate contained in
the envelopedData heading.  Many organizations will require that the
originator's D-H X.509 certificate must be validated before the originator's
D-H public key is used to form the pairwise key required to decrypt the
message encryption key.  This implies that the originator's entire
certification path must be validated.  Therefore, I believe that the E-S D-H
algorithm's use of an ephemeral originator's public key is a significant
advantage because there is not an originator's D-H X.509 certificate to be
validated.  This will save a significant amount of time during the
decryption process.

3) As Russ points out, the S-S D-H algorithm restricts an originator from
forming a pairwise key with a user whose public key is formed using
different p/q/g parameters.  The E-S D-H algorithm allows a user to form a
pairwise key with any user's D-H public key regardless of the p/q/g values.
I believe that this is a signifignat advantage of E-S D-H over S-S D-H.

4) There are no known patents or pending patents that apply to the E-S D-H.
I believe that this is a significant advantage of the E-S D-H option over
the S-S D-H option.

5) At the present time, Certicom states that they will offer a royalty-free
license covering S-S D-H.  What happens if they change their mind and stop
issuing such licsences?  Has Certicom completed the royalty-free license
offer?  How long will it take for Certicom to do so?  In summary, I believe
that we should avoid the "license path" if at all possible.

======================================================
John Pawling                         [email-masked]

J.G. Van Dyke & Associates, Inc.     www.jgvandyke.com       
======================================================

---

From: "Jim Schaad (Exchange)" <[email-masked]>
Date: Sat, 3 Oct 1998 21:49:55 -0700

I strongly vote for the ES version of D-H.  The benefits of not having to
define fixed groups (especially the really small ones needed for dealing
with import/export restrictions of some governments) combined with the
anonymous behavior of ES is just overwhelming.
 
Jim Schaad

-----Original Message-----
From: Russ Housley [mailto:[email-masked]]
Sent: Friday, October 02, 1998 5:28 AM
To: [email-masked]
Subject: Diffie-Hellman Choices

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: Russ Housley <[email-masked]>
Date: Mon, 19 Oct 1998 09:47:30 -0400

S/MIME Working Group:

The Concensus is clear.  We will proceed with Ephemeral-Static Diffie-Hellman.

Russ