david wong

Hey ! I'm David, a security consultant at Cryptography Services, the crypto team of NCC Group . This is my blog about cryptography and security and other related topics that I find interesting.

Socat new DH modulus February 2016

On February 1st 2016, a security advisory was posted to Openwall by a Socat developer: Socat security advisory 7 - Created new 2048bit DH modulus

In the OpenSSL address implementation the hard coded 1024 bit DH p parameter was not prime. The effective cryptographic strength of a key exchange using these parameters was weaker than the one one could get by using a prime p. Moreover, since there is no indication of how these parameters were chosen, the existence of a trapdoor that makes possible for an eavesdropper to recover the shared secret from a key exchange that uses them cannot be ruled out.
A new prime modulus p parameter has been generated by Socat developer using OpenSSL dhparam command.
In addition the new parameter is 2048 bit long.

This is a pretty weird message with a Juniper feeling to it.

Socat's README tells us that you can use their free software to setup an encrypted tunnel for data transfer between two peers.

Looking at the commit logs you can see that they used a 512 bits Diffie-Hellman modulus until last year (2015) january when it was replaced with a 1024 bits one.

Socat did not work in FIPS mode because 1024 instead of 512 bit DH prime is required. Thanks to Zhigang Wang for reporting and sending a patch.

The person who pushed the commit is Gerhard Rieger who is the same person who fixed it a year later. In the comment he refers to Zhigang Wang, an Oracle employee at the time who has yet to comment on his mistake.

The new DH modulus

There are a lot of interesting things to dig into now. One of them is to check if the new parameter was generated properly.

prime

It is a prime. Hourray! But is it enough?

It usually isn't enough. The developper claims having generated the new prime with openssl's dhparam command (openssl dhparam 2048 -C), but is it enough? Or even, is it true?

To get the order of the DH group, a simple \(p - 1\) suffice (\(p\) is the new modulus here). This is because \(p\) is prime. If it is not prime, you need to know its factorization. This is why the research on the previous non-prime modulus is slow... See Thai Duong's blogpost here, the stackexchange question here or reddit's thread.

Now the order is important, because if it's smooth (factorable into "small" primes) then active attacks (small subgroup attacks) and passive attacks (Pohlig-Hellman) become possible.

So what we can do, is to try to factor the order of this new prime.

Here's a small script I wrote that tries all the primes until... you stop it:

# the old "fake prime" dh params

dh1024_p = 0xCC17F2DC96DF59A446C53E0EB826550CE388C1CEA7BCB3BF1694D8A945A2CEA95B22255F9259941C22BFCBC8C857CBBFBC0EE840F98703BF609B08C68E99C605FC00D66D90A8F5F8D38D43C88F7ABDBB28AC04694A0B867337F06D4F04F6F5AFBFAB8ECE75534D7F7D17780E12464AAF9599EFBCA6C54177437AB9EC8E073C6D
dh1024_g = 2

# the new dh params

dh2048_p = 0x00dc216456bd9cb2acbec998ef953e26fab557bcd9e675c043a21c7a85df34ab57a8f6bcf6847d056904834cd556d385090a08ffb537a1a38a370446d2933196f4e40d9fbd3e7f9e4daf08e2e8039473c4dc0687bb6dae662d181fd847065ccf8ab50051579bea1ed8db8e3c1fd32fba1f5f3d15c13b2c8242c88c87795b38863aebfd81a9baf7265b93c53e03304b005cb6233eea94c3b471c76e643bf89265ad606cd47ba9672604a80ab206ebe07d90ddddf5cfb4117cabc1a384be2777c7de20576647a735fe0d6a1c52b858bf2633815eb7a9c0ee581174861908891c370d524770758ba88b3011713662f07341ee349d0a2b674e6aa3e299921bf5327363
dh2048_g = 2

# is_prime(dh2048_p) -> True

order = dh2048_p - 1

factors = [2]
print "2 divides the order"

# let's try to factorize the order by trial divisions
def find_factors(number):
    factors = []
    # use different techniques to get primes, dunno which is faster
    index = 0
    for prime in Primes():
        if Mod(number, prime) == 0:
            print prime, "divides the order"
            factors.append(prime)
        if index == 10000:
            print "tested up to prime", prime, "so far"
            index = 0
        else:
            index += 1

    return factors

factors += find_factors(order / 2)

It has been running for a while now (up to 82018837, a 27bits number) and nothing has been found so far...

The thing is, a Pohlig-Hellman attack is do-able as long as you can compute the discrete log modulo each factors. There is no notion of "small enough factor" defined without a threat model. This backdoor is not gonna be usable by small players obviously, but by bigger players? By state-sized attackers? Who knows...

EDIT: I forgot order/2 could be a prime as well. But nope.

nope

Well done! You've reached the end of my post. Now you can leave me a comment :)