Diffie-Hellman inconsistency: Accepting broken values, rejecting good ones

[diekmann]

I'm using cryptography 1.9 for python 3.4 on ubuntu 14.04 and python 3.5 on ubuntu 16.04.

The following is not a security issue.

I'm using Diffie-Hellman with extremely weak and broken values (for science). There are code paths where I get an error and there are code paths where my broken values are happily accepted. This is not a security issue since DH is not secure with broken or mitm-ed values (that is one reason why it is in the hazmat module). The other way round, there are also code paths which reject fine DH values.

The following works without complaint, loading my broken values.

#!/usr/bin/env python3
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.asymmetric import dh

#not a prime
notaprime = 2**512 - 1

pn = dh.DHParameterNumbers(notaprime, 2)
parameters = pn.parameters(default_backend())
bob_public = dh.DHPublicNumbers(pow(2, 42, notaprime), pn)
bob_public_key = bob_public.public_key(default_backend())
assert bob_public_key.key_size == 512
shared_key = parameters.generate_private_key().exchange(bob_public_key)
print(shared_key)

The shared key is completely broken (only one bit is set), but this is what we expect when using DH with a prime which is not a prime. PoC:

kint = int.from_bytes(shared_key, 'big')
for i in range(512):
    if 2**i == kint:
        print('key bruteforced: {}'.format(i))
        assert shared_key == (2**i).to_bytes(64, 'big')

However, if I try the same thing slightly different, I get an error:

#!/usr/bin/env python3
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.asymmetric import dh

#not a prime
notaprime = 2**512 - 1
pn = dh.DHParameterNumbers(notaprime, 2)
parameters = pn.parameters(default_backend())
bob_public_key = peer_public_key = parameters.generate_private_key().public_key()
print(bob_public_key.key_size)
shared_key = parameters.generate_private_key().private_numbers()
print(shared_key.private_key(default_backend()))

Traceback (most recent call last):
  File "dh_reject.py", line 12, in <module>
    print(shared_key.private_key(default_backend()))
  File "/usr/local/lib/python3.4/dist-packages/cryptography/hazmat/primitives/asymmetric/dh.py", line 43, in private_key
    return backend.load_dh_private_numbers(self)
  File "/usr/local/lib/python3.4/dist-packages/cryptography/hazmat/backends/openssl/backend.py", line 1687, in load_dh_private_numbers
    raise ValueError("DH private numbers did not pass safety checks.")
ValueError: DH private numbers did not pass safety checks.

It is also expected behavior that those broken values are rejected.

My only concern is that it appears somewhat random to me whether my weak values are rejected or not.

The opposite also holds. There are good and strong DH values which get rejected.

#!/usr/bin/env python3
import os
from binascii import unhexlify


# RFC3526 1536-bit DH values
p ="""FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
      29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
      EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
      E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
      EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D
      C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F
      83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D
      670C354E 4ABC9804 F1746C08 CA237327 FFFFFFFF FFFFFFFF"""
p = int.from_bytes(unhexlify(p.replace('\n', '').replace(' ', '')), 'big')
g = 2

#run a DH exchange manually

## Alice:
xa = int.from_bytes(os.urandom(192), byteorder="big")
#ya is party a's public key; ya = g ^ xa mod p
ya = pow(g, xa, p)
print("Alice sends {},{},{}".format(ya, g, p))

## Bob:
#yb is party b's public key; yb = g ^ xb mod p
xb = int.from_bytes(os.urandom(192), byteorder="big")
yb = pow(g, xb, p)
# ZZ = (yb ^ xa)  mod p  = (ya ^ xb)  mod p
ZZ_b = pow(ya, xb, p)
print("Bob sends {}".format(yb))

## Alice:
ZZ_a = pow(yb, xa, p)

## Both have the same key
assert ZZ_a == ZZ_b


#the following works
from cryptography.hazmat.primitives.asymmetric import dh
from cryptography.hazmat.backends import default_backend
pn = dh.DHParameterNumbers(p, 2)
parameters = pn.parameters(default_backend())
bob_public = dh.DHPublicNumbers(yb, pn)
bob_public_key = bob_public.public_key(default_backend())
assert bob_public_key.key_size == 1536
shared_key = parameters.generate_private_key().exchange(bob_public_key) #new key
print('worked', shared_key)

#the following fails
pn = dh.DHParameterNumbers(p, g)
parameters = pn.parameters(default_backend())
bob_public = dh.DHPublicNumbers(yb, pn)
bob_public_key = bob_public.public_key(default_backend())
assert bob_public_key.key_size == 1536
shared_key = dh.DHPrivateNumbers(xa, bob_public)
print(shared_key.private_key(default_backend())) #ValueError: DH private numbers did not pass safety checks.

debug: dh.generate_parameters(generator=2, key_size=512, backend=default_backend()).parameter_numbers().p % 24 is always 11. For my prime p p % 24is 23

Cryptography_DH_check seems not to like 23 but wants 11.

I'm not the first to notice this behavior of openssl. Yes, it is actually an issue of openssl. But somehow, I dislike the inconsistent behavior of pyhton-cryptography with regard to both, accepting obviously broken values as well as rejecting known good ones.

