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 &lt;&lt; (i-1);
    ej = 1 &lt;&lt; (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].