[cryptography] philosophical question about strengths and attacks at impossible levels

Zooko O'Whielacronx zooko at zooko.com
Thu Oct 14 23:09:49 EDT 2010


I like the way you think.

On Thu, Oct 14, 2010 at 12:32 PM, Marsh Ray <marsh at extendedsubset.com> wrote:
>>
>> What if a hash has 512-bit collision-resistance? What would that mean?
>> That an attacker might spend about 2^512 resources to find a collision
>> in it?
>
> The attacker can match any hash he generates with any other, not just one
> specific target value.

Mea culpa as I earlier posted. This is actually an edit-o and I'm embarrassed.

> Without saying whether or not I agree with it, here's my guess as to how a
> 512 bit output length might be justified:
>
> 1. The output hash value must be a power-of-two number of bits long, because
> everyone likes it that way.
>
> 2. If the hash value were 256 bits long it could have no better than about
> 128 bits collision resistance.
>
> 3. There are quantum computer attacks theorized which appear to cut the
> exponent in half again. Thus a 256 bit hash could possibly be collided in
> 2^64 operations on some future machine.

This part is a technical mistake, see
http://cr.yp.to/hash/collisioncost-20090517.pdf . I wouldn't be
surprised if you are right that this is how NIST came up with the
requirement for a 512-bit hash function though.

> Case in point: AES-256 appears to be significantly broken in a way that
> AES-128 is not.

A good example. One can argue about whether that weaknesses (a very
expensive related-key attack) ever really matters in practice, but you
do have to argue it—one can no longer simply assert that AES-256 is a
Pareto improvement over AES-128. The fact that you can't simply assert
that anymore shows that this "bit strength" measurement may not
predict future practice.

>> That position says that there *is* a need for a hash function which
>> takes much more CPU time than SHA-3-256 does in order to provide much
>> less likelihood that an attacker will be able to find a pre-image in
>> it than in SHA-3-256, but that this "much less likelihood" is not in
>> any meaningful sense correlated with the idea of having "512-bit
>> pre-image resistance".
>
> You won't find many people requesting that their hash function take more
> time.

I think if you want a hash function to be much less likely to fail at
pre-image resistance (without being much more likely to fail at
collision-resistance) then you need to increase the amount of
computation performed (while keeping the state size the same or
larger). For example, you could take SHA1 and double the number of
rounds. This would take twice as much CPU and it would be *much* less
likely to fail at pre-image resistance than SHA1. (Whether it would be
*more* likely to fail at collision resistance I'm not sure.)

Likewise I think if you are willing to throw more state at it
(double-width pipe, big fat sponge) and throw a proportionally greater
amount of CPU at it, you are can make any reasonable hash function
much less likely to fail at collision-resistance. So I do think there
is a (fuzzy) trade-off between computational efficiency and safety
here. This implies that the fastest SHA-3 candidates are the least
safe. ;-)

>> If I give you two
>> hash functions like that, are you confident that you could learn how
>> to find pre-images in the former before they find pre-images in the
>> latter?
>
> You mixed 'you' and 'they' there, so I'm not sure exactly the question.

Another edit-o. You are they.

> My guess is that there's not a chance in hell of actually constructing a
> preimage in any reasonably well designed 384-bit or longer hash function.
>
> So my only hope is for one of the functions turns out to be utterly broken,
> worse than even MD5, and this isn't directly related to the 384 vs 512 bit
> preimage resistance. (It would be interesting to know the actual output
> lengths of the functions. A 384-bit output length might suggest that
> function was better designed than a 512-bit output function that only
> delivered 384 bits of preimage resistance).

Yep, my intuitions about this match yours.

Regards,

Zooko Wilcox-O'Hearn



More information about the cryptography mailing list