A letter I wrote to the SHA-3 mailing list in 2010: From: Zooko O'Whielacronx To: hash-forum Date: 2010-10-14 03:46 UTC Folks: If a hash has 32-bit pre-image-resistance then this means an attacker might spend about 2³² resources to find a pre-image. If a hash has 64-bit pre-image-resistance then this means an attacker might spend about 2⁶⁴ resources to find a pre-image. What if a hash has 512-bit pre-image-resistance? What would that mean? That an attacker might spend about 2⁵¹² resources to find a pre-image in it? That is a meaningless possibility to discuss since 2⁵¹² 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 pre-image-resistance". Maybe it means something else? By analogy, suppose you considered the construction of a bridge that withstood 10³ tons of pressure. You could also consider a bridge that could withstand 10⁶ tons of pressure. If the bridge were to be deployed in a situation where more than 10³ tons but less than 10⁶ 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¹⁵⁰ 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¹⁵⁰ tons of pressure and another that would withstand 10³⁰⁰? Even though neither of them could ever experience as much as 10¹⁵⁰ 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³⁰⁰ 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 then 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 you 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