ElGamal key generation is broken

Bug #985164 reported by Legrandin
264
This bug affects 2 people
Affects Status Importance Assigned to Milestone
Python-Crypto
Fix Released
High
Unassigned

Bug Description

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!

CVE References

Legrandin (gooksankoo)
visibility: private → public
Legrandin (gooksankoo)
description: updated
Revision history for this message
Legrandin (gooksankoo) wrote :
Revision history for this message
Darsey Litzenberger (dlitz) wrote :

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.

Revision history for this message
Darsey Litzenberger (dlitz) wrote :
Revision history for this message
Darsey Litzenberger (dlitz) wrote :

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

Revision history for this message
Legrandin (gooksankoo) wrote :

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

Revision history for this message
Darsey Litzenberger (dlitz) wrote :

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

Changed in pycrypto:
importance: Undecided → High
status: New → In Progress
Revision history for this message
Darsey Litzenberger (dlitz) wrote :

Fixed in PyCrypto 2.6.

Changed in pycrypto:
status: In Progress → Fix Released
Revision history for this message
Mike Doherty (doherty) wrote :

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.

Revision history for this message
Mike Doherty (doherty) wrote :

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

To post a comment you must log in.
This report contains Public Security information  
Everyone can see this security related information.

Other bug subscribers

Remote bug watches

Bug watches keep track of this bug in other bug trackers.