It relies on the fact that there's no Si+1 that satisfies Si+1 XOR (Si+1 >> 1) = Si XOR w1 is this right? So I want to make a proof of that.
You are right, but there is a problem, it should be S
i-1 XOR (S
i-1 >> 1) = S
i XOR w
1.
If the specific proof is stuck, you can put it away first.
for example.
w0=10010110, w1=01110101
s0=10100010
s0 >> 1 = 01000101
give m=0
s1=w0 xor (s0 xor (s0 >> 1)) = 10010110 xor (10100010 xor 01000101) = 10010110 xor 11100111 = 01110001.
suppose we know s1=01110001, we don't know whether m=0 or m=1, now we guess w=1, we have s0 xor (s0 >> 1) = s1 xor w1 = 00000100.
by the definition of cycle shift, no s0 can be found.