[Cryptography] Pre-image security of SHA-256 reduced to 16 rounds

[Nemo]

John Kelsey <crypto.jmk at gmail.com> writes:

> No, this is a really important distinction, and one that otherwise
> pretty savvy people get mixed up all the time.

I disagree; I think the distinction is irrelevant. Let me try once more.

> Here's an example: If you have a smaller Keccak variant with a
> capacity of 80 bits, both collisions and preimages are easy to find
> with 2^{40} work.  However, suppose you have recovered a password file
> with lots of entries using this weak hash function.  The 2^{40}
> preimage attack doesn't help you *at all* in recovering passwords from
> the file.

You seem to be missing my point, which is this: *It is impossible to
invert any hash function, ever, by your definition*. In general, for any
output y, there are many (or an infinity) of possible inputs x such that
f(x) = y. If all you know is y, even if you can determine *every*
possible x, you have no way to know which was the actual input.

To make your definition of "invert" meaningful, you need to incorporate
a distribution of possible inputs, and then say something like "to
invert a hash function at y means to determine the _most likely_ input x
such that f(x) = y". But I have never seen such an elaborate definition,
either in a theoretical context or a practical attack. Have you?

What I have seen is the simple definition "To invert a function f at y
is to find any x such that f(x) = y", followed by the simple definition
"A one-way function is easy to compute but hard to invert". (The only
subtle part being the definitions of "easy" and "hard".)

I do not see how adding additional complexity to these definitions
contributes anything other than confusion.

 - Nemo
   https://self-evident.org/