October 14, 2010

philosophical question about strengths and attacks at impossible levels

Zooko writes to SHA-3 designers for the NIST hash competition:.


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.


Zooko Wilcox-O'Hearn

Posted by iang at October 14, 2010 12:30 AM | TrackBack

Analogies are a great way of discussing problems that you don't quite understand in terms of something that you do. Also sometimes analogies can be poorly choosen. I think we've got a bit of both here.

I think a bridge is a poor analogy because a bridge is a whole system, a hash function is a component of a whole cryptosystem. So if for hash function we substitute steel rod and consider this rod in the system of a bridge I think we've got a better analogy.

This immediately throws up how ignorant we are about whole cryptosystems. We understand how a steel rod in a bridge behaves - finite element analysis has become so good that the other day I was looking at 3D renderings of how an element from a car's crash absorber would collapse under certain loads alongside actual photographs of the same part experimentally tested and the crushed and twisted metal matched the prediction fold for fold. I defy anyone to make equally good predictions about cryptosystems of practical levels of complexity.

Back to the actual analogy. When choosing a steel rod as part of a whole bridge system there are elements beyond the simple mechanical strength of that part versus the applied load. Is the load multiplied by stress raisers such as bolt holes or welds? Is the applied load below the fatigue limit for this material? What is the strength of the material after it has been corroding for twenty years?

Posted by: Ian Mason at October 14, 2010 10:27 AM
Post a comment

Remember personal info?

Hit preview to see your comment as it would be displayed.