CTF Challenge Name Solves (Difficulty)
Midnight Sun Quals 2022 Pelle’s Rotor-Supported Arithmetic 🔥 35/346 (⭐⭐)
Midnight Sun Quals 2022 BabyZK 🔥 19/346 (⭐⭐)
Midnight Sun Quals 2022 kompot_512 🔥 15/346 (⭐⭐⭐)
Midnight Sun Quals 2022 WeedSolomon 420 3/346 (❓)
PlaidCTF 2022 pressure 18/431 (⭐⭐)
PlaidCTF 2022 choreography 14/431 (⭐⭐)
ångstromCTF 2022 log log log 104/1319 (⭐)
ångstromCTF 2022 Strike-Slip Fault 50/1319 (⭐⭐)
ångstromCTF 2022 Prophet 45/1319 (⭐⭐)
ångstromCTF 2022 RSA-AES 🔥 36/1319 (⭐⭐)

Midnight Sun CTF Quals 2022

Pelle’s Rotor-Supported Arithmetic 🔥

  • Solves: 35/346
  • Difficulty: ⭐⭐
  • Tags: rsa
  • Author: @carllondahl

Let $p$ and $q$ be two 512-bit primes for RSA and $n = pq$ be its modulus. Let $e = 65537$ and $d$ has $l$ digits in base 10. Here we denote $d = \overline{d_0 d_1 … d_{l-2} d_{l-1}}$).

