[Cryptography] How does the size of a set of target results influence the complexity of a preimage attack?

[Zooko Wilcox-OHearn]

I don't believe that forensics is really safe with
collision-vulnerable but pre-image-resistant hash functions.

What if a bad actor generates a malicious or illegal file with the
same MD5sum as an innocuous file and then submits the innocuous one to
the forensics databases? How do we know that isn't already happening?

That would be using collisions to do something bad in your use-case
1), but I suspect similar collision-based attacks could apply to the
other two use-cases.

Anyway, the reason we made sure BLAKE2 was faster than MD5 was so that
we wouldn't have to have this conversation. ;-) Just switch to BLAKE2.
It's faster *and* more secure.

In answer to your question, yes, I think the difficulty of finding a
2^M pre-image for any of 2^N different images is indeed 2^{M-N}.

Regards,

Zooko