Security of simple xor and s-box cipher? What weaknesses (or strengths) do block ciphers based on only key xor and s-box have when operating in CBC mode?

A cipher's internal primitive might be a simple as this:

$C = S[M \oplus k]$, where $C$ is ciphertext, $M$ is the plaintext message, $k$ is the key and $S$ is an S-box.

Assume the follwoing:


The key $k$ is sufficiently large and is random.
The initialization vector used by CBC is random.
The block size is reasonable, e.g. 128 or 256 bits.
The S-box is chosen such that correlation bias between $S[x]$ and $x$ is low.
The S-box is chosen such that $S[a]$ and $S[b]$ are independant for any random $a$ and $b$.


EDIT: Completely re-written to be more general, removing all specific implementation details.



Here's the original custom scheme, which was considered too broad to be a valid question:

$k$ is a 256-bit key, $S$ is a 16-bit S-box that has some set properties.

The cipher operates in CBC mode (as you'll see in the second step), has a block size of 256 bits, and operates as follows for a total of 16 rounds:


$k_r = rot(k, r)$, where $k$ is the key, $r$ is the round number and $rot()$ is a circular shift operation.
$C_n = S[M_n \oplus k_r] \oplus C_{n-1}$ where $n$ is the block number (assume $C_{-1}$ is the IV)
Select $a = 3(r+n) \space mod\space 256$
Select $b = (k_r \space\&amp; \space 255) \space mod\space 256$
Swap the bits $C_n[a]$ and $C_n[b]$
$C_n = S[C_n]$
Let a "block cipher" be defined with a fixed S-box $S$ (i.e. a permutation of some space) and a key $K$ (same size than a block), such that the encryption of a block $M$ is $C = S[P\oplus K]$. Everybody knows $S$ and can apply and invert it (that's a "S-box", not a "key" -- if the S-box is "key dependent" then the S-box is itself a block cipher in its own right, and that's another question). Since the key has the size of a block, blocks are supposed to be large enough to defeat exhaustive search on the key (say, we use 128-bit blocks).

Hence, given a single known plaintext block and the corresponding ciphertext, an attacker can trivially recover $K$: $K = S^{-1}[C] \oplus M$. This is weak unless you ever encrypt a single block with a given key, in which case this is just One-Time Pad. The S-box here is a red herring: as a generic rule, any fixed public permutation for which either the input or output is known can be "removed" at will, so it adds nothing to security. For instance, in DES, the "Initial Permutation" and the "Final Permutation" (which swap bits around in a 64-bit word) can be abstracted away from the security analysis, because anybody can apply and unapply them. Without the S-box, we get $C = M \oplus K$, the well-known equation for OTP.

Since a fixed permutation is as good as gone when it operates on known values, and since we usually consider that the attacker knows some plaintext/ciphertext pairs, this means that a S-box, to be useful, must be "isolated" from both plaintext and ciphertext. So we can imagine the following design:

$$ C = K \oplus S[M \oplus K] $$

This is what @Ethan suggests to study as an exercise (except the he talks about 16-bit blocks, hence a 16-bit key, which is trivially undone through exhaustive search; here, let's assume that $C$, $M$ and $K$ are sequences of 128 bits). If you look at the slides that Ethan points to, you will learn that this is a special case of a more generic construction from Even and Mansour, which goes like this:

$$ C = K_2 \oplus S[M \oplus K_1] $$

with two $n$-bit keys $K_1$ and $K_2$. John Daemen has then shown that although the total key material length is $2n$ bits, you get much less security, actually no more than $2^{n/2}$. With $n = 128$, that's "64-bit security", a rather low value against today's technology (64-bit exhaustive key search is expensive but has been done at least once with thousands of machine and 5 years of computation). With $n = 256$, we could hope for 128-bit security, albeit with 512 bits of key material.

However, there are two important points about that:


The subkeys $K_1$ and $K_2$ should be unrelated. Using the same key for both, or simply keys which admit simple algebraic relations, may allow for many additional attacks.
The $2^{n/2}$ bound is for a generic S-box, i.e. a permutation taken at random over all the permutations of $n$-bit blocks. But the S-box is computable. There exists a rather compact piece of code which can run it in both directions. Yet, there are $2^n!$ permutations of $n$-bit blocks, which implies that the minimal representation of a random permutation will need, on average, at least $2^{264}$ bits, if $n = 256$. This is ludicrously high (it will not fit in the known Universe). Conclusion: an actual implementation of that cipher will use a specific S-box out of the very limited set of S-boxes than can be computed by some code which fits in a few kilobytes of opcodes and constant arrays. The S-box necessarily has some structure. Structure might be exploitable, and often is. The $2^{n/2}$ theoretical strength may then be hard to reach in practice.


So the Even-Mansour scheme is not "secure enough". What do cryptographers do in such a situation ? They add more rounds ! So we are talking about something like:

$$ C = K_5 \oplus S[K_4 \oplus S[K_3 \oplus S[K_2 \oplus S[K_1 \oplus S[K_0 \oplus M]]]]] $$

for, say, 5 rounds. How many rounds do we need ? This depends on the specific unavoidable structure of $S$, and also on how "different" the $K_i$ are (we would, in practice, generate the $K_i$, dubbed "subkeys", from a master key $K$ through a deterministic process -- the "key schedule" -- which itself will have some potentially exploitable structure). We want the whole thing to be decently efficient, so we cannot add thousands of rounds, and we must cope with a relatively simple $S$.

Down that road lies... the AES itself. With 128-bit blocks and a 128-bit master key, the AES uses 10 rounds, hence 11 subkeys. Each round $S$ is a combination of a few operations, some linear (in a given vector space over $\mathbb{F}_{256}$), and an internal fixed permutation over 8-bit blocks (what the AES specification calls "the S-box", but not what we call $S$ in this text !). The AES is believed secure for what it is meant to be. It has raised a few concerns about "related keys": pairs of keys which induce the corresponding AES instances to behave in a related way, which can be detected; nothing serious for encryption, but something to watch for if you want to use the AES as part of, say, a hash function. This is due to the mathematical structure in the key schedule. The Whirlpool hash function is a hash function derived from the AES, and the first thing the Whirlpool designers do was to replace the AES key schedule with something with less exploitable structure (but also slower).

Summary: designing a block cipher as a sequence of XOR with (sub-)keys mixed with a fixed permutation of the whole block space is a valid block cipher design. But with a single "perfect" S-box and two sub-keys, you do not get your money worth of security (you get at most $2^{n/2}$ of a $n$-bit block). And since both the S-box and the key schedule cannot be "perfect", you have to add more rounds, and be very careful about the mathematical structures that you must necessarily employ. The current best-in-class design with that kind of structure is the AES, and it took many smart cryptographers and a lot of time to actually build some trust in its security.