Joining the Platypwnies for hack.lu

Overall event

As a member of the Platypwnies, my university’s CTF team, I participate in CTFs every now and again, some bigger and some smaller. This weekend, we competed in hack.lu 2025, a major CTF event in German-speaking Europe. Especially since this event counted towards qualifications for the German Hacking Championship (Deutsche Hacking Meisterschaft). We came in 10th/299 at this event :c

Due to personal time constraints, I only managed to join on the first day of the event. Nevertheless, I invited some non-member friends to join as well, and we managed to get some easy solves in. I did not stay for long enough to witness the more difficult challenges being solved, unfortunately.

Specifically, I want to present the challenge MANÜAL which I solved together with two of said friends. It is quite common for CTF players to create and publish write-ups about challenges they solved at an event. It is both interesting to read write-ups for challenges you did not end up solving and discovering other approaches for challenges you did solve through people’s write-ups. Additionally, write-ups can later serve as a personal reference when encountering similar challenges.

One challenge write-up

MANÜAL was an easy cryptography challenge.

The challenge read: Who needs a team of talented designers, when you can just get a computer to generate your instruction manuals?
Connect using ncat manual.flu.xxx 1024

Additionally, the Python backend of that server was supplied as an attachment:

import secrets
import random
import os

from typing import Callable

FLAG = os.getenv("FLAG") or "flag{this_is_a_test_flag_:D_>.<}"

class InstructionManual:
    STEP_COUNT = 40
    PIECE_SIZE = 256
    PIECE_COUNT = PIECE_SIZE // 8
    BIGGEST_PIECE = 2**PIECE_SIZE - 1

    _steps: list[Callable[[int], int]]

    def __init__(self):
        step_types = [self.step_screw_in, self.step_turn_around, self.step_hammer_together]
        prefix = [x() for x in step_types]
        suffix = [x() for x in step_types[::-1]]
        self._operations = prefix + [random.choice(step_types)() for _ in range(self.STEP_COUNT)] + suffix

    def build(self, value: bytes) -> bytes:
        assert len(value) == self.PIECE_COUNT, "These pieces don't seem to be the correct size :("
        wip_furniture = int.from_bytes(value, "big")
        for op in self._operations:
            wip_furniture = op(wip_furniture)

        return wip_furniture.to_bytes(self.PIECE_COUNT, "big")

    @classmethod
    def step_screw_in(cls):
        screw_tight = secrets.randbits(1) == 1
        screw_amount = secrets.randbelow(cls.PIECE_SIZE)
        def _inner(value: int) -> int:
            if screw_tight:
                return ((value >> screw_amount) | (value << (cls.PIECE_SIZE - screw_amount))) & cls.BIGGEST_PIECE
            else:
                return ((value << screw_amount) | (value >> (cls.PIECE_SIZE - screw_amount))) & cls.BIGGEST_PIECE

        return _inner

    @classmethod
    def step_turn_around(cls):
        def _inner(value: int) -> int:
            return int.from_bytes(value.to_bytes(cls.PIECE_COUNT, "little"), "big")

        return _inner

    @classmethod
    def step_hammer_together(cls):
        required_hammer = secrets.randbits(cls.PIECE_SIZE)
        def _inner(value: int) -> int:
            return value ^ required_hammer

        return _inner

def main():
    assert len(FLAG) == InstructionManual.PIECE_COUNT, "incorrect flag length!!"

    instruction_manual = InstructionManual()
    print("Here at FLUX, we always strive to include the latest technological advancements in our products.")
    print("This instruction manual has been generated just for you! But we don't know which pieces are needed to actually construct it...")
    print("Can you help us figure out how it all fits together?")
    print()

    max_count = 300

    print("We've allocated some time for one of our interns to help you with this task.")
    print(f"They will attempt to follow the instruction manual using pieces you provide, for a maximum of {max_count} attempts.")

    remaining = max_count
    while remaining > 0:
        val = input(f"({max_count - remaining}/{max_count}) Please enter your {InstructionManual.PIECE_COUNT} selected pieces as one hex encoded string, or 'finish' to exit early:\n")
        if val == "finish":
            break

        try:
            decoded = bytes.fromhex(val)
            if len(decoded) != InstructionManual.PIECE_COUNT:
                print("incorrect piece count.")
                continue

        except Exception:
            print("incorrect pieces.")
            continue

        assembled_furniture = instruction_manual.build(decoded)
        print("Here is what the intern put together:")
        print(assembled_furniture.hex())

        remaining -= 1

    print("The intern says they've understood what the manual is supposed to construct now, and to relay you this message:")
    print(instruction_manual.build(FLAG.encode()).hex())
    print("Thanks for your help!")

