1
$\begingroup$

The NIST and TLS standards for Diffie-Hellman key exchange over a finite field all work in a subgroup of ${\mathbb Z}_p^*$ having prime order $q$, where $p = 2q+1$. On the other hand, DSA has a larger cofactor, i.e., it works in a subgroup of ${\mathbb Z}_p^*$ having prime order $q$, where $p = rq+1$ and $r \gg 2$. The latter makes sense because it gives better efficiency while still giving the same security against known attacks.

So, why do the NIST/TLS standards not allow for cofactors greater than 2?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

So, why do the NIST/TLS standards not allow for cofactors greater than 2?

Actually, NIST does allow larger cofactors - see table 1 in SP800-56A - they allow the subgroup (q) to be significantly smaller than the modulus (p).

As for TLS, previous versions of TLS (1.2 and earlier) did allow the server to specify the group (and made no requirements about the cofactor). In TLS 1.3, they allow only a handful of specific groups to be used, all with a cofactor of 2. Is there a specific reason they should have included a group with a larger cofactor?

Improve this answer
$\endgroup$
8
  • $\begingroup$ Larger cofactor would be more efficient with the same security. $\endgroup$
    – user432944
    Commented Mar 18, 2020 at 23:54
  • $\begingroup$ Regarding the NIST standard: yes, it allows cofactor greater than 2 for server-generated parameters, but all the NIST-approved examples have cofactor 2. $\endgroup$
    – user432944
    Commented Mar 18, 2020 at 23:56
  • $\begingroup$ @user6584: "Larger cofactor would be more efficient with the same security." - can you please give an attack against DH based on a safe-prime that would be more efficient than against DH based on a large-cofactor prime of about the same size? I can cite a scenario where it is the opposite; there's an attack in that scenario that works on (some) large-cofactor primes, but not on safe primes $\endgroup$
    – poncho
    Commented Mar 19, 2020 at 3:00
  • $\begingroup$ I'm not claiming that an attack would be more efficient, I'm claiming the scheme would be. There are two classes of attacks on the Dlog problem in this case: those whose running time depends on the modulus p and those whose running time depends on the group order q. For fixed bitlength of p, we can set q to balance the running times of those attacks; smaller q will lead to better efficiency for honest users. $\endgroup$
    – user432944
    Commented Mar 19, 2020 at 13:14
  • $\begingroup$ @user6584: I don't understand. In case A (small subgroup), you pick a value $a$ between 1 and $q-1$ (a 256 bit number) and compute $g^a$. In case B (safe prime), you pick a value $a$ a random 256 bit number, and compute $g^a$. Why would case A be more efficient than case B? $\endgroup$
    – poncho
    Commented Mar 19, 2020 at 13:31
0
$\begingroup$

One possible reason for avoiding non-safe primes in the context of DH key exchange is to avoid small subgroup attacks like those identified in the paper by Valenta et al. (NDSS 2016).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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