3
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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). $\endgroup$ Aug 7, 2022 at 19:08
  • 2
    $\begingroup$ Related Q&A: crypto.stackexchange.com/questions/20228/… $\endgroup$ Aug 8, 2022 at 10:53
  • $\begingroup$ Stack overflows policy goes: Self-vandalism is reverted, You can still delete the question. We can also anonymize the post, if you want. $\endgroup$
    – fgrieu
    Aug 14, 2022 at 13:14

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ To be a bit picky, the affine vs. linear distinction means that this only holds for plaintext of odd Hamming weight. One additional chosen plaintext (e.g. the all zeros plaintext) is needed to recover the rest. $\endgroup$
    – Daniel S
    Aug 8, 2022 at 4:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.