31
$\begingroup$

Recently someone found that a Diffie-Hellman modulus used in a unix tool (socat) was not prime. This led some people to shout "backdoor".

What I don't understand is, how could this allow for a backdoor?

I'm guessing the problem could be small subgroup attacks. But this can be as much of a problem as when the modulus is prime. Or better: a non-prime group could have a big prime subgroup while a prime group could have small prime subgroups.

Thoughts?

It seems like Pohlig–Hellman could be one answer: you can compute the discrete log in a smooth order group. Someone started testing small factors of the non-prime modulus and found 3684787 = 271 x 13597 as a factor. It doesn't seem like any other "easy" factors are findable, so does this mean Pohlig–Hellman wouldn't work even if the adversary knows the factorization? (He needs small factors, not only known factors.)

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Has that modulus been publicly factored? ​ ​ $\endgroup$
    – user991
    Commented Feb 3, 2016 at 1:46
  • $\begingroup$ kind of, someone found 3684787 = 271 x 13597 to be a factor $\endgroup$
    – David 天宇 Wong
    Commented Feb 3, 2016 at 2:13
  • 4
    $\begingroup$ As long as the order of the multiplicative group order of each factor $p_i^{e_i}$ is smooth, i.e., whether $p_i^{e_i - 1}(p_i - 1)$ is smooth, Pohlig-Hellman will work quickly. The factors themselves can be arbitrarily large. But this cannot be the case, otherwise the number would be easily factorable with the $p-1$ method. $\endgroup$
    – Samuel Neves
    Commented Feb 3, 2016 at 5:20
  • $\begingroup$ what's the $p-1$ method? $\endgroup$
    – David 天宇 Wong
    Commented Feb 3, 2016 at 18:42
  • 1
    $\begingroup$ @David天宇Wong p-1 = en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm $\endgroup$
    – otus
    Commented Feb 3, 2016 at 19:49

2 Answers 2

Reset to default
24
$\begingroup$

How could this allow for a backdoor?

Well, if you do DH modulo a composite, an attacker can recover the shared secret if they can solve the DH problem (or the DLog problem) modulo each of the primes that make up the composite.

There are a couple of ways that could be used by someone who knows the factorization to solve the DLog problem easier than expected.

Each prime could be set up to admit to a small subgroup attack (that is, each of the primes $p, q$ has $p-1, q-1$ smooth; however that also makes it easier to factor (as Samuel notes). On the other hand, one could have a $p$ and $q$ "partially smooth"; say, both $p-1$ and $q-1$ would include a factor circa 64 bits. This would give a DLog that takes $O(2^{32})$ time (annoying, but quite feasible); while the $p-1$ factoring method would likely take $O(2^{64})$ time (which is likely that no one would bother trying).

A variant of this approach (if one can select $g$ as well) is to select $p-1 = 2p_1p_2$, where $p_1$ is a (say) 32 bit prime, and $p_2$ is a 479 bit prime, and select $g$ so that (mod $p$) generates a subgroup of order $p_1$. And, of course, you do the same for $q$. The DLog problem that you actually see would take $O(2^{16})$ work, and $pq$ would be hard to factor (unless someone guesses $p_1$, and computes $gcm(pq, g^{p_1}-1)$; the backdoor-installer would be hoping that no one would think of trying that).

Another way would be to have the composite be (say) a factor of 4 256 bit primes, which need not admit to small subgroups. In that case, to someone knowing the factorization can solve the DLog problem by solving 4 problems modulo 256 bit primes; a bit more effort than what a small group attack can do; however it's still practical (and the composite would still be difficult to factor).

A third method is to select primes $p$ and $q$ to be SNFS friendly; that is, both of the form $r^e + s$, for $r, s$ small. If $p$ and $q$ use different values for $r$, this would not be immediately apparent.

So, yes, the composite modulus could be a backdoor.

Improve this answer
$\endgroup$
29
  • 2
    $\begingroup$ @David天宇Wong: I'm looking at how someone who picks the modulus ("the attacker") can use a composite modulus to hide a small group (or other) attack. Yes, he could also pick a 1024 bit prime that is vulnerable to a small group attack, but anyone else who notices that $p-1$ is smooth can also listen in - I'm going through ways we can do NOBUS ("nobody but us") - that is, the installer can listen in, but it's hard for anyone else, even if they have a guess to what the attacker did. $\endgroup$
    – poncho
    Commented Feb 3, 2016 at 18:43
  • $\begingroup$ I deleted my question because I figured out the answer (and didn't see you had the time to reply), but I actually didn't think that doing this with a prime would cancel the NOBUS! (This is because the order is easy to calculate if p is prime, but hard if we don't know the factorization of a non-prime p) $\endgroup$
    – David 天宇 Wong
    Commented Feb 3, 2016 at 18:51
  • $\begingroup$ also in the $2p_1p_2$ way, you would only be able to do the dlog on the subgroup of order $p_1$, would that be enough to guess the dlog on the whole group? $\endgroup$
    – David 天宇 Wong
    Commented Feb 3, 2016 at 19:05
  • $\begingroup$ @David天宇Wong: no; however if you get to choose $g$ (the generator for the DH operation), you don't have to; as long as you can perform the dlog operation on $g^a$, that's good enough. $\endgroup$
    – poncho
    Commented Feb 3, 2016 at 19:11
  • 2
    $\begingroup$ @David天宇Wong: sure you can; if you have a solution $y = g^{a_p} \pmod{p}$ and a solution $y = g^{a_q} \pmod{q}$, then we know at the solution to $y = g^a \pmod{pq}$ has $a \equiv a_p \pmod{p-1}$ and $a \equiv a_q \pmod{q-1}$ $\endgroup$
    – poncho
    Commented Feb 29, 2016 at 16:16
12
$\begingroup$

I've since then wrote a paper to answer this question (of course with a huge help from Poncho)

I found many ways to implement a backdoor, some are Nobody-But-Us (NOBUS) backdoors, while some are not (I also give some numbers of "security" for the NOBUS ones in the paper).

The idea is to look at a natural way of injecting a backdoor into DH with Pohlig-Hellman:

prime backdoor

Here the modulus $p$ is prime, so we can naturally compute the number of public keys (elements) in our group: $p-1$. By factoring this number you can also get the possible subgroups. If you have enough small subgroups $p_i$ then you can use the Chinese Remainder Theorem to stitch together the many partial private keys you found into the real private key.

The problem here is that, if you can do Pohlig-Hellman, it means that the subgroups $p_i$ are small enough for anyone to find them by factoring $p-1$.

The next idea is to hide these small subgroups so that only us can use this Pohlig-Hellman attack.

CM-HSO

Here the prime $n$ is not so much a prime anymore. We instead use a RSA modulus $n = p \times q$. Since $n$ is not a prime anymore, to compute the number of possible public keys in our new DH group, we need to compute $(p-1)(q-1)$ (the number of elements co-prime to $n$). This is a bit tricky and only us, with the knowledge of $p$ and $q$ should be able to compute that. This way, under the assumptions of RSA, we know that no-one will be able to factor the number of elements ($(p-1)(q-1)$) to find out what subgroups there are. And now our small subgroups are well hidden for us, and only us, to perform Pohlig-Hellman.

There is of course more to it. Read the paper :)

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.