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.