4 ms·

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)

• 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.
      • pbsd 11y ago
        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.
• 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.