CS-Cipher is a block cipher which has been proposed at FSE 1998. It is a Markov cipher in which diffusion is performed by multipermutations. We first provide a formal treatment for differential, linear and truncated differential cryptanalysis, and we apply it to CS-Cipher in order to prove that there exists no good characteristic for these attacks. This holds under the approximation that all round keys of CS-Cipher are uniformly distributed and independent. For this we introduce some new techniques for counting active Sboxes in computational networks by the Floyd-Warshall algorithm.