[Cryptography] Name for a specific type of preimage resistance

[Michael Kjörling]

On 14 Dec 2022 13:21 +0100, from stephan.neuhaus at zhaw.ch (Stephan Neuhaus):
> On 12/13/22 11:32, Michael Kjörling wrote:
>> fixed-size output. For any input size larger than the output size,
>> which is likely to be the normal case for hashing in practice and
>> would certainly be a design criteria for a real-world hash function,
>> there _must_ exist more than one input that produces some given output
> 
> I've seen this assertion elsewhere on this thread, and it's just not true.
> While it is true that collisions must exist, it is not true that collisions
> must exist for *every* hash. It is exceedingly likely, but not necessary.

Which is precisely why I included the qualifier that immediately
followed what you quoted, and which you conveniently omitted. It read
"(though not _necessarily_ the _exact_ output you are working with)".

Which is to say, for a specific hash algorithm and _some subset of_
(possibly but not necessarily the entire set of) properly generated
output hash values, _given_ an input size larger than the output size,
there must _exist_ more than one input (preimage) which produces each
output value in that subset of outputs; but it is _possible_ that the
output hash value that you are looking at right then and there _is
not_ in that subset of output hash values, and therefore is one that
has only one single, true preimage.

I do agree that, with an effectively unbounded input size and a
bounded output size, especially if we are allowed to assume a
competently designed and reviewed cryptographic hash algorithm, the
probability of there existing output hash values which map uniquely to
exactly one preimage becomes exceedingly small. This becomes even more
the case if the preimage also needs to "make sense" by some criteria;
for example, it needs to consist only of valid English words encoded
using US-ASCII, or even just be valid, even if nonsensical, UTF-8.

The trick, of course, is to make it difficult to _find_ a preimage
(let alone some "valid" preimage according to some criteria; never
mind "the" preimage) that hashes to a given value, given only the
hash. But by, it seems to me, any reasonable interpretation, that's
not quite the question that started this discussion.

-- 
Michael Kjörling                     🏡 https://michael.kjorling.se
“Remember when, on the Internet, nobody cared that you were a dog?”