[Top] [All Lists]

Re: Decrypting ElGamal messages

1999-04-09 09:58:04

Hal Finney <hal(_at_)hal(_dot_)sb(_dot_)rain(_dot_)org>, writes: 
Daniel Bleichenbacher, <bleichen(_at_)research(_dot_)bell-labs(_dot_)com>, 
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 

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

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