[cryptography] Duplicate primes in lots of RSA moduli

Steven Bellovin smb at cs.columbia.edu
Wed Feb 15 11:13:08 EST 2012


On Feb 14, 2012, at 10:02 PM, Jon Callas wrote:

> 
> On 14 Feb, 2012, at 5:58 PM, Steven Bellovin wrote:
> 
>> The practical import is unclear, since there's (as far as is known) no
>> way to predict or control who has a bad key.
>> 
>> To me, the interesting question is how to distribute the results.  That
>> is, how can you safely tell people "you have a bad key", without letting
>> bad guys probe your oracle.  I suspect that the right way to do it is to
>> require someone to sign a hash of a random challenge, thereby proving
>> ownership of the private key, before you'll tell them if the
>> corresponding public key is in your database.
> 
> Yeah, but if you're a bad guy, you can download the EFF's SSL Observatory and just construct your own oracle. It's a lot like rainbow tables in that once you learn the utility of the trick, you just replicate the results. If you implement something like the Certificate Transparency, you have an authenticated database of authoritative data to replicate the oracle with.
> 
> Waving my hand and making software magically appear, I'd combine Certificate Transparency and such an oracle be combined, and compute the status of the key as part of the certificate logs and proofs.


Note that they very carefully didn't say how they did it.  I have my own ideas -- but they're just that, ideas; I haven't analyzed them carefully, let alone coded them.

		--Steve Bellovin, https://www.cs.columbia.edu/~smb








More information about the cryptography mailing list