Subject: Decrypting ElGamal messages

From: Daniel Bleichenbacher <[email-masked]>
Date: Thu, 8 Apr 1999 15:51:42 -0400 (EDT)

Can anyone tell me how an ElGamal encrypted message has to be 
decrypted? The open-pgp documentation doesn't give the answer.
I'm specially interested in how padding and checksums are handled.

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?

-- Daniel Bleichenbacher

---

From: [email-masked] (Peter Gutmann)
Date: Fri, 9 Apr 1999 09:46:07 (NZST)

Daniel Bleichenbacher <[email-masked]> 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 --
 
Peter.

---

From: Daniel Bleichenbacher <[email-masked]>
Date: Thu, 8 Apr 1999 18:26:39 -0400 (EDT)

> From: [email-masked] (Peter Gutmann)
> Date: Fri, 9 Apr 1999 09:46:07 (NZST)
>

I'm not sure how remarkable this would be. Quite a large number of SSL
servers actually returned the necessary error messages for an attack there.
I think one shouldn't leave the chance here that the implementor makes
mistakes and add some quidelines to the standard.

>    is around there which tells people about the problem and (very simple) fix.

They also have to know that ElGamal and RSA have similar mathematical
properties. But, again wouldn't it be better if these people were informed
via the standard?

>    the implementation bug which was found and fixed in the SSL implementations).

Sure. You need to include a message digest. But if I'm correct then 
open-pgp uses a 2 byte modular checksum. 

>    an exact indication of the decryption error it encountered, and sending it 

The latest that I heard of was a server presented at the RSA conference
that can do 1500 SSL connections per second.

> recovered a single MEK [S/MIME jargon for "message encryption key"].

The 1 million messages was an estimate for my algorithm for 1024 bit RSA
moduli. This algorithm is not optimal. 100'000 is probably reachable with
some work. Also for some strange moduli (e.g. 1025 bit) some experiments
required less than 10'000 messages. It's not hard to imagine that someone
configures a server that can be broken in much less than 1 hour.
(Please note, this is an estimate for plain PKCS #1 v 1.5 formatting.
I don't know anything about ElGamal padding yet.)
 
> continuous attack for 8 solid months has more than simple crypto problems to 

Intrusion detection tricks like this are certainly worth considering. But 
I'd prefer a protocol that doesn't rely on this.

Daniel

---

From: [email-masked]
Date: Thu, 8 Apr 1999 17:17:58 -0700

> I'm specially interested in how padding and checksums are handled.

With both RSA and ElGamal messages, the session key is prepended with a
byte identifying the symmetric algorithm used to encrypt the bulk message
data (typically one of three or four supported symmetric algorithm
values can go here).  It is then appended with a two-byte checksum.
The resulting string is PKCS-1 padded and encrypted.

Upon decryption, the recipient needs to check the PKCS-1 formatting,
the checksum, and that the symmetric algorithm byte is one of the
supported algorithms.  It then tries to decrypt the following message
block using that algorithm and session key, which block also has in
it a two-byte redundancy at the beginning to further detect bad keys.

> potentially works against ElGamal, when used with PKCS #1 v1.5 

It would be good to mention this attack in a future version of the draft.
It is important not to leak information about which step in the decryption
process fails.

Then, in order to fake a successful encrypted session key, it must not
only be properly PKCS-1 padded, it must also have a correct two-byte
checksum (adding 16 bits of difficulty), it must have a legal symmetric
algorithm byte (adding about 6 bits of difficulty), and it must pass the
checksum test when the payload data is decrypted (adding another 16 bits).
This would make the attack in total about 2^38 times harder than against
a bare PKCS-1 leaking decryptor, which should be a significant barrier
in most practical situations.

> BTW, is there any reason why PKCS #1 v1.5 padding is used and

Although the RFC came out recently, it documents existing practice which
was developed in 1996.  At that time version 1.5 of PKCS 1 was extant.

Hal Finney
NAI, Inc.

---

From: [email-masked] (Peter Gutmann)
Date: Fri, 9 Apr 1999 13:10:55 (NZST)

>I'm not sure how remarkable this would be. Quite a large number of SSL servers
>actually returned the necessary error messages for an attack there. I think
>one shouldn't leave the chance here that the implementor makes mistakes and
>add some quidelines to the standard.
 
That's what I'd proposed earlier on in the same thread.  In addition you have
to remember that S/MIME and PGP are very different beasties from SSL, unless
you go out of your way to design a protocol which returns decryption results
you'd never get this situation, the best you can hope for is an SMTP-level
"Your mail probably got to some machine from which the recipient can collect
it" which never gets near the security layer.  Even though S/MIME has
provisions for signed receipts, the most they can communicate is "I got your
message", which is just a glorified form of the SMTP-level response and doesn't
help with this particular attack.

>The latest that I heard of was a server presented at the RSA conference that
>can do 1500 SSL connections per second.
 
Again, it's a special case for SSL.  For it to affect S/MIME or PGP you'd need
to set up an autoresponder running a custom protocol designed to facilitate the
attack (since it can't be done using any feature of standard S/MIME or PGP).
 
Peter.