6
$\begingroup$

During the key exchange, Alice and Bob both select a random natural number.

The question is how big this integer is? How many digits/bits it must have at least/most?

$\endgroup$
  • 1
    $\begingroup$ I'd generate a random integer at least twice as long as the security level and mask out the least significant bit to make it even. $\endgroup$ – CodesInChaos Aug 19 '16 at 7:08
  • 2
    $\begingroup$ @CodeInChaos: why fix the parity? I we can solve $g^x\equiv a\pmod p$ for unknown random even $x$ of some size with non-negligible probability, then we can solve it for odd $x$ of similar size with similar probability using practically the same amount of work (only an extra multiplication of $a$ by $g$ and adjustment of $x$ by 1 is needed); and vice versa. $\endgroup$ – fgrieu Aug 19 '16 at 8:29
  • 3
    $\begingroup$ Answers guys, we'll help with comments, upvotes and downvotes. $\endgroup$ – Maarten Bodewes Aug 19 '16 at 9:00
  • 2
    $\begingroup$ @fgrieu I prefer operating in prime order groups. Feels simpler and cleaner, a single extra squaring is nearly free. Since the attacker can learn the value of the LSB anyways, it doesn't add any security, so in a way you actually save a multiplication. $\endgroup$ – CodesInChaos Aug 19 '16 at 11:17
7
$\begingroup$

I'll assume the question asks: in the Diffie-Hellman key exchange protocol, how large does the secret random natural number that Alice and Bob each select needs to be.

It can be used a newly generated cryptographically secure random integer $x$ of 256 bits. This is conjectured safe for sound parameters (detailed below) and protocols used in practice. That's possibly good for a few decades, not accounting for mathematical breakthrough, nor hypothetical quantum computers usable for cryptanalysis.

PKCS#3 v1.4:1993 (official home) allows this, with an optional parameter $l$ length of private value in bits. When this option is used, $2^{l-1}\le x<2^l\;$ (with this option, PKCS#3 uses $x$ of fixed bit length, perhaps to reduce leakage by timing analysis). The modern Java CryptoAPI also has an $l$ parameter.

This practice is used in the Internet Key Exchange protocol of RFC 2409 with parameters of RFC 3526. It limits the cryptographic resistance to at most $O(2^{l/2})$, but, conjecturally, not significantly further down if the order of the generator used is a prime $q$ of at least about $l$ bits (or twice such a prime), which to my knowledge is met by all recommended DH parameters. See Paul C. van Oorschot and Michael J. Wiener, On Diffie-Hellman Key Agreement with Short Exponents, in proceedings of Eurocrypt 1996, which gives justification and a narrower criteria.

Choosing a larger bound for $x$ does not harm (demonstrably: by more than one bit of security), except for speed (execution time is roughly proportional to the bit length of $x$, all other things being equal). The absolute maximal security is obtained when $x$ is uniform on an interval of width equal to the order of the generator, but for some recommended DH parameters this comes at significant performance cost.

Note: This answer has been considerably expanded, following constructive criticism of an earlier version. I now stress that the above statement is relying on a stronger (thus mathematically less certain) assumption than a pure Diffie-Hellman assumption, and detail the conditions conjectured sufficient to ensure that a short exponent is secure.


