Basic attacks on McEliece; finding S and P
After another good read through the current research papers [1, 2, 3] I'm not so sure anymore that the above stated problem does indeed have a solution, yet. I think it heavily depends on the chosen code $G$ whether it is possible to break the system; and all system breaking algorithms gave $S$ as well (or their equivalent in the Niederreiter cryptosstem).

I now do not think it is possible to retrieve $S$ given $G$ alone.