[Top] [All Lists]

Re: Decrypting ElGamal messages

1999-04-08 14:46:30
Daniel Bleichenbacher <bleichen(_at_)research(_dot_)bell-labs(_dot_)com> writes:

I'm asking this question, because ElGamal encryption has the same 
multiplicative properties as RSA. In particular, given the encryption of a 
message M (including padding), it is easy to generate the encryption of M*S 
(mod p) for a given S, without knowing M. Hence the same attack that was 
possible against SSL potentially works against ElGamal, when used with PKCS 
#1 v1.5 padding.

BTW, is there any reason why PKCS #1 v1.5 padding is used and not PKCS #1 v2?
This exact issue was debated on the ietf-smime list when I asked why X9.42 
(which looks like the winning candidate from a 'Worst way to apply the DLP to 
solving a key transport problem' competition... [remainder bobbitted to avoid 
another flamewar over this :-]) was being used instead of the far more logical 
Elgamal, which would be a direct, patent-free drop-in replacement for the 
existing RSA key transport.  The only reason anyone could put up against 
Elgamal was "You need to use OAEP because PKCS #1 padding is insecure".  In 
response to this (at the end of a longish debate) I posted the following 
back-of-the-envelope analysis:
-- Snip --
The second approach is to see just what it would take to implement this attack 
on CMS (not S/MIME, but anything involving CMS).  For this analysis I'll make 
several assumptions:
1. The implementor has managed to design a protocol which will accept 
   arbitrary numbers of chosen-ciphertext messages and reply to each one with 
   an exact indication of how the decrypt failed, leaking information about
   the decrypted message to an attacker.  This is a fairly remarkable feat, 
   but let's say, just for arguments sake, that someone did do this.
2. The implementor and any third-party reviewers have somehow missed the CERT 
   advisory, RSA labs bulletin, publicity about the attack, and whatever else 
   is around there which tells people about the problem and (very simple) fix.
3. The PKCS #1 implementation being used is correct (that is, it doesn't have 
   the implementation bug which was found and fixed in the SSL implementations).
4. A typical query+response takes half a second (this means opening a 
   connecting, generating a chosen-ciphertext message, transmitting it, having 
   the victim decode and try to decrypt it, generating a response, wrapping up 
   an exact indication of the decryption error it encountered, and sending it 
   back to the attacker).
OK, so we have a server which does all of the above sitting there ready for 
attack.  With a correct PKCS #1 implementation (that is, it checks the padding 
as per the PKCS #1 spec), the complexity is approximately 1 million attempts 
(for the 00 02 padding) x 20 (for the second 00 before the MEK) x 2 (for the 
minimum of 8 nonzero bytes), or 40 million attempts (the 1 million attempts 
requires the presence of the SSL implementation bug mentioned above).
This requires just under 8 months of CPU time to perform, after which you've 
recovered a single MEK [S/MIME jargon for "message encryption key"].
I would suggest that anyone who doesn't notice that their server is under 
continuous attack for 8 solid months has more than simple crypto problems to 
worry about.
-- Snip --

<Prev in Thread] Current Thread [Next in Thread>