4
$\begingroup$

can't we do a nobus backdoor with DH modulus prime? Some have argued that with a prime modulus you can just get the order by doing p-1 and then factor it, thus it is easy to reverse. I argue that this is not true.

The prime case

Our modulus is a prime $p$ such that the order of the group is $p-1 = p_1^{k_1} \times \cdots \times p_n^{k_n}$

For the backdoor to work, the discrete log should be do-able in groups of order $p_i^{k_i}$

For the NOBUS to work, you shouldn't be able to find the factors $p_i^{k_i}$

The non-prime case

Our modulus is now a composite $n = p_1^{k_1} \times \cdots \times p_n^{k_n}$ such that the order of the group is $p_1^{k_1-1}(p_1-1) \times \cdots \times p_n^{k_n-1}(p_n -1)$

For the backdoor to work, the discrete log should be do-able in groups of order $p_i^{k_i-1}(p_i-1)$

For the NOBUS to work, you shouldn't be able to find the factors $p_i^{k_i}$

The difference?

I see almost no difference between these two problems. It seems like a NOBUS backdoor could as easily be created with a prime modulus as with non-prime one.

Thoughts?

$\endgroup$
  • $\begingroup$ "do-able in" ​ -> ​ "do-able in groups of order" ​ ​ ​ ? ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user991 Feb 7 '16 at 0:24
  • $\begingroup$ yes this is right $\endgroup$ – David 天宇 Wong Feb 7 '16 at 1:57
  • $\begingroup$ While not relevant to the question (difference between prime and non-prime moduli), please note that it is possible to prove numbers to be prime and to quickly find out that a number is composite. So such a modulus would cast suspicion really quickly. $\endgroup$ – SEJPM Feb 7 '16 at 13:26
  • $\begingroup$ This is what happened with socat (news.ycombinator.com/item?id=11014175) $\endgroup$ – David 天宇 Wong Feb 8 '16 at 16:30
3
$\begingroup$

[In the non-prime case] For the backdoor to work, the discrete log should be do-able in $p_i^{k_i-1}(p_i - 1)$

Actually, that's not quite correct, and that's relevant for the answer.

If the factorization of $p_i^{k_i-1}(p_i - 1)$ is $p_i^{k_i-1} q_1^a q_2^b ... q_n^z$, then for NOBUS to work, someone else shouldn't be able to find the factors $q_i$.

Here's why this distinction is important: in the prime case, everyone knows the size of the group $p-1$, and anyone can hand off that value to a factoring method that's good at finding small factors, such as Elliptic Curve Method. That is an astoundingly good way for find small factors, and for ECM, small can be 128 bits...

So, if $p-1$ consists of factors that are small enough for us to use, ECM can find them without much difficulty.

However, if we use a composite modulus, the size of the group is now secret. In other words, we've shifted the problem to finding the $q_i$ values. Here, ECM doesn't help us much; unlike the prime case, there isn't a convenient $p-1$ value we can hand to ECM. And, by making the $p_1, p_2$ values comparatively large, ECM just doesn't work the modulus directly.

What would work (to some extent) is the $p-1$ factoring method. There, we keep making guesses as to the various primes that make up $q_i$; if we guess all of them on one side (and there's no penalty, apart from wasting time, for incorrect guesses), then we factor. So, if we have a 64 bit $q_i$ value (and assuming the attacker knows that), he can guess all 64 bit primes; however there's about $2^{58}$ of them, so it'll take a while...

$\endgroup$
  • $\begingroup$ right, I missed the fact that in the non-prime case. The DLOG doesn't have to be "do-able" in $p_i - 1$ if $p_i - 1$ is smooth. So in the non-prime case you can use $p_i$ that are much larger than in the prime case $\endgroup$ – David 天宇 Wong Feb 7 '16 at 2:15
2
$\begingroup$

Indeed, in both cases an attacker has to factor the group order and compute logarithms in small subgroups, but in the non-prime case there is an additional step: factoring the modulus.

The standard algorithm for computing logarithms in smooth-order groups requires a factorization of the group order. Of course, If those factors are "small", anyone can compute such a factorization given the group order. This is where the difference lies:

  • For prime moduli $p$, the group order is just $p-1$, which anyone can trivially compute.
  • But suppose the modulus $n$ is a product of two large primes $p$ and $q$ such that $p-1$ and $q-1$ are smooth: Then the group order is $\lvert(\mathbb Z/n\mathbb Z)^\ast\rvert=\varphi(n)=(p-1)(q-1)$, which is also smooth, but computing $\varphi(n)$ without knowledge of $p$ or $q$ is generally hard. Notice the difference between factoring the group order (which is easy in both cases since it is smooth) and factoring the modulus (which is trivial in the prime case but can be very hard in the composite case). Therefore "anyone but us" cannot obtain the group order while "we" (having generated $p$ and $q$) of course can.
$\endgroup$
  • $\begingroup$ "but in the non-prime case there is an additional step: factoring the modulus", well you have to factor the order in the prime case $\endgroup$ – David 天宇 Wong Feb 7 '16 at 1:49
  • $\begingroup$ what I'm saying in my post is that factoring the modulus in the non-prime case is equivalent to factoring the order in the prime case. $\endgroup$ – David 天宇 Wong Feb 7 '16 at 2:11
  • 1
    $\begingroup$ ahh... I completely missed the fact that p_i-1 is smooth in the non-prime case, so the factors p_i can be way bigger $\endgroup$ – David 天宇 Wong Feb 7 '16 at 2:12

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.