if __name__ == "__main__":
    main()

Thus, the first step was to read and understand the above code.

This is also the point where you can copy the above Python script, move it some place else, and try to come up with a solution yourself before reading on. Admittedly, you have no way of testing it out.

Technical solution

Doing so comes out to the following main points:

1. The server accepts a 32-byte user input 300 times and returns a transformation of that input each time.
2. After this process, the 32-byte transformed flag is given.
3. The transformation process is a sequence of 46 operations where each operation is one of the following:
   • step_screw_in: rotation of the string by a random amount
   • step_turn_around: mirroring of the string
   • step_hammer_together: string XOR random 32-byte value

Importantly, the random values for step_screw_in and step_hammer_together stay the same for between executions of the transformation. As in, the transformation is deterministic. The challenge would be quite a bit harder otherwise.

With this knowledge, we knew that we had to design inputs in some fashion that would allow us to reconstruct the transformation algorithm. The unknown components were technically the random operations chosen, and the random values used in those operations. However, there is a notable vulnerability in the three operations.

First I will describe how we observed it and how that itself led us to a solution. And then I want to briefly discuss the simple underlying mathematics.

The important observation is that step_screw_in and step_turn_around only change around the positions of the bits. This means that there is a clear mapping of which bit has moved where between each step and, thus, also across all movement steps. Meanwhile, step_hammer_together changes the value of every single bit. The fact that every bit of the bit string is hit by random “hammers” at random times sums up simply to the fact that the state change (flip/no flip) of every bit is random/unknown. So to find out whether a given bit of the input string ends up being flipped, we have to figure out where it goes.

This is easily possible. Consider the following: we send an all-zero string. In response, we receive some arbitrary bit string. Next, we send a string containing exactly one 1. In response, we will receive a string which resembles the previous response except for a difference of precisely one bit. This is given because the same bits move to the same locations, and each location is being flipped the same number of times. Therefore, the opposite bit in the same location will end up in the same resulting location, but in the opposite state. In this way, we have successfully tracked and mapped the behaviour of 1/256 bits. We can now repeat this 255 more times (each time exactly one bit is set to 1). We end up with a full map of each bit’s transformation. Now, we can waste the last 43 queries. When we finally receive the transformed flag, we only have to apply the inverse of this transformation and print the bit string in utf-8. This gives us: flag{crypt0_kn0wl3dg3_g4in3d_:3}.

Mathematical background

Now, onto some foundational concepts at play here. We have several interesting objects: the fixed-length bit strings and the transformations over these. Since we are working with bitwise operations here, we can formalise them using the finite field with two elements: \(\mathbb{F}_2\). These two elements are $ {0,1} $, the states of our bits. All 256-bit strings then are vectors embedded in the vector space \(V = {\mathbb{F}_2}^{256}\) (256-dimensional space over \(\mathbb{F}_2\)). Since the transformations being applied to our bit strings in the challenge all take a 256-bit string as input and return one as output, they are all functions $V \to V$.

Now, let us look at each of these functions. The rotation and inversion are both index permutations, meaning that a fixed permutation is being applied to the indices of the input vector, i.e., its components are reordered. This can be expressed as \(f(v)_i = v_{\sigma(i)}\) which says that the bit at the index $i$ in the vector $ f(v) $ is the bit in vector $v$ at index $ \sigma(v) $ where $\sigma$ is some permutation.

