Re: [openpgp] Fingerprint requirements for OpenPGP

Daniel Kahn Gillmor <dkg@fifthhorseman.net> writes:

> On Tue 2016-04-12 13:22:46 -0400, KellerFuchs <KellerFuchs@hashbang.sh> wrote:
>> I think it is sane here to require collision resistence, because that's what
>>   multi-target preimages devolves to: an attacker might not want to target
>>   one specific key, but one amongst a large set of key (says, the developers
>>   of a popular software, or perhaps any “widely signed” key in the WoT).
>>
>> In that case, the attacker gets a non-trivial speedup, and as the set of
>>   targets grows larger, the hardness of the problem devolves into that of
>>   finding a collision.
>
> The size of the set of possible targets is relevant here, though, right?
> if the pool of available targets is 2^16, you're not going to get more
> than a 2^16 speedup by targeting them.  Even if we had a separate key
> for every IPv4 address, that'd only be a 32-bit reduction in work
> factor.
>
> by comparison, a pre-image brute force costs 2^(2X) when a collision
> attack costs 2^X due to the "birthday paradox".
>
> We're talking about fingerprints in the range of 2^160 (the OpenPGPv4
> fingerprint) and 2^256 (probably the upper bound of what we can expect
> humans to be able to deal with).
>
> so you'd need a pool of keys to attack on the order of 2^80 or 2^128 to
> get a comparable speedup.

This was my thought, too.  The pool isn't going to get large enough to
really bring the preimage work down to collision-level work.

>> Moreover, colision resistence implies second-preimage resistence, and hash
>>   functions are usually considered “broken” by cryptographers once there is
>>   an attack for colisions, so it seems OK to be somewhat cautious here and
>>   require collisions to be hard.
>
> I think we're in quite a bit of trouble if we actually need both
> collision resistance and any sort of plausible human-accessibility for
> high-entropy strings.
>
>           --dkg
>
> _______________________________________________
> openpgp mailing list
> openpgp@ietf.org
> https://www.ietf.org/mailman/listinfo/openpgp

-- 
       Derek Atkins                 617-623-3745
       derek@ihtfp.com             www.ihtfp.com
       Computer and Internet Security Consultant