Crypto in CTF: Q3 2021

Pwn2Win CTF 2021⌗

Oh, Anna Julia⌗

• Solves: 49/720
• Difficulty: ⭐
• Tags: math

Suppose that $h_i \equiv g^{x_{i,1} + x_{i,2} + ... + x_{i,40}}\ (\text{mod}\ q)$ for $i = 1, 2, ...$. We are given $g$, $q$ and $h_i$'s. We are able to control $a_1, a_2, ..., a_{40} \in \{0, 1, 2, ..., 255\}$, pick $k\in\{1, 2, ..., 40\}$ multiple times and obtain

\[\begin{aligned} &c := {h_1}^{x_{2,k}} \cdot {h_3}^{x_{4,k}} \cdot ... \cdot g^{(a_i \oplus s_i) + r}\ \text{mod}\ q \\ &d := {h_2}^{x_{1,k}} \cdot {h_4}^{x_{3,k}} \cdot ... \cdot g^{r}\ \text{mod}\ q \end{aligned},\]

where $r$ is randomly generated each time. The objective is to find $s_k \in \{0, 1, 2, ..., 255\}$ for all $k = 1, 2, ..., 40$.

t00 rare 🔥⌗

• Solves: 13/720
• Difficulty: ⭐⭐
• Tags: ecdsa

We are allowed to obtain ECDSA signatures over P-256 via the given oracle, where the $k$ is generated deterministically from the given digest $h$. The secret key is computed by $a^x\ \text{mod}\ q$, where $q$ is the order of the curve. Notably, the order for $a$ is 40-bit long. Suppose that the signature for the flag is $(r_\text{flag}, s_\text{flag})$ and denote $R$ be a point on the elliptic curve with its x-coordinate being $r_\text{flag}$. The objective is to find $x$ such that $R = xG$.

cladorhizidae⌗

• Solves: 12/720
• Difficulty: ⭐⭐
• Tags: hash

We are given a hash algorithm $\mathcal{H}$ that looks alike to Merkle-Damgard scheme, where

1. the block size is two,
2. the length padding does not exist, and
3. the state is reversible if the message is known.

We are also given an oracle to compute $\mathcal{H}(s + x)$, where $s$ is the secret, from $x$. The objective is to find $\mathcal{H}(s + t)$, given $t$, after accessing to the oracle $2^{16}$ times.

A2S 🔥⌗

• Solves: 10/720
• Difficulty: ⭐⭐⭐⭐
• Tags: two-round aes

We are given three message-ciphertext pairs of AES, where the number of rounds is reduced from ten rounds to two. The objective is to recover the key.

Kangurei⌗

• Solves: 3/720
• Difficulty: ⭐⭐⭐
• Tags: postquantum

We are given a public key for Tsafenat-Paaneah-I (TP-I) and three ciphertexts, where each of them is encrypted from a part of the flag. The objective is to decrypt the ciphertexts for the flag.

Zh3r0 CTF 2021⌗

alice_bob_dave⌗

• Solves: 91/509
• Difficulty: ⭐
• Tags: rsa

Two RSA keys $\mathcal{K}_1$ and $\mathcal{K}_2$ are generated and two different messages $m_i$ are encrypted with $\mathcal{K}_i$. Suppose that the moduli of the two keys shared a common prime factor. We are given the private keys $d_1$, $d_2$, ciphertexts $c_1$, $c_2$ and $e=65537$ (Note that we do not have the moduli). The objective is to retrieve the $m_i$'s.

chaos⌗

• Solves: 50/509
• Difficulty: ⭐⭐
• Tags: hash

We are given the hash algorithm below. Find a pair of hash collision.

def hash(text:bytes):
    text = pad(text)
    text = [int.from_bytes(text[i:i+4],'big') for i in range(0,len(text),4)]
    M = 0xffff
    x,y,z,u = 0x0124fdce, 0x89ab57ea, 0xba89370a, 0xfedc45ef
    A,B,C,D = 0x401ab257, 0xb7cd34e1, 0x76b3a27c, 0xf13c3adf
    RV1,RV2,RV3,RV4 = 0xe12f23cd, 0xc5ab6789, 0xf1234567, 0x9a8bc7ef
    for i in range(0,len(text),4):
        X,Y,Z,U = text[i]^x,text[i+1]^y,text[i+2]^z,text[i+3]^u
        RV1 ^= (x := (X&0xffff)*(M - (Y>>16)) ^ ROTL(Z,1) ^ ROTR(U,1) ^ A)
        RV2 ^= (y := (Y&0xffff)*(M - (Z>>16)) ^ ROTL(U,2) ^ ROTR(X,2) ^ B)
        RV3 ^= (z := (Z&0xffff)*(M - (U>>16)) ^ ROTL(X,3) ^ ROTR(Y,3) ^ C)
        RV4 ^= (u := (U&0xffff)*(M - (X>>16)) ^ ROTL(Y,4) ^ ROTR(Z,4) ^ D)
    for i in range(4):
        RV1 ^= (x := (X&0xffff)*(M - (Y>>16)) ^ ROTL(Z,1) ^ ROTR(U,1) ^ A)
        RV2 ^= (y := (Y&0xffff)*(M - (Z>>16)) ^ ROTL(U,2) ^ ROTR(X,2) ^ B)
        RV3 ^= (z := (Z&0xffff)*(M - (U>>16)) ^ ROTL(X,3) ^ ROTR(Y,3) ^ C)
        RV4 ^= (u := (U&0xffff)*(M - (X>>16)) ^ ROTL(Y,4) ^ ROTR(Z,4) ^ D)
    return int.to_bytes( (RV1<<96)|(RV2<<64)|(RV3<<32)|RV4 ,16,'big')

Twist and Shout⌗

• Solves: 29/509
• Difficulty: ⭐
• Tags: mt19937

We are given 624 consecutive outputs (32-bit) from MT19937. The objective is to recover the state (where the flag is hidden inside).

import numpy as MT⌗

• Solves: 15/509
• Difficulty: ⭐⭐
• Tags: mt19937

We are given the flag encrypted with AES-CBC twice, with the keys and IVs each round are numpy.random.bytes(16). The objective is to retrieve the flag.

Real Mersenne⌗

• Solves: 13/509
• Difficulty: ⭐⭐
• Tags: mt19937

We are given $\approx 1000$ outputs from random.random(). The objective is to predict the upcoming values of random.random().

0CTF 2021 Quals⌗

zer0lfsr- 🔥⌗

• Solves: 35/464
• Difficulty: ⭐⭐⭐
• Tags: lfsr, nfsr

We are given three generators those composed of LFSRs (and NFSRs):

1. Generator1 composes of a 48-bit NFSR and a 16-bit LFSR,
2. Generator2 composes of a 16-bit NFSR and a 48-bit LFSR, and
3. Generator3 composes of a 64-bit LFSR.

Notably, the outputs for each of the generators are non-linear from the state.

We are asked to crack two of the three generators within 50 seconds. For each of the generators, we are given 40K bits from its output. The objective is to recover the initial state.

zer0lfsr+⌗

• Solves: 2/464
• Difficulty: ⭐⭐⭐⭐⭐
• Tags: lfsr, nfsr

This is a sequel to zer0lfsr- and the generators are reused.

We are given 160K bits from $\text{MAJ}(o_1, o_2, o_3)$ (the majority function), where $o_i$ is an output bit from the $i$-th generator. Each generator has a different initial state $k_1, k_2, k_3$ and there is a function $\text{KDF}$ such that $k_2 = \text{KDF}(k_1)$ and $k_3 = \text{KDF}(k_2)$. The objective is to recover all of the $k_i$'s within 100 seconds.

zer0lfsr++⌗

• Solves: 1/464
• Difficulty: ⭐⭐⭐⭐⭐
• Tags: lfsr, nfsr

