How does a non-prime modulus for Diffie-Hellman allow for a backdoor? 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.)
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$) is 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 for 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.