Re: [openpgp] Followup on fingerprints

[Derek Atkins <[e-mail]>]

Phillip Hallam-Baker <[e-mail]> writes:

> On Tue, Aug 4, 2015 at 9:08 AM, Derek Atkins <[e-mail]> wrote:
>
>     Phillip Hallam-Baker <[e-mail]> 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
       [e-mail]             www.ihtfp.com
       Computer and Internet Security Consultant