The simplest form of Diffie-Hellman key exchange protocol works in the multiplicative group modulo some suitable public prime $p\;$ (the group $\mathbb Z_p^*\;$), using some suitable public member $g$ of that group. Alice (resp. Bob):

  • selects a random integer $x_a\;$ (resp. $x_b\;$) less than the bound $m$ discussed; the lower bound for $x$ can be $0\;$, $1\;$ (Handbook of Applied Cryptography Protocol 12.47), or $m/2\;$ (PKCS#3 with optional parameters $l$ and $m=2^l\;$);
  • computes and sends $y_a\;=\;g^{x_a}\bmod p\;$ (resp. $y_b\;=\;g^{x_b}\bmod p\;$);
  • receives $y_b\;$ (resp. $y_a\;$);
  • computes $z_a\;=\;{y_b}^{x_a}\bmod p\;$ (resp. $z_b\;=\;{y_a}^{x_b}\bmod p\;$).

Assuming that the messages have not been altered during the exchange, $z_a=z_b\;$. Both are $z\;=\;g^{x_a\cdot x_b}\bmod p\;$. For proper choice of $p$, $g$ and $m$ it is believed computationally infeasible to determine that common $z\;$ from knowledge of $y_a$, $y_b$, $p$ and $g\;$. That $z$ can then be used to establish a common symmetric secret key using a Key Derivation Function (beware that this protocol is vulnerable to a Man-in-the-Middle).

An $l/2$-bit security level requires choosing an upper bound $m$ at least $O(2^l)\;$. That's because regardless of parameters $p$ and $g$, there are generic attacks recovering $z$ in full with cost $O(2^{l/2})$ modular multiplications. One such attack finds $x_b$ from $y_b$, by precomputing $y_b\cdot g^u\bmod p$ for $u<2^{l/2}$, then searching $(g^{2^{l/2}})^v\bmod p$ for $v\le2^{l/2}$ among that; once a match is found, it comes $x_b\;=\;v\cdot2^{l/2}-u\;$; and $z$ is then computed as ${y_a}^{x_b}\bmod p\;$. There are better methods requiring much less memory, but we know no method requiring much less time and still generic (that is working for any $p$ and $g$, and more generally any group used for a generalized Diffie-Hellman key exchange protocol).

Common wisdom is that baring mathematical breakthrough or quantum computers usable for cryptanalysis, and with otherwise sound parameters, random-enough primes $p$ of 3072 bits can give about 128 bits of security. Beyond that, various practices exist for the choice of $p$, $g$, and $m\;$.

  1. It can be used a safe prime $p\;$ (that is, such that $p=2q+1$ with $q$ a prime), and $g$ a generator of $\mathbb Z_p^*\;$ (a positive integer such that $g^q\bmod p\ne1\;$); and bound $m=p-1\;$. This works in the group $\mathbb Z_p^*\;$, which has even order $p-1\;$. Noticeably, a passive adversary can find whether the common $z$ is a quadratic residue modulo $p$ or not, which leaks ≈0.81 bit of entropy. This is a non-issue when $z$ is post-processed by a proper KDF.
  2. As a variant it can be used $g$ of order $q\;$ (that is with $g^x\bmod p$ taking $q$ distinct values for unbounded $x\;$, which can is insured if $g^q\bmod p=1\;$ and $g\bmod p\ne1\;$), and bound $m=q\;$; or equivalently it can be used $g$ and $m$ as in [1.] above, but with restriction to even $x\;$. This is relying on a pure Diffie-Hellman assumption in the group of quadratic residues modulo $p\;$, which has prime order $q=(p-1)/2\;$. It is demonstrably as secure as [1.] is.
  3. It can be used a prime $p$ such that $p=q\cdot r+1$ where $q$ is a prime of about $l$ bits; and $g$ of order $q\;$, which is equivalent to $g^r\bmod p\ne1\;$; and $m=q\;$. This is relying on a pure Diffie-Hellman assumption in a Schnorr Group of prime order $q$ of about $l$ bits. Common wisdom is that it offers about $l/2$ bits of security for small $l$; thus with a $p$ of 3072 bits, using $q$ of about 256 bits is believed not to harm security compared to $q$ of 3071 bits in [1.] or [2.] above. There's a speedup by a factor of nearly 12, which the applied cryptographer loves (even though Schnorr groups create complications for authenticated variants of the Diffie-Hellman key exchange protocol, where an active adversary could try to sneak in $y$ not member of the Schnorr group).
  4. As a variant of any of the above three practices, and as suggested in the first part of the present answer, it can be chosen $m=2^l$ (and $m/2\le x<m$ in a PKCS#3 context).

When [4.] is combined with [1.] or [2.], we have the speedup of [3.] with $p$ still a safe prime. With $l$ large enough, there is no known reduction in security compared to [1.] or [2.]; but we do not know for sure how large $l$ should be. I see no argument to assert if at equivalent $l$, the security is more or less than the security of [3.] alone, which is commonly used.

When [4.] is combined with [3.], there demonstrably can't be a significant reduction in security compared to [3.] alone: no more than $\max(\log_2(q)-l,0)+1$ bits worth could be lost.

When using one or both of [3.] or [4.], the upper bound $m$ for $x$ is typically 160 to 512 bits, further with $m=q$ when not using [4.]. Otherwise (when using [1.] or [2.] without [4.]) the bound is typically per $p-1$ or $q$, thus 1023 to 4096 bits (though $p$ of 512 bits has been used, including as intentionally weakened cryptography).

$\endgroup$
7
$\begingroup$

I have to strongly disagree with the previous answer. The standard Decisional Diffie-Hellman assumption holds for the case that $g^{x_a}$ and $g^{x_b}$ are uniformly distributed in the group (which should be a prime-order subgroup). Thus, it depends on the order of the group. For example, if one takes $p=2q+1$ with both $p$ and $q$ prime and works in the subgroup of order $q$, then each of $x_a$ and $x_b$ should be uniformly chosen between 0 and $q-1$. The same is true of ECDH.

If you take a shorter exponent then there may not be any known attacks, but it becomes a less-standard and less established assumption. Since there is almost no cost in taking random values of the full length of the exponent, this is my strong recommendation.

$\endgroup$
  • 2
    $\begingroup$ "Since there is almost no cost" Doesn't it make the exponentiation DH is based on, about 8x as expensive? (comparing 256 bit and 2048 bit exponents) $\endgroup$ – CodesInChaos Aug 21 '16 at 21:45
  • 1
    $\begingroup$ @fgrieu Are you referring to Schnorr groups with your "best of both worlds" suggestion? in that case you'll run into complications when an attacker presents you with their public key which isn't in the desired prime order subgroup. While that's still secure in practice, it seems riskier than small exponents combined with safeprimes. $\endgroup$ – CodesInChaos Aug 21 '16 at 22:42
  • $\begingroup$ @Yehuda Lindell: thanks for the constructive criticism. I have made my answer more precise, with references showing that what I propose is at least not unheard of. Do you see a reason why, for $p$ of a given size (like 3072-bit), secret entropy $l$ (like 256-bit), and $g$ of prime order $q$, there would be a security difference (demonstrable or justifiable by hand-waving arguments) between having $p=2q+1$ and secret $x$ of $l$ random bits; versus having $p=q\cdot r+1$ with $q$ of $l$ bits and a secret $x$ uniformly random on $[0,q[$ ? $\endgroup$ – fgrieu Aug 24 '16 at 15:48
  • 1
    $\begingroup$ @fgrieu I don't know of a difference but this isn't completely my field. To the best of my knowledge, there is no known equivalence and the short-exponent discrete-log assumption may well be easier to solve. However, this doesn't mean that we have any known attacks. In general, my conservative nature says that when the cost is small, go with a better assumption. (Of course, in some cases, this additional cost may be significant but I would guess that this is the exception rather than the rule.) $\endgroup$ – Yehuda Lindell Aug 24 '16 at 21:03
  • 1
    $\begingroup$ @fgrieu Note that if you assume that the discrete log problem is hard with short exponents, then this implies equivalence between the regular DDH assumption and the short-exponent DDH assumption. See here: iacr.org/archive/pkc2004/29470171/29470171.ps. $\endgroup$ – Yehuda Lindell Aug 24 '16 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.