This is a sequel for zer0lfsr+ to kill an unintended solution.

The problem is similar to zer0lfsr+ but the $k_i$'s are generated independently. On the other hand, we are given the first 16 bits for either $k_1$, $k_2$ or $k_3$. The objective is to recover all of the $k_i$'s within 180 seconds.

cloudpass⌗

• Solves: 3/464
• Difficulty: ⭐⭐
• Tags: application, keepass

There is a challenge server that allow us to import (or to create) a .kbdx file with a given password. We are allow to perform the following operations:

1. Add an entry given group $g$, title $t$, username $u$ and password $p$: $\text{Add}_\mathcal{E}(g, t, u, p)$,
2. Add a group given parent group $g_p$ and group $g$: $\text{Add}_\mathcal{G}(g_p, g)$,
3. Add binary given blob $b$: $\text{Add}_\mathcal{B}(b)$,
4. List entries: Return all the $(t, u)$'s,
5. List groups: Return all the groups $g$'s,
6. List binaries: Return all the $b$'s,
7. Add the flag via $\text{Add}_\mathcal{E}(g_\text{root}, \text{flag}, \text{0ops}, \mathcal{F})$ and change the master password to 32 random bytes, and
8. Export the .kdbx and terminate the program.

The objective is to recover the flag $\mathcal{F}$.

Addendum (2021.07.28). I have lowered the estimated difficulty. From @RBTree_, the challenge composes of 60% reversing, 30% forensics and 10% cryptography. Reversing the pykeepass package and learning the file structure constitutes the majority of the challenge. The cryptographic element itself is not particularly hard.

redpwnCTF 2021⌗

baby⌗

• Solves: 827/1418
• Difficulty: -
• Tags: rsa

We are given a 128-bit RSA modulus $n$ and the public exponent $e = 65537$. The goal is to decrypt a given ciphertext $c$. Notably, the factors of $n$ is available in factordb before the CTF begins.

blecc⌗

• Solves: 146/1418
• Difficulty: ⭐
• Tags: ecc

Given an elliptic curve $\mathcal{C}: y^2 = x^3 + ax + b$ over a prime field $\text{GF}(p)$ (where $p$ is a 64-bit prime). Also, the largest prime factor of the curve's order is 28-bit long. Find $d$ such that $Q = dG$ for given $G$ and $Q$.

Credits: TWY.

yahtzee⌗

• Solves: 103/1418
• Difficulty: ⭐
• Tags: ctr, repeated nonce

We are allowed to retrieve $c$, computed by the below procedure, for an arbitrary number of times.

1. Randomly pick a message $m$ from one of the 25 possible messages.
2. Insert the flag in a random position of $m$.
3. Randomly pick the nonce $\nu$ from one of the 11 candidates.
4. Encrypt $m$ with nonce being $\nu$ with AES-CTR - and denote it by $c$.
5. Return $c$ to the player.

The objective is to recover the flag.

scrambled-elgs⌗

• Solves: 70/1418
• Difficulty: ⭐
• Tags: elgamal

We are given a generator $g$ of the symmetric group with 25000 elements and a public key $h$. Given also a ciphertext $(c_1, c_2)$ encrypted with ElGamal cryptosystem, the goal is to find the corresponding message.

Keeper of the Flag⌗

• Solves: 42/1418
• Difficulty: ⭐⭐
• Tags: dsa

We are allowed to sign two different messages using DSA-SHA1 with the given oracle, where the nonce is somehow predictable. The objective is to forge a signature for a particular message (of course you cannot sign it during the first phase).

retrosign⌗

• Solves: 26/1418
• Difficulty: ⭐⭐⭐
• Tags: oss

Given $k$, $h$ and a composite modulus $n$, find $x$, $y$ such that $x^2 + ky^2 = h\ (\text{mod}\ n)$. This is also known as the OSS signature scheme.

Google CTF 2021 Quals⌗

H1⌗

• Solves: 23/379
• Difficulty: ⭐⭐
• Tags: ecdsa, ecdh

Alice and Bob have a private key $d_A, d_B$ respectively and they are used for both ECDSA and ECDH. They derive a shared secret for encryption with ECDH and sign with ECDSA-SHA512.

We are given four messages those are sent between Alice and Bob (two from Alice and two from Bob). Denote the $i$-th message, ciphertext and signature being respectively $m_i$, $c_i$ and $(r_i, s_i)$ - Hereby $m_1$ and $m_3$ are signed by Alice and the rest are signed by Bob. We are given all of them except $m_3$. The objective is to recover $m_3$ where the flag is hidden.

Notably, the entropy for the RNG while generating ECDSA nonces is 128 bits long.

pythia 🔥⌗

• Solves: 65/379
• Difficulty: ⭐⭐⭐
• Tags: gcm

A nine-letter password is split into three parts. Three keys are derived from each part of the passwords (namely $k_0, k_1, k_2$). We are given the below operations:

1. Set key specifies the key $\mathcal{K} = k_i$ we will be using in the subsequent operations.
2. Read flag requests the user to send the password. If it is correct, then the flag is revealed.
3. Decrypt text decrypts a specified ciphertext using $\mathcal{K}$ with AES-GCM. Only return if the ciphertext is decrypted successfully.

The goal is to read the flag within 150 calls.

story⌗

• Solves: 32/379
• Difficulty: ⭐⭐
• Tags: crc

When connected to the server, we are asked to send a message $m_1$ and $\text{CRC}(m_1)$ will be returned (We do not have the source code for the CRC). The server then sends a target $c_2$. The objective is to send $m_2$ such that

1. $c_2 = \text{CRC}(m_2)$ and,
2. the lowercase for $m_1$ is the same as the lowercase for $m_2$.

tiramisu⌗

• Solves: 28/379
• Difficulty: ⭐⭐⭐
• Tags: ecdh

When connected to the server, it sends a ServerHello message that includes the server's public key for ECDH (on the curve P-224), as well as the flag encrypted with server's ECDH private key. We will be replying a ClientHello message that the point should be either on P-224 or P-256. We will be sending SessionMessages which is a encrypted and HMACed payload when a secure channel is established. If the HMAC is correct and the content can be correctly decrypted, the server will be responding with another SessionMessage with a slightly changed IV. The objective is to decrypt the flag.

Note that the server's key does not change upon reconnect.

tonality⌗

• Solves: 30/379
• Difficulty: ⭐⭐
• Tags: ecdsa

The server generates a private key $x$ on P-256 upon connect. We are allowed to pick $\alpha$ and the server will sign $m_0$ with the private key $\alpha x$. The objective is to forge a signature for $m_1$ using the private key $x$ in a subsequent request.

ImaginaryCTF 2021⌗

Rock Solid Algorithm⌗

• Solves: 149/1018
• Difficulty: ⭐
• Tags: rsa

We are given the RSA public $n$ and $e := 5$ and a ciphertext $c$ (of the message $m$). Given that $0 < m^5 < 1000 n$, find $m$.

Lines⌗

• Solves: 128/1018
• Difficulty: ⭐
• Tags: math

We are given a $p$ and $g$. Two numbers $a$ and $b$ are generated privately and the shared secret $s := g^{ab}\ (\text{mod}\ p)$ is computed. Messages are encrypted as $c = m\cdot s\ (\text{mod}\ p)$.

Two pairs of messages $(m_1, c_1)$ and $(m_2, c_2)$ are encrypted in this way. We are given $c_1, m_2, c_2$ and the objective is to find $m_1$ - which is the flag.

Flip Flops⌗

• Solves: 160/1018
• Difficulty: ⭐
• Tags: cbc

We are given a server that performs the following operations:

1. Encrypts an user-defined message (that does not contain gimmeflag) with a secret key $\mathcal{K}$ and an initial vector $\mathcal{IV}$ in AES-CBC.
2. Sends the flag to the user if the user sends a ciphertext that the corresponding plaintext contains gimmeflag.

