At first, let’s define final_state(), which returns the last state of transduce(B, s) for input B.
def transduce(b, s=0):
if len(b) == 0:
return b
d, t = T[s]
b0, bp = b[0], b[1:]
return [b0 ^ t] + transduce(bp, s=d[b0])
def final_state(b, s=0):
if len(b) == 0:
return s
d, _ = T[s]
b0, bp = b[0], b[1:]
return transduce_state(bp, s=d[b0])
The problem of breaking the cipher is that there’s swapping action of left 32 bits & right 32 bits in each stage.
def swap(b):
l = BLOCK_SIZE // 2
m = (1 << l) - 1 return (b >> l) | ((b & m) << l)
class Transducipher:
def __init__(self, k):
self.k = [k]
for i in range(1, len(T)):
k = swap(transduceblock(k))
self.k.append(k)
def encrypt(self, b):
for i in range(len(T)):
b ^= self.k[i]
b = transduceblock(b)
b = swap(b)
return b
Let’s say self.k[i] as $Key_i$, and block of the each stage as $Data_i$. ($Data_0$ is the input of the encrypt() function. The output of the encrypt() function is $Data_6$.)
Next, let’s say the left 32 bits of some block $B_i$ as $B_{i, 0}$, and the right 32 bits as $B_{i,1}$.
From $Key_i$, we can write $Key_{i+1, 0}$ and $Key_{i+1, 1}$ like:
$$Key_{i+1, 1} = transduce(Key_{i, 0}, 0)$$ $$Key_{i+1, 0} = transduce(Key_{i, 1}, final\_ state(Key_{i, 0}, 0))$$
From these, we can write out some relations of the $Key_{i, j}$ blocks which are affected by $Key_{0, 0}$, with some unknown states.
$$Key_{1,1} = transduce(Key_{0,0}, 0)$$ $$Key_{3,1} = transduce(Key_{2,0}, 0)$$ $$Key_{5,1} = transduce(Key_{4,0}, 0)$$ $$Key_{2,0} = transduce(Key_{1,1}, final\_ state(Key_{1,0}, 0) )$$ $$Key_{4,0} = transduce(Key_{3,1}, final\_ state(Key_{3,0}, 0) )$$
Also, we can write out relations from $Data_{0,0}$.
$$Data_{1,1} = transduce(Data_{0,0} \oplus Key_{0,0}, 0)$$ $$Data_{3,1} = transduce(Data_{2,0} \oplus Key_{2,0}, 0)$$ $$Data_{5,1} = transduce(Data_{4,0} \oplus Key_{4,0}, 0)$$ $$Data_{2,0} = transduce(Data_{1,1} \oplus Key_{1,1}, final\_ state(Data_{1,0} \oplus Key_{1,0}, 0) )$$ $$Data_{4,0} = transduce(Data_{3,1} \oplus Key_{3,1}, final\_ state(Data_{3,0} \oplus Key_{3,0}, 0) )$$ $$Data_{6,0} = transduce(Data_{5,1} \oplus Key_{5,1}, final\_ state(Data_{5,0} \oplus Key_{5,0}, 0) )$$
The key idea is that, if we just assume the unknown values from final_state() in these relations, we can get $Data_{6,0}$ from $Key_{0,0}$ and $Data_{0,0}$ immediately. There are five unknown states, so we can assume those states and get $6^5$ settings for them.
From this, we can write a backtracking function for finding $Key_{0,0}$, from 0th bit to 31st bit.
def transduce_withstate(b, s=0): # Also returns the final state
if len(b) == 0:
return b, s
d, t = T[s]
b0, bp = b[0], b[1:]
rb, fs = transduce_withstate(bp, s=d[b0])
return [b0 ^ t] + rb, fs
# Backtracking function for first 32 bit of the first key
def backtrack_first32bit(idx, data_in, data_out, key_cand, states, data_num):
a, b, c, d, e = states
# First 32bits are filled
if idx == 32:
key_copy = [k for k in key_cand]
data_copy = data_in[:32]
next_states = []
istates = [ (0, 0), (a, b), (0, 0), (c, d), (0, 0) ]
# Get states for calculating last 32bits of the key
for i in range(5):
i1, i2 = istates[i]
for j in range(32):
data_copy[j] ^= key_copy[j]
key_copy, kstate = transduce_withstate(key_copy, i1)
data_copy, dstate = transduce_withstate(data_copy, i2)
if i%2 == 0:
next_states.append(kstate)
next_states.append(dstate)
# Backtrack for remaining
backtrack_last32bit(0, data_in, data_out, key_cand, next_states, states, data_num)
return
for b0 in range(2): # Test the idx th bit as b0
key_copy = [k for k in key_cand]
key_copy.append(b0)
data_copy = data_in[:idx+1]
# Run the encryption
istates = [ (0, 0), (a, b), (0, 0), (c, d), (0, 0), (0, e) ]
for i1, i2 in istates:
for j in range(idx+1):
data_copy[j] ^= key_copy[j]
key_copy = transduce(key_copy, i1)
data_copy = transduce(data_copy, i2)
# Compare
if data_copy[idx] != data_out[idx]:
continue # Failed
key_copy = [k for k in key_cand]
key_copy.append(b0)
backtrack_first32bit(idx+1, data_in, data_out, key_copy, states, data_num)
# Data of the problem
data = [[13079742441184578626, 15822063786926281121],
...
[10970386673164693022, 12683515533170128309]]
if __name__ == "__main__":
# Change data to binary vector form
for i in range(len(data)):
data[i][0], data[i][1] = block2bin(data[i][0]), block2bin(data[i][1])
# Test for each datum (total 16 data)
for data_num in range(len(data)):
# Assume five states
for i in range(6**5):
states = [(i // (6**j)) % 6 for j in range (5)]
backtrack_first32bit(0, data[data_num][0], data[data_num][1], [], states, data_num)
if i % 100 == 0:
print(data_num, i)
print(data_num, "end")
if data_num > 0:
pos_key[0].intersection_update(pos_key[data_num])
print(len(pos_key[0]))
if len(pos_key[0]) < 5:
print(pos_key[0])
After finding candidates of $Key_{0,0}$, we can also get candidates of $Key_{0,1}$ from $Key_{0,0}$. backtrack_last32bit() will do this.
Furthermore, we can re-calculate the five states, which are assumed at first, from $Key_{0,1}$. We can compare the value between the assumed ones and the re-calculated ones, and find out whether the assumed setting is right or not.
The key($Key_0$) is 11424187353095200769, and the flag is PCTF{9e8adddea4bfe001}.
You can download the commented payload from here.