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

Zooko O'Whielacronx zooko at zooko.com
Thu Oct 14 00:56:19 EDT 2010


Dear cryptography at randombit.net:

I just sent this letter to a mailing list of SHA-3 designers. I
thought you might be interested in the general question.

Regards,

Zooko

Folks:

If a hash has 32-bit pre-image-resistance then this means an attacker
might spend about 2^32 resources to find a pre-image.

If a hash has 64-bit pre-image-resistance then this means an attacker
might spend about 2^64 resources to find a pre-image.

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? That is a meaningless possibility to discuss since 2^512
resources will never exist in the life of this universe, so it can't
mean that, or if it does mean that then there is no use in talking
about "512-bit collision-resistance". Maybe it means something else?

By analogy, suppose you considered the construction of a bridge that
withstood 10^3 tons of pressure. You could also consider a bridge that
could withstand 10^6 tons of pressure. If the bridge were to be
deployed in a situation where more than 10^3 tons but less than 10^6
tons might rest on it, then this would be a very important distinction
to make.

But what would it mean to discuss a design for a bridge that could
withstand 10^150 tons of pressure? Such an amount of pressure could
never be applied to the bridge. Would there be any value in a
distinction between one bridge design that would withstand 10^150 tons
of pressure and another that would withstand 10^300? Even though
neither of them could ever experience as much as 10^150 tons of
pressure, perhaps the latter bridge would still be safer against some
other threat -- an error on the part of the builders or designers or a
stressful event that was not included in the model which we used to
evaluate our bridges in the first place.

Or perhaps not. Perhaps the bridge which is designed to withstand
10^300 tons of pressure is actually *more* likely to fail than the
other one when hit by this unpredicted, unmodelled event. Who can
tell?

One reasonable position to take is that it was a mistake for NIST to
specify that some of the SHA-3 hashes had to have 512-bit preimage
resistance. (If it *was* a mistake the I really have no idea what to
do about it at this juncture!)

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".

Another reasonable position to take is that a hash function which is
known to have at most 384-bit pre-image resistance is *more likely to
fail* than one which is known to have at most 512-bit pre-image
resistance. This is where my limited understanding of hash function
cryptanalysis comes to an end. Is that plausible? 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? How sure are you? Is it possible that it would be the other
way around--that you would discover a method of finding pre-images in
the latter before discovering a method of finding pre-images in the
former?

If someone who has real hash function cryptanalysis expertise and who
takes the latter position could explain what they mean by "more likely
to fail", then I would be fascinated to hear it.

In any case, I'm pretty sure that as a *user* of hash functions what I
care about is "more likely to fail" (and efficiency), not about "bits
of security" for any bit-level greater than about 128 (including
consideration of quantum attacks, multi-target attacks, etc.)

Thank you for taking the time to read this.

Regards,

Zooko Wilcox-O'Hearn



More information about the cryptography mailing list