[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