CVE-2012-2417: Cryptographic Issues (CWE-310)
value: PyCrypto before 2.6 does not produce appropriate prime numbers when using an ElGamal scheme to generate a key, which reduces the signature space or public key space and makes it easier for attackers to conduct brute force attacks to obtain the private key.
CWE description: Weaknesses in this category are related to the design and implementation of data confidentiality and integrity. Frequently these deal with the use of encoding techniques, encryption libraries, and hashing algorithms. The weaknesses in this category could lead to a degradation of the quality data if they are not addressed.
Published: 2012-06-17T03:41Z
Repository: https://github.com/Legrandin/pycrypto
Language: Python
Files changed: lib/Crypto/PublicKey/ElGamal.py
Commit date: 2012-04-18 23:13:08 +0200
Commit message: Fix to bug #985164 (ElGamal key generation). Fix to missing range check in signature verification.

Diff: diff --git a/lib/Crypto/PublicKey/ElGamal.py b/lib/Crypto/PublicKey/ElGamal.py
index 2b4d511..a9efe75 100644
--- a/lib/Crypto/PublicKey/ElGamal.py
+++ b/lib/Crypto/PublicKey/ElGamal.py
@@ -108,10 +108,13 @@ class error (Exception):
 
 # Generate an ElGamal key with N bits
 def generate(bits, randfunc, progress_func=None):
     """Randomly generate a fresh, new ElGamal key.
 
+    The key will be safe for use for both encryption and signature
+    (although it should be used for **only one** purpose).
+
     :Parameters:
         bits : int
             Key length, or size (in bits) of the modulus *p*.
             Recommended value is 2048.
         randfunc : callable
@@ -129,41 +132,52 @@ def generate(bits, randfunc, progress_func=None):
         current time and the ``random`` module.
 
     :Return: An ElGamal key object (`ElGamalobj`).
     """
     obj=ElGamalobj()
-    # Generate prime p
+    # Generate a safe prime p
+    # See Algorithm 4.86 in Handbook of Applied Cryptography
     if progress_func:
         progress_func('p\n')
-    obj.p=bignum(getPrime(bits, randfunc))
-    # Generate random number g
+    while 1:
+        q = bignum(getPrime(bits-1, randfunc))
+        obj.p = 2*q+1
+        if number.isPrime(obj.p, randfunc=randfunc):
+            break
+    # Generate generator g
+    # See Algorithm 4.80 in Handbook of Applied Cryptography
+    # Note that the order of the group is n=p-1=2q, where q is prime
     if progress_func:
         progress_func('g\n')
-    size=bits-1-(ord(randfunc(1)) & 63) # g will be from 1--64 bits smaller than p
-    if size<1:
-        size=bits-1
-    while (1):
-        obj.g=bignum(getPrime(size, randfunc))
-        if obj.g < obj.p:
+    while 1:
+        # We must avoid g=2 because of Bleichenbacher's attack described
+        # in "Generating ElGamal signatures without knowning the secret key",
+        # 1996
+        #
+        obj.g = number.getRandomRange(3, obj.p, randfunc)
+        safe = 1
+        if pow(obj.g, 2, obj.p)==1:
+            safe=0
+        if safe and pow(obj.g, q, obj.p)==1:
+            safe=0
+        # Discard g if it divides p-1 because of the attack described
+        # in Note 11.67 (iii) in HAC
+        if safe and divmod(obj.p-1, obj.g)[1]==0:
+            safe=0
+        # g^{-1} must not divide p-1 because of Khadir's attack
+        # described in "Conditions of the generator for forging ElGamal
+        # signature", 2011
+        ginv = number.inverse(obj.g, obj.p)
+        if safe and divmod(obj.p-1, ginv)[1]==0:
+            safe=0
+        if safe:
             break
-        size=(size+1) % bits
-        if size==0:
-            size=4
-    # Generate random number x
+    # Generate private key x
     if progress_func:
         progress_func('x\n')
-    while (1):
-        size=bits-1-ord(randfunc(1)) # x will be from 1 to 256 bits smaller than p
-        if size>2:
-            break
-    while (1):
-        obj.x=bignum(getPrime(size, randfunc))
-        if obj.x < obj.p:
-            break
-        size = (size+1) % bits
-        if size==0:
-            size=4
+    obj.x=number.getRandomRange(2, obj.p-1, randfunc)
+    # Generate public key y
     if progress_func:
         progress_func('y\n')
     obj.y = pow(obj.g, obj.x, obj.p)
     return obj
 
@@ -324,10 +338,12 @@ class ElGamalobj(pubkey):
         while t<0: t=t+p1
         b=(t*inverse(K, p1)) % p1
         return (a, b)
 
     def _verify(self, M, sig):
+        if sig[0]<1 or sig[0]>p-1:
+            return 0
         v1=pow(self.y, sig[0], self.p)
         v1=(v1*pow(sig[0], sig[1], self.p)) % self.p
         v2=pow(self.g, M, self.p)
         if v1==v2:
             return 1

Vulnerable code:     # Generate prime p
    obj.p=bignum(getPrime(bits, randfunc))
    # Generate random number g
    size=bits-1-(ord(randfunc(1)) & 63) # g will be from 1--64 bits smaller than p
    if size<1:
        size=bits-1
    while (1):
        obj.g=bignum(getPrime(size, randfunc))
        if obj.g < obj.p:
        size=(size+1) % bits
        if size==0:
            size=4
    # Generate random number x
    while (1):
        size=bits-1-ord(randfunc(1)) # x will be from 1 to 256 bits smaller than p
        if size>2:
            break
    while (1):
        obj.x=bignum(getPrime(size, randfunc))
        if obj.x < obj.p:
            break
        size = (size+1) % bits
        if size==0:
            size=4
Fixed code:     The key will be safe for use for both encryption and signature
    (although it should be used for **only one** purpose).

    # Generate a safe prime p
    # See Algorithm 4.86 in Handbook of Applied Cryptography
    while 1:
        q = bignum(getPrime(bits-1, randfunc))
        obj.p = 2*q+1
        if number.isPrime(obj.p, randfunc=randfunc):
            break
    # Generate generator g
    # See Algorithm 4.80 in Handbook of Applied Cryptography
    # Note that the order of the group is n=p-1=2q, where q is prime
    while 1:
        # We must avoid g=2 because of Bleichenbacher's attack described
        # in "Generating ElGamal signatures without knowning the secret key",
        # 1996
        #
        obj.g = number.getRandomRange(3, obj.p, randfunc)
        safe = 1
        if pow(obj.g, 2, obj.p)==1:
            safe=0
        if safe and pow(obj.g, q, obj.p)==1:
            safe=0
        # Discard g if it divides p-1 because of the attack described
        # in Note 11.67 (iii) in HAC
        if safe and divmod(obj.p-1, obj.g)[1]==0:
            safe=0
        # g^{-1} must not divide p-1 because of Khadir's attack
        # described in "Conditions of the generator for forging ElGamal
        # signature", 2011
        ginv = number.inverse(obj.g, obj.p)
        if safe and divmod(obj.p-1, ginv)[1]==0:
            safe=0
        if safe:
    # Generate private key x
    obj.x=number.getRandomRange(2, obj.p-1, randfunc)
    # Generate public key y
        if sig[0]<1 or sig[0]>p-1:
            return 0