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))

    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)\newline Key_{3,1} = transduce(Key_{2,0}, 0)\newline Key_{5,1} = transduce(Key_{4,0}, 0)\newline Key_{2,0} = transduce(Key_{1,1}, final\_state(Key_{1,0}, 0) )\newline 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)\newline Data_{3,1} = transduce(Data_{2,0} \oplus Key_{2,0}, 0)\newline Data_{5,1} = transduce(Data_{4,0} \oplus Key_{4,0}, 0)\newline Data_{2,0} = transduce(Data_{1,1} \oplus Key_{1,1}, final\_state(Data_{1,0} \oplus Key_{1,0}, 0) )\newline Data_{4,0} = transduce(Data_{3,1} \oplus Key_{3,1}, final\_state(Data_{3,0} \oplus Key_{3,0}, 0) )\newline 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:

        # Backtrack for remaining
        backtrack_last32bit(0, data_in, data_out, key_cand, next_states, states, data_num)


    for b0 in range(2): # Test the idx th bit as b0
        key_copy = [k for k in key_cand]
        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]
        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:

        if len(pos_key[0]) < 5:

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.