7 ms·

Reversing an integer hash function

87 points by flebron 5y ago

rurban 5y ago
I'm collecting such inverters at https://github.com/rurban/smhasher/tree/inverse/inverse https://github.com/rurban/smhasher/tree/inverse/inverse But only 3 so far.
- elsamuko 5y ago
  For the cryptopals challenge, you have to invert the Mersenne Twister scramble function: https://cryptopals.com/sets/3/challenges/23 https://cryptopals.com/sets/3/challenges/23 https://github.com/elsamuko/cryptopals/blob/610ab19bf6823a34ab22123cfeeedadacf0fcc13/src/random.hpp#L101 https://github.com/elsamuko/cryptopals/blob/610ab19bf6823a34...
- Retr0id 5y ago
  I wrote an inverter for XXHASH64, in python: https://gist.github.com/DavidBuchanan314/13020be9e2a251e2a2a5cd357049a756 https://gist.github.com/DavidBuchanan314/13020be9e2a251e2a2a...
superjan 5y ago
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.
- praptak 5y ago
  Basically every cipher works like this.
- ninkendo 5y ago
  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 5y ago
    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 https://lampwww.epfl.ch/papers/idealhashtrees.pdf
- hinkley 5y ago
  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).
- JD557 5y ago
  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 5y ago
    > 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)
- judofyr 5y ago
  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.
- namibj 5y ago
  For 64bit: (triple)DES should do the trick.
- omegalulw 5y ago
  A hash is typically used in the context of mapping arbitrary size input to fixed size output.
- Retr0id 5y ago
  XXHASH64 is bijective for 64-bit input strings.
duckfacts 5y ago
deleted 5y ago
[deleted]
clon 5y ago
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 5y ago
> 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".

87 points by flebron 5y ago

I'm collecting such inverters at https://github.com/rurban/smhasher/tree/inverse/inverse https://github.com/rurban/smhasher/tree/inverse/inverse But only 3 so far.

elsamuko 5y ago
For the cryptopals challenge, you have to invert the Mersenne Twister scramble function: https://cryptopals.com/sets/3/challenges/23 https://cryptopals.com/sets/3/challenges/23 https://github.com/elsamuko/cryptopals/blob/610ab19bf6823a34ab22123cfeeedadacf0fcc13/src/random.hpp#L101 https://github.com/elsamuko/cryptopals/blob/610ab19bf6823a34...
Retr0id 5y ago
I wrote an inverter for XXHASH64, in python: https://gist.github.com/DavidBuchanan314/13020be9e2a251e2a2a5cd357049a756 https://gist.github.com/DavidBuchanan314/13020be9e2a251e2a2a...

superjan 5y ago

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.

praptak 5y ago
Basically every cipher works like this.
ninkendo 5y ago
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 5y ago
  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 https://lampwww.epfl.ch/papers/idealhashtrees.pdf
hinkley 5y ago
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).
JD557 5y ago
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 5y ago
  > 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)
judofyr 5y ago
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.
namibj 5y ago
For 64bit: (triple)DES should do the trick.
omegalulw 5y ago
A hash is typically used in the context of mapping arbitrary size input to fixed size output.
Retr0id 5y ago
XXHASH64 is bijective for 64-bit input strings.

duckfacts 5y ago

deleted 5y ago

[deleted]

clon 5y ago

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 5y ago

> 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".