I'm reading about the attacks of the McEliece cryptosystem. I needed to work out a lot of things because most descriptions I have found so far on the internet seems to be quite hand-wavy about the details. So I wrote down what I understand or I think I understand then I have some questions at the end.
In a McEliece cryptosystem the public key consists of a $k×n$ key matrix $K$ and and the number of errors $t$ to introduce into the ciphertext. To encrypt we take a $k$ element long message $\mathbf{m}$, an $n$ element long error vector $\mathbf{z}$ with $t$ non-zero elements, and finally we get the ciphertext $\mathbf{y} = \mathbf{m}K + \mathbf{z}$.
The attacker can decode the plaintext using information set decoding (ISD). In which we choose $k$ random linearly independent columns from $K$ to form an invertible $k×k$ square matrix $A$, also we choose $k$ elements from the same positions as the columns to form the vector $\mathbf{a}$. In an attempt to get the plain text we compute $\mathbf{q} = \mathbf{a}A^{-1}$, if all elements in a are error free this should give us the plain text. Verify the result by computing $\mathbf{y} - \mathbf{q}K = \mathbf{m}K + \mathbf{z} - \mathbf{q}K = (\mathbf{m}-\mathbf{q})K + \mathbf{z}$. If $\mathbf{m} = \mathbf{q}$, then the result is $\mathbf{z}$ which has $t$ non-zero elements and we are done. If $\mathbf{m} \neq \mathbf{q}$, then our guess was wrong. The Hamming distance between two codewords is it least $2t+1$, so $(\mathbf{m}-\mathbf{q})K$ is a vector that has at least $2t+1$ non-zero elements. $\mathbf{z}$ has $t$ non-zero elements so even if $\mathbf{z}$ happens to cancel exactly $t$ elements from $(\mathbf{m}-\mathbf{q})K$, then the result still has $t+1$ non-zero elements. So having more than $t$ non-zero elements in the result means failure.
The McEliece cryptosystem chooses the parameters such that finding error free sub sequences is unlikely.
Then I read that there are other attacks. One that turns the problem into a shortest codeword finding problem. And does so by changing the linear code to such that message is mapped like this: $\mathbf{x} \mapsto \mathbf{x}K - \mathbf{y}$. So this translates the codewords in the code defined by $K$ and this preserves the minimum Hamming-distance requirements so it's still an error correcting code. In this code there is no zero element and the shortest codeword is $-\mathbf{z}$ with $t$ non-zero elements (when $\mathbf{x} = \mathbf{m}$). Since the minimum distance is still $2t+1$ all other codewords have at least $t+1$ non-zero elements. So if we can find this shortest codeword, then we can remove errors from the ciphertext making the ISD succeed on first try.
Now here is one thing I got stuck at: the code obtained by translation isn't a linear code because translation isn't linear transformation. The linear combination of codewords in it isn't necessarily another codeword, and doesn't contain an all-zero codeword. Right?
But still most descriptions I saw proceed by adding $\mathbf{y}$ as a new row into $K$, then compute the parity check matrix of this modified code and feed it into a minimum-length codeword searching algorithm such as Stern's algorithm. How and why does this work when the code isn't linear?
