help with cryptanalysis of a sponge permutation

Question

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
  • Set input_byte[index % input_byte_length] = psuedorandom_byte ^ (counter % 256)

In python:

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?

Edit

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.

Edit 2

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

Edit 3

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

Answer 1

I don't think there is a way to check the period of such a sequence without actually computing it. That being said, having a long period like that is not desirable in cryptography.

A psuedorandom permutation is invertible. The fact the algorithm presented is not means that it is closer to being a psuedorandom function then a psuedorandom permutation.

However, I say "closer to", because a psuedorandom function will enter a cycle after significantly less then $2^N$ applications. The behavior of having such a long cycle length distinguishes the function from a random one.

The function presented produces biased output. Ideally, a proper hash function should evenly distribute it's output over the space of all possible bytes. Meaning, that if you take enough samples, for each index of output, you should see 256/256 different symbols appear at each index. Running my metrics against a sponge using the supplied function produces heavily biased outputs:

Testing for byte bias...
Byte bias:  32 [256, 90, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]

The first number indicates the output size (32 bytes). The list that follows shows how many different possible byte values occurred at each index. Ideally, all the numbers should read "256" - the function supplied here has difficulty with all but the first index.

I blame this on pursuing the unnecessary requirement to produce a function that cycles through all inputs when applied recursively. Prioritizing this unnecessary "feature" comes at the expense of other features which are actually necessary.

The s-box created by the 251/257 modular exponentiation has a probability 128/256 differential (xor: 128 -> 253). This is very bad, and modular exponentiation is slow for a symmetric primitive on top of that. The framework of differential cryptanalysis can be applied to hash functions, and if the design were stronger, that's what I would suggest. It is probably overkill to bother with that here, however.

Now for the (relatively) good points. The function by itself achieves first preimage resistance - given the output, it is hard to find the specific input that produced it. Note the sponge construct itself would achieve this effect by virtue of the capacity bytes that are not output when output is "squeezed".

However, second preimage resistance, the ability to find any input that could produce a given output, is harder to acquire, and is arguably a more important requirement. Though, this is probably a difficult feat to achieve given a single pass over the data, even with a good, well thought out design. Many real world hash functions utilize upwards of dozens of rounds to help achieve this end.

The state variable is similar to a recursive diffusion layer, and is responsible for much of any good points the design does possess. I personally now opt for a xor-sum instead of an additive one, and create a nonlinear effect by adding the state byte to the target byte (mixing xor/modular addition contributes to a nonlinear effect).

Ideally, the counter acts like a nonce that can break up an otherwise identical string of bytes (i.e. 0000000...0). It fails to be particularly helpful here, as is evidenced by the biased output. But it's still a nice technique to keep in mind.