3 ms·

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

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.)

pbsd 11y ago
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.
- tptacek 11y ago
  I feel like maybe Colin is missing the point a little. Obviously it's a terrible backdoor simply by dint of targeting conventional DH. But it's a really fun exercise!
  - baby 11y ago
    > targeting conventional DH 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)
- baby 11y ago
  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?
  - pbsd 11y ago
    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: 3c6d8e07b9ec437a4177a6c5efbc95994aaf1246780e7d17 4d7f75538ecebfabf5af04f66d4f37f086734a0b046928ac bdbb8f7a43c8d38df5f890a8d66dfc00c6058e9908c6609b 03bff987e840bc0ecbbfc857cbc822bf941c9259255f5b22 cea945a2d8a91694b3bfa7bcc1cee388550cb8263e0e46c5 59a496dff2dccc17
    - baby 11y ago
      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.
- cperciva 11y ago
  Ah, I missed the "composite modulus" bit. Right, that could provide NOBUS, at the expense of being even more glaringly obvious.
- baby 11y ago
  > this is as glaring a backdoor as it gets which lasted a year in Socat. I wonder how long this would last in a closed source project.

pbsd 11y ago

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.

tptacek 11y ago
I feel like maybe Colin is missing the point a little. Obviously it's a terrible backdoor simply by dint of targeting conventional DH. But it's a really fun exercise!
- baby 11y ago
  > targeting conventional DH 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)
baby 11y ago
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?
- pbsd 11y ago
  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: 3c6d8e07b9ec437a4177a6c5efbc95994aaf1246780e7d17 4d7f75538ecebfabf5af04f66d4f37f086734a0b046928ac bdbb8f7a43c8d38df5f890a8d66dfc00c6058e9908c6609b 03bff987e840bc0ecbbfc857cbc822bf941c9259255f5b22 cea945a2d8a91694b3bfa7bcc1cee388550cb8263e0e46c5 59a496dff2dccc17
  - baby 11y ago
    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.
cperciva 11y ago
Ah, I missed the "composite modulus" bit. Right, that could provide NOBUS, at the expense of being even more glaringly obvious.
baby 11y ago
> this is as glaring a backdoor as it gets which lasted a year in Socat. I wonder how long this would last in a closed source project.