Somewhere under a big pile of paper I found some notes about this really cool encryption algorithm. I updated it to the digital age in the hope that it is much safer now.

Category: Crypto

Solver: Greenscreen23

Flag: GPNCTF{itturnsoutthatbitsdonotmakecolumnartransposedifficultenoughatleastifyouencodeitwithasciigjnogoandbreakdoppelwuerfeltheflagendshereenjoyreadingsomemoretextihopeyoulikedthechallenge}

Writeup

Context

We are given a rust file that encrypts the bits of the flag using a transposition cipher with a random key. The flag bits are split into blocks of an unknown key length, which are arranged as rows in a table, without any padding in the last row. The columns of the table are then permuted according to the key and concatinated column by column. This ciphertext is given.

Some important things to note are:

  • The columns don’t have to all have the same length, since there is no padding in the last row. This makes it difficult to split the ciphertext into columns. The key length is also random, making this even harder.
  • The GPNCTF{} part of the flag has been stripped, but it is guaranteed that the rest of the flag are lowercase letters.
  • The permutation key is generated by sampling lowercase letters, sorting them and taking the resulting permutation of indices. Although this does not appear to result in a uniform random permutation, I did not attack this function and I don’t think that it is easy to do so.
  • The random generators used come from the library rand and seem to be cryptographically secure.

Decryption

The first interesting unkown variable is the length of the key, since it determines the structure of the table. This length is between 21 and 34 (inclusive), so we just bruteforce all possible lengths.

After that, we can try to match the ciphertext to the possible columns. We use the fact that the flag consists only of lowercase letters, so every byte needs to start with the bits 011. With this, we can fill a pattern table that stores for every cell whether it should be a 0, a 1 or could be both (represented by x).

Now we can notice that there are only at most 16 different column patterns, as the pattern repeats ever 8 rows, and we might have two different column lengths. We now search all possibilities of splitting the ciphertext into columns by recursively trying both column lengths, matching the column with all patterns and continuing on every found match. We furthermore keep into account how many columns we have already matched to a pattern and limit this value to how many times that pattern appears in our table.

This search is implemented in [1], which gives us a single key length (33) and two possibilities to split the ciphertext into columns. Note that we have to skip key lengths that are multiples of 8, as our pattern leaves them with many “empty” rows (with just x). There key lengths are not a possibility anyway, as they lead to columns consisting of only 1. The longest sequence of 1 in the ciphertext has 7 characters, which is too small for a column given the length of the ciphertext.

Now we can begin bruteforcing all possible orderings of columns that match the same pattern. We have already assigned the columns to the possible 16 different pattern / length combinations, which results in 4 sets of 3 columns, 9 sets of 2 columns and 3 sets of 1 column. The total number of possible orderings is therefore 663552. This is implemented in [2], which is not the fastest implementation (it takes about 5 minutes on my laptop), but it prints the flag. Remember to wrap it in GPNCTF{}, as this was stripped before encryption.

Mitigations

This cipher was a transposition cipher, which on its own is not resistant to attacks that use partial knowledge of the plaintext. Both components of the cipher (the permutation of columns and concatenating by columns) only move bits, which makes it easy to predict where which bit came from. To mitigate these issues, one can pair the system with substitution ciphers like the S-box and AddRoundKey from AES, which makes it very hard to match where which bit came from.

The key generation also did not seem totally secure, although I did not manage to find an attack against it. Choosing a permutation uniformly at random by shuffling an existing permutation or increasing the alphabet to be significantly larger than the key length might also suffice, as this decreases the chance that a character is chosen twice. If characters are not chosen twice, then this system should also yield permutation uniformly at random.

Other resources

Scripts

[1] Script for finding possible splits of the ciphertext into columns.

out = open("./output", "r").read().strip()

bit_count = len(out)
byte_count = bit_count // 8

