ElGamal key generation is broken
Affects | Status | Importance | Assigned to | Milestone | |
---|---|---|---|---|---|
| Python-Crypto |
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
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 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) 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 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 6f312637208cc70
I can submit a complete/
Darsey Litzenberger (dlitz) wrote : | #6 |
I've got a CVE identifier for this issue: CVE-2012-2417
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 USN-1484-1 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/ 9f912f13df99ad3 421eff360d6a62d 7dbec755c2