1
$\begingroup$

There are 64-bit universal or almost universal hash functions, like CLHASH or VHASH:

https://arxiv.org/pdf/1503.03465.pdf

https://eprint.iacr.org/2007/338.pdf

Can we create secure 256-bit hash function by concatenation of this hash functions (by using different key for every function)? Similarly like authors of ECHO hash did based on AES (the only paper I found about this is "ASIC Evaluation of ECHO Hash Function").

In fact VHASH family has been proposed for cryptographic applications, and specifically message authentication VMAC:

https://en.wikipedia.org/wiki/VMAC

I think the same idea was behind CLHASH, because otherwise what is the point of proposing 64-bit hash function in 2015? But these functions seem to be very efficient, so why authors didn't go step further and did not propose 256-bit hash functions (especially computed in parallel), which may be then possibly in line with modern stardands of security?

$\endgroup$

1 Answer 1

4
$\begingroup$

Can we create secure 256-bit hash function by concatenation of this hash functions (by using different key for every function)?

Doesn't sound likely; the problem is that universal hash functions and cryptographical hash functions are very different things.

A universal hash function is a keyed function; its defining property is that for any two different messages, the universal hash function maps them to the same output for only a tiny subset of keys. That's it - that's the only property it needs to have. For one, there's nothing that says that, with a publicly known key, it has any security properties at all; it may be trivial to find preimages. In fact, for most known universal hash functions, this is quite easy.

In contrast, a cryptographical hash function is an unkeyed function - when someone computes it with a specific preimage, they can see everything that happens with it - that is, if there's a universal hash inside, they know the key to that universal hash. That voids any property we get from the universal hash (at least, as a universal hash).

Now, there might be universal hashes with additional properties - those might find a use within a cryptographical hash. However, just being a universal hash is insufficient.

$\endgroup$
3
  • $\begingroup$ It took me ages to figure out he wasn't talking about concatenating broken hash functions. MD2(x) + MD4(x) + MD5(x) might end up being quite strong after all because meet in the middle is consumed attacking the +. (It's still a bad idea because CPU waste even if it works so don't try too hard.) $\endgroup$
    – Joshua
    Oct 1, 2022 at 23:49
  • $\begingroup$ @Joshua if we talk about wasting CPU time CLHash uses about 0.1 cycles per byte on recent Intel processors. It is extremely fast. Even if we would use something slower, we can think about computing this functions in parallel, then it doesn't make much difference whether we compute one function or 4. $\endgroup$
    – Tom
    Oct 2, 2022 at 10:58
  • $\begingroup$ Issue remains that concatenation by itself doesn't make the hash function secure; you'd need a specific security proof. $\endgroup$
    – Maarten Bodewes
    Oct 4, 2022 at 13:57

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.