Suppose that we have an oracle, $\mathcal{O}(c, i)$, which returns $m$ defined by the below steps:

  1. Compute $d' = \overline{d_i d_{i+1} … d_{l-2} d_{l-1} d_0 d_1 … d_{i-2} d_{i-1}}$.
  2. Compute $m = c^{d'}\ \text{mod}\ n$.

We are given $\approx 340$ oracle calls and the encrypted flag $c_0$ (and nothing else). The goal is to decrypt $c_0$, which is encrypted with a different $e$ but the same $n$.

BabyZK 🔥

  • Solves: 19/346
  • Difficulty: ⭐⭐
  • Tags: math
  • Author: @carllondahl

Let $p$ be a 1024-bit safe prime (i.e., $p = 2q+1$ with $q$ is also a prime). Let $m(x)$ be a polynomial of degree 14 and $g \in \mathbb{Z}_p$.

Suppose that we have an oracle $\mathcal{O}(x)$, which returns $h$ defined below:

  1. Compute $u = m(x)\ \text{mod}\ (p-1)$.
  2. Compute $h = g^u\ \text{mod}\ p$.

We are given 17 oracle calls. After that, we are given $x_1, x_2, …, x_{100}$. The objective is to find $0 \leq y_1, y_2, …, y_{100} < p$ such that $y_i \equiv g^{\text{m}(x_i)}\ (\text{mod}\ p)$ for all $i = 1, 2, …, 100$.

kompot_512 🔥

  • Solves: 15/346
  • Difficulty: ⭐⭐⭐
  • Tags: math
  • Author: @carllondahl

Definition. If $f$ is a rational function of degree 1, then it can be represented by

$$f(x) = \frac{ax + b}{cx + d}$$

for some constants $a, b, c, d$.

Let $p$ be a prime. Define the addition (denoted by $\oplus$) of two rational functions of degree 1 (namely $f(x)$ and $g(x)$) under modulo $p$ by $f \oplus g := f(g(x))\ \text{mod}\ p$, i.e.,

$$\begin{aligned} & f(x) = \frac{a_1 x + b_1}{c_1 x + d_1}, g(x) = \frac{a_2 x + b_2}{c_2 x + d_2} \\ \qquad & \Longrightarrow f(x) \oplus g(x) = \frac{a_1 \frac{a_2 x + b_2}{c_2 x + d_2} + b_1}{c_1 \frac{a_2 x + b_2}{c_2 x + d_2} + d_1} = \frac{(a_1a_2 + b_1c_2) x + (a_1b_2 + b_1d_2)}{(c_1a_2 + d_1c_2) x + (c_1b_2 + d_1d_2)}. \end{aligned}$$

We are given $f$ and $g$ defined below:

$$f(x) = \frac{x + 2}{3x + 4}, \quad g(x) = \frac{2x + 1}{13x + 37}.$$

Four numbers $x_0, x_1, y_0, y_1 \in [0, 2^{128})$ are randomly generated (not given). We are also given $A$ and $B$ defined by

$$\begin{aligned} & A = \underbrace{f \oplus f \oplus … \oplus f}_{x_0\ f\text{’s}} \oplus \underbrace{g \oplus g \oplus … \oplus g}_{x_1\ g\text{’s}}, \\ & B = \underbrace{f \oplus f \oplus … \oplus f}_{y_0\ f\text{’s}} \oplus \underbrace{g \oplus g \oplus … \oplus g}_{y_1\ g\text{’s}}. \end{aligned}$$

Define $C$ by

$$C = \underbrace{f \oplus f \oplus … \oplus f}_{(x_0 + y_0)\ f\text{’s}} \oplus \underbrace{g \oplus g \oplus … \oplus g}_{(x_1 + y_1)\ g\text{’s}}.$$

The objective is to recover $C$.

WeedSolomon 420

  • Solves: 3/346
  • Difficulty: ❓
  • Tags: ?
  • Author: @carllondahl
Needs more information. I am unsure about this challenge yet. I will update the details later.

PlaidCTF 2022

pressure

  • Solves: 18/431
  • Difficulty: ⭐⭐
  • Tags: ecc, private set intersection
  • Author: mserrano

Notations. Denote $G$ be a generator of the curve ED25519. Let also $\mathcal{P}$ be the set of points on that curve.

Also, if $k \in \mathbb{Z}$ and $S \in \mathcal{P}$, the set $k \cdot S$ is given by $\{k Q \in \mathcal{P} : Q \in S\}$.

When connected to the server, the below private parameters are randomly generated:

  1. $r \in [1, 2^{32})$,
  2. $n \in [128, 256]$,
  3. $(x_0, …, x_{n-1}) \in \{1, 2, …, 255\}^n$, and
  4. $b_1, b_2 \in [0, 2^{512})$.

It is used to generate a secret set $\mathcal{S}$ with $n + 4096$ entries:

  1. [The $n$] $\text{SHA512}(25037 \cdot r \cdot x_i + i) \cdot G \in \mathcal{S}$ for $i = 0, 1, …, n-1$.
  2. [The 4096] $\text{SHA512}(k + 4096 \cdot (r\ \text{mod}\ k)) \cdot G \in \mathcal{S}$ for $k = 1, 2, …, 4096$.

The client (us) interacts with the server with the below procedures:

  • The client sends a set $A_1 \subseteq \mathcal{P}$ to the server.
  • The server computes $T = b_1 \cdot A$ and $B_1 = b_1 \cdot \mathcal{S}$ and sends them to the client.
  • The server computes $B_2 = b_2 \cdot \mathcal{S}$ and sends it to the client.
  • The client sends sets $A_2, B_2' \subseteq \mathcal{P}$ to the server.
  • The server checks if $\left|B_2\right| = \left|B'_2\right|$ and $B_2 \cap B'_2 = \phi$ and $B'_2 = b_2 \cdot A$. If that is the case, the server sends the flag to the client.

The goal is to win the flag from the server.

choreography

  • Solves: 14/431
  • Difficulty: ⭐⭐
  • Tags: block cipher
  • Author: @ubuntor

The challenge defined two ciphers encrypt1 and encrypt2 which encrypts a 4-byte message into a 4-byte ciphertext using a 4-byte key. Hereby sbox is a permutation of $\mathbb{Z}_{256}$ and ROUNDS = 2**22 + 2:

def encrypt1(k, plaintext):
    a,b,c,d = plaintext
    for i in range(ROUNDS):
        a ^= sbox[b ^ k[(2*i)&3]]
        c ^= sbox[d ^ k[(2*i+1)&3]]
        a,b,c,d = b,c,d,a
    return bytes([a,b,c,d])

def encrypt2(k, plaintext):
    a,b,c,d = plaintext
    for i in range(ROUNDS)[::-1]:
        b,c,d,a = a,b,c,d
        c ^= sbox[d ^ k[(2*i)&3]]
        a ^= sbox[b ^ k[(2*i+1)&3]]
    return bytes([a,b,c,d])

When connected to the server, a 4-byte key $k$ is generated. We can send 1000 4-byte plaintexts $m_1, …, m_{500}, m'_1, …, m'_{500}$ to the server. After that, we will obtain 1000 4-byte ciphertexts $\text{Enc}_1(k, m_1), …, \text{Enc}_1(k, m_{500}), \text{Enc}_2(k, m'_1), …, \text{Enc}_2(k, m'_{500})$. The goal is to recover $k$ in 30 seconds.

ångstromCTF 2022

log log log

  • Solves: 104/1319
  • Difficulty: ⭐
  • Tags: dlog
  • Author: lamchcl

Suppose that $p$ and $q$ are two primes such that $p = 2^{1024} q + 1$. Let $g \in \text{GF}(p)$ be a generator and $h \equiv g^x\ \text{mod}\ p$ for some hidden $x$. We are given $p$, $g$ and $h$ and the goal is to recover $x$.

q = 127049168626532606399765615739991416718436721363030018955400489736067198869364016429387992001701094584958296787947271511542470576257229386752951962268029916809492721741399393261711747273503204896435780180020997260870445775304515469411553711610157730254858210474308834307348659449375607755507371266459204680043
p = 2**1024 * q + 1

g = 3
h = 22167430376059430630679676235652972242459549427184424487101004659078731951275684400544395455032520211526504936260764167543579962894859895105461241638191329157341317508524604123528869569970436522398088133282816501026124675867597303023053315921006794737150458893962604878313958214001541026011431916550491653311353413427974497947502149907519824065494644815580044942957676947079119519638286167265601768018850753567210484166464342762618682061366667502051134347228205613775687498269608568148198217826596701451568949937835734503519735835665755712108573943924004834183073368205468093930976680849195434185471527862856627210807

Strike-Slip Fault

  • Solves: 50/1319
  • Difficulty: ⭐⭐
  • Tags: rsa
  • Author: lamchcl

We are given a RSA public key $(n, e)$ and the encrypted flag $c$. Denote $d$ be the private exponent, and $d'$ to be $d$ with three bits flipped. We are also given

$$m' = c^{d'}\ \text{mod}\ n.$$

