3
$\begingroup$

I have a model of substitution permutation networks, modified as follows:
instead of iterating $n$ times a round(each of which is composed of the key mixing phase, substitution S-BOX) and permutation), I apply the key mixing phase to the input $n$ times, followed by $n$ substitution, followed by $n$ permutation.
What can I say about the security of this model?

$\endgroup$
  • $\begingroup$ Hmm. So approximately overall you might have $ c \sim P(S(m \oplus z)) $ where $ z = f(k)$, which is just a constant expansion of $k$? $\endgroup$ – Paul Uszak May 6 at 16:30
  • $\begingroup$ yes, i guess the result is something like that $\endgroup$ – quaqua May 6 at 17:35
4
$\begingroup$

So, the mixing of the $n$ keys is at most as secure as having a uniformly distributed single key. If your key randomness is not strong, doing this kind of mixing can make the key distribution nearer to uniform and helps somewhat [though you should not need to do this but use good randomness and single keys].

The problem is the latter stages. There is no more key mixing. The composition of $n$ substitutions is equivalent to just a single substitution.

This is followed by the composition of the permutation layer, which is itself equivalent to just a single permutation.

So, you really have just a single round cipher, which will be very easy to break by the standard attacks, such as linear and differential cryptanalysis.

$\endgroup$
6
$\begingroup$

Your construction is completely insecure: a single known plaintext / ciphertext block pair is sufficient to decrypt all blocks encrypted with the same key.

Specifically, let me write your block encryption function $E_K$ as $$c = E_K(p) = P^{(n)}(S^{(n)}(p \oplus K_1 \oplus K_2 \oplus \dots \oplus K_n)),$$ where $p$ is the plaintext block, $c$ is the corresponding ciphertext block, $S^{(n)}$ and $P^{(n)}$ denote the $n$ times iterated substitution and permutation steps respectively, $K_1$ to $K_n$ are the $n$ subkeys derived from the encryption key $K$ by the key schedule, and $\oplus$ denotes the linear subkey mixing operation (i.e. normally bitwise XOR).

Since the substitution and permutation phases are invertible and independent of the key, I can just apply their known inverses $P^{(-n)}$ and $S^{(-n)}$ to the known ciphertext block $c$ to obtain the intermediate value $$x = S^{(-n)}(P^{(-n)}(c)) = p \oplus K_1 \oplus K_2 \oplus \dots \oplus K_n.$$ XORing this with the known plaintext $p$ then gives me the bitwise XOR of the subkeys $$\tilde K = p \oplus x = K_1 \oplus K_2 \oplus \dots \oplus K_n.$$ Clearly, given $\tilde K$, I can now decrypt any ciphertext block $c'$ to the corresponding plaintext block $p'$ as $$p' = S^{(-n)}(P^{(-n)}(c')) \oplus \tilde K.$$

The same attack works with trivial modifications also if the key is mixed with the plaintext e.g. using modular addition instead of bitwise XOR. Indeed, all it really needs is for the operation $\oplus$ to be associative and invertible.

Furthermore, even if the subkeys were somehow combined with the plaintext in some weird way that was not trivially invertible, we could still use the approach outlined above of first inverting the unkeyed substitution and permutation steps, leaving only the key mixing steps, and then focusing our cryptanalysis efforts on that. So, in effect, the substitution and permutation steps in your construction provide no cryptanalytic strength whatsoever beyond that provided by the key mixing step alone (which for normal key mixing methods, like bitwise XOR or modular addition, is essentially zero).

In fact, this is why normal substitution–permutation ciphers like AES both begin and end the encryption process with a key mixing step: any unkeyed substitution or permutation steps before the first key mixing step or after the last one would contribute no additional security to the cipher, since an attacker could just invert them even without any knowledge of the key.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.