# How can AES-like block cipher without non-linear component be broken?

I am taking a course on block ciphers and recently I have faced up with such an exercise: if an original AES's highly non-linear Sbox is replaced by a linear substitution (see example below), how one can attempt to break the ciphertext?

Complete text of the exercise looks like this: there is a 5120 bit file (40 AES blocks) which was crypted via such a "modified" AES-256 I described above in ECB mode with an unknown key. The attacker has the ciphertext and first 4 blocks of plaintext which corresponds to the first 4 blocks of ciphertext. The attacker does not have the ability to generate chosen plaintext/ciphertext pairs.

Is it possible for the attacker to recover the unknown part of the plaintext?

Here is the modified Sbox:

sbox = [142, 163, 232, 197, 255, 210, 153, 180, 2, 47, 100, 73, 115, 94, 21, 56, 156, 177, 250, 215, 237, 192, 139, 166, 16, 61, 118, 91, 97, 76, 7, 42, 87, 122, 49, 28, 38, 11, 64, 109, 219, 246, 189, 144, 170, 135, 204, 225, 69, 104, 35, 14, 52, 25, 82, 127, 201, 228, 175, 130, 184, 149, 222, 243, 15, 34, 105, 68, 126, 83, 24, 53, 131, 174, 229, 200, 242, 223, 148, 185, 29, 48, 123, 86, 108, 65, 10, 39, 145, 188, 247, 218, 224, 205, 134, 171, 214, 251, 176, 157, 167, 138, 193, 236, 90, 119, 60, 17, 43, 6, 77, 96, 196, 233, 162, 143, 181, 152, 211, 254, 72, 101, 46, 3, 57, 20, 95, 114, 240, 221, 150, 187, 129, 172, 231, 202, 124, 81, 26, 55, 13, 32, 107, 70, 226, 207, 132, 169, 147, 190, 245, 216, 110, 67, 8, 37, 31, 50, 121, 84, 41, 4, 79, 98, 88, 117, 62, 19, 165, 136, 195, 238, 212, 249, 178, 159, 59, 22, 93, 112, 74, 103, 44, 1, 183, 154, 209, 252, 198, 235, 160, 141, 113, 92, 23, 58, 0, 45, 102, 75, 253, 208, 155, 182, 140, 161, 234, 199, 99, 78, 5, 40, 18, 63, 116, 89, 239, 194, 137, 164, 158, 179, 248, 213, 168, 133, 206, 227, 217, 244, 191, 146, 36, 9, 66, 111, 85, 120, 51, 30, 186, 151, 220, 241, 203, 230, 173, 128, 54, 27, 80, 125, 71, 106, 33, 12]


Since the sbox is affine, you can view $s(v)=mv+b$ where $m$ is a 8-by-8 matrix and $b$ and $v$ is a dimension 8 vector over $F_2$. I will show you how to find $m$ and $b$ in Pari-GP. If it is not clear how to use that combined with the description of AES to create an even bigger linear equation and solve, ask.

Write $\mathbf{0} =(0, 0, 0, 0, 0, 0, 0, 0)$. Note that $s(\mathbf{0}) = b$, so all that is left to do is find $m$. Define $$l(v) = s(v) + s(\mathbf{0}) = mv + b + m\mathbf{0}+b=mv + b + b = mv$$ Note this is a linear function:

s(n) = sbox[n+1] \\ pari-gp is 1-indexed
l(n) = bitxor(s(n), s(0))
a = 10
b = 37
print(  bitxor(l(a),l(b)) == l(bitxor(a,b))  )


will output 1 (True in Pari-GP). To find out what the matrix is,

m = matrix(8, 8, {j}, {i}, {
ei = 1 << (i-1);
ej = 1 << (j-1);
bitand(s(ei), ej) == ej
})

print(m)


which outputs

[1, 0, 0, 0, 0, 1, 0, 1;
0, 0, 0, 1, 1, 0, 0, 1;
1, 1, 0, 1, 1, 0, 1, 0;
0, 0, 1, 0, 0, 1, 1, 0;
0, 1, 1, 0, 0, 1, 1, 1;
1, 1, 1, 0, 1, 0, 0, 1;
0, 0, 1, 1, 0, 1, 1, 0;
0, 0, 1, 0, 0, 1, 0, 1]


Note that because of how the indices work it is a little weird to read. The 128-th entry in your sbox, which corresponds to the vector $(0, 0, 0, 0, 0, 0, 0, 1)^T$ is 179, and the last column is $(1, 1, 0, 0, 1, 1, 0, 1)^T$ and binary(179) = [1, 0, 1, 1, 0, 0, 1, 1].

• Thank you very much, that would be extremely helpful for me! As you can see I am new to the cryptanalysis so could I also ask you to show how I should use this affine transformation to recover the key bits? Aug 27, 2017 at 1:33
• I will show you, but first I want you to do some work. Make a bulleted describing list each step of a round of AES in english, and how it can be expressed as a linear equation. Install PariGP (or some other program capable of doing linear algebra) and try to write the step in the syntax of your chosen language. Aug 27, 2017 at 1:55
• When you're done each step of the cipher will be a matrix which you can generate. Aug 27, 2017 at 1:56

You have 64 bytes of known plaintext. This gives $64$ linear equations (over $\mathbb{F}_8$) with the key bytes (32 bytes) as the only unknowns. This should easily be enough to solve the equations. It's possible to write programs to generate the equations and then solve them. Recall your linear algebra... First determine the linear function that the $S$-box implements.

• Thank you for the answer, it makes sense to me! But still I am a little bit confused about the form of the equations. Would you please give an example of such an equation and clarify where the linear function would be used? Aug 26, 2017 at 21:53