Help with linear cryptanalysis

Question

I am new to linear cryptanalysis, so I decided to try to break a toy cipher that was designed to be vulnerable to linear cryptanalysis. Unfortunately, I can't get it to work no matter how hard I try. I've read the Wikipedia article and several papers, but they always seem vague on how to turn equations that hold over the sbox into ones that hold with high probability over the entire cipher, and I am stuck on that. What am I doing wrong?

First off, the cipher.

# RustleJimmy 2 Block Cipher

sbox = [ ((2 * i + 1) * 0x4d / 2) & 0xFF for i in range(256) ]
sinv = sorted(range(256), key=lambda i: sbox[i])

def T(block):
    # bit transpose of 8 bytes
    x = sum(block[i] << (8 * i) for i in xrange(8))
    t = (x ^ (x >> 7)) & 0x00AA00AA00AA00AAL
    x = x ^ t ^ (t << 7)
    t = (x ^ (x >> 14)) & 0x0000CCCC0000CCCCL
    x = x ^ t ^ (t << 14)
    t = (x ^ (x >> 28)) & 0x00000000F0F0F0F0L
    x = x ^ t ^ (t << 28)
    return [ (x >> (8 * i)) & 0xFF for i in xrange(8) ]

def R(byte, n):
    return (byte >> n) | ((byte & ((1 << n) - 1)) << (8 - n))

def encode(block, key):
    block = [ord(b) for b in block]
    key = [ord(b) for b in key]

    for i in xrange(8):
        block = [ block[j] ^ key[(i + j) & 0x7] for j in xrange(8) ]
        block = [ sbox[block[j]] for j in xrange(8) ]
        block = [ R(block[j], j) for j in xrange(8) ]
        block = T(block)
        block = [ block[j] ^ block[i] if i != j else block[j] for j in xrange(8) ]
    block = [ block[j] ^ key[j] for j in xrange(8) ]

    return ''.join(chr(b) for b in block)

It's a block cipher with a 64bit key that operates on 64 bits. There is no key scheduling; the entire key is used for each round. The sbox is very simple, in fact the three least significant bits are just a linear function of the input. Unfortunately, the linear portion of each round mixes and rotates all the bits so it is not obvious how to take advantage of this.

Here is what I've tried so far.

The sbox is given by $y = 77x + 38 \mod 256$ where x is the input and y is the output. Scaling and rearranging this gives $5y + 2 = 129x + 192$, allowing the equality to be expressed using only xors and 5 nonlinear carry bits. I believe 5 is the minimum possible since the fourth bit is nonlinear and it has to propagate the rest of the way.

Each carry bit can be written using the majority function on three inputs. $$c_{xyz} = majority(x,y,z) = x \wedge y \oplus x \wedge z \oplus y \wedge z$$

This can also be written as the sum of a linear approximation and an error term. $$c_{xyz} = x \oplus y \oplus z \oplus 1 \oplus e_{xyz}$$

Where $e_{xyz}$ is 1 with probability $\frac{1}{4}$.

