Reversing an integer hash function

https://taxicat1.github.io/hash6432shift_inversion.html

by flebron • 5 years ago

87 16 5 years ago

taxicat1.github.io

rurban• 5 years ago

I'm collecting such inverters at https://github.com/rurban/smhasher/tree/inverse/inverse

But only 3 so far.

elsamuko• 5 years ago

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

Retr0id2• 5 years ago

I wrote an inverter for XXHASH64, in python: https://gist.github.com/DavidBuchanan314/13020be9e2a251e2a2a...

clon• 5 years 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".

superjan2• 5 years 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.

JD557• 5 years 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• 5 years 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• 5 years 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.

praptak• 5 years ago

Basically every cipher works like this.

ninkendo• 5 years 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.)

superjan2• 5 years 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

namibj• 5 years ago

For 64bit: (triple)DES should do the trick.

hinkley• 5 years 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).

omegalulw• 5 years ago

A hash is typically used in the context of mapping arbitrary size input to fixed size output.

Retr0id2• 5 years ago

XXHASH64 is bijective for 64-bit input strings.

blastonico• 5 years 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".

Reversing an integer hash function

Related Stories