This is a lot more interesting than I thought it would be from the title.
Obviously, anyone can trivially generate "backdoored" Diffie-Hellman parameters; for instance, just use a bogus generator that locks the algorithm into a tiny subgroup. No matter what private keys Alice or Bob generate, the DH computation will be predictable.
This writer wants to do something cooler: generate NOBUS parameters, in the fashion of Dual_EC DRBG, so that the parameter's authors can predict DH computations but (without Significant effort) nobody else can.
Several of the methods the writer is playing with involve DH parameters for which they can use Pohlig-Hellman to recover secrets. Pohlig-Hellman breaks DH when its victims are unfortunate enough to be in a group with a smooth order --- that is (I'm butchering this), when the group order factors into small primes. It works by collecting samples from the target for each factor of the group; each leaks a bit of the key modulo that factor. You knit the samples together with CRT.
Obligatory plug: a fun version of this attack is the kick-off problem on Sean Devlin's very excellent Set 8 of the Cryptopals challenges. Set 8 isn't on the website, but you can mail him (finding him is an exercise for the reader) to get a copy (on the honor system, like the other challenges were before we published). Set 8 builds this attack to an extremely useful attack on Elliptic Curve Diffie-Hellman.
Several of the methods the writer is playing with involve DH parameters for which they can use Pohlig-Hellman to recover secrets. Pohlig-Hellman breaks DH when its victims are unfortunate enough to be in a group with a smooth order --- that is (I'm butchering this), when the group order factors into small primes. It works by collecting samples from the target for each factor of the group; each leaks a bit of the key modulo that factor. You knit the samples together with CRT.
I'm not entirely sure how this gets you NOBUS parameters though. You can find any small prime factors of the group order using ECM, so if you're relying on those to let you run Pohlig-Hellman then everybody else can do it too.
(But in any case, you should be locking down your DH implementations to use a fixed nothing-up-my-sleeve group, so even if this is a backdoor it would be a backdoor with flashing neon lights around it.)
The idea is to hide the factorization of the group order by using a composite modulus, e.g., p = q . r, where q and r are kept secret. Now the order (q-1)(r-1) is safely protected from ECM (though not from Pollard's p-1, if the order is smooth enough). Better yet, make it p = q . r . s and make each of q, r, and s be safe primes, using index calculus instead of Pohlig-Hellman to find the logs quickly. Yes, I agree that this is as glaring a backdoor as it gets.
For what it's worth, the author missed that interpreting the modulus bytes as 16-bit words in little-endian order does get us a prime, though still not a safe one.
this is targeting ephemeral diffie-hellman. So this would work on any library/private product where you can "hey guys, we should start using 2048bits for DHE, let me suggest this one". This would not work on DH/RSA/... because people usually generate their own parameters for these.
If this remark was pointed at the fact that ECDHE > DHE: I'm not taking the point of view of an implementer trying to implement "new" crypto, I'm trying to take the point of view of a backdoorer (?) trying to push this backdoor in various products/libraries. And it seems like most still use DHE (some stats are in the logjam paper, but I'll do some stats myself out of scans.io when I get time)
the repo is a bit of a mess right now (current research). The p-1 factorization technique doesn't work because of the factor is large enough.
There is also another method that I use that hides the generator's subgroup with a composite modulus.
Both methods are NOBUS and are easy to exploit (no need for index calculus)
> For what it's worth, the author missed that interpreting the modulus bytes as 16-bit words in little-endian order does get us a prime, though still not a safe one.
I'm reading that over and over again and still don't understand what you're pointing at, care to expand?
But index calculus is the right way to do it, and it's not particularly difficult to exploit. P-H only puts a quadratic (at best) factor between you and an attacker; index calculus makes that gap subexponential.
Below is the prime number corresponding to the interpretation of the byte array I was speaking of:
Ahh, you were talking about the Socat modulus. I did miss that! Was it said somewhere or did you find it yourself? I'll check that later but nice finding!
> But index calculus is the right way to do it, and it's not particularly difficult to exploit. P-H only puts a quadratic (at best) factor between you and an attacker; index calculus makes that gap subexponential.
Right now it just doesn't make sense to use index calculus. Method1 is to use a hidden (by the composite modulus) subgroup of small order for the generator. So for a 1024bits modulus, you would either try to do index calculus in a 512 bits modulus or do something like Pollard Rho with a small order.
For the second method you use Pohlig-Hellman on small orders as well, so it wouldn't make sense to use index calculus on a 512 bits modulus again.
Now imagine a 2048bits main modulus n=pq, the problem is now split into two 1024bits modulus p and q. There is no way you can use IC there. But the method I "explained" previously will work. The backdoor will be a NOBUS.
You're misrepresenting my suggestion. The idea is to choose the factor size according to the complexity of ECM; the modulus size is irrelevant. So for a 2^80 security level, you choose factors of ~341 bits; relaxing the security to a 2^64-ish place, you can get away with 256-bit factors. This makes index calculus very quick, even on modest hardware, especially considering that the individual logarithm phase---the part you need to do in real-time---is much faster than the whole thing.
I see what you mean, but I don't see any reason to use NFS on the maximum sized group when you can reduce the size of that group (by using a generator of a "small" subgroup modulo each factor) and use a quicker Pollard Rho modulo each factors. You already have a significant advantage and you don't need any heavy pre-computations with NFS.
By doing it your way, you do increase both my computation and the reverser's computation who tries to do Pollard Rho on the full subgroup size. Which is good, but what I found is that this is not necessary as doing it my way is already too hard for someone with no knowledge of the factors to use.
They appear to be mysterious, magic numbers in every single crypto implementation. And many are written in byte form. I mean how can people comprehend them?
People generate large primes using programs designed to do that, and maybe generators/primitive roots for those primes using a CAS like Sage or Octave/Matlab. The same goes for ECC crypto, with a lot of extra testing/filtering to find "nice" constants.
A lot of the other giant numbers you see in cryptosystems are random numbers derived from other constants.
Sometimes there are things to learn by studying the numbers themselves. For instance, the prime field in Curve25519 is a special prime with (bit-level) characteristics that make it especially nice to do math on with general-purpose computers. Other times, the numbers are, for instance, just giant random primes, and aren't themselves very interesting.
Obviously, anyone can trivially generate "backdoored" Diffie-Hellman parameters; for instance, just use a bogus generator that locks the algorithm into a tiny subgroup. No matter what private keys Alice or Bob generate, the DH computation will be predictable.
This writer wants to do something cooler: generate NOBUS parameters, in the fashion of Dual_EC DRBG, so that the parameter's authors can predict DH computations but (without Significant effort) nobody else can.
Several of the methods the writer is playing with involve DH parameters for which they can use Pohlig-Hellman to recover secrets. Pohlig-Hellman breaks DH when its victims are unfortunate enough to be in a group with a smooth order --- that is (I'm butchering this), when the group order factors into small primes. It works by collecting samples from the target for each factor of the group; each leaks a bit of the key modulo that factor. You knit the samples together with CRT.
David wrote this up well here: https://www.cryptologie.net/article/196/pohlig-hellman-algor...
Obligatory plug: a fun version of this attack is the kick-off problem on Sean Devlin's very excellent Set 8 of the Cryptopals challenges. Set 8 isn't on the website, but you can mail him (finding him is an exercise for the reader) to get a copy (on the honor system, like the other challenges were before we published). Set 8 builds this attack to an extremely useful attack on Elliptic Curve Diffie-Hellman.