pgut001(_at_)cs(_dot_)auckland(_dot_)ac(_dot_)nz (Peter Gutmann) writes:
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".
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.
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.
I believe this estimate is unjustifiably optimistic.
-Ekr
--
[Eric Rescorla ekr(_at_)rtfm(_dot_)com]