0
$\begingroup$

I'm looking for a hash algorithm thats output can be reversed back into the input in a reasonable amount of time (a day or less) using a decent consumer computer. If anyone has any information on this, it would be very much appreciated.

Edit: After reading some of the comments and answers on this post, I feel I should clarify: I'm looking for a hash algorithm where it is relatively easy to reverse a hash into an input that is one byte larger than the hash. For example, if the hash output is 32 bytes, and the input was 33 bytes, I'd like to know if there's a hashing algorithm where it's possible to reverse the output into the input in a situation like this.

$\endgroup$
  • $\begingroup$ Generally finding pre-images of hash function outputs is not possible. The algorithm needs to be terribly broken for that to happen. Of course, you would not be able to reconstruct a movie, say "Species", from a 32 byte hash result - even if you wanted to. $\endgroup$ – Maarten Bodewes Mar 19 at 0:54
  • 2
    $\begingroup$ Could you specify the aim? Although some well known Cryptographic hash functions has no more collision resistance, MD5 and SHA1, there is no known pre-image attack on those. $\endgroup$ – kelalaka Mar 19 at 8:46
  • 1
    $\begingroup$ Maraca comes to mind. $\endgroup$ – Samuel Neves Mar 19 at 15:14
  • 2
    $\begingroup$ There is a difference between a "hash algorithm that the output can be reversed back to the input" versus a "hash algorithm that the output can be reversed back to an input", because a hash can have multiple different inputs that result in it. You may need to clarify which of these your question is about. $\endgroup$ – Ella Rose Mar 19 at 15:58
  • $\begingroup$ Perhaps 2-pass Snefru? $\endgroup$ – Squeamish Ossifrage Mar 19 at 16:01
1
$\begingroup$

Depending on what you want to do, maybe you can take a cryptographic hash function and truncate it. Adjust the length of the truncation to how much effort you want the preimage calculation to be. This is a valid way to create a proof-of-work mechanism. For example, if you want to require a party to perform about $2^{m+n}$ operations where $2^m$ is the estimated cost of hashing a very short string, then:

  1. Generate a random $s+n$-bit string and calculate its hash $h$.
  2. Send the hash $h$ and the first $s$ bits of the string and request a preimage.
  3. Read back a string and check that its hash is $h$.

(The salt length $s$ needs to be sufficiently long to prevent pre-computing possible inputs.)

With any cryptographic hash function in good standing, and even with most of the ones in bad standing such as MD5, the fastest way to find a preimage is brute force searching among all $n$-bit strings.

If proof-of-work is not what you're after, then maybe you can use a non-cryptographic hash, for example a CRC. In general, hash functions that aren't specifically designed to be cryptographic hashes have a low probability of accidental collision (but it's easy to craft a collision deliberately), and they're easy to invert.

Of course, “inverting” the hash will find a preimage, not necessarily the string you started with.

$\endgroup$
0
$\begingroup$

No There is not, as a hash function will output a set length of data, if it is longer than that, it truncates it. Take the MD2 Hash function that was invented in 1989.

From Wikipedia:

The 128-bit (16-byte) MD2 hashes (also termed message digests) are typically represented as 32-digit hexadecimal numbers. The following demonstrates a 43-byte ASCII input and the corresponding MD2 hash:

MD2("The quick brown fox jumps over the lazy dog")
03d85a0d629d2c442e987525319fc471

As you can see:

  • The input string is 43 bytes long
  • The output string is 32 bytes long

There is simply not enough space to store the information, it therefore can not be 'reversed'. There does exist 'hash collisions', where another string may equal the same hash as mentioned above in the comments to your question (as hashes are a finite length while input is not, there are therefore collisions in all hashes (although collisions in some modern hashes have not yet been found)). These collisions are however found by hashing strings and comparing the hashes, not by reversing the algorithm.

$\endgroup$
  • 2
    $\begingroup$ That's true but not really relevant. There are multiple preimages, ok, so how do you find one, even if it isn't the “original” one? $\endgroup$ – Gilles 'SO- stop being evil' Mar 19 at 12:37
  • $\begingroup$ @Gilles "These collisions are however found by hashing strings". There's no better way if you don't know the hash in advance. Not optimal though if you can afford to compute some stuff in advance. $\endgroup$ – John Dvorak Mar 19 at 12:39
  • $\begingroup$ @JohnDvorak That sentence is true for non-discredited hashes (it's not true for MD4, MD5 or SHA-1). Computing stuff in advance won't help you in general. It does help if the input space is limited. $\endgroup$ – Gilles 'SO- stop being evil' Mar 19 at 12:43
  • $\begingroup$ @Gilles it's hard to make a statement that applies to all possible hashes all the way from SHA512 down to f(x)=0. If the output space is too big, you won't have enough memory for a useful rainbow table. If it's too small, it might be cheaper to brute force all inputs (you don't need a ROM stick in that case, and nobody cares about 1500ms). But then again, you can dispute both of these, in which case the usefulness of rainbow tables becomes the one universal fact that you say isn't. $\endgroup$ – John Dvorak Mar 19 at 13:04
  • $\begingroup$ This answer directly contradicts the suggestion made by Samuel Neves in the comments where the authors find preimages of a hash function that was submitted to the SHA-3 competition. $\endgroup$ – Ella Rose Mar 19 at 15:58

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.