But probably this is not a bug at all.

Final disclaimer, in case this was not clear: This is not a security issue. Checking for bad DH values is a nice feature to prevent coding errors, but not a security feature. The following does not hold: "If we check that the DH values are good, then the DH exchange is secure." To get things secure, one needs to ensure the integrity and authenticity of a DH exchange. Though Cryptography_DH_check rejects my obviously broken value, it does not guarantee security (it is just a sanity checker, it would be approximately as hard to verify the goodness of DH values as just breaking DH).

[reaperhulk]

Thanks for the investigation here. Cryptography_DH_check duplicates the behavior of OpenSSL 1.1.0, but it was pulled in because we wanted a consistent check across all versions of OpenSSL we support. This seems like it might be an argument against running a DH_check at all since it doesn't prevent bad values from getting through anyway.

[palaviv]

I think that removing the DH_check from load_dh_private_numbers and encourage people to use dh_parameters_supported in the docs will be fine. How about in addition we will do something like they did in nodejs. We can do a similar API to the ECDH with the curves.

[diekmann]

I like the idea of removing Cryptography_DH_check and documenting that users may call dh_parameters_supported (but it is not necessary). It should be clearly stated that this is a sanity check and does not guarantee that the parameters are secure. The other way round, dh_parameters_supported may also reject perfect values because the backend does not like them. In the spirit of a hazmat module, I'd prefer to keep this check optional and leave it to the users.

default_backend().dh_parameters_supported(p, 2) also accepts my broken p = notaprime and rejects my good RFC prime. But this is expected behavior because we are not talking about the DH frontend anymore, but we are talking about the known limitation of the OpenSSL backend.

Maybe the two primes of this issue could even become a regression test to have code which documents these known limitations?

[reaperhulk]

p % 24 == 23 is now allowed when generator == 2. Still outstanding is what to do with generators that are not (2, 5) when subgroup order is not supplied. At the moment I'm aware of that limitation affecting custom DH groups in TLS...which is perhaps not a use case we want to support (and is gone in TLS 1.3 anyway). Are there any other cases of clearly "good" values (specifically ones contained in specs) that are rejected by current master?

[diekmann]

RFC 5114 Section 2.1. 1024-bit MODP Group with 160-bit Prime Order Subgroup has:

p = """B10B8F96 A080E01D DE92DE5E AE5D54EC 52C99FBC FB06A3C6
        9A6A9DCA 52D23B61 6073E286 75A23D18 9838EF1E 2EE652C0
        13ECB4AE A9061123 24975C3C D49B83BF ACCBDD7D 90C4BD70
        98488E9C 219A7372 4EFFD6FA E5644738 FAA31A4F F55BCCC0
        A151AF5F 0DC8B4BD 45BF37DF 365C1A65 E68CFDA7 6D4DA708
        DF1FB2BC 2E4A4371"""
p = int.from_bytes(unhexlify(p.replace('\n', '').replace(' ', '')), 'big')
p % 24 == 17

So this prime should also be rejected. Note that the generator is neither 2 nor 5.

The Section 2.2. 2048-bit MODP Group with 224-bit Prime Order Subgroup has a prime which is 7 modulo 24 (and a generator which is also neither 2 nor 5).

[diekmann]

By the way, I think we are on a dangerous path here:

I did not look into the details of OpenSSL, so this is just a guess: Clearly OpenSSL only wants certain "safe" primes and generators. Is it possible that there are optimizations deep within OpenSSL's code which assume that the primes and generators are constructed exactly as assumed by OpenSSL? If this is the case, the optimizations could be unsound for other types of primes or generators. Trivial example: exponentiation of a generator which is always 2 can be implemented by a simple left shift; this is unsound and insecure for any other generator. Worse, is there a guarantee that such a optimizations will never be introduced, not even in future releases of OpenSSL? If such optimizations exist, this would be a security issue!
Hence, Pull Request #3768 may be a dangerous path. Unless, of course, there is some part of the OpenSSL API that guarantees that OpenSSL's DH implementation is safe to use for any primes and generators (not just the specific ones OpenSSL likes).

Probably we have two use cases of the DH module. One with OpenSSL as backend which only accepts OpenSSL-style primes and generators. And another one which accepts arbitrary primes and generators (and which may be slower).

Of course, if OpenSSL computes correctly for arbitrary primes and generators, this is not an issue. I'm not fluent with OpenSSL's API but BUGS: If generator is not 2 or 5, dh->g=generator is not a usable generator. does not sound promising.

TL:DR If the OpenSSL code has certain optimizations which are only sound for the primes/generators generated by OpenSSL itself, we are heading straight into a security hazard. Even if we feed safe (RFC approved, but not with the internal structure assumed by OpenSSL) primes and generators, due to low-level optimizations relying on certain assumptions, the calculation by OpenSSL may be wrong

[reaperhulk]

While we're still inconsistent (thanks OpenSSL) I think we're okay with the situation as it currently stands. Closing for now (but feel free to reopen if you disagree or think there's a change that should be made)