[HN Gopher] Reversing an integer hash function
       ___________________________________________________________________
        
       Reversing an integer hash function
        
       Author : flebron
       Score  : 82 points
       Date   : 2022-01-14 18:06 UTC (1 days ago)
        
 (HTM) web link (taxicat1.github.io)
 (TXT) w3m dump (taxicat1.github.io)
        
       | duckfacts wrote:
        
       | [deleted]
        
       | rurban wrote:
       | I'm collecting such inverters at
       | https://github.com/rurban/smhasher/tree/inverse/inverse
       | 
       | But only 3 so far.
        
         | elsamuko wrote:
         | For the cryptopals challenge, you have to invert the Mersenne
         | Twister scramble function:
         | 
         | https://cryptopals.com/sets/3/challenges/23
         | 
         | https://github.com/elsamuko/cryptopals/blob/610ab19bf6823a34...
        
         | Retr0id wrote:
         | I wrote an inverter for XXHASH64, in python:
         | https://gist.github.com/DavidBuchanan314/13020be9e2a251e2a2a...
        
       | superjan wrote:
       | Is there a category of hash functions that hash a 64/32 bit input
       | to exactly 64/32 bits output, such that all inputs are uniquely
       | preserved? This could be an interesting property for a hash table
       | of integers, because a hash match implies a key match.
        
         | judofyr wrote:
         | This would be a "bijective function" or a "perfect hash
         | function", although the latter is usually used when the input
         | is much smaller than the output.
        
         | praptak wrote:
         | Basically every cipher works like this.
        
         | omegalulw wrote:
         | A hash is typically used in the context of mapping arbitrary
         | size input to fixed size output.
        
         | ninkendo wrote:
         | Even if you used such a bijective hash, your hash table would
         | have to have 2^32 available buckets in order for the hash match
         | to be all you need for lookup. Or 2^64 for 64-bit... which is
         | why nobody really does this. (And if you did this, why even
         | hash the input? The input integer could just be the key, and
         | you're basically using a really big sparse array.)
        
           | superjan wrote:
           | I agree that for standard hash tables this won't work.
           | However, I recently read about "Ideal Hash Trees" [0], that
           | preserves the entire hash. That design also requires all bits
           | to be "random" because it lacks the usual prime division.
           | 
           | [0] https://lampwww.epfl.ch/papers/idealhashtrees.pdf
        
         | namibj wrote:
         | For 64bit: (triple)DES should do the trick.
        
         | JD557 wrote:
         | I think the word you are looking for is "permutation".
         | 
         | However, if you can use a permutation as a hash function, you
         | might be fine with just using the identity function.
        
           | dragontamer wrote:
           | > However, if you can use a permutation as a hash function,
           | you might be fine with just using the identity function.
           | 
           | This certainly isn't true for 8-bit characters using ASCII.
           | 
           | The top-bit of all ASCII strings is always zero, its
           | effectively a wasted bit. Permuting all ASCII characters to
           | randomly use all 8-bits means a better distribution in
           | virtually any hash-based data-structure. (ex: 64 slot
           | hashtable will have fewer collisions after you permute the
           | 7-bit ASCII into an 8-bit random permutation)
        
         | hinkley wrote:
         | Linear congruential generators in some cases can do that,
         | though more often they are used to convert n bits of input data
         | into a uniform distribution over a range from 0-m. For instance
         | simulating chance in a game (dice rolls, or % probability).
        
       | clon wrote:
       | Excellent tutorial for bitwise arithmetic this is. The key is the
       | motivation you receive from the prospect of being able to do
       | something that seems "l33t".
        
       | blastonico wrote:
       | > otherwise you could simply trace backwards and generate an
       | input that produces a specific hash
       | 
       | This is when I know for sure that I'm not included in that "you".
        
       ___________________________________________________________________
       (page generated 2022-01-15 23:02 UTC)