Reversing an integer hash function (opens in new tab)

(taxicat1.github.io)

87 pointsflebron4y ago16 comments

16 comments

rurban4y ago

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

But only 3 so far.

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

Retr0id4y ago

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

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

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

superjan4y 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

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

dragontamer4y 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)

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

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

praptak4y ago

Basically every cipher works like this.

namibj4y ago

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

omegalulw4y ago

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

Retr0id4y ago

XXHASH64 is bijective for 64-bit input strings.

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

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

j / k navigate · click thread line to collapse

16 comments

rurban4y ago

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

But only 3 so far.

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

Retr0id4y ago

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

superjan4y ago

ninkendo4y ago

superjan4y ago

[0] https://lampwww.epfl.ch/papers/idealhashtrees.pdf

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

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

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

hinkley4y ago

praptak4y ago

Basically every cipher works like this.

namibj4y ago

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

omegalulw4y ago

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

Retr0id4y ago

XXHASH64 is bijective for 64-bit input strings.

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

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

j / k navigate · click thread line to collapse