AES with a different implementation of byte substitution step

Question

I have tried to answer this question for quite some time now. But a complete intuitive understanding still eludes me:

suggested a new implementation for AES:
The byte substitution step will be replaced by the function: $$s(b_0b_1b_2b_3b_4b_5b_6b_7)\,=\,b_7b_0b_1b_2b_3b_4b_5b_6$$

( a cyclic shift of one bit to the right) The question is: How does this change affect the safety of AES, and how many pairs (p,c) are needed to attack successfully?

Note: I understand that the purpose of the replacement step is to reduce the correlation between the input bits and the output bits at the byte level and that the above implementation weakens the safety, but I don't understand how and why more deeply..

Answer 1

If this is the mapping for the Sbox then $$ S(a\oplus b)=S(a)\oplus S(B),$$ i.e., we have a linear Sbox. If you add two vectors and shift it is the same result as shifting them first then adding.

Combined with the ShiftRows and MixColumns and AddRoundKey stages the whole AES is now linear (strictly speaking affine, due to additive constant in the MixColumns).

Edit: Being more precise, if the plaintext * has even Hamming weight* then an additional known plaintext (the all zero plaintext) is needed, as pointed out in the comments.

This means, for example, that if you can mount a chosen plaintext attack where only the $128$ plaintexts $$ e_1=(1,0,0,\ldots,0,0),\\ e_2=(0,1,0,\ldots,0,0),\\ e_3=(0,0,1,\ldots,0,0),\\ \vdots\\ e_{127}=(0,0,0,\ldots,1,0),\\ e_{128}=(0,0,0,\ldots,0,1), $$ with their corresponding ciphertexts, say $f_i=E_K(e_i) \in \{0,1\}^{128},$ are enough to obtain the mapping (for the given secret key $K$). This is because any plaintext is just a linear combination of these plaintexts. For example $$ (p_1,\ldots,p_{128})=\sum_{i=1}^{128} p_i e_i=\sum_{i=1:p_i=1}^{128} e_i $$ and the corresponding ciphertext is $$ \sum_{i=1:p_i=1}^{128} f_i. $$ So you can directly obtain any unknown plaintext from the ciphertext by solving a linear system of equations. Since AES is by design bijective for a fixed key this will work.