[Cryptography] blake2b 160

Sidney Markowitz sidney at sidney.com
Tue Jan 1 22:13:52 EST 2019


jamesd at echeque.com wrote on 30/12/18 6:33 PM:
> So, for a given number of bits in the hash, how much time and resources
> are required to produce two blocks of data of moderate size such that
> the last n bits of the hash are the same for both blocks?
[...]> sufficient I could test it to produce a collision in the last sixty or
> so bits of the hash.

If the "technobabble" tried to say  that hashes could be broken in less than 
brute force times without using some specific cryptanalysis of the hash 
algorithm, it is probably nonsense. But if you really do intend to only use 
the last n bits of the hash and you really are trying to protect against 
collision, then 60 bits may not be good enough.

Brute force lets you find some two blocks with a collision on an n-bit hash by 
trying on the order of 2^(n/2) hashes on random blocks. The algorithm is to 
generate blocks, hash each, and save the results in a way that you could 
quickly find when you have encountered the hash before and what data block 
made it. The details are left as an exercise. Because of the birthday 
"paradox" finding a collision makes it n/2 instead of n when you don't care 
which two blocks have the collision.

If what you are concerned about is second preimage resistance, i.e., given a 
specific block of data  find a different block that hashes to the same value 
as the first, that would take on the order of 2^n hashes to brute force, but 
you would not have to use the memory to save all the hashes you compute until 
you find it.

Which of the two you are concerned with depends on your threat model. 
Collision resistance protects against somebody producing two things that have 
the same hash and using them in some kind of bait and switch scam. But if what 
you want to use the has for is to prove that an item you supply has not been 
tampered with, all you need is second preimage resistance.

When you say "the last n bits of the hash", that's the n that you use in those 
estimates. Finding a collision in just the last 60 bits would only take on the 
order of a bit more than a billion hashes and a billion numbers in memory. 
What would that be, a few hours on just one core and tens of GB of RAM? But if 
you really intended to use the full 160 bits of a 160-bit hash, then you are 
looking at 2^80, so multiply that by another 2^50 which would be bigger than 
is feasible.

And if you really meant second preimage, even only using the last 60 bits 
would require a brute force attack to calculate 2^60 hashes, which my really 
rough fermi estimate tells me would be more than a thousand years running on a 
thousand cores.

  Sidney Markowitz
  sidney at sidney.com



More information about the cryptography mailing list