# AES with a different implementation of byte substitution step

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..

• S-Boxes, that can be approximated with some linear functions, make a cipher more vulnerable for linear cryptanalysis. For instance, 5-th S-Box in DES cipher has "tiny linearity" and it makes possible an attack, that recovers key bits with high probability in $2^{43}$ $(m, c)$-pairs (compared to $2^{56}$ for exhaustive search). Aug 7, 2022 at 19:08
• Related Q&A: crypto.stackexchange.com/questions/20228/… Aug 8, 2022 at 10:53
• Stack overflows policy goes: Self-vandalism is reverted, You can still delete the question. We can also anonymize the post, if you want.
– fgrieu
Aug 14, 2022 at 13:14

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.
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.