[cryptography] Duplicate primes in lots of RSA moduli

Steven Bellovin smb at cs.columbia.edu
Wed Feb 15 22:30:44 EST 2012

On Feb 15, 2012, at 11:56 45AM, Ben Laurie wrote:

> On Wed, Feb 15, 2012 at 4:13 PM, Steven Bellovin <smb at cs.columbia.edu> wrote:
>> 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.
> I did this years ago for PGP keys. Easy: take all the keys, do
> pairwise GCD. Took 24 hours on my laptop for all the PGP keys on
> keyservers at the time. I'm trying to remember when this was, but I
> did it during PETS at Toronto, so that should narrow it down. With
> Matthias XXX (I've forgotten his surname!).

How many keys?  They had 11M keys, meaning there are 121e12 pairs.  That's
a lot of GCD operations...

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

More information about the cryptography mailing list