Security of simple xor and s-box cipher?

Question

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\& \space 255) \space mod\space 256$
• Swap the bits $C_n[a]$ and $C_n[b]$
• $C_n = S[C_n]$

Answer 1

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.

Answer 2

I'm going to ignore the "CBC" part of the question and focus on "What are the strengths and weaknesses of a s-box and xor cipher. I'm going to assume that the s-box size is smaller than the message block size since any cipher that has a block size that is equal to it's s-box size is going to have a block size small enough to be brute forced.

Using xor and s-boxes we need some way to "mix" or diffuse the information in the message block to all the bits in ciphertext block. Typically this is down using a permutation as is done in a permutation-substitution network.

To reframe this within the scope of the question, a cipher that did not use permutations to mix the bits across substitution boundaries will be easy to brute force since the ciphertext block can we broken into chunks and each chunk can be attacked independently.

EDIT: These attacks on the scheme apply to the original scheme (which is posted at the bottom of the question) and may not apply to the new scheme (although they are general methods of attack).

I like this question a lot because it gets at the heart of what makes a strong block cipher and what makes a weak block cipher. If I have made mistakes in understanding your scheme, please don't hesitate to correct me. Here are the weaknesses in the design that a strong block cipher would protect against:

Known plaintext attack - Given that an inverse s-box $S^{-1}$ exists the final step $C_n = S[C_n]$ is always invertible by an attacker. The second to the last step is only 256 possibilities since we know $S^{-1}[C_n]$ and we can check all possibilities. We now know several bits of the round key (which is bad as we will discuss below) we also know the result of $S[M_n \oplus k_r] \oplus C_{n-1}$ which we will call $R_n =S[M_n \oplus k_r] \oplus C_{n-1}$. This is really bad because the ciphertext $C_{n-1}$ is public knowledge and $S[M_n \oplus k_r]$ is invertible. Given these two facts we can find $M_n \oplus K_r$ by

$$S^{-1}[R_n \oplus C_n] = M_n \oplus K_r$$

Given a known plaintext $M_n$, and $M_n \oplus K_r$ we learn the round key $K_r$. As I'll talk about below, the round key gives us the full key $K$ which allows us to decrypt the rest of the message.

Weak Keys Schedule - Rotations don't mix up the round keys ($k_r$) enough. Consider these three attacks:

1. Weak Keys - Someone chooses a key that is the same key under some or all of the rotations, for example consider the key $00000...000$ or the key $010101010...01010$. Under these conditions each round or some percentage of rounds is using the same key making attacks far easier.

2. Round keys are invertible to full keys - Given a round key $K_r$ we can easily perform the inverse rotation to get the full key $K$. Therefore breaking one round (the last round) breaks all the rounds.

3. Related Keys Attacks - Related keys have related round keys only different by a fixed rotation and therefore they have the same number of 1's, the same distance between these 1's, etc... This is bad.

The number of round keys is related to the number of message blocks - If I read your scheme correctly the each round key is used for a different message block. That is $K_0$ is used for $M_0$, $K_1$ is used for $M_1$, and so on. If you are only encrypting one block, you are only performing one round. This is extremely dangerous because you aren't performing 16 cipher rounds per ciphertext block, but 1 round per ciphertext block meaning that the equations to determine the input bits from the output bits are going to be extremely short and easy to solve. I also doubt that you would get sufficient active S-boxes in that many rounds.

You might enjoy these slides on minimalist cryptography.

For the purposes of inquiry consider the simpler and most secure scheme, though still not actually secure.

$$C_n = S[K \oplus M_n] \oplus K$$

Where $S$ is a 16-bit s-box and the block size is also 16-bits.

Answer 3

As I already said in my comment, what you have here is not what one usually calls a block cipher.

A (standard) block cipher is a pair of functions $$E : K \times M \to M \text{ and } D : K \times M \to M$$ _{This means $E$ takes an element of $K$ and an element of $M$ as input, and gives an element of $M$ as output – same for $D$.}
(where $K$ is called the key space and $M$ the "block space") such that for each $y \in K$ and $x \in M$, we have $$D(y, E(y, x)) = x.$$

Normally $K$ and $M$ are finite sets of the form $K = \{0,1\}^k$ and $M = \{0,1\}^m$, where $k$ is called the key size, $m$ is called the block size. (But block ciphers for other block types can be constructed from these, see "format-preserving encryption").

We then evaluate the security of the primitive $(E, D)$ (considering the key secret), before going on to fit the block cipher into a mode of operation (which itself can then have its security evaluation independent of the cipher).

What you are using, is a function pair of the signature $$E, D : K \times I \times M \times M \to M$$ (where I is some index space – in your case $I = \mathbb Z_m = \{0, ..., m-1\}$ is enough, with $m = 256$ being the block size, but we could also use $I = \mathbb N$, the set of all natural numbers).

^{I.e. both your encryption function $E$ and your decryption function $D$ each take a key, an index, and two message blocks as input, and output a message block.}

These functions should have this property: $$ D(y, n, c, E(y,n,c, x)) = x \qquad \forall y \in K, n \in I, c \in M, x \in M.$$

^{Giving the same key, index and "additional block" to encryption and decryption function, the decryption function just gives back the original plaintext provided to the encryption function.}

Function pairs such as these are known as tweakable block ciphers, though usually the tweak is smaller than the key and block. (The tweak in your case would be the pair $(n, c)$.) An example for a known tweakable block cipher is the Threefish cipher which is used as a primitive inside of the Skein hash function (one of the SHA-3 candidates).

This is then used in a special mode (not CBC, though it looks similar) where the block number is used as the $n$ input, and the previous ciphertext block as the $c$ input (to both encryption and decryption), in addition to the key $y$ – we could call this "ciphertext-to-tweak chaining" mode.

Now, you have multiple things to do:

• define a suitable security notion for your cipher type.
• make it credible that your concrete cipher has these security properties
• make it credible that your chaining mode, provided the cipher itself is secure, has the necessary properties to use it for message encryption.

This is more complicated than defining a block cipher (in the ordinary sense) and using a standard mode of operation (which already comes with a security proof), and thus less likely to succeed. Also, you will likely get less cryptanalysis this way, as it is a non-standard model.