Offline RSA strong prime test similar to Phuctor?

Question

One of the ways that RSA keys get consistently owned is when they're generated without enough entropy. Dan Kaminsky refers to a study which found that 1 in 200 RSA keys were badly generated and these were the ones that were found, not to mention the millions of others that were not found.

Thus, a good, properly seeded RNG is needed during RSA keypair generation for GPG, SSL, SSH, etc. wherever RSA key generation happens.

Phuctor is an online tool which searches for PGP RSA key pairs and factors them. Surprisingly, they even factored a 4096bit RSA key in the strong set which was badly generated with the first factor being the number 231 (3 * 77). (According to Polynomial, they only factored a corrupt subkey, which should have no real-world impact.)

When I'm generating RSA public/private keypairs for SSL, SSH, GPG, etc., is there an offline tool I can use to determine how hard and how large the primes are? Can I estimate the computational difficulty in factoring this given RSA key pair so I can determine whether they were generated properly?

Obviously, I use a secure desktop computer for key-pair generation (and optionally /dev/random), as Linux's RNG is seeded by "mouse and keyboard activity, disk I/O operations, and specific interrupts"(source, PDF) which virtual machines often don't have. While this should be enough, I like to understand the underlying methods and would like to test my key pairs to ensure security.

Answer 1

In general, there is no clear distinction between "hard to factor" and "not hard to factor" RSA keys. This is a continuum. For instance, the ECM algorithm (that uses elliptic curves in a smart way to factor integers) tend to have a computational cost that depends on the size of the smallest factor of the target integer. If you try harder then you can find larger factors. The consequence is that even if you spend one full day of computations to "try" with ECM your modulus for small factors, and find none, then you don't know if an attacker with more patience might not find a factor by devoting two days of computation.

There is no known method that can test a given integer and return the size of its factors, without actually recomputing the factors, which is (hopefully !) computationally infeasible for a proper RSA key.

Testing RSA keys after generation is a fool's quest. This is a nice thing to do to detect some poor implementations, not poor keys. Moreover, it detects only certain classes of poor keys (specifically, those with small factors). It does not detect poorly seeded RNG used in an otherwise correct RSA private key generation. This highlights an important point: while having very small factors is a sure sign of flawed key generation, having only large factors does not guarantee secure generation.

For proper security, ensure that keys are properly generated by auditing the key generation process, not the result.

Answer 2

How about the other keys we found? Some of them have valid self-signatures. As in, a naive user querying SKS for an email address without regard to fingerprint will be shown one of these as the top search result. And, for all we know, they will display a valid fingerprint on some broken PGP-compatible system.

If, as Mr. Böck would have us believe, we had found that 'cosmic rays' or 'disk corruption' are able to generate valid PGP key-self-signatures - we'd be collecting the gold at Stockholm for this find, rather than settling for this small change.

Answer 3

Offline RSA strong prime test similar to Phuctor?

Yes. https://github.com/gdisneyleugers/NED-RSA. I've tried it successfully against 128 bit keys. I haven't had the time yet to try it against 1024 bit keys, but it does work as advertised - weak values during generation result in weaker keys.