Crypto in CTF: Q2 2022

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

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

PlaidCTF 2022⌗

pressure⌗

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

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: aes, rsa
• 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.