Introduction

Pwnies at Copenhagen University arranged this years CTF at Bornhack.

This is a short post detailing 2 of the crypto challenges I designed for this years CTF.

Birthday-PRESENT

The challenge (and solution) can be found on github

The Sweet16 / birthday-PRESENT challenge is based on a variant of the Sweet32 vulnability, with a block cipher (small scale variant of PRESENT) having a block size of 32-bit, which makes the attack more practical.

Participants were given the C source code of a server which writes the flag into a large buffer (repeated), then allows the user to overwrite the start of the buffer with any plaintext of their choosing. The buffer is then encrypted under a random key using Small-PRESENT in CBC mode and the ciphertext is returned to the user.

The vulnerability is exploited by overwriting half the buffer with known content and letting the remainder contain the unknown flag. After receiving the ciphertext, it is split into two sets \(A\) and \(B\) of blocks, containing the cipher text of the known plaintext and and the unknown flag respectivly:

\[ ct = IV \ \| \ A_{0} \| \ A_{1} \| \ \ldots \| \ A_{n/2} \| \ B_{0} \| \ B_{1} \| \ \ldots \| \ B_{n/2} \]

Since the block size is 32-bit, we expect collisions after \( \approx 2^{16} \) blocks. When we detect a collision between two blocks \(C_{i}\) and \(C_{j}\), we know that:

\[ E(P_{i} \oplus C_{i-1}) = E(P_{j} \oplus C_{j-1}) \]

Since E is a permutation:

\[ P_{i} \oplus C_{i-1} = P_{j} \oplus C_{j-1} \]

Hence knowing \(P_{i}\) allows us to recover \(P_{j}\) and vise versa. This is especially useful when \(P_{i} \in A \) and \(P_{j} \in B \) (or some part of \(A\) already known). Should we fail to find all the plaintext blocks of the flag initially, we simply try again (since the plaintext remains fixed) and collect samples until the entire flag is known.

Notec

The challenge (and solution) can be found on github

Notec is definitly not EC, it is an implementation of the simple Lamport signature scheme. The participants where given a python server which signs any message except from a specific challenge text, 4 messages are signed using the same key and SHA-256. The challenge is then to forge a signature on the challenge text, if the prover succeeds the server returns the flag.

The primary challenge is finding messages for which the “signature bits” overlap completely with that of the challenge text, which results in the server revealing all the necessary elements of the private key needed to sign the challenge text. In other words, letting \( c \) be the challenge string to sign and \( H_{i}(\cdot) \) the function outputting the \( i \)th bit of the SHA-256 digest.

Then we are searching for a set of strings \( A \) with \( | A | \leq 4 \) st.

\[ \forall i \in \{0, \ldots, 255\} : H_{i}( c ) \in \bigcup_{a \ \in \ A} \ H_{i}(a) \]

Notice that this process is independent of the key.

Final notes

I promise that there will be more algebra next year.