# 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\& \space 255) \space mod\space 256$
• Swap the bits $C_n[a]$ and $C_n[b]$
• $C_n = S[C_n]$
-
I don't readily see how you decrypt ... do you have an inverse S-box, too? Also, you seem to have mixed the mode of operation (CBC) with your block cipher design itself, which seems to be not a good idea. – Paŭlo Ebermann Nov 23 '11 at 13:44
"In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation" - I'd say that my cipher fits that definition. Regardless, it's semantics, and its name doesn't affect its security (or lack thereof). I'm really just trying to learn here. – Polynomial Nov 23 '11 at 14:06
You state that the cipher has 16 rounds; which steps are repeated in a round? Step 2 refers to $M_n$ (which is presumably the plaintext message); is that final value of $C_n$ from the previous round? – poncho Nov 23 '11 at 14:26
As is, I'm itching to revert that edit (preferred option) or close whilst we work out how best to accommodate this. Don't get me wrong, I want to accommodate this question, I just don't think one huge open question is the way to go. Specifically, from the FAQ: "Your questions should be reasonably scoped. If you can imagine an entire book that answers your question, you’re asking too much." – user46 Nov 23 '11 at 16:18
@Polynomial Thanks. I think it now works - general question with specific example. I'm even more happy with that way than the way we had it before. Thanks for bearing with us and very sorry for the noise - but when we see a question with a lot of potential we'd rather make the effort to help it out than not. – user46 Nov 23 '11 at 17:15

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.

-
+1, this is an excellent answer, thanks Thomas. – Ethan Heilman Nov 23 '11 at 19:32
Wow. This answer is precisely what I was looking for. The only part I don't quite get is the S-box section - are you implying that a $S[x]$ is meant to exist for every $n$-bit $x$, where $n$ is the block size? Wouldn't this result in ludicrously sized S-boxes? I know you mentioned something about huge S-boxes that can't fit in the universe (yay for the $10^{89}$ particle limit!) but I'm not sure how this works practically. – Polynomial Nov 24 '11 at 7:07
Hmm, do we compute each $S[x]$ for $x$ on the fly, using some function $f$, rather than "caching" the entire $S$ field in an array somewhere? – Polynomial Nov 24 '11 at 7:14
$S$ "exists" as code which can compute a value ($S[x]$) for every $x$. One possible implementation is as a big array. Or you could have a sequence of instructions. That's equivalent here: if you have, e.g., 2 kB of ROM (code + arrays) then you have 16384 bits, and you can possibly compute only $2^{16384}$ distinct functions with that. But there are far many more possible functions with 256-bit inputs than that. Whether you use your ROM budget for code or for data is irrelevant in this computation. – Thomas Pornin Nov 24 '11 at 13:26
Actually, it has been shown that the two keys in the Even-Mansour construction can be identical, with no loss of security. – Demetri Apr 30 at 0:12

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.

-
Does the known plaintext not get prevented by the use of multiple rounds? Since it's essentially $C_n = S[S[S[K_n \oplus M_n] \oplus M_{n+1}] \oplus M_{n+2} ... ]]]$ – Polynomial Nov 23 '11 at 15:15
The above scheme does not use multiple rounds but rather uses only one round with a different round key per message block. A multiple round scheme would have the same the same message block be enciphered by more than one round key. You may have conflated CBC with rounds. I think you should probably abandon the CBC stuff until you have a secure block cipher and then figure out how to use that secure block cipher in a CBC mode. – Ethan Heilman Nov 23 '11 at 15:32
Sorry, must've missed it off my re-write. If you take a look at the edit history, you'll see my original design. It specifies 16 rounds of $C_n = S[K_r \oplus M_n]$ on each block. Would this result in any significant changes in the feasibility of the attacks you described? – Polynomial Nov 23 '11 at 15:36
@Polynomial - Consider the case in which you only have one message block, $C_n = S[K_0 \oplus M_0]$. $S$ is invertible and so we are back to the known plaintext attack. You need the second xor of the key to prevent an attacker from inverting S ($C_n = S[K_0 \oplus M_0] \oplus K_0$) . The approach you should take is, to build a secure block cipher that only processes one message block. If it isn't secure with only one block it is unlikely to be secure with more than one block. – Ethan Heilman Nov 23 '11 at 15:48
Problem: nothing is getting mixed outside of these $16$-bit chunks (a bit in the first $16$-bits never effects the outcome of a bit in any other chunk). That is, the block cipher is really a $16$-bit block cipher. You can brute force and attack each of these $16$-bit chunks. To make it stronger we need diffuse the bits outside of your chunk. You have key substitution network, but what you really want is a key permutation/substitution network ( en.wikipedia.org/wiki/Substitution-permutation_network ). – Ethan Heilman Nov 23 '11 at 16:17

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.

-
Buh? Any chance you could clear up your explanation to avoid use of stuff like $\mathbb{Z}_m$, or at least explain the meaning of them? I'm not versed in such formal notation. I didn't understand a single part of anything you typed in LaTeX. – Polynomial Nov 23 '11 at 17:04
$\mathbb{Z}_m$ is simply the set of integer numbers from $1$ to $m$. In your case, this is the same $m$ as the block size, since after each 256 blocks the effect of the block number $n$ to the cipher is the same as before. I'll try to reword it, though. – Paŭlo Ebermann Nov 23 '11 at 17:09
Same issues for all the stuff like $E : K \times M \to M$. It's completely opaque to me without a description. – Polynomial Nov 23 '11 at 17:16
Probably a question on notation would be in order but let me try to provide a concise explanation here. $E : K \times M \rightarrow M$ means $E$ is a function that uses $K$ to map values of $M$ to other values of $M$. That is the encryption function $E$ uses a key $K$ to map a message to another message with message-space $M$ where messsage-space is the space of all possible messages. It is a notational definition of encryption. – Ethan Heilman Nov 23 '11 at 17:29
@Polynomial: I added some (small-font) explanation for the notation to my article. Though in general, if you don't even know this basic mathematical notation, you are nowhere near the knowledge level necessary to design a secure cipher, sorry. – Paŭlo Ebermann Nov 23 '11 at 17:47