The goal is to recover the flag.

Prophet

  • Solves: 45/1319
  • Difficulty: ⭐⭐
  • Tags: prng
  • Author: aplet123

Let $\mathcal{R}$ be the PRNG that is used in the math package in Golang 1.18 with a hidden 64-bit seed. Let $v_k$ be the $k$-th 64-bit output (zero-indexed) from $\mathcal{R}$. We are given

  • the encrypted flag (the flag XOR-ed with $v_{100000}, v_{100001}, v_{100002}$ and $v_{100003}$), and
  • 607 non-consecutive outputs: $v_{n_0}, v_{n_1}, …, v_{n_{606}}$.

Here $n_0 = 100004$ and $n_{k+1} = n_k + 1 + (k\ \text{mod}\ 13)$ for all $k \geq 0$. The objective is to recover the flag.

RSA-AES 🔥

  • Solves: 36/1319
  • Difficulty: ⭐⭐
  • Tags: ?
  • Author: lamchcl

We are given a RSA exponent $(n, e)$ and the encrypted flag $c$ (this is unchanged for all server connections). Upon connecting to the server, a 32-byte key $\mathcal{K}$ and a 16-byte IV (used for AES-CBC) are generated.

n = 0xbb7bbd6bb62e0cbbc776f9ceb974eca6f3d30295d31caf456d9bec9b98822de3cb941d3a40a0fba531212f338e7677eb2e3ac05ff28629f248d0bc9f98950ce7e5e637c9764bb7f0b53c2532f3ce47ecbe1205172f8644f28f039cae6f127ccf1137ac88d77605782abe4560ae3473d9fb93886625a6caa7f3a5180836f460c98bbc60df911637fa3f52556fa12a376e3f5f87b5956b705e4e42a30ca38c79e7cd94c9b53a7b4344f2e9de06057da350f3cd9bd84f9af28e137e5190cbe90f046f74ce22f4cd747a1cc9812a1e057b97de39f664ab045700c40c9ce16cf1742d992c99e3537663ede6673f53fbb2f3c28679fb747ab9db9753e692ed353e3551
e = 0x10001

We are allow to interact with the server by sending $c \in [0, n)$. We will then obtain $s$:

$$s := \text{AES-CBC}_\mathcal{K}(c^d\ \text{mod}\ n),$$

where $d$ is the private exponent of RSA, and the IV used in $\text{AES-CBC}$ is the last ciphertext block (or IV if no encryptions are done yet). The objective is to recover the flag.