Let me see if I understand the security of this algorithm correctly.

It relies on the fact that there's no S_i+1 that satisfies S_i+1 XOR (S_i+1 >> 1) = S_i XOR w₁ is this right? So I want to make a proof of that.

- w₀ and w₁ are L-bit numbers with an odd number of different bits. S₀ and therefore 1, 2, etc are L-bit too.
- XOR is a commutative and associative operation so that makes some of the math easier. The >> is a right shift except it also rotates the bits from the end to the beginning. (XOR is 0 if bits are the same, 1 if they are different)
- S₀ is the initial state.

So that means S₁ = S₀ XOR (S₀ >> 1) XOR w₀, S₂ =  S₁ XOR (S₁ >> 1) XOR w₀, and so on.

In other words we are trying to prove S_i XOR (S_i >> 1) XOR w₀ XOR ([S_i XOR (S_i >> 1) XOR w₀] >> 1) != S_i XOR w₁ .

Which is just (S_i >> 1) XOR w₀ XOR ([S_i XOR (S_i >> 1) XOR w₀] >> 1) != w₁
=  (S_i >> 1) XOR ([S_i XOR (S_i >> 1) XOR w₀] >> 1) != w₁ XOR w₀

So we know that w₁ XOR w₀ = A is going to have an odd number of 1 bits.

And now I'm unable to simplify this further because while I know regular shifts are distributive, and can be distributed over XORs, cyclic shifts can't AFAIK unless there's away to simplify that C function in that Wikipedia link for cyclic shift.

Let me take another statement from the paper that is S₀ looks something like 000011111. Then S₀ >> 1 will be 100001111 (7 positions with different bits) XORing those two makes 011101111. This does correspond to the property mentioned in your paper that XOR of two numbers with N different positions will make a number with an 1s. But I'm unsure how to prove this for all numbers (or if someone has already done this). But at least I verified something from this part myself.