Phillip Hallam-Baker <phill(_at_)hallambaker(_dot_)com> writes:
On Fri, Jul 31, 2015 at 9:28 AM, Derek Atkins <derek(_at_)ihtfp(_dot_)com>
wrote:
Daniel Kahn Gillmor <dkg(_at_)fifthhorseman(_dot_)net> writes:
>> At this point, any attempt to hold Mallet accountable is going to have
to
>> rely on a human examining the logs and working out that Mallet must
have
>> generated the malicious pair of keys. There is going to be no way to
unwind
>> the thing automatically.
Why? M1 and M2 are completely different fingerprints, unless you're
assuming that the x's are the same. If the x's are the same that means
that Mallet has performed a 2^50 level attack to get 100 bits to match!
How long and how much energy does Mallet have to do this? It's
certainly not something s/he is going to do over a long weekend!
Not with RSA keys. With ECC keys, different matter entirely.
Even if you could do 30,000,000 ECC key generations per second (I think
my laptop can do about 3,000-10,000 -- I'm not sure how to measure that
beyond running an openssl speed test), and also assuming the SHA hash to
compute the fingerprint is "free", to do 2^50 keygen + sha computations
would still take 37,529,996 seconds or 434 days, which is over a year!
Remember, the fingerprint is over the public key, so you still have to
actually perform the ECC g^x operation for each trial.
So no, this is not something Mallet is going to be able to do over a
weekend without expending a LOT of effort and cost. I guess if they had
access to a few hundred really beefy machines (and the electricity to
power them) they might be able to accomplish this feat. So sure, maybe
a large corporation or gov't agency could perform this kind of Mallet
attack, but generally not some teenager sitting in their basement.
Maybe in a decade or two this will be feasible to a singleton.
This of course is still based on your (rather forced) 100-bit truncated
hash concept. If applications use the full 160-bit fingerprint (or more
if we migrate up to a larger hash) then a 2^80 attack would still be out
of reach.
-derek
--
Derek Atkins 617-623-3745
derek(_at_)ihtfp(_dot_)com www.ihtfp.com
Computer and Internet Security Consultant
_______________________________________________
openpgp mailing list
openpgp(_at_)ietf(_dot_)org
https://www.ietf.org/mailman/listinfo/openpgp