The objective is to win the flag via the second operation.

New Technology⌗

• Solves: 50/1018
• Difficulty: ⭐
• Tags: math

We are given $n$ such that $n = p_1^{k_1}p_2^{k_2}...p_5^{k_5}$ where $p_i$'s are all primes and $1 \leq k_i \leq 3$. The key $k$ defined below is used to derive an AES key that encrypts the flag. The goal is to decrypt the ciphertext.

\[k = \sum_{d_1|n}\sum_{d_2|d_1} d_2 \cdot \varphi(d_2) \cdot \varphi\left(\frac{d_1}{d_2}\right)\]

Roll it back⌗

• Solves: 58/1018
• Difficulty: ⭐
• Tags: lfsr

There is a LFSR in this challenge. We are given the feedback polynomial and the state after clocked 421337 times. The objective is to recover the initial state, which is the flag.

Primetime⌗

• Solves: 41/1018
• Difficulty: ⭐⭐
• Tags: dh, math

This challenge implements Diffie-Hellman in a handcrafted group (called Element), where addition and scalar multiplication is defined. A generator $G$ is given and the shared secret is computed by $H := abG$, where $a, b\in\mathbb{Z}$ are two private keys from the two parties. We are also given $C := mH$ where $m\in\mathbb{Z}$ is the flag. The objective is to recover $m$.

ZKPoD⌗

• Solves: 19/1018
• Difficulty: ⭐⭐
• Tags: rsa

We are given a pair of RSA public key $(n, e)$, an encrypted flag $c_0$ and a pair of constants $g, p$ (will be mention later). We are also given an oracle $\mathcal{O}$ that "signs" a message given a ciphertext $c$. The objective is to recover the flag from $c_0$. Below is the procedure for $\mathcal{O}$:

1. Compute $m := c^d\ (\text{mod}\ n)$, i.e., decrypt with RSA.
2. Generate $k \in [0, p)$.
3. Compute $r := g^k\ (\text{mod}\ p)$.
4. Compute $e := F(r)$ for a given deterministic function $F$.
5. Compute $s := k - me\ (\text{mod}\ p-1)$.
6. Return $(r, s)$.

Crypto CTF 2021⌗

Robert⌗

• Solves: 19/444
• Difficulty: ⭐⭐
• Tags: math

We are given a number of integers $m$'s and the objective is to find a corresponding $n$ such that $\lambda(n) = m$, where $\lambda$ is the Carmichael's lambda function.

Rohald⌗

• Solves: 21/444
• Difficulty: ⭐⭐
• Tags: ecc

Suppose that $\mathcal{C}$ is a curve defined by $u^2 + v^2 \equiv c^2 (1 + du^2v^2)\ (\text{mod}\ p)$ (the parameters $c$, $d$ nor $p$ are given). We are given four points on the curve: $P$, $Q$, $sP$ and $tQ$. The objective is to find $s$ and $t$, where each of them encodes half of the flag. Note that the prime factors of the curve order does not exceed $2.5 \times 10^9$.

Ecchimera 🔥⌗

• Solves: 11/444
• Difficulty: ⭐⭐⭐
• Tags: ecc

We are given a curve $\mathcal{C}: y^2 \equiv x^3 + Ux^2 + Vx + W\ (\text{mod}\ n)$ and two points $G, H\in \mathcal{C}$ with $H := sG$. The objective is to find $s$.

The parameters are given below:

n = 43216667049953267964807040003094883441902922285265979216983383601881964164181
U = 18230294945466842193029464818176109628473414458693455272527849780121431872221
V = 13100009444194791894141652184719316024656527520759416974806280188465496030062
W = 5543957019331266247602346710470760261172306141315670694208966786894467019982

G = (6907136022576092896571634972837671088049787669883537619895520267229978111036, 35183770197918519490131925119869132666355991678945374923783026655753112300226)
H = (14307615146512108428634858855432876073550684773654843931813155864728883306026, 4017273397399838235912099970694615152686460424982458188724369340441833733921)

My Sieve⌗

• Solves: 1/444
• Difficulty: ❓
• Tags: ❓

