On Feb 15, 2012, at 11:56 45AM, Ben Laurie wrote:
> On Wed, Feb 15, 2012 at 4:13 PM, Steven Bellovin <[email protected]> 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
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
