3
$\begingroup$

The site badssl.com provides examples of bad (red icon) and good (green icon) uses of TLS for the purpose of testing TLS implementations. I'm a bit confused by the test called dh-composite. This explanation is given for the test: "This site uses an ephemeral Diffie-Hellman key exchange over a composite group." What exactly is a composite group? How would I test if given parameter set describes a composite group?

$\endgroup$

1 Answer 1

3
$\begingroup$

TL;DR: It allows the parameters to be backdoored and the solution is a simple primality test.

What exactly is a composite group [and why does it matter]?

First, we need to get a quick understanding of the Diffie-Hellman Key-Exchange. Diffie-Hellman (DH) works on a mathematical construct named group, which is a set and an operation which adhere to some basic requirements. You can call any set with an operation that adheres to these requirements "group". Now the idea of DH is that you have two parties pick positive integers $x,y$ and let them compute and exchange $X=g^x,Y=g^y$ for some agreed-upon group element $g$. In practice this means that $g$ is an integer such that $1<g<n$ for some $n$, which we call modulus and the actual operation is $X=g^x\bmod n$ (same for $y$), using modular arithmetic which basically means "if you get beyond $n$, subtract $n$ from the number until it's smaller than $n$ again". Now it can be shown that multiplication with modular reduction ("applying the $\bmod$ operation") and the set of all integers $<n$ form a group, which we typically call $\mathbb Z_n^*$. What this is about is the case where $n$ is composite, ie not prime.

"So why is a composite group bad?"

Well, it turns out that the security of DH relies on the fact that given $X,g,n$, you can't recover $x$ from $X=g^x \bmod n$. Now when we apply some special precautions to the structure of $n$ and the choice of $g$ this is actually assumed to be secure for sufficiently large parameter choices. However, when $n$ is large and composite and you now the factors of $n$ (and they're sufficiently small) you can in fact recover $x$. "Good, then I have a solid key-backup system now", you may think, but in fact such backdoored parameters have already been exploited in other cases, where an attacker replaced these parameters with their own, so they could eavesdrop on communication.

"OK, so how does this work then?"

There's a mathematical trick, called the Chinese Remainder Theorem (CRT) which allows you to split your instance of $\mathbb Z_n^*$ into several smaller groups like $\mathbb Z_p^*,\mathbb Z_q^*$. Now if you can do an operation in all these groups you can transfer the result back into the larger group with minimal effort. So let's just for the fun of it suppose we wanted to do this. We'd pick an $n=a\cdot b\cdot c\cdot d$ where $a,b,c,d$ are 512-bit long each and $n$ is 2048-bit long. Factoring $n$ or taking the discrete logarithm in $n$ would take on the order of $2^{112}$ operations using the best known algorithm (the GNFS), but computing the discrete logarithm in $\mathbb Z_a^*$ (and the other three groups) takes a week of pre-computations for each group, followed by a few seconds to minutes per group and discrete logarithm (PDF), which is definitely feasible.

How would I test if given parameter set describes a composite group?

In theory it's simple: You run a standard primality test against the parameters you receive and deny the connection if a composite modulus is used and accept the connection if the modulus is prime. The cost of this however is several times more expensive than not bothering and just accepting the parameters...

[T]he modulus is a prime in this case

In this case we need a bit of background on group theory. Especially the fact that there are $\varphi(p)=p-1$ elements in $\mathbb Z_p^*$ and the fact that each subgroup has $q$ elements where $q$ divides $\varphi(p)=p-1$. This means that you have at least one subgroup with two elements (because primes $> 2$ are odd and $p-1$ is thus even) and one with $(p-1)/2$ elements. Ideally you want this number to be a prime (and thus $p$ being a safe prime) to avoid the Pohlig-Hellman attack. If it is not a prime, then you can split the (full, "composite") group into (many) smaller groups and solve the discrete logarithm problem in all those subgroups (which can be significantly faster than in the full group) and recombine the result using the CRT again. Now if you pick $(p-1)/2$ to be composite consisting of let's say 128-bit primes it's gonna be hard for other people to find these factors, especially if you use 16 und it's easy for you to compute discrete logarithms, having only a cost of about $2^{70}$ (which should be feasible) instead of $2^{112}$. So again it allows parameters to be backdoored and can be prevent with a "simple" primality test on $(p-1)/2$

$\endgroup$
5
  • $\begingroup$ Note: I've left the full details on how a complete DH key exchange out, because they don't matter for this discussion. $\endgroup$
    – SEJPM
    Feb 14, 2017 at 16:01
  • $\begingroup$ That's exactly what I thought at first, except the modulus is a prime in this case. $\endgroup$
    – MMx
    Feb 15, 2017 at 14:32
  • $\begingroup$ @MMx I'm too tired to write a proper explanation right now but the TL;DR is Pohlig-Hellman and test whether $(p-1)/2$ is prime. $\endgroup$
    – SEJPM
    Feb 15, 2017 at 22:57
  • $\begingroup$ I totally get it that the prime is not a safe prime, but I can't find an RFC requiring servers to use safe primes only. Also why is the test talking about composite groups? Does using non-safe primes make the group composite? $\endgroup$
    – MMx
    Feb 16, 2017 at 10:18
  • $\begingroup$ @MMx I've updated my answer accordingly and yes the servers aren't required to use safe primes, but it's their problem if the connections they're trying to protect (by using TLS or whatever) get breached... $\endgroup$
    – SEJPM
    Feb 16, 2017 at 14:23

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.