How should I check the received ephemeral Diffie-Hellman public keys?

Question

In my application I'm doing a DH key exchange, where both sides generate their own ephemeral key. No static keys are used. I am trying to make my application resistant against an active attack and therefore need to validate the public key that my counterpart is sending me.

Below I'm using standard DH variable names: DH parameters $g$ and $p$. Party $A$ has a private key $x_a$ and public key $y_a = g^{x_a} \bmod p$. Party $B$ has a private key $x_b$ and public key $y_b = g^{x_b} \bmod p$. The calculated secret is then $z = g^{x_ax_b} \bmod p$. Also $p$ is a safe prime $p = 2q+1$.

In my application I will authenticate the shared secret $z$ via an out of bounds way (basically a user verifying a fingerprint).

OpenSSL has a function to validate a DH public key (DH_check_pub_key()) which does the following check:

$$2 \leq y_b \leq p-2$$

I believe this always excludes the generators that generate the order-2 subgroup. Because $p$ is a safe prime, I think these generators are always $1$ and $p-1$. Is this correct? Is it also correct that all integers in $[2, p-2]$ either generate an order-$q$ or an order-$2q$ subgroup?

Secondly, in NIST SP800-56, section 5.6.2.4, it is mentioned that I should also check:

$$y_b^q \bmod p = 1$$

I don't understand the background of this check. Is it needed when $p$ is a safe prime? OpenSSL does not implement this.

Answer 1

The check $y_b^q = 1 \mod p$ is there to prevent two possible weaknesses:

• Suppose someone gave us (either because of a programmer error or deliberate attack) gave us a $y_b$ value of small order. If so, then someone listening in can guess the shared secret you derive.

• Suppose an attacker gave us a $y_b$ value with an order with a small factor $r$. Then, by seeing the shared secret value $z$ you derived (which will be one of $r$ possibilities), then the attacker could rederive the value $x_a \bmod r$; whether that is interesting would depend on whether you reuse $x_a$ elsewhere.

Now, for a "safe prime" (one where $q=(p-1)/2$ is prime), neither of these attackers are of much concern; there are no small subgroups other than the trivial order-1 and order-2 subgroups (and yes, you are correct, all group members in $[2, p-2]$ are either of order $q$ or $2q$). In addition, which the attacker could give us a $y_b$ value with order 2q (and potentially learn $x_a \bmod 2$, that just gives him one bit of your private exponent; as he can't learn anything else, this is not much of a concern (even if you reused $x_a$ in other DH exchanges).

On the other hand, NIST SP800-56 doesn't assume a safe prime. In fact, a strict reading of NIST SP800-56 would appear to forbid it; if you look at Table A, it specifies the size of $q$ to be either 160, 224 or 256 bits (and not "at least so many bits", precisely that size).

As for your question as to whether the check $2 \le y_b \le p-2$ will always exclude all members of an order-2 subgroup, that is actually true for any prime $p$, not just "safe primes". For any prime $p$, the only group member with order 2 will be $p-1$.

Also, if you think you want to perform the $y_b^q = 1 \mod q$ check (even though it doesn't appear to be strictly necessary), one optimization that a safe prime allows is that you can compute the Lagrange symbol; that's a short cut for computing $x^q \bmod p$ for $q = (p-1)/2$ (which is a lot faster than computing $x^q \bmod p$ directly)