for key_length in range(21, 35):
    if key_length % 8 == 0:
        continue

    short_column_height = bit_count // key_length
    long_column_height = bit_count // key_length + 1
    num_long_columns = bit_count % key_length
    num_columns = key_length

    def mark(pattern_table, index, marker):
        index_in_column = index // num_columns
        column_index = index % num_columns
        pattern_table[column_index][index_in_column] = marker

    def build_pattern_table():
        pattern_table = [
            [
                "x"
                for _ in range(
                    long_column_height if ci < num_long_columns else short_column_height
                )
            ]
            for ci in range(num_columns)
        ]

        for byte_index in range(byte_count):
            mark(pattern_table, byte_index * 8, "0")
            mark(pattern_table, byte_index * 8 + 1, "1")
            mark(pattern_table, byte_index * 8 + 2, "1")

        return pattern_table

    def matches(column, pattern):
        return all(
            pat_elem == "x" or col_elem == pat_elem
            for pat_elem, col_elem in zip(pattern, column)
        )

    pattern_table = build_pattern_table()
    long_column_patterns = pattern_table[:8]
    short_column_patterns = pattern_table[num_long_columns : num_long_columns + 8]

    max_long_columns = [0 for _ in range(8)]
    for wi in range(num_long_columns):
        max_long_columns[wi % 8] += 1

    max_short_columns = [0 for _ in range(8)]
    for wi in range(num_columns - num_long_columns):
        max_short_columns[wi % 8] += 1

    solutions = []

    def scrape(index, num_long_columns, num_short_colums, current_splits):
        if index == bit_count:
            solutions.append(current_splits.copy())
            return

        # test for a long column
        if index + long_column_height <= bit_count:
            column = out[index : index + long_column_height]

            for pi, pattern in enumerate(long_column_patterns):
                if (
                    matches(column, pattern)
                    and num_long_columns[pi] < max_long_columns[pi]
                ):
                    current_splits.append((long_column_height, pi))
                    num_long_columns[pi] += 1
                    scrape(
                        index + long_column_height,
                        num_long_columns,
                        num_short_colums,
                        current_splits,
                    )
                    num_long_columns[pi] -= 1
                    current_splits.pop()

        # test for a short column
        column = out[index : index + short_column_height]

        for pi, pattern in enumerate(short_column_patterns):
            if (
                matches(column, pattern)
                and num_short_colums[pi] < max_short_columns[pi]
            ):
                current_splits.append((short_column_height, pi))
                num_short_colums[pi] += 1
                scrape(
                    index + short_column_height,
                    num_long_columns,
                    num_short_colums,
                    current_splits,
                )
                num_short_colums[pi] -= 1
                current_splits.pop()

    scrape(0, [0 for _ in range(8)], [0 for _ in range(8)], [])

    print(f"{key_length}: {solutions}")

[2] Script for bruteforcing all possible permutations of columns that match the same pattern, for every possibility to split the ciphertext into columns.

from itertools import permutations, product

out = open("./output", "r").read().strip()

bit_count = len(out)
byte_count = bit_count // 8

key_length = 33
short_column_height = bit_count // key_length
long_column_height = bit_count // key_length + 1
num_long_columns = bit_count % key_length
num_columns = key_length

# Output from the previous script
solutions = [
    [
        (43, 5),
        (43, 1),
        (44, 0),
        (43, 7),
        (44, 4),
        (44, 1),
        (43, 2),
        (44, 2),
        (43, 6),
        (43, 6),
        (43, 3),
        (43, 7),
        (44, 5),
        (43, 2),
        (43, 3),
        (44, 7),
        (43, 1),
        (44, 6),
        (43, 0),
        (43, 4),
        (43, 2),
        (44, 2),
        (43, 3),
        (43, 1),
        (44, 3),
        (44, 4),
        (43, 4),
        (44, 0),
        (44, 1),
        (43, 0),
        (43, 5),
        (44, 3),
        (43, 0),
    ],
    [
        (43, 5),
        (43, 1),
        (43, 3),
        (44, 3),
        (44, 4),
        (44, 1),
        (43, 2),
        (44, 2),
        (43, 6),
        (43, 6),
        (43, 3),
        (43, 7),
        (44, 5),
        (43, 2),
        (44, 0),
        (43, 3),
        (43, 1),
        (44, 6),
        (43, 0),
        (43, 4),
        (43, 2),
        (43, 5),
        (44, 7),
        (43, 1),
        (44, 3),
        (44, 4),
        (43, 4),
        (44, 0),
        (44, 1),
        (43, 0),
        (44, 2),
        (43, 7),
        (43, 0),
    ],
]


for solution in solutions:
    print(f"Testing solution {solution}")
    long_column_sets = [[] for _ in range(8)]
    short_column_sets = [[] for _ in range(8)]

    index = 0
    for length, column_set_index in solution:
        col = out[index : index + length]
        index += length
        if length == short_column_height:
            short_column_sets[column_set_index].append(col)
        else:
            long_column_sets[column_set_index].append(col)

    for long_column_sets_permuted in product(
        *[list(permutations(columns)) for columns in long_column_sets]
    ):
        for short_column_sets_permuted in product(
            *[list(permutations(columns)) for columns in short_column_sets]
        ):
            columns = []

            for column_index in range(num_long_columns):
                column_set_index = column_index % 8
                index = column_index // 8
                columns.append(long_column_sets_permuted[column_set_index][index])

            for column_index in range(num_columns - num_long_columns):
                column_set_index = column_index % 8
                index = column_index // 8
                columns.append(short_column_sets_permuted[column_set_index][index])

            bits = ""
            for bit_index in range(bit_count):
                column_index = bit_index % num_columns
                index = bit_index // num_columns
                bits += columns[column_index][index]

            flag = b"".join(
                [
                    int(bits[index : index + 8], base=2).to_bytes(1)
                    for index in range(0, bit_count, 8)
                ]
            )
            if flag.isascii() and flag.decode().isalpha() and flag.decode().islower():
                print(flag.decode())