4
$\begingroup$

Assume that I have a huge file, which I split up into blocks. Each block is hashed with a hash function of $x$ bits. The chance of an error going undetected in a block should therefore be $1/2^x$.

Now, let's assume a block is $y$ bytes in size, meaning there are $2^y$ possible values for that block of data. As $y$ gets bigger, there are more possible collisions for any given hash value, yet the chance of such a collision occurring seems to remain the same (correct?).

For my purposes, I need to split the data in many blocks, the more the better, but the more blocks, the more hashes which at some point take quite a lot of space to store. So I want to use a hash where $x$ can be small while still having a high chance of detecting errors.

So I got this idea that instead of hashing every block with a hash function of $x$ bits (illustation 1), I instead hash every block with a hash of $x/2$ bits. However to ensure that it is still possible to detect errors at the same rate as before, I add a second hash over every group of 4 blocks of $x/2$ bits (illustration 2):

Illustration 1

 |-----|-----|-----|-----|   4 hashes of x bits

 Total bits = 4*x

Illustration 2

 |-----|-----|-----|-----|   4 hashes of x/2 bits
 |-----------------------|   1 hash of x/2 bits

 Total bits = 5*x/2 = 2.5*x

Are these equivalent, how do they differ if not and how can I compare them?

Another possibility would be:

 |-----|-----|-----|-----|   4 hashes of x/2 bits
 |-----------------------|   1 hash of x bits

 Total bits = 4*x/2 + x = 3*x

I couldn't find much on this topic through the usual sources.

$\endgroup$
1
  • $\begingroup$ As a note: You're not expected to find collisions in cryptographic hashes, except if they're severely broken or you picked the output length too short. What about just throwing BLAKE2 at your problem and stopping to worry? $\endgroup$
    – SEJPM
    Jan 19, 2017 at 8:36

1 Answer 1

1
$\begingroup$

The usual way this is performed is through a Merkle tree, of which you will definitely find information on the Internet. What you can do is to separately hash each block (for performance reasons) and then hash the hashes together (in the correct order). Then you can simply store just the resulting hash.

In your scheme you perform a hash with half output. But you only want to trust the block after you've also verified the additional hash. So basically your "half-hashes" over the blocks are pretty useless. You may just as well hash the 4 blocks together or use a Merkle tree as described above.

Note that none of your constructions is likely to have more security than the output of a single hash (the state of both the single block hash and four-block hash would be the same after the first block), even though the output is larger than that. That said, I don't directly see how it could be less than the security of a single hash either.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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