CTF Writeup: Simple Encryption

Flagyard cryptography challenge.

Challenge Overview:

The challenge provided a Python script (chal.py) implementing a custom encryption algorithm and an output file (output.txt) containing the resulting ciphertext. The goal was to reverse the encryption and find the flag, which was known to be in the format FlagY{...}.

Encryption Algorithm (chal.py):

The encryption was a stateful stream cipher-like process, where each new ciphertext block depends on the secret key, the previous two blocks, and the current plaintext character.

The parameters were:

• Modulus (M): $2^{128}$
• Key: A 64-bit integer generated by randbelow(2**64).
• Initial State: The output list o was initialized with [2, 73].

The core encryption loop iterated over the plaintext characters $p_i$ (represented by their ASCII ordinal value) and generated a new output block $o_{i+2}$ using the formula:

oi+2=((key⋅oi+1)⊕(key+(oi⋅pi)))(modM)oi+2​=((key⋅oi+1​)⊕(key+(oi​⋅pi​)))(modM)

Get 3mksaad1600’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Where:

• $o_i$ and $o_{i+1}$ are the two preceding blocks in the output list.
• $p_i$ is the current plaintext character’s ordinal value.
• $\oplus$ denotes the bitwise XOR operation.

Solution Strategy:

The primary challenge was to recover the 64-bit secret key. Since the encryption is deterministic given the key and the plaintext, and we have a known plaintext prefix, we can set up a system of equations to solve for the key.

Step 2: Solving with Z3:

We used the Z3 SMT solver to find the 64-bit integer key that satisfies both equations. The Z3 code was structured as follows:

1. Define the unknown key as a 64-bit bit-vector: key_candidate = BitVec('key_candidate', 64).
2. Define the modulus $M$ as $2^{128}$.
3. Express the two equations using Z3’s bit-vector arithmetic and modular operations.
4. Solve the system.

The solver successfully found the secret key: key=17608713827523745640key=17608713827523745640

Step 3: Decryption:

With the key recovered, the decryption process is straightforward. Since the encryption is a one-to-one mapping for each character, we can reverse the process by iterating through all possible plaintext characters (ASCII values 0–255) for each ciphertext block.

For each block $ct_{i+2}$, we iterate through $p_{val} \in [0] [255]$ and check if:

cti+2=((key⋅cti+1)⊕(key+(cti⋅pval)))(modM)cti+2​=((key⋅cti+1​)⊕(key+(cti​⋅pval​)))(modM)

The $p_{val}$ that satisfies the equation is the correct plaintext character. We repeat this process for the entire ciphertext to recover the full flag.

Final Result:

The full decryption process yielded the flag:
FlagY{e4sy_3nc_3asy_d3c_a6cebdf01bf8a8feb61f}