Subject: Some comments on the use of DH in S/MIME

From: [email-masked] (Peter Gutmann)
Date: Mon, 21 Dec 1998 19:51:31 (NZDT)

Well OK, a bit of a rant rather than just comments...
 
I've had a go at implementing this, and after stuffing around with it for 
awhile I've come to the conclusion that this option must have been designed by 
RSADSI to make the alternative of getting a patent license to use 
KeyTransRecipientInfo look good[0].  What a mess!  Consider the most obvious 
use for DH keying material, which is to use it in Elgamal as per the existing 
KeyTransRecipientInfo and RFC TBA, the X.509 profile for Elgamal.  All it 
takes is a few lines of code to use it with existing mechanisms.
 
Now let's look at the way it's applied here.  A rough outline of what's 
contained in KeyAgreeRecipientInfo is:
 
  originatorDH  -- Originators DH values p, g, y = g^x mod p
  recipientDH   -- Recipients fixed DH values p, g, y' = g^x' mod p
  nonce         -- Extra material to mix in to ensure different keys are 
                   produced
 
First of all, both sender and recipient need to somehow agree on using the 
same p and g values, which means either everyone shares the same values 
(presumably these will be ones for which the NSA et al have performed the 
necessary precomputations to make solving the DLP easier), or alternatively 
you need to get a new certificate for each users values (OK, looks like 
Verisign were in on designing this thing as well).  As a result you either end 
up with a solution which is of questionable security due to use and re-use of 
widely-shared public values, or which is extremely expensive and practically 
impossible to manage because you need to have a certified DH public key 
corresponding to each recipients DH key (CMS tries to kludge around this by 
requiring the use of originatorKey, an uncertified, unauthenticated DH public 
value).
 
Anyway, moving past this, you either have a DH static key (inexpensive but 
insecure due to reuse), a DH ephemeral key (expensive since you need a new 
cert issued for each key), or the abovementioned unauthenticated DH public 
value (again, CMS explicitly requires the use of a static key for the 
recipient).  Since the DH exchange with fixed parameters always produces the 
same output, you also need to mix in extra keying material in a further kludge 
to try and shoehorn straight DH into functioning as a form of key transport 
mechanism.
                "To walk right past the correct solution and come up with this 
                 takes some beating" 
                        - Comment from someone who reviewed this rant
 
I realise there's probably some sort of motivation to try and do something 
with X9.42, but do we really have to jump off a cliff just because X9.42 does 
as well?  
                "Just because it's possible to push a pea up a mountain with 
                 your nose doesn't mean that this is a good way of getting it 
                 there"
                        - Chris Strachey
 
Why not just change the requirements to:
 
  "Implementations MUST support key transport using Elgamal.  Implementations 
   MAYM[1] include key agreement using X9.42 Ephemeral-Static Diffie Hellman".
 
This provides a straightforward nonpatented alternative to RSA which uses DH 
keys just as KeyTransRecipientInfo does (so it's possible to claim compliance 
to X9.42 or reference it in the spec or include it in the product advertising 
or whatever the rationale for working with it is) while still having something 
which is practical and simple to implement.
 
Peter (and I made it right through that without including the "looks like the 
       winning candidate from a 'Worst way to apply DH to a key management 
       problem' competition" comment :-).
 
[0] This is satire folks, not intended as a slight on RSADSI.
[1] "MAY if the implementors are Masochists".  An alternative is MAYEURKW, 
    "MAY if they Enjoy Unnecessary Root Canal Work".

---

From: EKR <[email-masked]>
Date: 21 Dec 1998 07:17:05 -0800

> Well OK, a bit of a rant rather than just comments...
Peter, I'm having a lot of trouble understanding what you're
actually complaining about here. I've done a lot of trimming
to separate out the actual comments from the ranting, but
if I've overtrimmed, feel free to restore the relevant
material.

>  nonce         -- Extra material to mix in to ensure different keys are 
This is incorrect. Here's the ASN.1 for reference:

      KeyAgreeRecipientInfo ::= SEQUENCE {
        version CMSVersion,  -- always set to 3
        originator [0] EXPLICIT OriginatorIdentifierOrKey,
        ukm [1] EXPLICIT UserKeyingMaterial OPTIONAL,
        keyEncryptionAlgorithm KeyEncryptionAlgorithmIdentifier,
        recipientEncryptedKeys RecipientEncryptedKeys }

      RecipientEncryptedKey ::= SEQUENCE {
        rid KeyAgreeRecipientIdentifier,
        encryptedKey EncryptedKey }

      KeyAgreeRecipientIdentifier ::= CHOICE {
        issuerAndSerialNumber IssuerAndSerialNumber,
        rKeyId [0] IMPLICIT RecipientKeyIdentifier }

The originator's information consists of the originator's public
key (y) only.
The recipient's information is a pointer to the recipient's certificate
indicated by issuerserial or by keyid. At no time is the recipient's
keying material explicitly in the message. In point of fact, this
same ASN.1 type RecipientIdentifier, is pointed to by 
KeyTransRecipientInfo.

The ukm is indeed a nonce intended to differentiate keys generated
by the same DH originator-recipient pairs.

> As a result you either end 
This is the expected mode of operation. Whether it's a kludge or not
is a matter of opinion, I suppose.

> cert issued for each key),
> or the abovementioned unauthenticated DH public 
> value 
It was never intended that you would have a certified public key for
each recipient's DH key if a large number of groups were in use. The
only two reasonable options are Static-Static with a few (1?) groups
(presumably in a closed community) and Ephemeral-Static.  

