3 ms·
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 ano
by 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 agoBut 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 agoAhh, 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 agoYou'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.
- baby 11y agoI 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.