On Tue 2016-04-12 13:22:46 -0400, KellerFuchs
<KellerFuchs(_at_)hashbang(_dot_)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.
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(_at_)ietf(_dot_)org
https://www.ietf.org/mailman/listinfo/openpgp