There was a 4-round SPN implemented in python with 64-bit key and block sizes. We were given 65536 pairs of random plaintexts and corresponding ciphertexts encrypted with a single key. The task was to find the key.
The P-box used in the cipher was a pretty standard transposition, the weak part was the S-box. Our attack followed the great tutorial on Linear Cryptanalysis. It was possible to find probabilistically biased linear expressions on the input and output bits of the S-box. We used the following script for this part:
for insum in xrange(256):
for outsum in xrange(256):
if insum&(insum-1) and outsum&(outsum-1):
continue
bias = sum((bin(x&insum).count('1') + bin(sbox[x]&outsum).count('1')) % 2 for x in xrange(256)) - 128
if abs(bias) > 40:
print '+'.join(['X'+str(i) for i in xrange(8) if insum&(2**i)] + ['Y'+str(i) for i in xrange(8) if outsum&(2**i)])This gave us the following expressions (only those are needed where there are only one input or only one output bit involved):
X0+Y0+Y1+Y2+Y7
X1+Y0+Y1+Y3+Y4+Y7
X2+Y0+Y1+Y2+Y3+Y4+Y6+Y7
X3+Y1+Y4+Y5+Y7
X4+Y0+Y2+Y4+Y5+Y6
X0+X3+X4+Y6
X0+X1+X2+X3+X4+Y2
X5+Y0+Y1+Y2+Y3+Y4
X0+X2+X3+X4+X5+Y7
X6+Y1+Y7
X1+X2+X3+X4+X6+Y0
X0+X2+X3+X4+X5+X6+Y1
X7+Y0+Y4
X1+X2+X4+X7+Y5
X1+X6+X7+Y3
X1+X2+X3+X4+X6+X7+Y4
The next part was to find biased linear expressions not just on a single S-box but on the plaintext bits, some bits of the expanded key and on the input bits of the last round S-box, like this is shown in Figure 3 of the tutorial. I started from biased expressions of the first S-box where only one output bit is used and started to propagate those through the the permutations and the other S-boxes using the other biased expressions of S-boxes where only one input bit is used.
# Some precomputations of the P-box to use (byte,bit) indexing
pt = [[None for i in xrange(8)] for j in xrange(8)]
for i in xrange(8):
for j in xrange(8):
c = bytearray('\0'*8)
c[i] = chr(2**j)
d = permutation(c)
i2 = None
for k in xrange(8):
if d[k] != 0:
assert i2 is None
i2 = k
j2 = None
for k in xrange(8):
if (d[i2]&(2**k)) != 0:
assert j2 is None
j2 = k
pt[i][j] = (i2,j2)
K = sympy.IndexedBase('K')
P = sympy.IndexedBase('P')
U4 = sympy.IndexedBase('U4')
def k(i, j, b):
# not interested in which key bits are involved
return 0
def p(i, b):
# plain-text bits
return P[i, b]
def u(i, j, b):
if i == 4:
# this is the input of the last S-box, leave it as it is
return U4[j, b]
# These numbers are from the S-box biases where there is only a single input bit involved, map them to output bits
return sum(map(lambda x: v(i, j, x), [[0,1,2,7], [0,1,3,4,7], [0,1,2,3,4,6,7], [1,4,5,7], [0,2,4,5,6], [0,1,2,3,4], [1,7], [0,4]][b]))
def v(i, j, b):
# From the output of an S-box we can get to the input of the next S-box by using the permutations (and some key bits)
return k(i+1, pt[j][b][0], pt[j][b][1])+u(i+1, pt[j][b][0], pt[j][b][1])
def x(i):
# Input of the first S-box is the plaintext bit ^ a key bit
return p(0, i)+k(1, 0, i)
def y(i):
# Output of the first S-box
return v(1, 0, i)
print x(1)+x(2)+x(3)+x(4)+x(6)+y(0)
print x(0)+x(2)+x(3)+x(4)+x(5)+x(6)+y(1)
print x(0)+x(1)+x(2)+x(3)+x(4)+y(2)
print x(1)+x(6)+x(7)+y(3)
print x(1)+x(2)+x(3)+x(4)+x(6)+x(7)+y(4)
print x(1)+x(2)+x(4)+x(7)+y(5)
print x(0)+x(3)+x(4)+y(6)
print x(0)+x(2)+x(3)+x(4)+x(5)+y(7)This gave us the following biased linear expressions:
P[0, 1] + P[0, 2] + P[0, 3] + P[0, 4] + P[0, 6] + U4[0, 0] + U4[0, 4] + U4[5, 0] + U4[5, 4] + U4[6, 0] + U4[6, 4] + U4[7, 0] + U4[7, 4]
P[0, 0] + P[0, 2] + P[0, 3] + P[0, 4] + P[0, 5] + P[0, 6] + U4[0, 0] + U4[0, 4] + U4[3, 0] + U4[3, 4] + U4[4, 0] + U4[4, 4] + U4[6, 0] + U4[6, 4] + U4[7, 0] + U4[7, 4]
P[0, 0] + P[0, 1] + P[0, 2] + P[0, 3] + P[0, 4] + U4[0, 0] + U4[0, 4] + U4[1, 0] + U4[1, 4] + U4[3, 0] + U4[3, 4] + U4[4, 0] + U4[4, 4] + U4[5, 0] + U4[5, 4] + U4[6, 0] + U4[6, 4] + U4[7, 0] + U4[7, 4]
P[0, 1] + P[0, 6] + P[0, 7] + U4[0, 0] + U4[0, 4] + U4[2, 0] + U4[2, 4] + U4[3, 0] + U4[3, 4] + U4[6, 0] + U4[6, 4]
P[0, 1] + P[0, 2] + P[0, 3] + P[0, 4] + P[0, 6] + P[0, 7] + U4[1, 0] + U4[1, 4] + U4[2, 0] + U4[2, 4] + U4[3, 0] + U4[3, 4] + U4[5, 0] + U4[5, 4] + U4[7, 0] + U4[7, 4]
P[0, 1] + P[0, 2] + P[0, 4] + P[0, 7] + U4[3, 0] + U4[3, 4] + U4[4, 0] + U4[4, 4] + U4[5, 0] + U4[5, 4] + U4[6, 0] + U4[6, 4] + U4[7, 0] + U4[7, 4]
P[0, 0] + P[0, 3] + P[0, 4] + U4[0, 0] + U4[0, 4] + U4[6, 0] + U4[6, 4]
P[0, 0] + P[0, 2] + P[0, 3] + P[0, 4] + P[0, 5] + U4[3, 0] + U4[3, 4] + U4[7, 0] + U4[7, 4]
Let's look at the one before the last. It involves 3 bits from the first plaintext byte, and two of the last round S-boxes. Our goal is to guess the subkey used after the last S-box round. Because only two of those S-boxes are used here, only 2 bytes of the last subkey matters. We can brute-force these 2 bytes from the last subkey. If we start from the cipher text and xor the last subkey bytes to it, then apply the inverse S-box we get what were the input bits of the last S-box. We also know the corresponding plaintext bits, so we can simply calculate the value of that linear expression for each plaintext-ciphertext pairs. If we guessed the 2 bytes correctly then it should show some bias, for other values it should not.
int bit(int n, int k)
{
return (n & (1 << k)) != 0;
}
int main()
{
auto f = fopen("data", "rb");
for (int i = 0; i < 65536; i++) {
uint8_t p[8], c[8];
fread(&p, 8, 1, f);
fread(&c, 8, 1, f);
for (int a = 0; a < 256; a++) {
for (int b = 0; b < 256; b++) {
int u4b0 = sbox_inv[(int)c[0] ^ a], u4b6 = sbox_inv[(int)c[6] ^ b];
if (bit(p[0], 0) ^ bit(p[0], 3) ^ bit(p[0], 4) ^ bit(u4b0, 0) ^ bit(u4b0, 4)
^ bit(u4b6, 0) ^ bit(u4b6, 4)) {
cnt[a][b]++;
}
}
}
}
for (int a = 0; a < 256; a++) {
for (int b = 0; b < 256; b++) {
int bias = abs(cnt[a][b] - 32768);
if (bias > 1000)
cout << a << " " << b << " " << bias << endl;
}
}
}This code outputs this:
130 103 1068
130 118 1044
130 194 2220
130 196 1111
130 213 1068
149 194 1045
From this we can be pretty sure that the 0-th byte of the last subkey is 130 and the 6-th byte of it is 194. Similar to this we can continue to brute-force the other bytes (we can use the already guessed parts so we don't have to brute-force more than 2 bytes at once). This gave us the last subkey from which it is pretty straight-forward to reverse the key-schedule and get the original key which was the flag.
def inv(rnd, r5):
r4b = bytearray(r5[i]^r5[4+i] for i in xrange(4))
r4a = bytearray(r5[i]^sbox[r4b[(i+1)%4]] ^ (rcon[rnd] if i == 0 else 0) for i in xrange(4))
return r4a + r4b
r5 = bytearray([130, 167, 150, 65, 235, 239, 194, 40])
r4 = inv(4, r5)
r3 = inv(3, r4)
r2 = inv(2, r3)
r1 = inv(1, r2)
print 'flag{%s}'%(str(r1).encode('hex'))And at last this gave us the flag: flag{48667ec1a5fb3383}