[ictf Mar 2021] My challenges

As last month, several of my submitted challenges were used for Imaginary CTF. This month was round 8. A brief overview of the challenges, mostly with the writeups as I submitted the challenges, can be found in this post. All relevant files can be found here.

Too smoll (2021-03-13)

Description

Can you solve this for me? I’ll give you the leftovers from my chinese food if you do…

Provided

• too_smoll.py
• the output of running too_smoll.py: output.txt

Solution

The moduli are definitely small enough so that we can solve each RSA instance individually without any trouble. What we need to observe is that we only get the flag mod each individual $n$, so to reconstruct it, we need to apply the chinese remainder theorem.

Get lost! (2021-03-21)

Description

Just get lost! (submit in flag format, all lowercase, replace spaces by underscores)

Provided

• get_lost.png

Solution

In the LSB of the blue channel, we find a maze. Solving it spells out the flag for us.

Restricted access (2021-03-29)

Description

Little Timmy is stuck again. Not down a well this time, but in a pyjail.

Provided

• A network connection to restricted_access.py, running on a system with flag.txt
• The source code was later provided as a hint.
• Another hint that was given: Errors are a form of output too

Solution

After some initial exploration, we find that we are in a python environment with the following restrictions:

• When sending a line to be executed, all repetitions of a character are removed
• We don’t have access to a lot of builtins. e.g. we have no print available

So how do we circumvent these restrictions? For the repeated characters, we can experimentally verify that we do have access to eval, so we want to build a string containing everything we want to eval. We can do this step by step, every time executing s += chr(x) for some value of x, as long as we’re careful not to have duplicate characters. Getting the initial empty string can be achieved through s = chr(1)[:0], taking the first 0 characters of a length 1 string. To actually see and read output, we apply another trick. If we can trigger an exception that contains what we want to see in its description, we do get to see that. So we can simply trigger a SyntaxError by taking eval("PREFIX" + str(eval(s)) + "SUFFIX") (which obviously needs to happen in smaller steps). The introduction of a prefix and suffix is there so we can easily find the exact boundaries of our output.

From there, we’re left with a more or less standard pyjail, that we can escape by finding ways to read files (to just read flag.txt) or fire up a shell through the subclasses of object, which we can get to via e.g. ().__class__.__base__.__subclasses__()

Almost Encryption Standard (2021-03-30)

Description

I feel like I’m forgetting a few things. It’s probably not important, just ship it!

Provided

• almost_encryption_standard.py
• Connection to the python file running, with access to flag.txt
• Hints provided some time after the challenge release:
  • What if the two major operations didn't really influence each other?
  • annotated.py was released, a more readable and annotated version of the server source
  • Read the title and description carefully. Something is missing.

Solution

It’s an implementation of AES, without the SBOX/SubBytes step, and without MixColumns (and a weird key derivation because I’m lazy).

For a first solution (that was unintended initially, because I wanted to make the source shorter and not implement mixcolumns), we can observe that the composition of all ShiftRows and AddKey operations overall simply results in a single key addition (when we consider the round keys as totally) and transposition. On top of that, we can also separate this into the action on each row of the matrix.

The way the reference solution then approaches this might not be optimal, but it works: we try all permutations of both the row of the IV and the row of the ciphertext, derive the corresponding part of the keystream, and check against a second known plaintext/ciphertext pair if this would be correct. Once we can solve a single block like this, from IV and ciphertext block, we can simply use this in a cbc decryption format to recover the entire flag.

See solve_no_mixcolumns.py for an implementation of this approach.

Fun fact: I realised and implemented this version only some time after the challenge was released. I was happy to be able to solve it still before someone else got first blood.

In the original solution, we take a more math-based approach, and we notice that the absence of the S-box gives us some very nice properties. Notice that the ShiftRows operation is a linear transformation when regarded over the individual bits of the state (in particular, it’s a permutation, which can be seen as a $128 \times 128$ row-permutation of the identity matrix). The AddKey operation in turn is simply addition mod 2.

So here we introduce the form we’ll be working with for our state: a vector of length 128 over $\mathbb{F}_2 = \{0, 1\}$. In short, this just means that addition is performed modulo 2, aka as xor. Then if we write the round keys as $\mathbf{k}_i$ (boldface indicates a vector), the ShiftRows matrix as $\mathsf{SR}$, encryption round $i$ for state $\sigma\_i$ comes down to: $$\sigma_{i + 1} = SR \times (\sigma_i + \mathbf{k}_i),$$ and when we look at this more closely, we can see that multiple rounds can still be expressed in the form $$\mathrm{ciphertext} = M \times (\mathrm{plaintext} + \mathbf{\kappa}) = M \times \mathrm{plaintext} + M \times \mathbf{\kappa} = M \times \mathrm{plaintext} + \mathbf{\kappa'},$$ for some $\mathbb{F}_2$ matrix $M$ and vectors $\mathbf{\kappa}$ and $\mathbf{\kappa'}$.

So overall, this block cipher is an affine transformation, and those can be solved by linear algebra. We need 129 plaintext/ciphertext pairs (128 for the bits of a block + 1 for the affine constant). To get these, even though we can’t query the oracle 129 times, we can just send longer messages and extract pairs from the CBC ciphertext. With those, we can solve a system of $\mathbb{F}_2$-linear equations to recover a matrix that can decrypt any arbitrary block for us.

With that matrix in hand, we can then apply regular CBC decryption techniques to recover the flag. This approach, as I implemented in sage, can be found in solve_affine.sage.