2
$\begingroup$

Suppose I always reuse p, g and a in DH and there is someone monitoring my communication. Is there a way this person can use this to perform some kind of attack to me?

I believe that reusing p and g isn't a big issue, however I'm not quite sure about a.

$\endgroup$

migrated from security.stackexchange.com Oct 10 at 19:17

This question came from our site for information security professionals.

  • $\begingroup$ You might get good answers on Cryptography.SE. $\endgroup$ – Adonalsium Oct 4 at 13:35
  • $\begingroup$ To be clear: p is prime. g need not be prime, although it often is and it must be coprime to p-1. q must be prime but is sometimes not explicitly stated, e.g. SSL and TLS through 1.2, and SSH 'GEX'. If a is a private or public key for one party, those need not be and usually are not prime. $\endgroup$ – dave_thompson_085 Oct 10 at 23:45
1
$\begingroup$

In the seminal paper of Diffie-Hellman describes Diffie-Hellman Key Exchange* (DHKE), we have Alice and Bob want to key exchange and Oscar is the bad guy (Oscar is not mentioned in the paper). In DHKE settings

  • $p$ is a public prime modulus known by Alice and Bob and Oscar.
  • $g$ is a public base known by Alice and Bob and Oscar and need not to be a prime number.

The $a$ and $b$ are random values ( not necessarily a prime) generated by Alice and Bob per session. After the key is generated they can delete $a$ and $b$. They are not transferred as $a$ or $b$, they are transferred as $g^a$ and $g^b$.

-This is called ephemeral-ephemeral DHKE (or standard DHKE)

Standard DHKE and vulnerable to Man-in-the-Middle-Attack ( an active attacker who replaces both public keys with his own and creates two channels). To mitigate you need authentication as in TLS.

ephemeral-ephemeral DHKE has forward secrecy that generates a new key per session and discards at the end of the session. There is no easy way for an attacker to find the exchanged keys if they are erased.

As a passive man in the middle, Oscar sees $g^a$, $g^b$ and wants to calculate $g^{ab}$. This is called Diffie–Hellman problem and for some groups, this is a hard problem.

To access $a$ or $b$, Oscar must solve the Discrete Logarithm Problem (DLP) and generic algorithms for DLP runs in $O(\sqrt{p})$. To protect against the generic discrete logarithm attacks the $p$ is chosen a safe prime $p = 2q+1$ where $q$ is another prime aginst Pohlig-Hellman. For the key sizes see keylength.com.

  • There is also static-ephemeral DHKE where one side always chooses a new random $a$ and one is fixed $b$.

  • There is also static-static DHKE where both sides use fixed $a$ and $b$.

So your case:

It is either static-static or static-ephemeral.

In short: No problem for $p$ and $g$. But the Oscar doesn't get $a$ and $b$ as a passive man in the middle. If you use again, he will see the same values $g^a$ and $g^b$, however, you will not have forward secrecy.


Note: static DHKE's are removed from TLS 1.3.

* Actually, in DHKE, the key is established not exchanged.

$\endgroup$
  • $\begingroup$ So, if I always use the same 'a' everytime, I wouldn't have to worry about anyone trying to attack me. Even if Oscar could know that I'm reusing 'a', because g^a is the same. Is it correct? $\endgroup$ – FY Gamer Sep 29 at 21:37
  • $\begingroup$ It all depend on chosen p, if p is small(768 bit or less) , oscar can break it and retrieve a. Typically p is chosen as safe prime i.e. p = 2q+1 $\endgroup$ – Chits Oct 11 at 3:29
1
$\begingroup$

Actually, there is one potential problem to reusing $a$ values:

Background: $g$ generates a subgroup of size $q$; $q$ is a divisor of $p-1$, but it is usually selected as a prime, and is hence less than $p-1$ (which is obviously composite).

What an attacker could do is, for any small prime $r$ which divides $(p-1)/q$, he can potentially learn $a \bmod q$; he does this by negotiating with you, selecting as his share a value $g^b \cdot h$, where $b$ is a value he knows (doesn't matter what it is), and $h$ is a value of order $q$. Then, when you'll do is generate a shared secret $(g^b \cdot h)^a = g^{ab} \cdot h^{a \bmod r}$; he can easily compute $g^{ab}$, and so he knows the shared secret is one of $r$ different values (depending on the value of $a \bmod r$).

If $(p-1)/q$ has a number of small primes, the attacker can deduce quite a bit about $a$. One example of such a $p, q$ pair which has been actually proposed is Group 23 of RFC 5114; this particular group has $$(p-1)/q = 2 * 3 * 3 * 5 * 43 * 73 * 157 * 387493 * 605921 * 5213881177 * 352891 0760717 * 83501807020473429349 * C489$$ (where $C489$ is a 489 digit composite), and so the attacker can actually deduce enough to make brute force search of a 256 bit exponent feasible.

Now, there are several ways to protect yourself from this:

  • When you receive a value $b$, always check to see if $b^q = 1$; if not, someone is playing games. This works, but it is expensive.

  • Use a 'safe prime' group; that is, one where $p-1 = 2q$. This implies that the attacker can learn one bit of $a$ (the least significant bit), but nothing else.

  • Don't reuse $a$ values; what the attacker learns is the value $a \bmod r$ for the $a$ you used with the exchange with him; if you use different values of $a$ for unrelated exchanges, this doesn't buy him anything.

Also, note that the idea of using $q = p-1$ really isn't a protection; if $q$ has a small factor $r$, the attacker can also learn $a \bmod r$ just by examining $g^a$, hence the same vulnerability is there (except that not reusing $a$ doesn't actually provide protection).

$\endgroup$

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.