Subject: Re: Decrypting ElGamal messages

From: Daniel Bleichenbacher <[email-masked]>
Date: Fri, 9 Apr 1999 12:56:43 -0400 (EDT)

Hal Finney <[email-masked]>, writes: 
> Daniel Bleichenbacher, <[email-masked]>, writes:
> > 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.
> 
> 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.

Thanks a lot for the information. Would have missed the checksum
in the bulk data otherwise.

> > 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.
> 
> 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.

I'm not sure about this "2^38 times harder...", but estimating 
this number is exactly the goal of the whole exercise.
Are there any publications considering the security of the openpgp
message format against chosen ciphertext attacks?
As Peter Gutmann pointed out, a chosen ciphertext attacks would be
almost impossible against plain PGP. The openpgp standard should 
however be useful for any application using the same message format,
and client-server applications should not be prevented. 

> > BTW, is there any reason why PKCS #1 v1.5 padding is used and
> > not PKCS #1 v2?
> 
> 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.

Daniel Bleichenbacher

---

From: [email-masked] (Ulf Möller)
Date: Mon, 12 Apr 99 20:32 +0200

>in the bulk data otherwise.

I don't think you can count it in.  While the semantics of a (Session
Key Packet, Literal Packet) message is not defined in the RFC, a naïve
implementor may very well try to be "generous in what they accept", as
is suggested elsewhere in the document.

PGP 5 does not accept such messages, but prints an "assertion failed"
message only if the PKCS #1 padding and the Session Key Packet
checksum are correct.