# Reverse Hash Function

Discussion in 'Recreational Math' started by Linda Pan, Dec 17, 2004.

1. ### Linda PanGuest

Dear experts,

I met a problem, and I don't have experience to solve it. Thus, please give
me a help.

My question is:

I have a hash function: h().

I have a plain text: A

So I can get a hash value B = h(A)

Suppose that I have a reverse hash function: h'()

Then I can get a fade plain text A'= h'(B), probably A' is not equal to A,
but it doesn't matter!

I want to ask: Is it possible to build a reverse hash function h'() so that
h(h'(B)) is equal to B?

I do appreciate if you could answer me or send me a hint.

Merry Christmas!

P. L.

Linda Pan, Dec 17, 2004

2. ### Dave LangersGuest

I have a hash function: h().
It all depends upon the nature of the function h of course. If for all B
there exists some A that maps to B, then it is possible to define such a
function h'. Finding the explicit formula might somewhat difficult.

For instance, suppose we have a hash function that maps any text (I
understand that you are using hashes for text) to a number. For
simplicity, let's say this is a short hashtable and the number is in the
range 1-26, then a very simple (but enormously stupid) hash function
would be to take the first letter of the text and convert it to the
corresponding index in the alphabet. For instance
h('example') = 5
h('instance') = 9
etc.etc.
Now an inverse h' could easily be constructed, giving the n'th letter of
the alphabet if supplied with a number n. So
h'(1) = 'a'
h'(2) = 'b'
etc.etc.
A lot of other h' are possible too.

However, it is possible to construct hash functions that cannot always
be inverted. For instance, consider the same function h, but using a
hashtable of length 32. Then h' does not always exist
h'(1) = 'a'
...
h'(26) = 'z'
h'(27) = <undefined>
However, usually hash functions are designed to cover the whole range of
possible indices into the table.

Unless you precisely specify the nature of your function h, we can't be
more specific about whether any such h' exists, and if so, what it is.

Dave Langers, Dec 17, 2004

3. ### Bill McCrayGuest

Was that meant to be "fake plain text"? If not, what is fade plain
text"?
h(B) = B
h(B) = B XOR X'111111111111111 ..."
h(B) = B with the bits reversed

Note that none of these is really a good hash function, since the
purpose of a hash function is to compress a large range of values into
a small range of values. Anytime two or more values hash to the same
value, it is not possible to reconstruct the original from the hashed
value.

Bill

Bill McCray, Dec 17, 2004
4. ### OppieGuest

Wouldn't a reversible hash function be of little use? I mean, if you
have a 1-1 relationship, than what hash is needed? Just use the identity
function.

--
Oppie the Bear
aka TOJ (The Other John)

'Remove' MYWORRIES to email me!

Some days, you're the pigeon.
And some days, you're the statue.

Oppie, Dec 17, 2004
5. ### Bob HarrisGuest

You might get better responses to this at sci.crypt.

and Oppie pondered:
The hash function is many to one, which she implied by 'probably A' is not
equal to A'.

One example would be a password checker. When a user sets her password p
the system stores h(p) in a file. When someone attempts to log in to her
account, they type p', the system compares h(p') to the stored value h(p),
and if they are equal it assumes p' = p and grants access.

p could be a string of any length while h(p) might only be 64 bits. If the
hash function is good the chance that a random guess gives access is 1 in
2^64. Theoretically (the passwords people use aren't that random).

the stored password file, they can't reverse the hash function so they can't
find a p' that works.

For that reason, cryptographic hash functions are designed with the intent
to make reversing them difficult. I presume this is what the OP is
interested in because she used the cryptographic term "plain text".

Bob H

Bob Harris, Dec 17, 2004
6. ### John BaileyGuest

I think the mask value (11111111111.... above) can actually be any
binary sequence.

And if you want to increase the security, shuffle the bits with a
reversible permutation. 52 cards which are exactly shuffled 4 times
results in a sequence which would return the original sequence if
shuffled four more times. Finding other block sizes which allow
similar results requires a tiny bit of playing around.

I think the mask value (11111111111.... above) can actually be any
binary sequence.

John Bailey

John Bailey, Dec 18, 2004
7. ### Bill McCrayGuest

You're right that any sequence of ones and zeros would work.
It seems like I heard that somewhere recently.
Bill

Bill McCray, Dec 18, 2004
8. ### Linda PanGuest

Mr. Harris's answer is exact what I asked. I don't want to obtain the
original plain text via hash value B; instead, I want to get the control.
Once I have a value A', where h(A') = B, I can be granted as a valid user.
That is the problem.

Linda Pan, Dec 30, 2004