I don't agree with your characterization that a DH static key is
'insecure due to reuse'. While it's true that a common group makes
common group, because fewer computations are required to actually send
a message, the group can be substantially larger while still retaining
good performance. However, it's not reuse that's the problem here.
Provided that you use pubInfo (and you MUST if you reuse keys),
it's fine to have a static key.

>(again, CMS explicitly requires the use of a static key for the 
> recipient). 
Of course it does; it's in his certificate. This would be a requirement
with ElGamal as well. The point here is that you have 1 static key
which you use to receive messsages and that you generate a new
ephemeral key for each group every time you send a message,
just as you would with ElGamal. [0]

Perhaps it would be a useful exercise to review ES-DH (the required
mode) and ElGamal side by side, from the Originator's perspective:
Assume that the receiver's key is Yr and the group is g,q,p.
ES-DH                                  ElGamal
1. Generate random Xo.                 1. Generate random Xo.
2. Y=g^Xo mod p.                       2. Compute Y=g^Xo mod p.
3. ZZ=Yr^Xo mod p.                     3. ZZ=Yr^Xo mod p
4. KEK=H(ZZ,...)                       4. PM=Pad M to fit in p.
5. Wrapped Key=3DES(KEK,MEK || H(MEK)) 5. Wrapped key = PM * ZZ
6. Send Y,Wrapped Key                  6. Send Y,wrapped Key

So, in point of fact, the only difference between ElGamal and and
ES-DH is how you wrap the DH key (steps 4,5), and I don't think that
this particularly favors ElGamal, either in terms of security of
implementation complexity. I don't specify step 4 of ElGamal above,
but it SHOULD be OAEP, in which case it's certainly not any simpler
than the X9.42 key expansion transform. The CMS wrapping algorithm
(step 5) is a little tricky, but not overly so.

So, you might ask, given that these schemes are so similar, why favor
X9.42?

Basically, it's more flexible. In particular, its best case behavior
is much faster.

As noted above, it can be run in a Static-Static mode which requires
half as many modular exponentiations as either ElGamal or ES, and also
provides Data Origin Authentication. If you cache ZZ, the number of
exponentiations per message drops to zero (a la SKIP). Also, of
course, in a closed community, you can arrange to hardwire the group
and thus reduce the certificate size substantially.

Moreover, because of the pubInfo input to the key expansion, even the
ES mode can optimized by caching the generated ephemeral keys, with
the consequence that repeated transactions with the same party can be
very fast. [1]

I don't know of any balancing technical advantages to ElGamal.
        
So, exactly what features of the current X9.42 draft are you
complaining about? Your message implies that the problem is
implementation complexity, but I don't see where that complexity is
supposed to lie.

On the other hand, if your problem is a matter of taste, de gustibus
non est disputandum.

-Ekr

[0] I suppose you could have an ephemeral recipient key as well, but
you wouldn't explicitly place it in the message, you'd merely refer to
it by KeyId (or not at all, if it was somehow externally specified.)
In any case, the syntax allows this case, if somewhat implicitly. It
may be banned in the document text somewhere.

[1] It's possible that you could perform this optimization with
ElGamal, provided that your padding function was sufficiently
strong. Anyone know?

-- 
[Eric Rescorla                                   [email-masked]]

---

From: EKR <[email-masked]>
Date: 21 Dec 1998 09:03:48 -0800

EKR <[email-masked]> writes:
> good performance.
Ooops. This should read:

I don't agree with your characterization that a DH static key is
'insecure due to reuse'.  While it's true that a common group makes an
attractive target, because fewer computations are required to actually
send a message, the group can be substantially larger while still
retaining good performance.

-Ekr