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

Question

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]

Answer 1

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

Answer 2

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.