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

From: [email-masked] (Peter Gutmann)
Date: Thu, 24 Dec 1998 20:43:55 (NZDT)

>The same sorts of issues that have been raised with respect to PKCS-1 in RSA
>are worth worrying about with ElGamal. In particular see the Bleichenbacher
>attack. I don't know that these attacks are feasible for ElGamal, but I'd
>rather not take chances.
 
I don't have Bleichenbachers paper in front of me right now but as I recall it
applied only to Elgamal *signatures* (the title is a sure giveaway, it was
something like "How to generate Elgamal signatures without knowing the key").
Since we're talking about key transport, the attack isn't even relevant.  In
any case it's trivial to protect against, all you need to do is make sure that
g != 2 (or any other small, smooth divisor of p-1).  I don't know of anything
which does use Elgamal signatures except in their DSA variant (as Anderson and
Vaudenay put it in their analysis of DSA, "DSA is Elgamal with the bugs
fixed").  Given that fact, and that there's a well-established standard for
DSA, I can't see any incentive to use Elgamal signatures.  In any case, we were
debating key transport/agreement, not signatures.
 
>As I said previously, I agree that there is additional implementation
>complexity in parsing te new ASN.1 structs, but the CRYPTO implementation cost
>is fairly similar. In particular, OAEP and the X9.42 expansion/wrapping
>transforms are of comparable cost. I stand by this statement.
 
I agree with you 100%.  If you use OAEP then they're probably of roughly
similar complexity.
 
Since there's no need to use OAEP, it's also obvious that DH as Elgamal is
vastly simpler than DH as ES-DH.  QED.
 
>2. I don't believe you are correct about the security problems. What precisely
>do you believe the problem is with reusing the sender's key with ES-DH
>provided that you use a new pubInfo for each message? I agree that there is a
>security issue wrt to a shared group for SS mode, and that's why it's
>optional.
 
I was referring to Static-Static, cached (ie reused) cryptovariables, etc etc:
 
  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).
 
>I think you're overstating the amount of implementation complexity. I estimate
>it as being no more than a day or two's work.
 
Have you actually tried it?  It's a lot more than a day or two's work, and as
I've mentioned before once you've got it all going there's no guarantee,
because of the complexity, that your version will interoperate with anyone
elses version.
 
Just as a data point, in the implementation I have the use of Elgamal for key
transport actually required zero time, it's a heavily object-oriented design so
throwing an Elgamal object at key transport works just as well as throwing an
RSA object at it.  At the moment I've actually had to put in special code to
disable Elgamal for key transport, so I guess you could say it'd take a
negative amount of code to implement because I'd have to delete the code which
disables it.  That's got to be fairly conclusive proof that the implementation
overhead is minimal.
 
Peter.

---

From: EKR <[email-masked]>
Date: 24 Dec 1998 14:30:25 -0800

> something like "How to generate Elgamal signatures without knowing the key").
I'm referring to the Bleichenbacher attack on RSA key transport,
aka the "Million Message Attack." I don't believe it's known that this cannot
be extended to ElGamal. I prefer not to take chances.

> vastly simpler than DH as ES-DH.  QED.
I'm not convinced that there's no need to use OAEP. As Mihir Bellare
is fond of pointing out, when you're designing new protocols, it's good
to protect against attacks you don't know about as well as attacks
you do. Hence a provably secure padding algorithm seems like a good
choice.

>   message drops to zero (a la SKIP).
Fair enough. However, there are caching optimizations available when you
use ES-DH as well that do not have the problems of SS. Moreover, as
I originally indicated, SS can be used safely, you just have to choose
a larger group.

> Have you actually tried it?
Not yet. It's my estimate based on triangulating between the effort
to do DH in SSL and the original effort to do PKCS-7 with RSA. 

>  It's a lot more than a day or two's work, and as
Yes, but we expect to publish examples, so I'm not really that concerned
about this issue. 

> disables it.  That's got to be fairly conclusive proof that the implementation
I didn't say the ElGamal overhead wasn't minimal. I said that I didn't
consider the DH overhead prohibitive. Implementation complexity is
always a concern, but it's not the only concern.

-Ekr
-- 
[Eric Rescorla                                   [email-masked]]