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

Nemo nemo at self-evident.org
Sat Feb 1 12:48:08 EST 2014

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

> Just to define my terms: Suppose I give you F(x).  If you can find x,
> then you can invert the function.

If the function is many-to-one (like, say, a hash function), then your
definition of "invert" is pointless because it is vacuously
impossible. For example, the function "x modulo 12" is non-invertible by
your definition. This has nothing to do with cryptography.

> If you can find *any* value y such that F(x)=F(y), whether y=x or not,
> you're finding a preimage.

If, on the other hand, the function is one-to-one (like, say, a block
cipher with a fixed key), then your definition of "invert" is equivalent
to your definition of "finding a preimage". Again, this has nothing to
do with cryptography.

Either way, it seems totally pointless to distinguish the concept of
"invert" from "find a preimage" in cryptography. And indeed I have not
seen this distinction in practice (see
e.g. http://en.wikipedia.org/wiki/One-way_function).

Or am I missing something?

 - Nemo

More information about the cryptography mailing list