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

From: [email-masked] (Peter Gutmann)
Date: Wed, 23 Dec 1998 23:54:16 (NZDT)

>>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
 
>This is incorrect. Here's the ASN.1 for reference:
 
I'd abstracted it down to what was actually being processed for
KeyAgreeRecipientInfo, for the ASN.1 I assumed most people on the list would
already have a copy of the S/MIME spec so I didn't copy it all out.
 
>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
 
This obscures a great amount of detail in the ES-DH case.  To really compare 
the level of complexity, let's assume that you have an underlying 
implementation which does (or can do) either DH or Elgamal as a primitive 
operation (it's a dozen or so lines of code using any common bignum library).  
Let's assume in addition that you have at least S/MIME v2 implemented (so you 
have code to wrap and unwrap data, handle the older types like 
KeyTransRecipientInfo, etc etc).  I assume this is valid for pretty much 
anyone on the list who has an implementation.
 
In order to implement key transport using a DH key as Elgamal, the overall 
change to the code is:
 
  switch( algorithmType )
      ...
      case Elgamal:
         elgamalEncrypt( ... );
 
alongside the existing case of RSA in the code which handles 
KeyTransRecipientInfo (it's somewhat implementation-dependent, for example in 
mine there's no overhead at all because Elgamal is automatically available for 
use where appropriate).
 
In contrast to implement key transport (agreement) using a DH key as ES-DH 
key, you need to implement a completely new RecipientInfo type with associated 
processing, and large amounts of X9.42 with the associated increase in 
complexity and virtually guaranteed interoperability problems between 
implementations.
 
>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.
 
See above.  For DH as Elgamal you typically need to add one more case 
statement to your KeyTransRecipientInfo code, while for DH as DH-ES you need 
to implement and somehow make interoperable an entirely new RecipientInfo type 
with associated complexity from X9.42.  Adding a single new algorithm type to 
KeyTransRecipientInfo is vastly less complex than adding a whole new 
RecipientInfo type, and when they're providing exactly the same service I 
really don't see why ES-DH should be the way to go (thus the "pushing a pea up 
a mountain with your nose" quote in the previous message).
 
>On the other hand, if your problem is a matter of taste, de gustibus non est
>disputandum.
 
Yeah?  Well mater tua caligas gerit!  (That's more in tone with a rant :-).
 
Peter.

---

From: EKR <[email-masked]>
Date: 23 Dec 1998 10:20:15 -0800

> already have a copy of the S/MIME spec so I didn't copy it all out.
Peter, my complaint is that you DIDN'T abstract it down. Your 
text implies that p,q,g, are carried in the message. They are not. 
Neither is y'. The text that you snipped makes this clear. I supplied
the ASN.1 merely as background for my comments.

> operation (it's a dozen or so lines of code using any common bignum library).  
No more so than in the ElGamal case. The ElGamal bignum primitves
are indeed simple, as are the DH ones. The implementation trickiness
is in the symmetric wrapping stages. To correctly use ElGamal, you
should use OAEP, which is not widely implemented. Similarly, X9.42
requires the expansion and key wrapping transforms. I consider these
of approximately similar complexity, as I indicated in my 
previous message.

> complexity and virtually guaranteed interoperability problems between 
I agree that there is some additional implementation complexity in
managing the new ASN.1 types. I don't consider it that substantial.
Moreover, once we've taken this one-time hit, we are able to use a 
broader class of algorithms than before. (A number of elliptic curve
algorithms come to mind.)

> a mountain with your nose" quote in the previous message).
Asked and answered. It's better, for technical reasons which I laid out
in my previous message. 

-Ekr

-- 
[Eric Rescorla                                   [email-masked]]