[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Decrypting ElGamal messages
> From: pgut001@xxxxxxxxxxxxxxxxx (Peter Gutmann)
> Date: Fri, 9 Apr 1999 09:46:07 (NZST)
>
> Daniel Bleichenbacher <bleichen@xxxxxxxxxxxxxxxxxxxxxx> 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.
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.
> 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.
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?
> 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).
Sure. You need to include a message digest. But if I'm correct then
open-pgp uses a 2 byte modular checksum.
> 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).
The latest that I heard of was a server presented at the RSA conference
that can do 1500 SSL connections per second.
> 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"].
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.)
> 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.
Intrusion detection tricks like this are certainly worth considering. But
I'd prefer a protocol that doesn't rely on this.
Daniel