Is there a key length definition for DH or DHE?

  • I found this in wiki

    The Finite Field Diffie-Hellman algorithm has roughly the same key strength as RSA for the same key sizes. The work factor for breaking Diffie-Hellman is based on the discrete logarithm problem, which is related to the integer factorization problem on which RSA's strength is based. Thus, a 3072-bit Diffie-Hellman key has about the same strength as a 3072-bit RSA key.

    How to define a Diffie-Hellman key length?

    According to DH priciple:

    Y = g^X mod p

    p, g, X, or Y? Which one equals 3072 bit according to wiki's opinion

    For finite-field DH we typically call `p` the key length. `Y` has the same size as `p`. `g`'s size is pretty much irrelevant it just needs to fulfill certain properties, `X` needs to be at least twice the security level (e.g. you need a 256 bit `X` for 3072 bit keys, corresponding to a 128 bit security level), and `p-1` needs sufficiently large factors.

  • Key sizes are traditional. By this I mean that there is no universal, mathematically accepted notion of "key size" which will match all algorithms. For symmetric algorithms, it is customary to have keys which are sequences of bits of a given length n, such that all possible sequences of length n (there are 2n of them) are acceptable keys; in which case cryptographers tend to speak of n as "the key size". There is already room for trouble here, with DES, which has 64-bit keys out of which only 56 bits are used, so DES can be said to use 56-bit keys. Similary, 3DES uses a 192-bit key which is in fact a 168-bit key; and, to further the confusion, there is a known algorithm which (theoretically) breaks 3DES in effort 2112 so 3DES is sometimes said to have security level "112 bits". Another troublesome algorithm is RC2, which has an extra "effective key size" parameter which lowers the resistance of RC2 against brute force down to a configurable value, even if the key is longer.

    For asymmetric cryptography, things are more complex since public and private keys no longer are "just sequences of bits". For instance, a RSA public key consists of two integers, the modulus and the public exponent. It is traditional to use the size of the modulus as "RSA key size", even though it is not possible to fit an entire RSA public key into a sequence of bits of that size (because there would be no room for the public exponent).

    For Diffie-Hellman, the standard is ANSI X9.42. This standard consistently avoids to speak of "the key size". Instead, it always talks of "the size of p" and "the size of q". Both sizes are important for security, but not within the same range. Namely, DH works with numbers modulo a big prime p, and with a generator g. The generator g "generates" a subgroup of integers modulo p: if you consider the successive values 1, g, g2, g3... modulo p, you will get back to 1 at some point. The order of g is the smallest integer k > > 0 such that gk = 1 mod p. Mathematics tell us that k necessarily divides p-1. With these notations:

    • DH can be broken if discrete logarithm modulo p, with base g, is broken. There are some algorithms whose cost depends on the size of p, so you want p to be big enough to make these algorithms too expensive. The best known algorithm of that type is a variant of the General Number Field Sieve and the current record, for a "random" modulus p is 530 bits (it is possible to craft a special-form modulus p which makes discrete logarithm easier, but a random prime will avoid that with overwhelming probability).

    • Discrete logarithm can also be broken in a time which depends on both the used exponent size, and the order of k. If, within Diffie-Hellman, a party selects its private exponent in a range of t successive values, and the largest prime factor of k (the order of g) is q, then the algorithms of that type will break DH in a time which depends on the smallest of q and t. These are the "generic" algorithms, whose running time is proportional to the square root of q (or t, if it is smaller).

    So basically you have three sizes:

    • The size of t for DH private key generation: each involved party generates a random DH private key in the 1..t-1 range.
    • The size of q, which is the largest prime factor of the order k of the generator g.
    • The size of the modulus p.

    In some protocols, q is generated explicitly, thus with a known size, and then p is generated so that p-1 is a multiple of q. Then g is selected to have order exactly q (gq = 1 mod p). In these protocols, we set t = q: q is known, and systems generate private keys in the 1..q-1 range.

    In some other protocols, p is generated as a so-called "safe prime", i.e. such that (p-1)/2 is also prime. In that case, p = 2q+1. For these protocols, the DH private keys will be generated in a smaller range t, typically 160 to 256 bits.

    In yet some other protocols, q is not known at all, and just assumed to be large enough. This is the case of SSL/TLS (for DHE cipher suites, the Server Key Exchange message contains p and g but not q, so the client does not know q). There again, a range t is used.

    We want n-bit security for some n, meaning that breaking the algorithm should have average cost 2n operations. To achieve such a security level, the size of q and the size of t shall be at least 2n bits, but p must be much larger. To give figures, it is generally estimated that if you look for n = 112 (112-bit security, which is what you get for symmetric encryption with 3DES), then you need q and t to be at least 224 bits, but p should be at least 2048 bits.

    Summary: when talking about DH, a "big" size like 1024 or 3072 normally means "the size of p", while a "small" size like 160 or 256 normally means "the size of q" or "the size of t". There is no standard for "the size", and indeed the standard does not define a unique one-size-fits-all size.

    In your Wikipedia quote, the "3072 bits" is the size of p (the modulus). The value y, which is a DH public key, is in the 1..p-1 range, thus also a number of 3072 bits (or slightly smaller). The private exponent x is chosen in a range 1..t-1 which may be as big as 3072 bits as well (or even bigger) but a much smaller range, down to (say) 256 bits, is perfectly acceptable for security.

    As @Polynomial says, see this site for comparisons between key sizes.

    "For these protocols, the DH private keys will be generated in a smaller range t, typically 160 to 256 bits" do you have a reference for this? Because I would be very interested. My take away from the classic "van Oorschot and Wiener" paper was that for the safe prime case you still had to pick t in the range of q (although it was assuming you would be using a small g)

  • Diffie-Hellman has two key sizes: the discrete log key size, and the discreet log group size. These map onto q and p respectively.

    Reasonable sizes for them, as of 2013, are 224 bits for q and 2048 bits for p.

    You can use KeyLength to get estimates for various key lifetimes and security margins.

    It's also worth looking at this question over on Crypto SE, which provides more technical details on the matter.

License under CC-BY-SA with attribution

Content dated before 7/24/2021 11:53 AM