[Cryptography] blake2b 160

[Ray Dillinger]

On 12/29/18 9:33 PM, jamesd at echeque.com wrote:
> I have an application that requires that no one can ever produce a hash
> collision on two data blocks of moderate size.
> 
> Seems to me that Blake2b 160 suffices, and Blake2b 256 is overkill.
> 
> Someone claimed its easy to produce collisions and sprayed what sounded
> to me like random technobabble in support of that claim.
> 
> 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?

Pretty hard.  I don't think you have anything to worry about, although
I'd probably have reflexively picked 256-bit.  Is a post-quantum
future part of your design requirements?  I think quantum gives a
marginal speedup on Blake, but not by more than a fairly small constant
factor.

I worry about hashes because the vast majority, including BLAKE and
variants, are subject to length-extension attacks.  That is, if you can
find a string that matches the hash of any prefix of the message, then
the remainder of the message can be appended to it resulting in a
collision on the whole message.  So there is an attack surface at every
block (at the end of every prefix), not just at the final block.

Although not ideal this is generally an accepted design point for
hashes.  People want to be able to hash a stream of data linearly,
without knowing in advance the length of the message, without having to
access anything out of sequence, and with a tightly bounded number of
bits of state.

That said, producing a collision on any prefix is just as hard as
producing any collision.  So even with the attack surface multiplied by
the number of blocks in the message, the prefix collision isn't easy to
exploit.  I worry about "reduced" security because I'm a worrywart by
nature but in practice it's not much of a reduction.

SHA256 reduces the length-extension attack space by appending the
message length to the message before hashing.  That means any prefix
collision has to be on a prefix exactly the same size as the string that
collides with it.  SHA256D effectively eliminates it by hashing twice;
that way the state of the hash function depends on every bit of the
message (from the first time through) WHILE hashing (on the second time
through). The prefix string that collides with something (against
astronomical odds) starting from the default state won't likely collide
again (astronomical odds squared) starting from a different state.


> If someone wants to say it is easy, that it does not take all that much
> time and resources, I would like to hear an explanation that sounds like
> a description of an algorithm, an algorithm described in detail
> sufficient I could test it to produce a collision in the last sixty or
> so bits of the hash.

I got no such algorithm.  Offhand I don't see how it could exist.  While
the length extension attack is a thing, marginally, for finding total
collisions, Blake2B has good diffusion in each block so no partial
collision could be extended.

				Bear




-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20181230/f6849790/attachment.sig>