-2
$\begingroup$

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?

|improve this question
$\endgroup$
  • 4
    $\begingroup$ Review shake functions. They are hash functions with arbitrary length outputs $\endgroup$ – Node.JS May 9 '17 at 3:11
  • $\begingroup$ If you need to widen the result for cryptographic purposes you need to do this with an approved KDF (key derivation function). They are usually a bit more complex than simple concatenation to make the construction more robust. Especially if the input is low entropy (passwords). $\endgroup$ – eckes May 9 '17 at 6:18
  • $\begingroup$ Your question is very interesting, as one could think to gain security in some cases by concatenation of two hashes. The book "Introduction to Cryptography with Coding Theory" by L. Washington and W. Trappe answers to your specific question. Since most of the hash function (e.g. the SHA or MD families) use an iterative algorithm (there is a compression function f that is iteratively called), there exist an attack exploiting the so called "birthday paradox" that makes the concatenation of two hashes useless. I will post a detailed answer when I have time :) $\endgroup$ – richard May 9 '17 at 9:10
  • 1
    $\begingroup$ "bigger is always better" This statement is a misconception, and it isn't true in general: Assume you increase the size by simple concatenating $H(x)$ a few times. The output is bigger (as big as you like), but it doesn't make a difference in security at all. The output size can be considered an upper bound for the security - but it's no guarantee without proper analysis. $\endgroup$ – tylo May 9 '17 at 10:37
2
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ Hmm. Joux suggests that there is some increase in collision resistance though. Stupidity prevents me from being able to divide his increased resistance by normal (unconcatenated) resistance to obtain the ratio of improvement. I hate being thik! However. A marginal improvement over zero = huge improvement, which is the case for functions of 2048 bit width as linked to in the original question. Or wider? Don't know why they want these hashes, but they asked, and this is after all a theoretical site, no? $\endgroup$ – Paul Uszak Jun 8 '17 at 11:00
  • $\begingroup$ And if the improvement ratio was only ~1, then for widths >1024 (for which there are no native functions), wouldn't the collision resistance still be 2^(n/2)? $\endgroup$ – Paul Uszak Jun 8 '17 at 11:02
  • $\begingroup$ And so 5 concatenated SHA-512's would have the same security level as the still uninvented 2048 bit wide hash of the question? Flog me with spaghetti, but have we invented something? Even if it's kinda useless? $\endgroup$ – Paul Uszak Jun 8 '17 at 12:57
  • $\begingroup$ I believe you can find a collision in uberMD5 in $O(2^{64})$ time (and perhaps $O(2^{70})$ with minimal memory); where that's counts as "efficient", well, I'm not sure... $\endgroup$ – poncho Jun 8 '17 at 14:47
  • $\begingroup$ @poncho: Yes, I also see how it follows the Joux paper, and was discounting that as not efficient. In the context of an attack for SHA-512 similar to what we have MD5, that translates to an attack against uberhash2 in $O(2^{256})$ time (and perhaps $O(2^{264})$ with minimal memory). $\endgroup$ – fgrieu Jun 8 '17 at 16:42
3
$\begingroup$

"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).

|improve this answer
$\endgroup$
  • $\begingroup$ Bigger can also make things more problematic by requiring more rounds to fully diffuse the input. $\endgroup$ – forest Jul 3 '18 at 7:27
1
$\begingroup$

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.

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.