Bit Attack¶

Overview¶

Simply put, this is an attack that exploits the relationships between individual bits.

2018 Plaid CTF transducipher¶

The challenge is as follows:

#!/usr/bin/env python3.6
import os

BLOCK_SIZE = 64

T = [
    ((2, 1), 1),
    ((5, 0), 0),
    ((3, 4), 0),
    ((1, 5), 1),
    ((0, 3), 1),
    ((4, 2), 0),
]


def block2bin(b, length=BLOCK_SIZE):
    return list(map(int, bin(b)[2:].rjust(length, '0')))


def bin2block(b):
    return int("".join(map(str, b)), 2)


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 transduceblock(b):
    return bin2block(transduce(block2bin(b)))


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


if __name__ == "__main__":
    flag = bytes.hex(os.urandom(BLOCK_SIZE // 8))
    k = int(flag, 16)
    C = Transducipher(k)
    print("Your flag is PCTF{%s}" % flag)
    with open("data1.txt", "w") as f:
        for i in range(16):
            pt = int(bytes.hex(os.urandom(BLOCK_SIZE // 8)), 16)
            ct = C.encrypt(pt)
            f.write(str((pt, ct)) + "\n")

The challenge provides 16 plaintext-ciphertext pairs:

• Plaintext size: 8 bytes
• Ciphertext size: 8 bytes
• Key size: also 8 bytes

What we need to solve for is the key.

We can see that there are mainly two basic operations here:

• swap

def swap(b):
    l = BLOCK_SIZE // 2
    m = (1 << l) - 1
    return (b >> l) | ((b & m) << l)

This swaps the upper 32 bits and lower 32 bits of the given data.

• transduce

T = [
    ((2, 1), 1),
    ((5, 0), 0),
    ((3, 4), 0),
    ((1, 5), 1),
    ((0, 3), 1),
    ((4, 2), 0),
]
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])

Where:

• b is a binary (0/1) array, initially of size 64.
• s is an index.

The basic process is as follows:

1. Based on s, select which element of T to use, then split it into d and t.
2. Split b into two parts: one containing only the first element, and the other containing the rest.
3. XOR the first element with t as the current first element, then continue converting the remaining part.

In fact, we can convert this function into an iterative function:

def transduce_iter(b, s=0):
    ans = []
    for c in b:
        d, t = T[s]
        ans += [c ^ t]
        s = d[c]
    return ans

Furthermore, since each time the first element of the list is processed, this function is actually reversible, as follows:

def invtransduce(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 ^ t])

Now let's analyze the core flow of the program. First is the key generation part. This encryption algorithm generates 6 keys, with each key generated by:

1. Applying transduce to the previous key to get an intermediate value t
2. Applying swap to t
3. Iterating this process 5 times consecutively

    def __init__(self, k):
        self.k = [k]
        for i in range(1, len(T)):
            k = swap(transduceblock(k))
            self.k.append(k)

The encryption algorithm is as follows, iterating for a total of 6 rounds with the basic flow:

1. XOR with the key, then transduce
2. Swap

    def encrypt(self, b):
        for i in range(len(T)):
            b ^= self.k[i]
            b = transduceblock(b)
            b = swap(b)
        return b

Through analyzing the program, we can see that this encryption algorithm is a block cipher with the following basic information:

• Block size: 8 bytes
• Number of rounds: 6
• The basic operations in each round of encryption are transduce and swap.
• Key expansion is also related to transduce and swap.

More specifically:

1. swap exchanges the upper 32 bits and lower 32 bits of 8 bytes.
2. transduce XORs each bit of the 8 bytes with a certain value, bit by bit. This value is related to T.

Through further analysis, we can find that both functions are reversible. That is, if we know the final ciphertext, we can actually reduce the original number of rounds to approximately 5, because the last round's transduce and swap have no effect.

We can define the following variables:

Since one of the core operations is swap, which only manipulates the upper or lower 32 bits, we can consider them in two separate parts. The simplified definitions are as follows:

• Transduce is simplified as T. Although this conflicts with the variable in the source code, we can understand it for now.
• Swap is simplified as S.

The plaintext-ciphertext and key for each round are as follows:

Then, we can enumerate the upper 32 bits of k bit by bit, while also enumerating the possible s state during the T operation. This way, we can obtain the upper 32-bit key. After performing the bit-by-bit brute force, we can obtain two possible results:

[2659900894, 2659900895]

Based on the left side results, we can then obtain the possible results for the right side. The possible results obtained using 2659900894 are as follows:

# Too many possible keys for the first plaintext-ciphertext pair.
# The second group has a total of 6.
[2764038144, 2764038145, 2764038152, 2764038153, 2764038154, 2764038155]
# The third group
[2764038144, 2764038145]

Then we can actually manually try encrypting all the plaintext-ciphertext pairs. If incorrect, we can simply determine it's wrong. This way, we can filter very quickly. In the end, the key is found to be:

2659900894|2764038145

Which is 11424187353095200769. And that gives us the flag.

Of course, this challenge can also be solved using the meet-in-the-middle attack method, which means enumerating the key used in round 0 and the key used in the last round separately, and finding a collision where they meet at the third round.

References¶

• http://blog.rb-tree.xyz/2018/05/07/plaidctf-2018-transducipher/