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

From: [email-masked] (Peter Gutmann)
Date: Fri, 25 Dec 1998 21:32:54 (NZDT)

>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.
 
For those of you who have been sitting on the sidelines watching the messages 
whooshing past overhead, it looks like we were talking about two different 
"Bleichenbacher attacks" in the last few messages.  The one I was thinking 
about was from 1996, applies only to Elgamal signatures (not encryption), and 
even then only works if a badly chosen key is used.  This attack doesn't apply 
to Elgamal key wrapping.
 
The one Eric was thinking of was from 1998.  In order to work for the Elgamal 
key wrapping I've proposed for CMS, this attack requires that an attacker send 
you around a million pieces of CMS encrypted email with attached receipt 
requests, that you respond with a million receipts indicating to the attacker 
the exact details of why the decrypt failed, that you reuse the same 
per-message key for each of those million messages, and that you (rather than 
the attacker) know this per-message key.
 
Now maybe I'm being a bit optimistic here, but I do think that claiming this 
is a weakness is a pretty silly.  First of all you need to assume that an 
attacker can somehow send you a million pieces of email without you noticing 
and without it getting stopped by spam blockers.  Your own software then has 
to try to decrypt each of the one million pieces of email, find that it can't, 
and send out a receipt to the sender containing an indication of exactly how 
the decryption failed (this isn't possible even if you wanted to do it, 
although who knows what the Receipt Notification WG have been working on 
recently).  Finally, the whole attack only works if you reuse cryptovariables 
- it would work nicely if you use something like the ES-DH cached values which 
Eric mentioned in a previous message, but not against Elgamal key wrapping.  
This is why the CERT advisory on this problem specifically points out "This 
vulnerability does not affect S/MIME or SET".
 
As a security threat, I'd say this rates somewhere down with "Router hit by 
meteorite", "Computer trampled by stampeding water buffalo", "Hard drive 
kidnapped by space aliens", and similar FUD.
 
#include <previous stuff about DH as Elgamal being better than DH as ES-DH>
 
Peter.

---

From: EKR <[email-masked]>
Date: 29 Dec 1998 23:27:53 -0800

> vulnerability does not affect S/MIME or SET".
I believe you've misunderstood the attack. It is indeed a problem
for CMS (though likely not for S/MIME). Let's deal with the RSA case
for a second:
The purpose of the attack is to recover the MEK given a wrapped MEK
in a known public key.
The attack depends on the attacker being able to differentiate a 
message which when decrypted yields an badly formatted (in the PKCS-1)
sense message from a message which is correctly formatted but
(presumably) yields a bad message encryption key. 

Remember, PKCS-1 padding is 00 02 [random nonzero bytes] 00 MEK

So, if the attacker can determine whether a candidate message decryptes
to 00 02  <garbage> or XX XX <garbage> where XX XX is something other
than 00 02, he is able to mount this attack. When I say determine,
what I mean is that he can get the recipient to tell him.

So, the attacker takes message M with a wrapped MEK (W) off the wire and
generates a new message M' with a modified W (W') which s otherwise
the same. He sends it to the recipient and waits for the error response.
Now, the recipient's decryption algorithm usually looks like this:

RSA Unwrap
Check PKCS-1 padding. (Case 1) If bad return an error.
Decrypt the message. 
Check the message integrity (case 2) If bad return an error.

If the attacker can distinguish between case 1 and case 2, he can
mount an adaptive chosen ciphertext attack, generating successive 
W's and eventually recover the wrapped MEK. This takes a long time
like a million messages. However, it's quite feasible for SSL.

You raise several issues which need to be considered:
1. Does this apply to S/MIME? Probably not. As you indicate, it's hard
to believe that someone wouldn't notice getting a million probe
messages. However, as I said before, CMS does not apply only to
S/MIME, and it's important to get it right for automated applications
where this could be a problem.  

Incidentally, while it's true that this attack does not apply to SET,
that's BECAUSE SET uses OAEP. If SET used PKCS-1, it would be
vulnerable.

Note that the attack does NOT necessarily require return receipt or even 
accurate error reporting if it's being used in an interactive
protocol. If the message is long, you may be able to differentiate
these two error tpes through timing analysis. However, interactive
protocols might well use error reporting mechanisms which would
reveal this sort of difference.

2. Does this attack apply to ES/SS-DH. No. There's no block formatting
in X9.42. In fact, there's no public key wrapped key at all. Rather,
the KEK is implied by the DH pairs. And since there's a checksum
on MEK unwrapping that fails with a probability of 2^64/1 if the 
wrapped MEK has been tampered with, this attack is impractical.

3. Does this attack work on ElGamal? I don't know. The only cryptovaribale
it depends on being reused is the recipient's key pair, which
would be the case with both ES-DH and ElGamal, so it's not
inconceivable that it would work.

The broad outlines of such an attack would be the same, however. You'd
generate successive W's and examine the server's response. 

> kidnapped by space aliens", and similar FUD.
I believe this estimate is unjustifiably optimistic.

-Ekr

-- 
[Eric Rescorla                                   [email-masked]]