In a lot of data management systems, a hash is used as a kind of data fingerprint, with the intent not to cryptographically defeat an opponent, but to quickly identify duplicate data by seeing if other data with the given hash already exists in the system.
An example of this is data deduplication in the ZFS filing system, which can use fletcher-4 (for a quick exclusionary check) or sha-256, and optionally can also check byte-for-byte if a matching hash is found, to confirm if it's a chance match of different data, or is genuinely a duplicated data item.
If a hash function is used this way, the number of records can be huge - think of something like Amazon's cloud system or another major data store, and imagine dedup running on 4k-128k blocks of data. So the number of ways a collision can happen goes up combinatorially, and much like the well-known chance of people sharing a birthday, a very unlikely event (2 different files or data items/file blocks having different data but the same hash) becomes unexpectedly likely.
The problem is that if data X and data Y have the same hash, and byte-for-byte isn't checked on match, then when a file contains Y, the system will return X instead as it's stored one copy believing the data the same for X and Y on the basis of their matched hash.
Assuming the data store host wants a guarantee of no misidentification, they would probably have to check byte-for-byte. But if they are prepared to accept some small theoretical risk (say 10^-20) of a matching hash not representing matching data for any data in the pool, then they need to figure how "strong" a hash to use and whether to back it up by bytewise checking on a match, to obtain that risk. My question is, how should they make that decision (in theory and in practice).
In theory it seems easy enough, given nice idealised assumptions:
- the dataset contains N items whose uniqueness will be determined by comparing hashes,
- a given hash function is believed to produce true "random" output across 2^M values of output (all values equally likely, or whatever the correct expression is, which is tested when modern hash functions are scrutinised),
- the user has in mind some specific value E for the risk of matching error across the entirety of data items stored, such that 0 < E << 1 (and probably E < 10^-lots),
and - it's assumed data items are completely random in their hash values for all practical purposes (the data isn't such as to enhance the risk of a mismatching situation between any two data items being hashed)
then it's not hard to calculate if the hash is likely to deliver this.
But in practice this might be a wildly inappropriate way to assess the risk. Perhaps there may be some bias in hash values; the cost of an error may be large and the risk required to be very tiny (and perhaps the hash isn't quite as perfectly random if a sufficiently tiny probability is sought?); the dataset may contain many data items that are closely related (4k blocks from variants or derivatives of common files); the cost of bytewise checking may be substantial suggesting a halfway solution of a "stronger" hash with few expected exceptions and bytewise checking those few data items only, and it's not clear in any case what value of E would be considered "sensible" in a given scenario and how to assess that.
I can't take this thinking any further as I lack the specialist knowledge for it - details of hashes and perhaps other crypto related issues I haven't thought of. The bottom line is about how one to evaluate from a crypto as well as practical perspective, the choice of hash + choice of whether or not to back up apparent hash collisions with bytewise checking, for a huge dataset.
Can someone with cryptography knowledge and also practical knowhow suggest how this kind of decision might best be addressed by a person planning a new dataset or record store where it's a potential issue? Is it "likely" in amy case to be an issue with modern hashes such as SHA256 on a large/huge dataset (whatever that word might mean!) and if so at what point?
