ElGamal key generation is broken

[Legrandin]

In the ElGamal schemes (for both encryption and signatures), g is supposed to be the generator of the entire Z^*_p group.
However, in the current implementation, g is more simply the generator of a random sub-group of Z^*_p.
The order of such sub-group may be smaller than p-1, and since there are not constraints or checks on the factorization of p-1, the order may be *much* smaller than what it should be.

To say, if I limit the bit size to 8 bits, I get p=211 and g=107. The order of g is 42, much less than the expected (and "secure") 210!

[Legrandin (gooksankoo)]

Patch available here:

https://github.com/Legrandin/pycrypto/commit/9f912f13df99ad3421eff360d6a62d7dbec755c2

[Darsey Litzenberger (dlitz)]

Thanks for this. Do you know if there is a way to take an existing key and find out whether it has this problem? (Even better, to compute the order of the sub-group?)

Also, given that this is a *random* sub-group, does this actually help an attacker? I'm going to fix this anyway, but I want to get an understanding of how bad this is. I don't know much about ElGamal encryption.

[Darsey Litzenberger (dlitz)]

This looks relevant: http://tools.ietf.org/html/rfc2785

[Darsey Litzenberger (dlitz)]

Is it okay if I just merge your entire tree (up to 6f312637208cc70b231892109564e2aebc92728a)?

[Legrandin (gooksankoo)]

> Do you know if there is a way to take an existing key and find out whether it has this problem? (Even better, to compute the order of the sub-group?)

One way is to factor p-1 and find all its divisors. The divisors are also all the possible orders a sub-group of Zp can have.
The generator g is safe (with respect to this problem) if g^d mod p is not 1 for all divisors other than p-1.
That may not be enough though: when the key is used for signing, one should also check that g and g^{-1} don't divide p-1 (see patch). Those are at least the additional contraints I have found so far for the key...

> Also, given that this is a *random* sub-group, does this actually help an attacker? I'm going to fix this anyway, but I want to get an understanding of how bad this is. I don't know much about ElGamal encryption.

g is also made public, so that would be only relevant if the attack was based on some precomputation I think. The main problem I see is that the signature space (when the key is used for signing) or the public key space (when the key is used for encryption) may be greatly reduced from log(p) bits down to up 1 bit (worst case if the order of g is 2). That's already bad enough, but it could be that such fact may also be used to work out the private key (which the RFC you have found seem to imply).

> Is it okay if I just merge your entire tree (up to 6f312637208cc70b231892109564e2aebc92728a)?

I can submit a complete/tested/polished set of changes in one week time. As you can guess, the changes are mostly about improving documentation of the public key module: right now, qnew and maybe pycrypt.rst are still missing. I run into this problem by reviewing the Elgamal code.

[Darsey Litzenberger (dlitz)]

I've got a CVE identifier for this issue: CVE-2012-2417

[Darsey Litzenberger (dlitz)]

Fixed in PyCrypto 2.6.

[Mike Doherty (doherty)]

How can the user know whether they have an ElGamal key generated by the vulnerable versions of PyCrypto? For example, it is not stated in USN-1484-1 whether this library is used by Seahorse. The security notice also did not specify that users should replace the potentially-vulnerable keys. Even more disappointing, the notice states that "The problem can be corrected by updating your system..." Well, the software may be fixed, but the potentially-insecure keys are not magically made more secure by upgrading PyCrypto.

[Mike Doherty (doherty)]

I'm sorry, the notice does in fact recommend regenerating keys.