Critically, index permutations are always linear! This can easily be shown:
Let $u,v \in V$ and $f$ be an index permutation.

\[f(u+v) = f((u_1+v_1, u_2+v_2, ..., u_n+v_n))\]

This means:

\[f(u+v)_i = (u_1+v_1, u_2+v_2, ..., u_n+v_n)_{\sigma(i)} = u_{\sigma(i)}+v_{\sigma(i)} = f(u)_i + f(v)_i\]

Thus, the $f$ is linear. Since both the rotation and inversion are index permutations, both are linear transformations.

Now, onto the hammer. The hammer is defined as taking the input string and XORing it with some unknown bit string. Since addition in GF(2) is equivalent to the bitwise XOR, this function can be represented as simply: $ h: V \to V, v \mapsto v+c $ with $ c \in V $. This means $ h(v) = I(v)+c $ with $I$ being the identity, a known linear transformation. A function is affine if and only if it can be represented as $ \phi(v)+c $ where $\phi$ is linear. Therefore, $h$ is affine.

The composite function of affine functions is always affine, as shown here:
Let $f,g: V \to V$ be affine functions. Let $v\in V$. Thus, $f(v)=Av+c$ and $g(v)=Bc+d$ where $A,B$ are linear transformations and $c,d$ are constant translations.

Now

\[g\circ f(v) = g(Av+c) = B(Av+c)+d\]

This can be distributed using the linearity of $B$:

\[B(Av+c)+d = BAv + Bc + d\]

With $A’=AB$ and $c’ = Bc+d$, this equals

\[A'v+c'\]

We know that the composite of two linear functions is linear, making $A’$ linear. And $Bc+d$ is simply some constant in $V$. Therefore, $g\circ f$ is affine.

Since all linear functions are also affine functions, we can deduct that the entire algorithm, a composition of 46 affine functions, is one affine function: $a($input$)=A\cdot$output$+c$.

To reconstruct the function, we only need to determine the components $A$ and $c$. And this is actually exactly what our solution script does!

Sending the all-zero bit string is crucial, since $A0=0$ for all linear functions. Thus, $a(0)=0+c$, or simply $a(0)=c$.

Next, we needed $A$. As is the case for all linear functions, they have a transformation matrix. In fact, $A$ is this transformation matrix. When we send an input which has position $i$ set to 1 and the rest to 0, we are sending what are called ‘unit vectors’. The result of $Au_i$ will be column $i$ of $A$. Since $(a(u_i) = Au_i+c)$, this equals column $i$ of $A$ plus $c$. But since we already know $c$, we can then subtract it: $a(u_i)-c = Au_i+c-c = A[:, i]$. Therefore, sending unit vector 1 will give us the first column of matrix $A$, sending $u_2$ gives us the second column, and so on. We need to send all 256 unit vectors of $V$ to retrieve all columns of $A$ and thus $A$ itself.

Finally, we have extracted both $A$ and $c$ and can reconstruct the algorithm $a$.
So, given the encrypted flag $x = a($flag$)$, flag = $A^{-1}(x-c)$.

Now, consider how this matrix $A$ is composed of all matrices in the 46 operations. In fact, it is strictly the result of their multiplication. We represented the hammer operation’s linear component with the identity function, which is multiplicatively neutral. The other two functions are both index permutations, which are bijective linear functions. Therefore, their linear inverse functions exist. We can show that the matrix of that inverse function is the inversion of the original function’s matrix.
Let $f: V \to V$ be such a bijective linear function and $M$ its transformation matrix. $f^{-1}$ is the inverse of $f$ and has a transformation matrix $N$.
Let $v\in V$.

\[MNv = M(Nv) = f(f^{-1}(v)) = f\circ f^{-1}(v) = I(v) = v\]

Since $MNv = v$, $M$ and $N$ must be inverses.

We thus know that all matrices of the rotate, invert and hammer functions are invertible. So all composites of $A$ are invertible matrices. The product of two invertible matrices is, itself, invertible. Therefore, $A$ is invertible, which makes $A^{-1}(x-c)$ solvable. This gives us access to the flag. :)