Andrew Kensler's permute(), a function for stateless, constant-time pseudorandom-order array iteration

18 points by pushcx

bitshift

I knew of cycle-walking but this is my first time seeing a hash function designed for it. It took me a while to see why Kensler's hash stays invertible even when you mask off some of the bits:

Multiplication does not allow high-order bits to affect low-order bits. So multiplication by an odd number is invertible, but just as importantly you can look at bit suffixes (of any length) in isolation, and they will have the same property.
Similarly, whenever idx is XORed with a right-shifted copy of itself, the mask is applied to the right-shifted copy, preventing bits from outside the masked region from changing anything inside the masked region. So this too stays invertible.

Because each individual step keeps the low-order bits invertible, the hash function as a whole is also invertible over those low-order bits, which means you can use it for efficient cycle walking. Pretty cool stuff!

pervognsen

A lot of these things can be explained in a simple and general way algebraically. E.g. if x is a nilpotent operator (the nth iterate x^n eventually becomes the 0 operator) the geometric series 1/(1+x) = 1 - x + x^2 + ... truncates to a finite sum, so the operator 1+x is invertible with that as its inverse. This makes it easy to solve toy cryptanalysis problems like https://cryptopals.com/sets/3/challenges/23.