Can we widen hash functions with concatenation?

Question

There seems to be an interest in wider and wider hash functions. This is understandable as bigger is always better. So there have been questions asking about 1024 and 2048 bit functions.

So rather than having something native, could we do the following?

uberhash = SHA-512(message) || SHA-512(message || "1")... 

And of course this could be further extrapolated in blocks of 512 bits ad infinitum depending on the level of one's paranoia. Counter concatenation is a common technique but is my use of it flawed in some way, other than efficiency? I realise that a native function might use less operations, but I don't know how the degree of this advantage could be estimated. Is this an example of too good to be true?

Answer 1

The proposed 1024-bit hash

  uberhash(message) = SHA-512(message) || SHA-512(message || "1")

is hardly more collision-resistant than SHA-512 is: an hypothetical collision of messages for SHA-512 (with messages of equal length, as all known collisions for the SHA familly and ancestors are) can be turned into (or already is) a collision for uberhash (if the collision for SHA-512 involves the last block, we simply extend the colliding messages with their padding).

---

A construction immune to this particular attack would be

  uberhash2(message) = SHA-512( prefix0 || message ) || SHA-512( prefix1 || message )

(with prefix0 ≠ prefix1). But it is not demonstrably much more secure; see Antoine Joux: Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions, in proceeding of Crypto 2004. That paper constructively proves that uberhash2 collision resistance can't be much more resistant than SHA-512 is to brute force attacks (that is, 256-bit).

On the other hand, uberhash2 seems to stand a fair chance of blocking extensions to SHA-512 of existing much-better-than-brute-force collision attacks against SHA-1 and ancestors (and that arguably could matter in practice). At least, even though MD5's collision resistance is hopelessly broken, I do not immediately see how to efficiently find a collision for

  uberMD5(message) = MD5(prefix0 || message) || MD5(prefix1 || message)

Also, my reading is that the quoted paper does not rule out that concatenating $n$ secure $k$-bit different hashes might have $(n-1)k/2$-bit security.

I pass at how uberhash2 improves resistance to brute force attack using a quantum computer.

---

More generally: SHA-512 internal parameters (such as internal state size and number of rounds) are carefully chosen with 256-bit security in mind, and getting true 512-bit security with an argument about that would require increasing these parameters.

Answer 2

"This is understandable as bigger is always better"

This is not accurate, which can be discovered by following the links which follow the statement.

Bigger is not always better:

• There is an upper bound to the amount of security that is achievable
  • There is no benefit to having more then a certain number of bits of security
• But there is a cost
  • CPU registers are only so large with so many available
  • using too much data will degrade performance with excess load/stores
  • A larger state requires more rounds to diffuse the inputs

Counter concatenation is a common technique but is my use of it flawed in some way, other than efficiency?

You have not stated what exactly you expect this construction to accomplish. Judging whether or not your approach is flawed is not possible. That being said:

• It increases code complexity
• It increases the storage cost for storing the hash output
• It appears to be a hopeful shot-in-the-dark attempt to fix an unspecified and potentially non-existent problem

This last bullet is a concern: What if you were engineering a car instead of an algorithm?

I realise that a native function might use less operations, but I don't know how the degree of this advantage could be estimated.

It is pretty simple in this case. The space and time efficiency scale with the number of excess hash invocations beyond the first. If it requires 1 invocation of SHA-512 to hash data normally, and $N$ invocations with your construction, then your construction requires $N$ times the time and space of standard SHA-512.

Can we widen hash functions with concatenation?

Of course you can. This is basically the definition of what concatenation does: it extends some block of data with some other block of data. The real question is why would you want to?

The counter does not add any entropy to the output. Hashing the same input multiple times with a counter does not increase the effort required by an adversary to guess the input (note: I am not talking about kdfs and slow hashing with millions of iterations).

Answer 3

Yes you could with some security gain but not necessarily as much as you would like. You wouldn't want to concatenate your salt at the end of the message, you would want it at the beginning. As with many hash constructions a collision at the begining will continue with constant suffix.

You also probably don't want your salt to be mostly zero but would prefer something more randomish. Essentially you are replacing the chaining value, you want something very different fromb the original chaining value. You can do all sorts of interesting constructions to make a new hash function out of an existing one which will be different and hopefully collide on different inputs.

H(m||m) or H(salt || m) or start throwing things at and hope it will all work out.

The problem is of course we need to think of what is the weakness of H, because with no weakness this is not needed.