Reverse Hash Function

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

  1. Linda Pan

    Linda Pan Guest

    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
    #1
    1. Advertisements

  2. Linda Pan

    Dave Langers Guest

    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
    #2
    1. Advertisements

  3. Linda Pan

    Bill McCray Guest

    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

    Swap first and last parts of username and ISP for address.
     
    Bill McCray, Dec 17, 2004
    #3
  4. Linda Pan

    Oppie Guest

    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
    #4
  5. Linda Pan

    Bob Harris Guest

    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 advantage of this system would be that even if someone gains access to
    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
    #5
  6. Linda Pan

    John Bailey Guest

    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
    http://home.rochester.rr.com/jbxroads/mailto.html
     
    John Bailey, Dec 18, 2004
    #6
  7. Linda Pan

    Bill McCray Guest

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

    Swap first and last parts of username and ISP for address.
     
    Bill McCray, Dec 18, 2004
    #7
  8. Linda Pan

    Linda Pan Guest

    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
    #8
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.