# Bornhack CTF (2017)

> Source: https://rot256.dev/post/bornhack-2017/
> Author: Mathias Hall-Andersen
> Date: 2017-08-30
> Tags: CTF, Denmark, Bornhack, Crypto, PRESENT, Lamport
> License: CC BY 4.0 — reuse permitted with attribution to Mathias Hall-Andersen (rot256.dev).

Math macros in scope (KaTeX, `\name = expansion`):

```text
\Div = \mathrm{Div}
\FF = \mathbb{F}
\GG = \mathbb{G}
\NN = \mathbb{N}
\Norm = \mathrm{N}
\PRF = \mathsf{PRF}
\RR = \mathbb{R}
\Tr = \mathrm{Tr}
\ZZ = \mathbb{Z}
\adv = \mathscr{A}
\bin = \{0, 1\}
\coloneqq = \mathrel{\mathop:}=
\defeq = \coloneqq
\deg = \text{deg}
\divides =  \ | \ 
\gcd = \text{gcd}
\hash = \mathsf{H}
\img = \text{img}
\ker = \text{ker}
\language = \mathcal{L}
\lc = \mathrm{lc}
\lcm = \text{lcm}
\msg = \mathsf{msg}
\negl = \text{negl}(\lambda)
\pk = \mathsf{pk}
\prob = \mathbb{P}
\sample = \overset{\$}{\gets}
\secpar = \lambda
\sig = \sigma
\sign = \mathsf{Sign}
\sk = \mathsf{sk}
\support = \mathrm{Supp}
\tensor = \otimes
\verify = \mathsf{Verify}
```


# Introduction

Pwnies at Copenhagen University arranged this years [CTF](https://ctftime.org/ctf-wtf) at [Bornhack](https://bornhack.dk/bornhack-2017).

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](https://github.com/kokjo/bornhack-ctf/tree/master/challenges/birthday-PRESENT)

The Sweet16 / birthday-PRESENT challenge is based on a variant
of the [Sweet32](https://sweet32.info/) vulnability, with a block cipher ([small scale variant of PRESENT](https://eprint.iacr.org/2010/143.pdf))
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.

![CBC mode of operation](cbc-encryption.png#center "CBC mode")

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](https://github.com/kokjo/bornhack-ctf/tree/master/challenges/notec)


Notec is definitly not EC, it is an implementation of the simple [Lamport signature scheme](https://en.wikipedia.org/wiki/Lamport_signature).
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.