Given these equations, plugging them into the full 8 round cipher and simplifying gives 64 linear equations relating ciphertext to plaintext and key bits. However, since these equations have error terms, they are not guaranteed to hold. Assuming the error terms are independent (they aren't but for simplicity I had to assume that), then the probability of an equation with $n$ error terms holding is $\frac{1}{2} + \frac{1}{2^n}$. Therefore, we need to find equations with very few error terms.

Unfortunately, the equations produced above had 80-140 error terms each. Using the greedy algorithm to find linear equations with fewer errors resulted in a reduced set with 70-123 terms. Unfortunately, this means that the probability advantage is still only $2^{-70}$, meaning it is much slower than brute force. So at this point I am stuck. What am I doing wrong? With such a weak sbox and few rounds, it doesn't seem like it should be this hard to break the cipher.

Answer 1

For this cipher, I suggest finding all possible linear approximations by simply enumerating them. If $S$ is the S-box, the bias of the linear approximation $\alpha \cdot x = \beta \cdot S(x)$ is given by

$$b(\alpha,\beta) = |2 \Pr[\alpha \cdot x = \beta \cdot S(x)] - 1|.$$

Notice that you can compute $b(\alpha,\beta)$ for a single value of $\alpha,\beta$ with $2^8$ evaluations of the S-box. Also, there are only $2^{16}$ values of $\alpha,\beta$, so it is easy to enumerate all of them and compute $b(\alpha,\beta)$ for all of them. This should help you find high-quality approximations for the S-box.

---

Your next step will be to piece these together into one-round characteristics and then multi-round characteristics. You can do that by hand, but for your cipher, you might want to look at Matsui's algorithm, which is designed to find the highest-bias linear characteristic for multiple rounds, given the biases for approximations of the S-box.

As a starting point, it may be helpful to be familiar with the notion of active S-box. A S-box is considered active in a particular linear characteristic if it is being approximated by some linear approximation other than the trivial approximation $\alpha=\beta=0$. The linear diffusion layer places some constraints on the set of active S-boxes in round $r+1$ as a function of the set of active S-boxes in round $r$. Generally speaking, the more active S-boxes, the lower the bias. (Non-active S-boxes are free: the approximation holds with probability 1 for them, i.e., with bias 1.)

Serge Vaudenay has suggested the following approach for finding high-bias linear approximations: summarize a one-round linear characteristic by a vector $a \in \{0,1\}^8$, where $a_i=1$ if the $i$th S-box is active in that round. Now we can look at pairs $(a,a')$ where $a$ is the summary for a linear characteristic in one round and $a'$ is the summary for a linear characteristic in the next round. Not all pairs $(a,a')$ will be feasible, but some will be. In this way, we can build a graph where the vertices are elements of $\{0,1\}^8$ and there is an edge $a \to a'$ whenever the pair $(a,a')$ is feasible. Now we can look for a path of length 8 in this graph that minimizes the total Hamming weight of the vertices visited along this path; this will correspond to looking for an 8-round linear characteristic with the smallest possible number of total active S-boxes. More precisely, it gives us an upper-bound on the bias of any such 8-round linear characteristic; if the number of active S-boxes in the path is small, there might be a good 8-round linear characteristic with high bias; but if the number of active S-boxes is too large, there's no hope for a good 8-round linear characteristic.

We can even push this idea a bit further. We can annotate each edge $a \to a'$ with the log of the maximum bias of any 2-round approximation where $a$ represents the S-boxes active in the first round of that characteristic and $a'$ the S-boxes active in the second round. Then, we can look for a path of length 8, where we try to minimize the sum of the labels on the edges in the path. This corresponds to a all-pairs shortest-paths path problem in a graph with 256 vertices, and can be solved efficiently using the Floyd-Warshall algorithm.

To test whether the edge $a \to a'$ is feasible, here is a technique that might be helpful. Let $\alpha,\alpha' \in \{0,1\}^{64}$ denote the linear approximation for the first round that we are considering, i.e., $\alpha \cdot x = \alpha' \cdot R_k(x)$ where $R$ is the round function. Note that $a$ is a deterministic function of $\alpha$; i.e., $a_i=0$ if and only if $\alpha_{8i}=\alpha_{8i+1}=\dots=\alpha_{8i+7}=0$. Now we can break $R_k$ into three pieces: the key xor, the S-box application, and a linear function, i.e., $R_k(x)=L(S(x\oplus k))$ where $S(\cdot)$ denotes parallel application of 8 S-boxes. Now both the key xor and the S-box preserve the set of active S-boxes, so we really want to look at the set of feasible linear approximations $\alpha,\alpha'$ for $L$, i.e., $\alpha \cdot x = \alpha' \cdot L(x)$. Given $a,a'$ it is easy to determine whether there exists $\alpha,\alpha'$ that are consistent with $a,a'$ and such that the approximation $\alpha \cdot x = \alpha' \cdot L(x)$ has non-zero bias. You can solve this using Gaussian elimination: for each $i$ such that $a_i=0$, add linear constraints $\alpha_{8i}=\alpha_{8i+1}=\dots=\alpha_{8i+7}=0$, and similarly for $a',\alpha'$; now treat the remaining bits of $\alpha,\alpha'$ as unknowns. Now notice that $\alpha \cdot x = \alpha' \cdot L(x)$ has bias 1 if $\alpha = L(\alpha')$, and bias 0 otherwise. This gives additional linear constraints on the unknowns. Now use Gaussian elimination to check whether there exists a non-zero solution to this set of linear equations.

Or, you can look for multi-round characteristics by hand. That works, too.

---

I am assuming you have read some basic tutorials on linear cryptanalysis, e.g.,

• A Tutorial on Linear and Differential Cryptanalysis. Howard M. Heys.

You can also read some advanced literature that establishes the theoretical foundations underlying linear cryptanalysis, e.g.,

• How far can we go beyond linear cryptanalysis? Thomas Baignères, Pascal Junod, Serge Vaudenay, ASIACRYPT 2004.

• Statistical Cryptanalysis of Block Ciphers. Pascal Junod, PhD thesis, École Polytechnique Fédérale de Lausanne, Switzerland, 2004.

The following paper introduces Matsui's algorithm for finding linear characteristics for DES:

• On correlation between the order of S-boxes and the strength of DES. Mitsuru Matsui. EUROCRYPT '94.