Would it be valuable to set up a service that could check your public keys against a database of others checking for common factors? Or just better to fix the entropy problems and assume the problem doesn't exist anymore?
I think the original article alludes to this but doesn't say it explicitly:
If they built such a service to let people test their own public keys, the service would actually provide a much bigger service to attackers than it would to users.
Public keys are public, right? There are huge LDAP databases out there just brimming with certificates (i.e. signed public keys) just waiting to be harvested. And most of the people whose certificates are in these databases would not be paying attention to this news, but an attacker certainly would.
Couldn't the service allow you to check your private keys, rather than check a public key, without transmitting the actual key.
You know (pub,priv). They know either (pub,priv) or (pub).
Essentially, make use of your unique (probably!) ability to sign something with your private key.
There's the issue of traffic analysis which needs to be solved - they have to reveal to you whether the key is compromised, and there's only two possible answers, so they have to be careful not to reveal it to in the traffic metadata.
Better yet, they can just publish something encrypted with every compromised public key. Only people with the corresponding private keys can ascertain if they're compromised.
