Identifying a bad public key

Question

The great thing about public key cryptography is that anyone can generate a keypair, keep the private key secret and publish the public key anywhere they want. This is used in CAs where an administrator presents a CSR containing a public key and gets a certificate back with the same public key signed. It's also used by Github to allow users to do Git operations via SSH.

Both asymmetric keys and passwords can thus used as a credential. There's a lot written about best practices for passwords, but I was wondering if there are also similar best practices for asymmetric keys? Length is a factor of course (the internet tells me that my RSA key should be at least 2048 bits and that my ed25519 key should be at least 256 bits). Still, even when a key has the correct length, it may be generated by a bad random generator (Debian key).

Do (should) services where the customer has to provide a public key, check this public key for weaknesses? What kind of weaknesses could a key be tested for? How would you test for these?

Some tests that I think might be useful:

• The bit length is appropriate for the algorithm the key is used for (best practices?)
• The key is not a known compromised key (public databases?)
• The key is not generated using a bad random generator (how would you test this?)

Answer 1

Do (should) services where the customer has to provide a public key, check this public key for weaknesses? What kind of weaknesses could a key be tested for?

I'm pretty sure that there's no easy way to find out if a public key has been generated safely without some sort of brute-force attack.

Ultimately I think it's up to the creator of the public key to make sure that the generated key has been created in an orderly fashion, i.e. by using a secure CSRNG. So services should probably not check public keys provided by customers for weaknesses.

The three tests that you have listed are generally good ways to check for possible weaknesses (if you would want to do so). Your second point though (The key is not a known compromised key (public databases?)) might be very inefficient, depending on how large such a public database could be.

---

How would you test for these?

• The bit length is appropriate for the algorithm the key is used for (best practices?)

A list of recommended key lengths: BlueKrypt.

• The key is not a known compromised key (public databases?)

If the database consists of the factors (in case of RSA), you could just try to divide a public key with all these factors and see if it results in a whole number. If the database only consists of public keys (in case of RSA), you could use the Euclidean algorithm and go through all keys in the database.

• The key is not generated using a bad random generator (how would you test this?)

Unknown, unless you know which tool was used to generate the key.