4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

The hypothesis

it's assumed data items are completely random in their hash values for all practical purposes

is unrealistic (it is very easy to build data items which hash values are even). Fortunately, we can do with:

  1. preparation of the dataset involved computing no more than $N$ hashes
  2. the hash used is a cryptographically secure $M$-bit hash
  3. the user has in mind some specific value $\epsilon$ for the risk of matching error across the entirety of data items stored, such that $0<\epsilon\ll 1$ (and probably $\epsilon<10^{-\text{lots}}$ ).

If $N\le\sqrt{2^{M+1}\epsilon}$ then the security goal is met; that follows from the definition of a cryptographically secure hash, and the square approximation of the birthday problem.

If we use $M=256$ (say SHA-256, assuming this remains unbroken), and want $\epsilon=10^{-18}>2^{-60}$ (one chance in a million million million), then we are good for up to $N=2^{98.5}$ (over 4 hundred thousand million million million million hashes used to prepare the dataset), which is significantly more hashes than was ever computed by mankind as of 2017.

$\endgroup$
  • $\begingroup$ More specific, and technically detailed answer, which is what I hoped for. (FWIW: "Assuming SHA256 remains unbroken" - breaking isn't so much of an issue in this situation other than in some very unlikely attack by trying to get a confounding file on a file server with the hope of causing a misread of a different file, which is hard as it assumes matching of records or data block, not just raw files or certain fields, not a concern for this situation or for now) $\endgroup$ – Stilez Mar 7 '17 at 8:22
  • $\begingroup$ @Stilez: in IT, only the paranoids can be confident that they'll stand unharmed by the nastyness of users. Look at what happened to github in late Feb 2017: it uses SHA-1 precisely for the purpose of recognizing distinct files; collision-resistance of SHA-1 is broken; within days, it becomes easy, then common, to upload different files with identical content to github, causing some level of mess (more mess is caused by faulty patches trying to prevent that). $\endgroup$ – fgrieu Mar 7 '17 at 8:28
3
$\begingroup$

This short calculation might address some of your concerns:

Lets assume we are talking about 10^15 datasets of 4KB. That's about 3.6 Exabytes of data and 10^15 hashes.

From the table at: https://en.wikipedia.org/wiki/Birthday_attack we get that given 4.8 10^29 hashes are needed in order for the possiblity of a brithday attack to reach 10^-18 when using a 256-bit hash function like SHA-256.

So in my opinion there is a lot of headroom for the hashfunction not being perfectly uniform distributed. I don't think that there are worries about SHA-256 security. A practial example is the use of SHA-256 in Bitcoin - about 3.2 * 10^18 hashes are computed for mining Bitcoin every second (https://bitcoinwisdom.com/bitcoin/difficulty).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.