ElGamal key generation is broken
Affects  Status  Importance  Assigned to  Milestone  

 PythonCrypto 
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 subgroup of Z^*_p.
The order of such subgroup may be smaller than p1, and since there are not constraints or checks on the factorization of p1, 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
visibility:  private → public 
description:  updated 
Legrandin (gooksankoo) wrote :  #1 
Darsey Litzenberger (dlitz) wrote :  #2 
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 subgroup?)
Also, given that this is a *random* subgroup, 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) wrote :  #3 
This looks relevant: http://
Darsey Litzenberger (dlitz) wrote :  #4 
Is it okay if I just merge your entire tree (up to 6f312637208cc70
Legrandin (gooksankoo) wrote :  #5 
> 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 subgroup?)
One way is to factor p1 and find all its divisors. The divisors are also all the possible orders a subgroup 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 p1.
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 p1 (see patch). Those are at least the additional contraints I have found so far for the key...
> Also, given that this is a *random* subgroup, 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 6f312637208cc70
I can submit a complete/
Darsey Litzenberger (dlitz) wrote :  #6 
I've got a CVE identifier for this issue: CVE20122417
Changed in pycrypto:  
importance:  Undecided → High 
status:  New → In Progress 
Darsey Litzenberger (dlitz) wrote :  #7 
Fixed in PyCrypto 2.6.
Changed in pycrypto:  
status:  In Progress → Fix Released 
Mike Doherty (doherty) wrote :  #8 
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 USN14841 whether this library is used by Seahorse. The security notice also did not specify that users should replace the potentially
Mike Doherty (doherty) wrote :  #9 
I'm sorry, the notice does in fact recommend regenerating keys.
Patch available here:
https://github.com/Legrandin/pycrypto/commit/9f912f13df99ad3421eff360d6a62d7dbec755c2