CVE-2012-2417 (Python, published 2012-06-17T03:41Z)
Description: 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.
Severity: MEDIUM (CVSS v3 base score: )
Weakness: CWE-310 \u2014 Cryptographic Issues
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.
Repository: https://github.com/Legrandin/pycrypto
Files changed:
lib/Crypto/PublicKey/ElGamal.py
Commit message: Fix to bug #985164 (ElGamal key generation). Fix to missing range check in signature verification.


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