I have been studying and researching hash functions. So far my research has led me to the sponge construction. It appears that the permutation used in the sponge to stir the state is more or less central to the security, along with the capacity/rate. Consequently, I have been making and breaking toy permutations to better understand them. I have managed to put together a permutation that I would like assistance or a pointer in cryptanalyzing, as I have more or less run out of ideas.
The permutation is as follows:
- A state is initialized to
(45 + sum(input_bytes)) * input_byte_length * 2
- For each index and byte in the enumerated input bytes:
- Generate a psuedorandom byte:
(251 ** (state xor byte) % 257) % 256
input_byte[index % input_byte_length] = psuedorandom_byte ^ (counter % 256)
- Generate a psuedorandom byte:
def permute_state(_bytes): byte_length = len(_bytes) state = (45 + sum(_bytes)) * byte_length * 2 for counter, byte in enumerate(_bytes): psuedorandom_byte = pow(251, state ^ byte, 257) % 256 _bytes[counter % byte_length] = psuedorandom_byte ^ (counter % 256) return _bytes
What I have found is that it appears to have a long period relative to the length of the input bytes. Recursively permuting an initial state of 1 null byte cycled after 255 applications, an initial state of 2 null bytes cycled after 30 some odd thousand applications, and I did not wait for the initial state 3 null bytes to finish, so I don't know long before it cycled.
Is there a way to calculate the period of this permutation? It appears to vary greatly depending on the magic expression that initializes the state; I found the state presented here after trying various combinations of expressions, but do not understand how/why it appears to influence the cycle length when recursively permuting.
I was able to invert the permutation when the input size was a single byte. However, my attempt to apply the same strategy for longer lengths was unhelpful; I ended up with a list of 256 state/byte pairs that could have produced the output byte. My strategy to invert a permutation of 1 byte was as follows:
- The first output byte can be inverted via finding the combination of state xor byte that is supplied to the modular exponentiation step;
- The state is a relatively small space to search through, but guessing is efficient when the length of the input bytes is
1; state equals
90 + input_byte_value
- Cycle through 256 bytes and find the one that produced the output
However, when I attempt to apply these steps to a permutation of input size > 1, I found I ended up guessing state and input byte independently of each other, and thus ended up with 256 different byte + state combinations, which provides nothing to go on for me.
I have seen awesome questions and answers like this and was wondering if there was a more statistical sort of way to reverse engineer the state/input bytes of the permutation.
The formula of the permutation here sort of reminds me of linear congruential generators or linear feedback shift registers or the like. Does this permutation fit into any general class of algorithms with particular known weaknesses? If so, what weaknesses could I exploit to recover the state or reverse the permutation? Are there any ways to compensate for said weaknesses?
I have not considered the platform endianness during any of my research so far. Incidentally, my platform is little endian.
No padding is applied inside the permutation to either the "state" or the input.
Note that the "state" that is initialized each permutation function call is not the internal state of a hash function; The internal state of a hash function is what this permutation would operate on, and the "state" mentioned here is temporary and could possibly be better named (open to suggestions, if so). "Key" may be a more accurate term, though it is generated and not supplied to the call.
I made a modification with a longer cycle when applied recursively, by including the next byte when generating the psuedorandom byte. I am not sure if this also resolves the mistake pointed out by CodesInChaos, but it increased the cycle length which is something I'm very curious about:
psuedorandom_byte = pow(251, state ^ byte ^ (_bytes[(counter + 1) % byte_length] * counter), 257) % 256
Upon further consideration of the simplest example of a 1 byte state, I realized that, for a 1 byte state, the function basically produces the same noise wave. A different input is to the function is equivalent to selecting a different starting point on the wave, and recursive calls just cycle forward through the wave one point at a time.
The initial state could be determined by recording 2 ** 8 outputs, or the entire cycle. Technically, for a one byte state, just knowing the one output allows you to know the previous one, and by extension all the ones before that.
However, I am not exactly sure how this train of thought extends to a multiple byte input state. I'm not sure if the same wave is generated with the difference being where on the wave it starts, or if different noise waves are generated by differing combinations of bytes. I conjecture the latter, as some combinations of input bytes do not have the same cycle length. I'm also not sure how to extend this idea beyond capturing all of the output bytes and finding which seed produced that particular order.
I graphed the noise wave for the one byte cycle, if anyone is curious to see it:
Permutation explained (as mentioned in the comment area):