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

Rob Meijer pibara at gmail.com
Thu Oct 15 04:41:18 EDT 2015


I am working on a opportunistic hashing implementation for a computer
forensic framework and I'm currently trying to objectively evaluate the
candidates for the hashing algorithm. Given that in computer forensics
there are many sources of 'known-good' and 'known-bad' that still use MD5
or a combination of SHA-1 and MD5 in the distribution of their data sets,
I'll need to come with convincing arguments to move forward from SHA-1 to
something like BLAKE2. I might even need convincing arguments to show if
MD5 is no longer acceptable. My current subjective take on this is that MD5
support should be considered depricated even for computer forensic purposes
and that I should probably aim for using a combination of SHA-1 with
BLAKE2-2bp to provide something of a transition path.

Collision-resistance arn't really in the threat model, but preimage
resistance of a sort is.  The thing is, given that most of the known-good
and known-bad hash sets are publicly available, it would be unacceptable if
it was practically possible to either create large amounts of known-bad
collisions as that would potentially create a DOS on the forensic process.
It also would be unacceptable if it was practically possible to modify
content to match any known-good hash as that would allow evidence to
falsely be discarded as known-good.

Now my question is: If a currently impractical preimage attack against a
hash function exists, but the threat model does not require a single hash
as result but a random hash from a large set of known hashes (in my case
somewhere between 2^26 and 2^28 individual hashes), how would the size of
this set of hashes influence the complexity of the attack; worst case?

Intuitively I would think if MD5 has a preimage attack of 2^116.9
complexity and a set of known hashes has worst-case size 2^28 entities,
than the worst-case combined attack complexity would be 2^88.9. But as
intuition has often proven to be a poor guide for me when cryptography is
concerned, this could be extremely pessimistic even to the extend that the
size of the hashset has zero impact on the complexity of the attack.

Could anyone share any insights on the true worst-case influence of the
size of the target hash set on the complexity of a pre-image attack ?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20151015/0087b5fb/attachment.html>


More information about the cryptography mailing list