While I read that hashes are not meant to be reversible, but assuming we have part/half of the message/input of a hash? Is there any method that we can use to recover the remaining message via this part of the message that we have?
Thanks in advance
4 Answers
$\begingroup$
$\endgroup$
2
It depends of course on the hash function you're dealing with. Assuming it is a cryptographically secure hash function, you're still looking at brute forcing the output: in other words, trying every possible input, computing the hash and then comparing with the output. Finding two inputs with the same output is a hash collision. Consider the MD5 hash function, which is no longer considered secure, the known collision attacks end up flipping more bits across the whole input, so depending on exactly which parts of the input you know, you might be closer to a collision.
However, most hash functions besides MD5 have only theoretical collision attacks, with no known working examples. If you aren't extremely lucky, then you will have to search for exactly as long as for what you know is different from the real input.
Knowing part of the input does reduce the search space of your brute force attempts, especially if you know the total size of the input. Most hash cryptographic functions can be used a checksums, which means they can function on inputs of arbitrary length. So in other words, if you don't know the total size of the input, then you may be searching literally forever.
If you know the input class to the hash function is fairly straightforward (for example, it's an English dictionary word, or a series of words), then you can potentially employ a rainbow table. If the input is sufficiently noisy, the rainbow table becomes prohibitively large, which is why salt is an effective countermeasure.
-
$\begingroup$ Discussing collisions only blurs the picture. In the situation considered in the question, even for MD5, they do not occur, thus do not matter. $\;$ As stated, the best known attack method (for practically used hashes) is trying every possible input, computing the hash and then comparing with the output. Thus having half of the message is of tremendous help; for a 20-digits message, the expected effort goes from $10^{20}/2$ hashes (hopeless with a few PCs) to $10^{10}/2$ hashes (10 billion times easier, feasible with a single PC unless the hash is purposely slow). $\endgroup$– fgrieu ♦Mar 19, 2015 at 7:10
-
1$\begingroup$ Having half of the message helps only if the message is shorter than twice the hash length. $\endgroup$ Mar 19, 2015 at 9:54
$\begingroup$
$\endgroup$
It depends on which hash you are talking about. There are fundamentally two types of hash: cryptographically secure hashes, that (presumably) cannot be reversed without brute force, and regular hashes that may or may not have shortcuts to reverse them.
With a cryptographically secure hash, even having all but one byte of the hashed data will yield a completely different hash that does not allow you to deduce what the hash would be with the one-letter change.
That said, a number of hashes had been thought to be cryptographically secure, until some method of attack was detected. An example is MD5 (which is still secure for your problem though).
$\begingroup$
$\endgroup$
Actually you can't. Either way - bruteforcing or performing a collision search - you will not be technically "reversing", you will be brute-forcing. Remember that table-matching is kind of a brute force too, because the table must be pre-generated :) Knowing a part of message can help you in brute-forcing cipher streams/blocks, but not dealing with the hashes.
$\begingroup$
$\endgroup$
q.1 No. That's the entire point of a hash: total non-reversibility, for even the smallest possible change in input.
q.2 Yes. If the message is small enough, you can do a dictionary attack on the missing part. In a practical sense, we're only talking about a few bytes or a few English words here: you can't reproduce half of Hamlet from a 256bit hash (at least, not without help from an impractically large number of monkeys).
