Phillip Hallam-Baker <phill(_at_)hallambaker(_dot_)com> writes:
On Tue, Aug 4, 2015 at 9:08 AM, Derek Atkins <derek(_at_)ihtfp(_dot_)com>
wrote:
Phillip Hallam-Baker <phill(_at_)hallambaker(_dot_)com> writes:
> Luckily my computations (which you unfortunately cut out) were based
on 30
> million attempts per second, so my results (the attack taking over a
year)
> is still correct! Indeed, your numbers are still 3x slower than my
> computation estimates.
>
> Your original assertion was broken. I don't think it very likely that
someone
> is going to spend more than a machine year to generate a vanity key
unless they
> can get someone else to pay for the time.
Phill, it was *your* proposal that I was talking to, Mallet creating
keys M1 and M2 to attack some open source project using PGP Signatures.
That is not a vanity fingerprint, it is an attack. A vanity fingerprint would
be doing a brute force search for a key whose fingerprint begins
MINIO-Nxxxx-xxxxx-xxxxx-xxxxx
The "MINIO-Nxxxx-..." vanity fingerprint issue is yet another issue you
brought up, which is still different than this one. Yes, a vanity key
fingerprint is definitely less work because there are many fewer bits
that you care about. There's really no way to disallow it that I can
see, but we should definitely remind people to always check the full
fingerprint.
Spending a hundred computer years to insert malware into an open source
project
is a much more probable attack.
I think you're mis-remembering your attack setup. The hundred
computer-years effort is for someone to generate two keys that have the
same matching truncated-to-100-bits fingerprint to use in a broken
source code control system that only checks the truncated hash. But
it's more than that; Mallet has to be trusted to actually push data into
the source repository in the first place.
For your attack scenario to succeed Mallet needs to generate both keys
prior to being added to the project and only then will he be able to
surrepticiously add code. Of course Mallet needs to have been trusted
enough to get M1 added to the authorized commiters list first! My point
is that finding an adversary that is trusted enough to get M1 added, and
also a bad player such that they generated an M1 and M2, is probably
going to be hard, because they have to control BOTH keys and generate
them together. It also depends on this broken truncated-hash system.
That's why I find that attack scenario unlikely.
More likely Mallet would want to find a key that matches an already
trusted key. This is NOT a collision attack but is a preimage attack;
you know the hash result and need to find a second item that matches.
Luckily that's still a 2^N and not a 2^(N/2) attack, so unachievable
even with your 100-bit truncated hash system.
So thank you for acknowledging that your original assertion was broken!
My point was that particular notion isn't viable; nobody is going to
expend that much effort just to be able to spoof a broken source control
system. And moreover, a non-broken system (that uses the full
fingerprint) is still out of reach even for stronger adversaries.
The moral here is to use a sufficiently long fingerprint. But the point is
that
the fingerprint is indeed subject to birthday attack under rare circumstances.
I do agree with this.
> A hundred machine years for creating a key collision attack is
completely
> viable.
It's only a hundred machine years for a 100-bit collision. A 160-bit
collision is much much further out!
Yes, but if you didn't have to worry about a birthday attack at all, 80 bits
would be acceptable by that metric.
The point is that 80 bits is sufficient for a KeyID type use but a fingerprint
should be at least 160 bits. 100/125 and 256 offer some safety margin.
Agreed, which is why we should tell people not to truncate! :)
> Also when we are talking about PGP Key fingerprint, the fingerprint is
over the
> key binding and not just the key and so it is malleable.
I don't see how that helps (today) with SHA1 or SHA2.
If you are doing RSA, it greatly reduces the cost of a collision attack as you
can avoid the need to generate new keypairs on each trial. But I don't think
that is important as we are going to ECC in the near future anyway.
-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