0

I have a basic question about hashing. It is said that hashing is one way. I have a doubt that if we simply reverse the steps in program/algorithm/logic then can't we find at least one input which hashes to the given output hash value?.

I found 2 related posts, but I am still not completely clear:

How is one way hashing possible?

How do one-way hash functions work? (Edited)

I have the same question as the comment to the accepted answer in the first post:

"Well, but if I want to bypass a password check it suffices to find one string that hashes to the same value as the original password". Does this comment hold water?.

grit639
  • 316
  • 1
  • 9
  • It's not clear to me what your question is, and the part you claim is a question is a statement. If you think you can run programs in reverse, why not pick a hash function and try it? (Note that achieving this efficiently for SHA-256 would make you rich, because for you will be able to mine bitcoin). – Paul Hankin Mar 20 '21 at 16:40
  • @PaulHankin : can't we run the algorithm in reverse manually by hand computation?. We can manually compute input and output of each step in algorithm. – grit639 Mar 20 '21 at 17:05
  • 1
    @grit639: Not all mathematical operations are perfectly invertible. – datenwolf Mar 20 '21 at 18:34
  • How do you reverse `a=b`? You don't know what `a` was before. You can pick a value, but it may be incompatible with any path through the code. – Paul Hankin Mar 20 '21 at 18:53
  • 1
    A better example: suppose the hash function is `integer hash(integer k) { return pow(65537, k, M) }` where pow(65537, k, M) is 65537 to the power of k modulo M (where M is a product of two large primes), and `integer` is a 4096 bit integer . How do you reverse that? That this function is hard to reverse is what makes RSA encryption work. – Paul Hankin Mar 20 '21 at 19:03

3 Answers3

3

What you're thinking of is called "hash collisions".

And you're right to think, that if one could find an efficient method to determined inputs for a given hash functions that produce a desired output, this would break a lot of systems (https://en.wikipedia.org/wiki/Preimage_attack)

That's there the bones and meat of cryptographically secure hash functions come in. Those are built in a way, that it is very, very difficult to find a preimage that produces a desired hash.

Over time mathamaticians and cryptologists are chipping away on those hashes and quite a number of hash functions that were used for securing thing have been broken (MD4, MD5, SHA-1).

Also it's important to differentiate between hashes that are intended to check the integrity of messages, and hashes that are intended to protect secrets.

For integrety checking you want fast hashes, so that you can put a lot of data through them with minimal effort. MD5, SHA-1, SHA-2 are such hashes.

For secret keeping you want SLOW -er than molasses hashes, so that one can't easily brute force through dictionaries of other predicable patterns of a secret. SCrypt, BCrypt, Argon and many-round PBKDF schemes are such hashes.

datenwolf
  • 159,371
  • 13
  • 185
  • 298
  • "That's there the bones and meat of cryptographically secure hash functions come in. Those are built in a way, that it is very, very difficult to find a preimage that produces a desired hash." =>> could you please give some concrete examples of functions/program steps which can't be reversed to find even one input which will map to the given hash value. Assuming that the algorithm is open source, can't we just reverse each statement of program so as to find at least one valid input. – grit639 Mar 20 '21 at 16:57
  • The most common example (and one that is easy to understand, and is also commonly used in crypto systems) is the discrete logarithm: https://en.wikipedia.org/wiki/Discrete_logarithm If every efficient algorithm had an efficient inverse, then that would be enough to prove that P=NP (https://en.wikipedia.org/wiki/P_versus_NP_problem). The common example of that is that it is hard to solve a Sudoku puzzle, but it is easy to show that a given solution is valid. – Rob Napier Mar 20 '21 at 17:06
  • 1
    I realized a better example, that's even easier to understand, is prime factorization. Multiplying two values of n-digits can be done in < O(n^2). But there is no known algorithm that can find prime factors in polynomial time (i.e. O(n^k) for any constant value of k). It's possible such an algorithm exists, but no one has found one (Shor's algorithm is O(n^3), but can only achieve that on a quantum computer). Prime factorization isn't used in any hashing algorithm I know, but it's a common example of a one-way function. – Rob Napier Mar 20 '21 at 18:33
1

The operations in a cryptographic hash function are so complex and there are so many of them that reversing the function (compute at least one valid input for a given output) is incredibly infeasible. It doesn't matter if you do that reversing by hand or with the help of some sort of algorithmic solver. This is called (first) preimage resistance and this is what cryptographers are attacking when a new hash function is proposed. If the hash function stood the test of time, it is considered secure.

On the other hand it is much easier to just generate a bunch of candidate passwords and run the known hash function over them to check for equality with the given output. Humans are pretty bad at generating good passwords or passphrases. Have a look at this talk.

In Hashing, can't we find AT LEAST one original text hashing to the given hash value

In that context, "finding" as in brute forcing the input space is easier than attacking the hash function itself.

Artjom B.
  • 61,146
  • 24
  • 125
  • 222
0

There's a very simple way of giving a hash function that is not reversible:

int GetHashCode(byte[] myData)
{
    return 1;
}

This is a perfectly valid hash function, as it maps the contents of an arbitrary data set to a much smaller domain (int in this case). It satisfies the condition that the same input data gives the same output data.

It is obvious that this function is not reversible.

(Of course, this hash function is not suitable for securing anything, but that's only one application of hash functions)

PMF
  • 14,535
  • 3
  • 23
  • 49
  • 1
    I am thinking of application where hashing is used for passwords and hashed values are stored not the original text password. In this case, if someone has access to the database and sees the hashed value, then can't by reverse tracking, he can find AT LEAST one text password which will hash to the same value and so he can use that password to login. In your example, a valid original password can be ANY text. – grit639 Mar 20 '21 at 17:17
  • Yes, right. But I was answering the "one way" part. – PMF Mar 20 '21 at 17:18
  • While this is a very good illustration of one-wayness, the example falls apart pretty quickly, since we care about preimage resistance for cryptographic hash functions. With this function I can find infinitely many, but at least one valid input that produces a known and desired output. – Artjom B. Mar 20 '21 at 20:01
  • @ArtjomB. Sure, for security, my function is really bad, but it points out how a function can be irreversible. – PMF Mar 20 '21 at 20:29