# Is it possible to find a preimage for a reduced size hash?

Given a message $M$ and a 256 bit key $K$, perform HMAC($K$, $M$) with a 256 bit hash function resulting in:

$a$ = 9a58e0eef2effc968d27cd61c47394867ceae43c7a877d59938f8400fe1a0204

Now take every second hexadecimal symbol resulting in a 128 bit hash:

$b$ = a80e2fc6d7d14346ca4ca7d93f40ea24

Assume the attacker knows the HMAC hash function.

1. Knowing only $b$, is it possible to find a preimage for $M$ or $K$?
2. Knowing only $b$, to find the original $K$ or $M$, does an attacker need to repeat the same process (HMAC($K$, $M$) + taking every second symbol) and perform a brute force search with 2256 different keys to match the hash back to $b$? Or is there a faster way?
-
Are the given $a$ and $b$ values just examples? $\:$ Should "a preimage for" be removed from $\hspace{1.17 in}$ your question's body? $\:$ If no, what do you mean by that? $\;\;\;$ – Ricky Demer Sep 19 '13 at 5:18
I mean technically you could find a preimage for the original hash $a$ if the hash function was weak enough. What I'm trying to ask, that given the reduction (taking every second letter) can you still find a preimage? In other words, given $b$ is it still possible to find $M$ or $K$? – NDF1 Sep 19 '13 at 5:20
I don't get what "find a preimage for the original $M$ or $K$" is supposed to mean. $\:$ I would understand $\;\;$ "find a preimage for $M$ or $K$" and "find the original $M$ or $K$", but since you don't refer to any other $M$ or $K$ values, I can't figure out what the question you wrote there is supposed to mean. $\hspace{.64 in}$ – Ricky Demer Sep 19 '13 at 5:26
"find a preimage for $M$ or $K$", yes this exactly. – NDF1 Sep 19 '13 at 5:34

We don't really know exactly how hard it is to find preimages of most cryptographic hash functions. Even for MD5 it is only "easy" to create collisions, while finding preimages is still considered "hard".

That said, we can apply statistical tools to estimate a "worst case", if we assume a random oracle for the hash function. In this case, we need in average $2^{255}$ tries to find a preimage to a 256 bit hash. Now, if we are looking only for a partial match (only 128 bits, it doesn't really matter which ones), we can estimate a match in average at $2^{127}$ tries.

Now, hash functions take an arbitrary input and map it to a fixed size output. There are no "preimages for M or K", there are just preimages (an input which maps to the same hash value). So once you found a preimage, you have this input. If the HMAC scheme requires a certain format of the input values for key, message and possibly other information, then you should only test inputs which fit this format.

To your second question: The attacker can not distinguish between the original message/key and any other preimage, if he has only the hash value (since they are the same). This might only be possible with additional information about the message: For example if the message is composed of English words in UTF8, preimages of random bits are not a "wrong preimage". However, in this case he would not even try this random input.

In general, the difference between HMAC and a cryptographic hash function is not that big. The difference becomes important, if the message is chosen from a small set of possible messages. In this case, the attacker can not just test all possibilities and find the real one, but he would have to test all messages with all keys (which should be larger than the hash value space). But in average, he will still find a preimage in 2^{k-1} tries for a k-bit hash value.

As final note: While $2^{127}$ possibilities is too much to brute-force, the security of this reduced hash value is less than the original one. Each ignored bit of the hash value cuts the complexity of finding a preimage by brute force into half. If you consider cutting down to something like every 4th bit of a 256 bit hash value (or any other fixed 64 bits of it), you get into the "possible to find with today's tools"-range. You have to ask yourself if this is worth saving a couple of bits for a potentially longer message, especially if you consider the other message overhead (e.g. IPv4 and TCP headers are each 160+ bits)

-
I'm talking about preimage resistance from that definition on the Wiki not second-preimage resistance. In question 1 finding the original M or K given the resulting hash $b$ may be impossible if you were to try "reverse" the hash function to get back the original $M$ or $K$ because half of the original hash has been removed. However you could find it, by trying all combinations of $M$ and $K$ and recomputing in the same way. For second-preimage resistance/collision resistance I think it is reduced to $2^{127}$ yes. – NDF1 Sep 19 '13 at 11:17
For the difference between 1st and 2nd preimage attacks, you can check this topic, which shows that the actual difference is not that clear at all. But no, I am not talking about actual attacks, I am talking about average case estimates of brute force (assuming the random oracle), as upper bounds on your security. If I throw $2^{128}$ random key/message combinations in your construction, in avervage I will find something that has the same 128 bit hash output. – tylo Sep 19 '13 at 13:22
I think you could put $2^{255}$+ random key/message combinations into the construction and you will probably get x number of collisions in $2^{127}$ time, that's for certain yes, as the final hash $b$ is reduced to 128 bits. But how exactly would an attacker know which was the original $M$ or $K$ if there are multiple collisions found? – NDF1 Sep 20 '13 at 9:40
He can not. I thought I wrote that earlier as well. If you only have the hash values, then you can not distinguish between which was the actual preimage (assuming you found multiple) – tylo Sep 20 '13 at 11:33
Ok many thanks for your answers tylo. – NDF1 Sep 21 '13 at 11:33