We are given a corrupted pubkey.pem where four characters are redacted.

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCB*QKBgQCkRgRCyTcSwlBKmERQV/BHkurS
5QnYz7Rm18OjxuuWT3A*Ueqzq7fHISey2NEEtral/*E7v2Dy59DYHoRAAouWQd03
ZYWnvU5mWoYRcpNmHIj8q*+FOtBWcCGzMZ8uxOxaV74vqqerjxyRI14rXZ+QOcNM
/TMM84h0rl/IKqqWsQIDAQAB
-----END PUBLIC KEY-----

On top of that, we are also given a msieve.dat and enc.txt. The objective to decrypt enc.txt for the flag.

Hyper Normal⌗

• Solves: 69/444
• Difficulty: ⭐
• Tags: adhoc

We are given a $55\times55$ matrix $W$ defined by

\[ W = \begin{bmatrix} r_{1,1}x_1 & 2r_{1,2}x_2 & 3r_{1,3}x_3 & ... & 55r_{1,55}x_{55} \\ r_{2,1}x_1 & 2r_{2,2}x_2 & 3r_{2,3}x_3 & ... & 55r_{2,55}x_{55} \\ && \vdots && \\ r_{55,1}x_1 & 2r_{55,2}x_2 & 3r_{55,3}x_3 & ... & 55r_{55,55}x_{55} \\ \end{bmatrix}\ \text{mod}\ p, \]

hereby $r_{ij}, x_j \in [0, 126]$ for all $i, j \in \{1, 2, ..., 55\}$ and $p = 8443$. The objective is to find $x_j$, which each of them represents one character of the encoded flag.

KeyBase⌗

• Solves: 118/444
• Difficulty: ⭐
• Tags: cbc

We are given the flag $c_0$ encrypted with AES-CBC under a fixed IV and key. Although the IV is unknown, we have 14 bytes (out of 16) of the key. We are also given an oracle $\mathcal{O}$ that encrypts a 32-byte message $m$ and return the corresponding ciphertext with part of the first block redacted.

Triplet⌗

• Solves: 50/444
• Difficulty: ⭐
• Tags: rsa

We are asked to find three RSA moduli $n_1 = p_1q_1, n_2 = p_2q_2$ and $n_3 = p_3q_3$ and a pair of exponents $e, d$ such that the below conditions hold for all $i = 1, 2, 3$:

\[p_i, q_i > 2^{160}\qquad \text{and} \qquad 1 < e, d < \varphi(n_i) \qquad \text{and} \qquad ed \equiv 1\ (\text{mod}\ \varphi(n_i)).\]

We will be given the flag if all of the conditions hold.

DoRSA 🔥⌗

• Solves: 2/444
• Difficulty: ⭐⭐⭐⭐
• Tags: rsa

Four 256-bit numbers $u, v, x$ and $y$ are generated and compute $p = uv+1, q = uy+1$ and $r = xy+1$. If $p, q$ and $r$ are all primes, generate a 256-bit number $e$ and find the corresponding $d \in \mathbb{Z}$ such that there exists $k \in \mathbb{Z}$ with $ed - k \varphi(pr) = 1$.

Define also $s = kv+1$, which should also be a prime. Compute the modulus $n_1 = pr$ and $n_2 = qs$. We are given $n_1, n_2$, a common public exponent $e$ and two ciphertexts $c_1, c_2$ being the encrypted $m$ (the flag) with respectively $(n_1, e)$ and $(n_2, e)$ using RSA. The objective is to recover the flag.

Hamul⌗

• Solves: 56/444
• Difficulty: ⭐
• Tags: rsa

We are given a modulus $n$ and $e = 65537$ for RSA and the encrypted flag $c$. The objective is to recover the flag.

In particular, the primes $p$ and $q$ are derived by concatenating two 64-bit primes $u$ and $v$ in the following way:

\[p = u\ \|\ v\ \|\ v\ \|\ u\qquad\text{and}\qquad q = v\ \|\ u\ \|\ u\ \|\ v.\]

Double Miff⌗

• Solves: 16/444
• Difficulty: ⭐⭐⭐
• Tags: ecc, math

Suppose that there is a curve $\mathcal{C}: ax(y^2 - 1) \equiv by(x^2 - 1)\ (\text{mod}\ p)$ (we are not given the parameters) where the addition operator is defined. We are given $A, B, C\in \mathcal{C}$ such that $A = P+Q$, $B = Q+Q$ and $C = P+P$. The objective is to find $P$ and $Q$, and each of their $x$-coordinates encodes half of the flag.

Elegant Curve⌗

• Solves: 16/444
• Difficulty: ⭐⭐
• Tags: ecc

When connected to the server, we are asked to send a pair of triples $(a, b, p)$ and $(c, d, q)$ satisfying the below conditions:

1. $0 < a, b < p$ and $0 < c, d < q$, and
2. $p, q$ are both 160 bits long and $0 < q - p < 2022$.

Two curves are defined by $\mathcal{C}_1: y^2 \equiv x^3 + ax + b\ (\text{mod}\ p)$ and $\mathcal{C}_2: y^2 \equiv x^3 + cx + d\ (\text{mod}\ q)$. We are then given $G, rG \in \mathcal{C}_1$ and $H, sH \in \mathcal{C}_2$ and asked for $r, s$ to redeem the flag.

Improved⌗

• Solves: 37/444
• Difficulty: ⭐⭐
• Tags: math

We are given a hash algorithm $\mathcal{H}$ where the procedures when given an integer $m$ are defined below:

1. Asserts that $1 < m < n^2 - 1$.
2. Computes $e := m^f \text{mod}\ n^2$.
3. Computes $u := (e - 1) / n$.
4. Computes $L := u\cdot v\ \text{mod}\ n$.
5. Returns $\text{SHA256}(L)$ as the digest.

The objective is to find a pair of collisions. Note that the parameters $n$, $f$ and $v$ are given.

Polish⌗

• Solves: 1/444
• Difficulty: ⭐⭐⭐
• Tags: rsa, math

We are given a 773-bit RSA modulus $n$, $e = 65537$ and the lowest 221 bits for $d$. We are also given an equation on $x$ and $y$:

\[x^2 (y - s) + y^2 (x - s) = t,\]

where $s$ and $t$ are given constants. We are also given $c := (x^2 + m + y)^e\ \text{mod}\ n$. The goal is to recover $m$, the flag.

Ferman⌗

• Solves: 31/444
• Difficulty: ⭐
• Tags: math

When connected to the server, we are asked to find $p$ and $q$ such that

\[(p - s)^2 + (q - t)^2 = u^7,\]

for some given constants $s, t$ and $u$ (will be changed in different connections).

Trunc⌗

• Solves: 7/444
• Difficulty: ⭐⭐
• Tags: ecc, signature scheme

When connected to the server, a private key of SECP256k1 is generated (denote by $x$). We are given the corresponding public key and a signature oracle, $\mathcal{O}$, to sign messages. The goal is to forge a signature $(u, v, s)$ such that it is a valid for $m_0$, which cannot be signed via $\mathcal{O}$.

Specifically, the signature scheme is handcrafted and defined below. Suppose that we are given a message $m$ (of length not exceeding 14):

1. Generates $k, l$ randomly.
2. Computes $u$ and $v$ are respectively the $x$-coordinates of $kG$ and $lG$, where $G$ is the generator for SECP256k1.
3. Computes $h = \text{SHA256}(m)$.
4. Computes $s = k^{-1} (hu - vx)\ (\text{mod}\ n)$.
5. Returns $(u, v, s)$ as the signature.

Frozen⌗

• Solves: 29/444
• Difficulty: ⭐⭐
• Tags: lcg

We are given a 128-bit prime $p$ and $r \in [1, p)$ as the parameters. A secret number $s$ is generated and five numbers $u_1, u_2, ..., u_5$ is defined by $u_k = r^ks\ \text{mod}\ p$ for $k = 1, 2, ..., 5$.

We are also given those $u_k$'s except that the lowest 32 bits are redacted. The goal is to fully recover the $u_k$'s.

Wolf⌗

• Solves: 33/444
• Difficulty: ⭐
• Tags: gcm

When connected to the server, a nonce of size $r\in[1, 11]$ (denoted by $\eta$) is generated. We are given the key $k$, the flag encrypted under AES-GCM with key $k$ and nonce $\eta$. We are also given an oracle $\mathcal{O}$ that encrypts arbitrary messages $m$ under the same key and nonce under AES-GCM. The goal is to recover the flag.

Salt and Pepper⌗

• Solves: 69/444
• Difficulty: ⭐
• Tags: hash

We are asked to forge an authentication token such that the username contains n3T4Dm1n and password contains P4s5W0rd, where the authentication token for a given username and password is defined by:

\[\text{SHA1}(\text{pepper}\ ||\ \text{password}\ ||\ \text{MD5}(\text{salt}\ ||\ \text{username}))\]

We are also given $\text{SHA1}(\text{pepper})$ and $\text{MD5}(\text{salt})$, and their lengths are both 19.

Tiny ECC⌗

• Solves: 16/444
• Difficulty: ⭐⭐
• Tags: ecc

When connected to the server, we are asked to provide $a, b$ and $p$ satisfying the below conditions:

1. $p$ is 128-bit long, and
2. $p$ and $q = 2p+1$ are both primes, and
3. $a, b \neq 0$.

Two curves are defined by $\mathcal{C}_1: y^2 \equiv x^3 + ax + b\ (\text{mod}\ p)$ and $\mathcal{C}_2: y^2 \equiv x^3 + ax + b\ (\text{mod}\ p)$. We are then given $P, kP \in \mathcal{C}_1$ and $Q, lQ \in \mathcal{C}_2$ and asked for $k, l$ to redeem the flag. (This challenge is similar to Elegant Curve but with relaxed conditions)

Lower 🔥⌗

• Solves: 0/444
• Difficulty: ⭐⭐⭐⭐
• Tags: ❓

When connected to the server, $e_1, e_2, ..., e_5 \in \text{GF}(127)$ are randomly generated. Also, $x_1, x_2, ..., x_{20} \in \text{GF}(127)$ represent the flag. We can request an arbitrary amount of equations, each of them in the form of:

\[s = c_1 x_1 + c_2 x_2 + ... + c_{20} x_{20} + e_k,\]

where we are given $c_1, c_2, ..., c_{20}$ and $s$. Also, $k \in \{1, 2, ..., 5\}$ is picked randomly. The goal is to find $x_i$'s, i.e., the flag.

LINDA⌗

• Solves: 23/444
• Difficulty: ⭐⭐
• Tags: elgamal

We are given a ElGamal cryptosystem variant with public key $(p, u, v, w)$. To encrypt a message $m \in [0, p)$, two random numbers $r, s \in [1, p)$ are generated and the ciphertext is $(u^r\ \text{mod}\ p, v^s\ \text{mod}\ p, mw^{r+s}\ \text{mod}\ p)$. We are given the public key and the encrypted flag. We are also given an oracle $\mathcal{O}$ to encrypt arbitrary messages. The objective is to find the flag. Note that the prime factors of $p-1$ does not exceed $10^{10}$.

RSAphantine⌗

• Solves: 29/444
• Difficulty: ⭐⭐
• Tags: math

We are given $r, s$ and $t$ and three equations related to $x, y$ and $z$:

\[ \begin{cases}\begin{aligned} 2z^5 - x^3 + yz &= r \\ x^4 + y^5 + xyz &= s \\ y^6 + 2z^5 + zy &= t \end{aligned}\end{cases}. \]

$x, y$ and $z$ are used to derive the primes for RSA modulus by:

\[ \begin{cases}\begin{aligned} p &= \text{NextPrime}(2^{76} \cdot (x^2 + z^2 + y^2)) \\ q &= \text{NextPrime}((z^2 + y^3 - yxz) \oplus 67) \end{aligned}\end{cases}. \]

We are also given the encrypted flag $c$, encrypted with $e = 31337$ and $n = pq$ - and the objective is to recover the flag.

Onlude⌗

• Solves: 48/444
• Difficulty: ⭐
• Tags: math

We are given four $11 \times 11$ matrices $E$, $LUL$, $L^{-1}S^2L$ and $R^{-1}S^8$. Here $L$ and $U$ are respectively a lower and upper triangular matrix such that $S = LU$.

The objective is to find the matrix $X$, the encoded flag, such that $E = U(X + R)$.

Tuti⌗

• Solves: 71/444
• Difficulty: ⭐
• Tags: math

We are asked to find $(x, y)$ such that $(x^2 + 1)(y^2 + 1) - 2(x - y)(xy - 1) = 4(k + xy)$ for a given $k$. In particular, each $x$ and $y$ encodes half of the flag.

Maid⌗

• Solves: 36/444
• Difficulty: ⭐⭐
• Tags: rabin

We are given an encryption oracle $\mathcal{E}$ and a decryption oracle $\mathcal{D}$ of a variant of the Rabin cryptosystem, where the modulus is defined by $n = p^2q$ instead of the product of the two primes.

On top of that, we are also given the flag, $c$, encrypted with RSA with modulus $pq$ and the public exponent $e = 65537$. The objective is to recover the flag.

UIUCTF 2021⌗

dhke_adventure⌗

• Solves: 64/658
• Difficulty: ⭐
• Tags: dh

Upon connected to the server, we are asked to send a prime $p$ which is between 1024 and 2048 bits. The generator $g = 2$ is used and two random private keys $a, b \in [2, p)$ are generated. Denote $A := g^a\ (\text{mod}\ p)$ and $B := g^b\ (\text{mod}\ p)$ and $c$ be the flag encrypted with the key derived from $g^{ab}\ (\text{mod}\ p)$. The objective is to decrypt the flag given $A$, $B$ and $c$.

pow_erful⌗

• Solves: 16/658
• Difficulty: ⭐⭐
• Tags: hash

We are given 64 proof-of-work challenges. In the $k$-th round, we are given a two-byte prefix and we are asked to find $x$ such that $\text{SHA256}(\text{prefix} + x)$ has $k$ trailing zero bits. We will be given the flag after solving the proof-of-work challenges.

RaRCTF 2021⌗

sRSA⌗

• Solves: 220/845
• Difficulty: -
• Tags: math

We are given a public key of RSA $n, e$ and an encrypted flag $c$. However the encryption algorithm is $c \equiv me\ (\text{mod}\ n)$. The goal is to recover the flag.

unrandompad⌗

• Solves: 89/845
• Difficulty: ⭐
• Tags: rsa

Upon connected to the server, we are given a RSA public key $n, e = 3$. We can also retrieve flag encrypted with the aforementioned public key. The objective is to recover the flag.

Shamir's Stingy Sharing⌗

• Solves: 85/845
• Difficulty: ⭐
• Tags: math

Upon connected to the server, a degree 30 polynomial $p(n)$ with integral coefficients generated randomly in $[0, 2^{128})$ is produced. We are allowed to supply $k\neq 0$ and get the $k$-th share (defined by $p(k)$). On top of that, the flag xorred with a random stream seeded by $p(0)$ is given. The objective is to recover the flag.

babycrypt⌗

• Solves: 108/845
• Difficulty: ⭐
• Tags: rsa

Upon connected to the server, we are given a RSA public key $n, e$, a hint defined by $d\ \text{mod}\ (q-1)$ and an encrypted flag $c$. The objective is to recover the flag.

rotoRSA⌗

• Solves: 29/845
• Difficulty: ⭐⭐
• Tags: math, rsa

Upon connected to the server, we are given a RSA public key $n, e = 11$ and $a_0, a_1, ..., a_{15}$ are generated in $[0, 128)$ and they are used to build $p_0(x) = a_0 + a_1 x + ... + a_{15} x^{15}$, $p_1(x) = a_1 + a_2 x + ... + a_{15} x^{14} + a_0 x^{15}$, ..., $p_{15}(x) = a_{15} + a_0 x + a_1 x^2 + ... + a_{14} x^{15}$.

We are able to access the oracle $\mathcal{O}$ many times - On the $k$-th time, we can:

1. supply a message $m$ and obtain an encrypted copy of $p_{k\ \text{mod}\ 16}(m)$ with RSA, or
2. obtain an encrypted copy of $p_{k\ \text{mod}\ 16}(m_0)$, where $m_0$ is the flag.

The objective is to recover the flag.

PsychECC⌗

• Solves: 39/845
• Difficulty: ⭐⭐
• Tags: ecc

We are asked to send a point $P$ on P-256 (they does not check if $P$ lies on the curve though) and they generated a random $k$ between 1 and the curve's order and compute $Q = kP$. We are also asked too send a point $\hat{Q}$ and will be given the flag if $\hat{Q} = Q$ while $\hat{Q} \not\in \{P, O\}$.

snore⌗

• Solves: 17/845
• Difficulty: ⭐⭐
• Tags: signature scheme

A 32 byte secret $s$ is generated at the beginning. Other than that, $x \in [0, p)$ is randomly generated and $y = g^x\ \text{mod}\ p$.

The challenge uses a variant of the data signature algorithm. To sign a message $m$, the following steps are performed:

1. Compute $k$ by xorring $s$ and (part of) $m$.
2. Compute $r = g^k\ \text{mod}\ p$.
3. Compute $e = \text{SHA224}(r\ ||\ m)$.
4. Compute $s = k - xe\ \text{mod}\ (p-1)$.
5. Return $(r, s)$ as the signature.

We are given $g$, $p$ and $y$ as well as six pairs of message-signature pairs. We are also given the flag encrypted with the key derived from $x$. The objective is to recover the flag.

randompad⌗

• Solves: 24/845
• Difficulty: ⭐⭐
• Tags: mt19937, rsa

Upon connected to the server, we are given a RSA public key $n, e = 3$. We are allowed to encrypt arbitrary messages and retrieve an encrypted flag padded with PKCS#1 v1.5 (using streams generated from predictable random). The objective is to recover the flag.

A3S⌗

• Solves: 4/845
• Difficulty: ⭐⭐⭐
• Tags: aes variant

We are given a custom block cipher called A3S, which looks like AES but uses a trit (a ternary digit) instead of a bit as the base unit. On top of that, we are given a message-ciphertext pair and the encrypted flag with the same key. The objective is to recover the flag.

mini-A3S⌗

• Solves: 1/845
• Difficulty: ⭐⭐⭐⭐
• Tags: aes variant

We are still using A3S mentioned in the above challenge. However, there are some modifications including updating the S-box involved, and reducing the key size. We are given $3^9$ message-ciphertext pairs with the same key $k$, and the flag xorred with $\text{SHA512}(k)$. The objective is to recover the flag.

corCTF 2021⌗

4096⌗

• Solves: 219/904
• Difficulty: -
• Tags: rsa

We are given a RSA modulus $n = p_1 p_2 ... p_{32}$ an encrypted flag $c$. Here each of the $p_i$'s is a 32-bit prime. The objective is to find the flag.

dividing_secrets⌗

• Solves: 121/904
• Difficulty: ⭐
• Tags: math

We are given a 512-bit prime $p$ and $g$ with $1 \leq g < p$. We are also given $y = g^x\ \text{mod}\ p$ where $x$ is the flag. We are given 64 attempts of the oracle $\mathcal{O}(k)$, where we could obtain $g^{\lfloor x/k \rfloor}\ \text{mod}\ p$ each time. The objective is to recover the flag.

supercomputer⌗

• Solves: 85/904
• Difficulty: ⭐
• Tags: math

We are given three 2048-bit primes $p, q, r$. Suppose that $n = p^qr$ and $a_1$ is a random number generated in $[0, n]$. Denote $a_2 = n - a_1$ and $t = {a_1}^n + {a_2}^n$. Define $\upsilon: \mathbb{N}^2 \rightarrow \mathbb{Z}_{\ge0}$ by

\[\upsilon(p, k) = \sum_{i=0}^\infty{\lfloor{\frac{p}{k^i}\rfloor}}.\]

The flag is encrypted with the XOR cipher under the key $\upsilon(t, p)$. The objective is to recover the flag.

babyrsa⌗

• Solves: 50/904
• Difficulty: ⭐
• Tags: rsa

We are given a 1024-bit RSA modulus $n$ and part of the $p$ and $q$ (with 40 digits in the middle missing). We are also given the encrypted flag $c$. The objective is to recover the flag.

babypad⌗

• Solves: 35/904
• Difficulty: ⭐
• Tags: ctr, padding oracle

When connected to the oracle, a key $k$ is generated. We are given an oracle $\mathcal{O}(\upsilon, c)$ that performs the below procedure:

1. Decrypt $c$ using key $k$ and initial counter value being $\upsilon$ using AES-CTR.
2. Unpad the above message with PKCS7 padding.

We are also given a ciphertext of the padded flag. The goal is to recover the flag.

babyrand⌗

• Solves: 29/904
• Difficulty: ⭐⭐
• Tags: lcg

We are given three numbers $c_1, c_2, p$ with $p$ being a 512-bit prime and $c_1 \in [0, p)$. Denote $a = p \oplus c_1 \oplus s_1$ and $b = p \oplus c_2 \oplus s_2$ where $0 \leq s_1, s_2 < 2^{200}$, and $c_2 = (c_1\cdot a + b)\ \text{mod}\ p$.

Suppose that a key is derived by $a$ and $b$ and the flag is encrypted with AES-CBC. The objective is to recover the flag.

LCG_k⌗

• Solves: 25/904
• Difficulty: ⭐⭐
• Tags: ecdsa, lcg

Suppose $m_0$ is the message i wish to know the ways of the world.

We are given a ECDSA public key $H$ and we can sign four different messages (except $m_0$) that corresponds to $H$. However, the random number, $k$, is generated with a LCG with a known prime modulus. The objective is to send a signed $m_0$ afterwards.

bank⌗

• Solves: 25/904
• Difficulty: ⭐⭐
• Tags: quantum

When connected to the server, 50 qubits $\lvert q_1 \rangle, \lvert q_2 \rangle, ..., \lvert q_{50} \rangle$ are generated and we are allowed to perform operations on those qubits. The objective is to recover the initial state of the qubits.

Credits: hoifanrd

mystery_stream⌗

• Solves: 10/904
• Difficulty: ⭐⭐⭐
• Tags: lfsr

A flag is inserted to a random position of a large plaintext. It is encrypted with a custom cipher which involves a LFSR, where the initial state is generated with from a particular script (pub.sage). The objective is to recover the flag, given the ciphertext file.

fried_rice 🔥⌗

• Solves: 6/904
• Difficulty: ⭐⭐⭐
• Tags: lcg, discrete log

When connected to the server, $k, a, b\in \text{GF}(2^{128})$ are generated. We are given $a$ and $b$.

A PRNG parametrised by $k, a, b$ is defined and two 512-bit primes $p, q$ are generated with this PRNG. There are multiple cryptosytems involved:

1. $k$ is used to derive an AES key and the flag is encrypted with the key.
2. $n = pq$ and $e = 65537$ is used in the RSA key and $d$ is the corresponding private key - and $d_p = d\ \text{mod}\ (p-1)$.

We are allowed to send $m$ and retrieve $f(m)$, defined below, 26 times:

\[f(m) = g^{d_p \oplus m}\ \text{mod}\ r.\]

The objective is to recover the flag.

leave_it_to_chance 🔥⌗

• Solves: 5/904
• Difficulty: ⭐⭐⭐
• Tags: math

When connected to the server, a 256-bit prime $p$ such that $p \equiv 1\ (\text{mod}\ 4)$ is generated. A number $a$ is generated such that $a^2 \not\equiv 1\ (\text{mod}\ p)$ and $a^4 \equiv 1\ (\text{mod}\ p)$. Furthermore, a private key $(x_0, x_1, ..., x_{15}) \in \mathbb{Z}_p^{16}$ is generated. Denote the function $\mathcal{S}(m)$ by

\[\mathcal{S}(m) = \sum_{i=0}^{15} m^i x_i.\]

We are allowed to perform the three operations:

1. [Sign] We are allowed to send $m \in \mathbb{Z}_p$ (each $m$ could only be signed once). Denote $s = \mathcal{S}(m)$ and we are given $s^4\ \text{mod}\ p$. We are also asked for an number $x$ and two numbers from $\{ -s, as, -as \} \setminus \{ x \}$ are also given as hint.
2. [Verify] We send $m, s\in \mathbb{Z}_p$ and we will be told if $s = [\mathcal{S}(m)]^4\ \text{mod}\ p$.
3. [Guess] We send $(\hat{x_0}, \hat{x_1}, ..., \hat{x_{15}})$ and we will be given the flag if $\hat{x_i} = x_i$ for all $i$. Otherwise the connection ends immediately.

The objective is to recover the private key and send it via guess.

CakeCTF 2021⌗

discrete log⌗

• Solves: 55/157
• Difficulty: -
• Tags: math

A 512-bit prime $p$ and $g, r\in[2, p)$ are generated. Let the flag being $m_1, m_2, ..., m_n$ where $m_k \in [0, 256)$. The flag is encrypted into $c_1, c_2, .., c_n$ with

\[c_k = g^{r \cdot m_k}\ \text{mod}\ p.\]

We are given $p$, $g$ and $c_k$'s. The objective is to recover the flag.

improvisation⌗

• Solves: 34/157
• Difficulty: -
• Tags: lfsr

We are given the taps of a 64-bit LFSR, and an encrypted flag. We are also given the first 8 bytes of the plaintext. The objective is to recover the flag.

Together as one⌗

• Solves: 21/157
• Difficulty: ⭐⭐
• Tags: math, rsa

Three 512-bit prime $p, q, r$ are generated. We are given $n = pqr$, $x = (p+q)^r\ \text{mod}\ n$ and $y = (p + qr)^r\ \text{mod}\ n$, as well as an flag $c$ encrypted with multi-prime RSA with modulus $n$. The objective is to recover the flag.

Matrix Cipher⌗

• Solves: 14/157
• Difficulty: ⭐⭐⭐
• Tags: ggh

Two matrices $R, B \in \mathbb{Z}^{46\times 46}$ are generated such that

\[R = kI + E,\qquad B = UR\]

where $k = \lfloor100\sqrt{46}\rfloor$, $E\in \mathbb{Z}^{46\times 46}$ with $-100 \leq E_{ij} \leq 100$ for all $i, j$ and $\text{det}(U) = \pm1$. For a message $M$, a ciphertext $C$ is defined by $C = BM + \mathcal{E}$, where $\mathcal{E} \in \mathbb{Z}^{46}$ with $-50 \leq \mathbb{E}_i \leq 50$ for all $i$.

We are given $B \in \mathbb{Z}^{46\times 46}$ and the encrypted flag $c \in \mathbb{Z}^{46}$. The objective is to recover the flag.

Party Ticket 🔥⌗

• Solves: 12/157
• Difficulty: ⭐⭐⭐
• Tags: rabin signature

We are given $(b_i, c_i, n_i)$ for $i = 1, 2$, where they satisfy $c_i \equiv m(m + b_i)\ (\text{mod}\ n_i)$. Suppose that $n_i$ is a product of two primes, and $b_i, c_i \in [0, n_i)$. The objective is to recover $m$, which is the flag.

FwordCTF 2021⌗

Leaky Blinders⌗

• Solves: 121/429
• Difficulty: -
• Tags: -

Upon connected to the server, a 32-byte AES key $k$ is generated. We are also given the encrypted flag $c_\text{flag}$. We are allowed to perform the below operations:

• Encrypt encrypts a random 32-byte message $m$ with the key $k$ into ciphertext $c$. However, if $c_i = k_i$ for some $i$, then the ciphertext will not be printed.
• Decrypt takes a ciphertext $c$ and a key $k'$. $c$ will be decrypted with the $k'$. If the plaintext contains FwordCTF, the flag will be printed.

Boombastic⌗

• Solves: 55/429
• Difficulty: ⭐
• Tags: math

Upon connecting to the server, a 1024-bit prime $p$ and a secret $x\in [1, p)$ is generated. A ticket for code $c$ is generated by compute $y = \text{SHA256}(c)$, and

\[r = \frac{y^2 - 1}{x^2}\ \text{mod}\ p\qquad\text{and}\qquad s = \frac{1 + y}{x}\ \text{mod}\ p.\]

The ticket for code $c$ is given by $(s, r, p)$. Suppose that we are able to make tickets for random code $c$ that we could not control. The objective is to generate a ticket for code Boombastic.

Invincible⌗

• Solves: 29/429
• Difficulty: ⭐⭐
• Tags: ecc, prng

The service implements Dual_EC_DBRG as a PRNG where we are able to send $P$ (where $P \neq O$) and they pick a $Q$ and a seed. There are 100 challenges afterwards. An AES-key is derived from the PRNG output and a random IV and message is generated (with os.urandom), and we are given the IV and ciphertext. The objective is to decrypt and recover the message for each of the challenges.

Login⌗

• Solves: 11/429
• Difficulty: ⭐⭐
• Tags: rsa

We are given the RSA parameters $e, d$ and $p^{-1}\ \text{mod}\ q$. The objective is to sign a given message using the recovered RSA key.

Transfer 🔥⌗

• Solves: 6/429
• Difficulty: ⭐⭐⭐
• Tags: ed25519

When connected to the server, an ed25519 signing key is generated. We are allowed perform the below operations:

• Transfer asks us to provide $m$ which is shorter than 256 bytes. It returns a signed $m$.
• Verify asks us to provide a message $m$ and its corresponding signature $s$. It returns the flag if $s$ is a valid signature of $m$, and $m$ is at least than 256 bytes.

The objective is to successfully provide a pair of $(m, s)$ for the verify command. Additionally, the sign and verify functions used are excerpted below.

# Variables:
# - sk is the secret key
# - pk is the public key.
#
# Functions:
# - H(m: bytes) -> bytes
#   returns the SHA512 digest of m
# - Hint(m: bytes) -> int
#   returns the SHA512 digest (in integer) of m

def sign(m, sk, pk):
  m = long_to_bytes(m)
  h = H(sk)
  a = bytes_to_long(h[:32]) % l
  r = Hint(h[32:] + hmac.new(m, h, digestmod=hashlib.sha512).digest())
  R = mult(B, r)
  S = (r + Hint(point_to_bytes(R) + pk + m) * a) % l
  return point_to_bytes(R) + long_to_bytes(S)

def verify(s, m, pk):
  m = long_to_bytes(m)  
  R = bytes_to_point(s[:32])  
  A = bytes_to_point(pk)  
  S = bytes_to_long(s[32:]) 
  h = Hint(point_to_bytes(R) + pk + m) 
  r1 = mult(B, S)  
  r2 = add(R, mult(A, h)) 
  return r1 == r2

Procyon 🔥⌗

• Solves: 4/429
• Difficulty: ⭐⭐⭐
• Tags: dh

When connected to the server, a 1024-bit prime $p$ is generated and $g = 3$. Alice and Bob will be generating their corresponding Diffie-Hellman secrets, namely, $x$ and $y$. The shared secret, defined by $g^{xy}\ \text{mod}\ p$, is used to encrypt the flag via the below function (hereby $s$ is the shared secret and $t$ is the timestamp in seconds):

\[\text{Enc}_s(m) = t\cdot s + (m \cdot s\ \text{mod}\ p).\]

We are given the flag encrypted with the shared secret. We are also able to forge Alice's public key and obtain $\text{Enc}_{s'}(m')$ where $s'$ is the forged shared secret and $m'$ is a random 512-bit message. The objective is to recover the flag.

ALLES! CTF 2021⌗

Secure Flag Service⌗

• Solves: 46/523
• Difficulty: ⭐
• Tags: ctr

Suppose that there is a master password $\mathcal{P}$ which derives the encryption key $k_\mathcal{E}$ and the MAC key $k_\mathcal{M}$. A message $m$ is encrypted by the function $\text{Encrypt}(m)$ by:

\[\text{Encrypt}(m) = \nu\ \|\ \text{AESCTR}_{k_\mathcal{E}}\left(\text{Encode}\left(m\ \|\ \text{MAC}_{k_\mathcal{M}}\left(m\right)\right), \text{nonce}=\nu\right).\]

Remarkably, $\text{Encode}$ is a function that encode a $n$-bit message into a $2n$-bit message. Each 0 bit will be encoded into 00 and otherwise encoded into either 01 or 10 (picked randomly).

We are given an encrypted $\mathcal{P}$ and a oracle $\mathcal{O}$ - we are able to supply a ciphertext $c$:

• If the MAC is incorrect, it prints Get off my lawn or I call the police!!!.
• If $\text{Decrypt}(c) \neq \mathcal{P}$, it prints Wrong Password!!!.
• Otherwise it will print us an encrypted flag.

The objective is to recover the flag.

RCTF 2021⌗

Uncommon Factor I 🔥⌗

• Solves: 14/483
• Difficulty: ⭐⭐⭐
• Tags: factor

We are given 512-bit moduli $n_1, n_2, ..., n_{2^{22}}$, where

• $p_k = x + r_k$ with $0 \leq x < 2^{176}$, $0 \leq r_k < 2^{24}$, and
• $q_k$ is a 312-bit prime.

The objective is to recover $x$.

Uncommon Factor II 🔥⌗

• Solves: 29/483
• Difficulty: ⭐⭐
• Tags: factor

We are given 512-bit moduli $n_1, n_2, ..., n_{2^7}$, where

• $p_k = x + r_k$ with $0 \leq x < 2^{208}$, $0 \leq r_k < 2^{104}$, and
• $q_k$ is a 200-bit prime.

The objective is to recover $x$.

CSAW'21 CTF⌗

forgery⌗

• Solves: 127/1216
• Difficulty: ⭐⭐
• Tags: dsa

We are given a set of parameters for digital signature algorithm: the modulus $p$, a generator $g$ and a public key $y$. The objective is to find a triple $(m, r, s)$. Denote $m' = m\ \text{mod}\ 2^{1024}$, the triple needs to satisfy:

1. $m$ is a message that contains Felicity, Cisco or both,
2. $0 < m' < p-1$ and $0 < r, s < p - 1$, and
3. $g^m \equiv y^rr^s\ (\text{mod}\ p)$.

Bits 🔥⌗

• Solves: 24/1216
• Difficulty: ⭐⭐⭐
• Tags: discrete log

When connected to the server, we are given $n$, $g = 2$ and $y_i$ (where $y_i \equiv g^{x_i}\ (\text{mod}\ n)$ for some integers $x_i$) for $i = 1, 2$. It is also known that the order for $g$ modulo $n$ is of $m$ bits.

We have an oracle $\mathcal{O}(y)$ which finds the $x \in [0, q)$ such that $g^x \equiv y \ (\text{mod}\ n)$ and returns

• -1 if such $x$ does not exist,
• 1 if $x \wedge 2^{m - 123} \neq 0$, or
• 0 otherwise.

We are also given a flag encrypted with a shared secret derived by $g^{x_1x_2}\ \text{mod}\ n$. The objective is to decrypt the flag.

ACSC 2021⌗

RSA stream⌗

• Solves: 121/483
• Difficulty: -
• Tags: rsa

We are given a modulus for RSA $n$ and three public exponents $e_1$, $e_2$ and $e_3$. Let $m$ be the flag and $k_i = m^{e_i}\ \text{mod}\ n$.

The $k_i$'s are used as a bitstream of stream cipher, i.e., $C_i = M_i \oplus k_i$ for message $M_i$ and ciphertext $C_i$. We are also given $(M_1, C_1)$, $(M_2, C_2)$ and $(M_3, C_3)$. The goal is to recover the flag $m$.

CBCBC⌗

• Solves: 35/483
• Difficulty: ⭐⭐
• Tags: cbc, padding oracle

Let $\mathcal{K}$ be a key and $\mathcal{IV}_1, \mathcal{IV}_2$ be two IVs. Define the encryption function $\mathcal{E}$ by:

\[\mathcal{E}(m) = \text{AES-CBC}_{\mathcal{K}, \mathcal{IV}_2}\left(\text{AES-CBC}_{\mathcal{K}, \mathcal{IV}_1}\left(m\right)\right)\]

When connected to the server, an AES key $\mathcal{K}$ and two IVs $\mathcal{IV}_1, \mathcal{IV}_2$ are generated. There are two functions provided from the server:

1. Create user requests for a username $n$ and a corresponding token $t$, defined below, is returned.

   \[t := \mathcal{E}(\text{\{``username":}\ n\text{, ``is\_admin": false\}})\]

   If a username is not provided, then the below token is returned (note that we do not know $n_0$):

   \[t := \mathcal{E}(\text{\{``username":}\ n_0\text{, ``is\_admin": true\}})\]

2. Login requests a username $n$ and a token $t$ and performs the below routine:

   • Decrypts $t$ and unpad. Returns Failed to login! Check your token again if an exception is caught (for example, the ciphertext size is not a multiple of 16, the padding is invalid, etc).
   • Parses the JSON object. Returns Failed to login! Your token is malformed if an exception is caught.
   • Gets the username and compares with $n$. Returns Failed to login! Check your username again if the values do not match.

The objective is to login as an admin, i.e., is_admin is truthy.

Secret Saver⌗

• Solves: 12/483
• Difficulty: ⭐⭐
• Tags: compression oracle, crime

We are given a PHP service with the below source code:

 <?php
    include "config.php";

    $msg  = $_POST['msg'] ?? "";
    $name = $_POST['name'] ?? "";
    if ( strlen($name) < 4 || strlen($msg) < 8 )
        highlight_file(__FILE__) && exit();

    $data = array(
        "name" => $name, 
        "msg"  => $msg, 
        "flag" => "ACSC{" . $KEY . "}" // try to get this flag!
    );

    $iv   = openssl_random_pseudo_bytes(16);
    $data = gzcompress(json_encode($data));
    $data = openssl_encrypt($data, 'aes-256-ctr', $KEY, OPENSSL_RAW_DATA, $iv);
    $data = bin2hex( $iv . $data );

    $conn = new mysqli($HOST, $USER, $PASS, $NAME);
    $sql  = sprintf("insert into msgs (msg, name) values('%s', '%s')", $data, $name);
    if (!$conn->query($sql))
        die($conn->error);
    
    echo $conn->insert_id;
    $conn->close(); 

In short, when we provide the service message and name, a JSON object with fields message, name and flag is created. It is compressed with ZLIB and encrypted with AES-CTR. The end result is stored into the database (note that there is a SQLi issue which allows one to retrieve the length of the ciphertext). The goal is to recover the flag.

Swap on Curve⌗

• Solves: 34/483
• Difficulty: ⭐
• Tags: ecc

We are given an elliptic curve $y^2 = x^3 + ax + b\ (\text{mod}\ p)$. Let $x_0$ be the flag and it is known that both $(x_0, y_0)$ and $(y_0, x_0)$ lies on the curve. The objective is to recover the flag.

Wonderful Hash 🔥⌗

• Solves: 11/483
• Difficulty: ⭐⭐
• Tags: hash

Define a hash algorithm $\mathcal{H}$ for messages $m_1 m_2 ... m_k$ (where $m_i$ is a 16-byte message block) as $h(m_1) \oplus h(m_2) \oplus ... \oplus h(m_k)$, where $h(m)$ is defined by the below procedure:

1. Let $x_1 = \text{AES}_m(00...00)$ ($x_1$ is the ciphertext of 16 null bytes with key $m$).
2. Let $x_2 = \text{ARC4}_{x_1}(00...00)$ ($x_2$ is the ciphertext of 8 null bytes with key $x_1$).
3. Let $x_3 = \text{DES}_{x_2}(00...00)$ ($x_3$ is the ciphertext of 8 null bytes with key $x_2$).
4. $h(m)$ is the first six bytes of $x_3$.

When connected to the server, a default command $\mathcal{C}_0$ (of 417 bytes) is deployed. We can execute arbitrary commands $\mathcal{C}$ that satisfies the below conditions:

1. $\text{len}(\mathcal{C}) = \text{len}(\mathcal{C}_0)$,
2. $\mathcal{H}(\mathcal{C}) = \mathcal{H}(\mathcal{C}_0)$, and
3. each of the characters of $\mathcal{C}$ is ASCII-printable.

The flag is in /flag. The objective is to print the content of the file.

Two Rabin 🔥⌗

• Solves: 20/483
• Difficulty: ⭐⭐⭐
• Tags: rabin signature

There are two stages in the challenge. They share the same set of parameters: 1024-bit modulus $n = pq$ and 512-bit $B$. The flag is broken into two parts and each part is 98 bytes long. Denote the Rabin's signature $\mathcal{S}$ for signature $m$ being:

\[\mathcal{S}(m) = m(m + B)\ \text{mod}\ n.\]

• The first half of the flag $m_1$ is padded to 128 bytes with PKCS5, into $m_2$. We are given $c_1 = \mathcal{S}(m_1)$ and $c_2 = \mathcal{S}(m_2)$.
• The second half of the flag $M$ is padded into 128 bytes by $m_i = 256^{30}M + r_i$ where $r_i \in [0, 256^{30})$. We are given $c_1 = \mathcal{S}(m_1)$ and $c_2 = \mathcal{S}(m_2)$.

The objective is to recover the whole flag.

Share the flag 🔥⌗

• Solves: 1/483
• Difficulty: ⭐⭐⭐
• Tags: linear system

We are given $(x_1, y_1), (x_2, y_2), ..., (x_{15}, y_{15})$ when connected to the server, where

\[y_k = \sum_{i=0}^{31} c_i x_k^i\ \text{mod}\ p.\]

Hereby $p = 251$, $x \in [1, p)$ and $c_i$ are the ASCII values of printable characters. Note that $c_0, c_1, ..., c_{15}$ are unchanged every time and $c_{16}, c_{17}, ..., c_{31}$ will be changed each time. Additionally, $97 \leq c_{16}, c_{17}, ..., c_{31} < 123$ (i.e., they are lowercase alphabet). The objective is to recover $c_0, c_1, ..., c_{15}$, which is the flag.