# collision resistant summarizer for long hash values

how we can summarize SHA-256 into shorter values when we for example can't handle more than 128 bits on system? its better just use first 128bit and ignore the rest of bits or split full value and XOR them? or use another hash function that produce required bit long hashes to generate a hash from SHA-256's value (e.g SHA-1)? which way is more robust and unpredictable?

-
While it doesn't directly answer your question, this answer of mine should point you in the right direction. In short, we usually just truncate the hash straight up and don't worry about the later bits. –  Reid Dec 12 '13 at 18:16

The answer is "any sane summarization function is about as good as any other; pick whichever is convenient"

To the best of our knowledge, SHA-256 acts pretty much like a random function (except for the length extension attack; that wouldn't apply here)

So, the output of SHA-256 is essentially a random 256 bit number; so, if we have a 128 bit hash function:

Hash(M) = Summarize(SHA256(M))

then, as long as the Summarize function has $2^{128}$ preimages (of 256 bits) for each possible output (of 128 bits), it should be good. Both the "use the first 128 bits" and "split the full value and XOR them" functions have this property.

Now, since you talk about collision resistance, you can find a collision with a 128 bit hash function with about $O(2^{64})$ effort, by the simple expedient of generating $2^{64}$ random strings and hashing them, and then looking for two hashes with the same value (and, in case you're hoping the memory requirements of this would save you, there are clever ways to reduce the memory requirements drastically without requiring that much more computation time). As long as those random strings are longer than 128 bits, there's nothing a hash function can do to avoid a collision. If you need stronger collision resistance than that, you need to rethink the problem.

Also, since I mentioned the length extension attack, I'll summarize it here:

If you hash the value $SHA256(M)$, and the length of $M$, then you can compute a string $A$ such that, for any string $B$, you can compute the value:

SHA256(M | A | B)

You can compute this even though you know nothing more about $M$.

This wouldn't apply in this specific case, because for this to work, you need to know the entire $SHA256(M)$ output, and your summarize function will drop a lot (precisely 128 bits, actually) of that information.

-
is there any way to increase entropy of our hash against collisions e.g by chaining hash operations? for example compute SHA512(M)=hash1 then compute SHA256(hash1)=hash2 then compute SHA256(hash2)=hash3 then truncate hash3 to 128 bits by XORing it? how much entropy this add and how many chain we need? –  user10851 Dec 12 '13 at 18:52
@user10851: I'd say know, but I don't know exactly what you mean by entropy; that certainly isn't true for the standard (Shannon) definition of entropy. Do you mean 'making the output a more complex function of the input'? If so, well, as far as we know, a SHA256 output is already a complex function of the input; it's unclear how making the function more complex adds to security (except for making the attacker's job incrementally harder). –  poncho Dec 12 '13 at 19:00
so chaining hashes don't add any security to our design and collision attack is still 2^64 right? we need 2^128 operation at least. what about use KDF on hash? –  user10851 Dec 12 '13 at 19:09
@user10851: if you use a keyed hash (where the attacker doesn't know the key), then the attacker obviously cannot perform an offline collision attack. And, if you limit the messages being hashed to no longer than 128 bits, you could conceivably use an invertable function for your hash; that obviously doesn't have any collisions. Other than that, there's not much you can do (other than increasing the length of the hash output) –  poncho Dec 12 '13 at 19:59
do you mean if message if short like a domain name (e.g google.com) there is a way to use a short collision resistant hash? sounds good tell me more about invertable function for SHA-256 please –  user10851 Dec 13 '13 at 13:57