CTF Challenge Name Solves (Difficulty)
TSG CTF 2021 Beginner's Crypto 2021 126/775 (⭐)
TSG CTF 2021 Minimalist's Private 49/775 (⭐⭐)
TSG CTF 2021 Baba is Flag 34/775 (⭐⭐)
TSG CTF 2021 Flag is Win 10/775 (⭐⭐⭐)
TSG CTF 2021 This is DSA 9/775 (⭐⭐)
TastelessCTF 2021 crybaby 🔥 14/162 (⭐⭐⭐)
pbctf 2021 Alkaloid Stream 132/210 (⭐⭐)
pbctf 2021 Steroid Stream 38/210 (⭐⭐)
pbctf 2021 GoodHash 🔥 30/210 (⭐⭐⭐)
pbctf 2021 Seed Me 🔥 24/210 (⭐⭐⭐)
pbctf 2021 Yet Another PRNG 🔥 14/210 (⭐⭐⭐)
pbctf 2021 Yet Another RSA 🔥 12/210 (⭐⭐⭐)

## TSG CTF 2021⌗

### Beginner's Crypto 2021⌗

• Solves: 126/775
• Difficulty: ⭐
• Tags: rsa

We are given $p$ and $q$, the primes for RSA. Denote $n = pq$. We are also given the flag $c_1, c_2, c_3$ encrypted with the same modulus but different exponents. Those exponents, $e_1, e_2, e_3$, are computed by

\begin{aligned} & e_1 = e^{65537}\ \text{mod}\ \varphi(n) \\ & e_2 = (e + 2)^{65537}\ \text{mod}\ \varphi(n) \\ & e_3 = (e + 4)^{65537}\ \text{mod}\ \varphi(n) \end{aligned}

Note that $e$, $e+2$ and $e+4$ are all primes. The objective is to recover the flag.

### Minimalist's Private⌗

• Solves: 49/775
• Difficulty: ⭐⭐
• Tags: rsa

We are given a RSA public key $(n, e)$ and a ciphertext $c$. Additionally, $\lambda(n)$ (the order of $\mathbb{Z}^*_n$) satisfies

$\lambda(n)^2 \leq 10000n.$

The objective is to decrypt $c$ for the flag.

### Baba is Flag⌗

• Solves: 34/775
• Difficulty: ⭐⭐
• Tags: ecdsa

When connected to the server, a ECDSA private key $d$ for SECP256k1 is generated. We are allowed to perform the below operations in a total of five times:

1. [Sign] We will be given a signature of Baba. The ECDSA is slightly modified (will be described below) and the nonce $k$ is around 80 bits.
2. [Find rule] We will be asked to send a message $m$ and the signature $(r, s)$. It would return the flag if we have a valid signature for message Flag.

For ECDSA, $s = k^{-1} (z + rd_A)\ \text{mod}\ n$. However in this challenge, $s$ is computed by

$k^{-1} (z + d_A)\ \text{mod}\ n.$

The objective is to forge a signature for the message Flag.

### Flag is Win⌗

• Solves: 10/775
• Difficulty: ⭐⭐⭐
• Tags: ecdsa

When connected to the server, a ECDSA private key $d$ for SECP256k1 is generated. We are allowed to perform the below operations in a total of five times:

1. [Sign] We will be given a signature of Baba. The nonce $k$ is around 80 bits.
2. [Find rule] We will be asked to send a message $m$ and the signature $(r, s)$. It would return the flag if we have a valid signature for message Flag.

The objective is to forge a signature for the message Flag.

### This is DSA⌗

• Solves: 9/775
• Difficulty: ⭐⭐
• Tags: dsa

The challenge uses a modified pycryptodome package with the below code difference:

When connected to the server, we are given a 256-bit order $q$ and is asked a 2048-bit $p$ and $h$. The generator $g$ is computed by

$g = h^{\lfloor{(p-1)/q\rfloor}}\ \text{mod}\ p.$

Also, a private key $x \in [0, q)$ is generated and the public key $y$ is given by

$y = g^x\ \text{mod}\ p.$

We will be given $g$ and $y$. The goal is to craft a signature of flag in 15 seconds.

## TastelessCTF 2021⌗

### crybaby 🔥⌗

• Solves: 14/162
• Difficulty: ⭐⭐⭐
• Tags: gcm

When connected to the server, a 16-byte AES key $\mathcal{K}$ is generated. There are two stages and during the $k$-th stage, we are given the $k$-th oracle $\mathcal{O}_k$. We are able to call the oracles as much as we could (unless an exception is thrown).

• $\mathcal{O}_1$ uses AES-CTR and it asks for nonce $\mu$ and ciphertext $c$. It returns

$\text{Encrypt}_\mathcal{K}(\mu, \text{Login successful!})$

and proceed to the next stage if $\text{Decrypt}_\mathcal{K}(\mu, c)$ is equal to adminplz, and otherwise

$\text{Encrypt}_\mathcal{K}(\mu, \text{Unknown command!}).$

• $\mathcal{O}_2$ uses AES-GCM and it asks for nonce $\mu$ and ciphertext $c$. It returns

$\text{Encrypt}_\mathcal{K}(\mu, \mathcal{F})$

if $\text{Decrypt}_\mathcal{K}(\mu, c)$ is equal to flagplz, and otherwise

$\text{Encrypt}_\mathcal{K}(\mu, \text{Unknown command!}).$

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

## pbctf 2021⌗

### Alkaloid Stream⌗

• Solves: 132/210
• Difficulty: ⭐⭐
• Tags: math

Suppose that the flag is $m$ bits long ($m = 600$ in this challenge). Initially, an invertible $m\times m$ matrix in $\text{GF}(2)$ (denote by $\mathcal{K}$) is generated and is interpreted as $m$ $m$-bit integers, 0 <= key[0], key[1], ..., key[m-1] < 2^m. A keystream and a public key is generated from the key by the function gen_keystream, defined below:

def gen_keystream(key):
ln = len(key)

# Generate some fake values based on the given key...
fake = [0] * ln
for i in range(ln):
for j in range(ln // 3):
if i + j + 1 >= ln:
break
fake[i] ^= key[i + j + 1]

# Generate the keystream
res = []
for i in range(ln):
t = random.getrandbits(1)
if t:
res.append((t, [fake[i], key[i]]))
else:
res.append((t, [key[i], fake[i]]))

for r in res:
print(r)

# Shuffle!
random.shuffle(res)

keystream = [v[0] for v in res]
public = [v[1] for v in res]
return keystream, public

We are given a public key and the flag xorred with the keystream. The objective is to recover the flag.

### Steroid Stream⌗

• Solves: 38/210
• Difficulty: ⭐⭐
• Tags: math

The challenge is similar to Alkaloid Stream, except that $m = 616$ and gen_keystream is defined below:

  def gen_keystream(key):
ln = len(key)
+     assert ln > 50

# Generate some fake values based on the given key...
fake = [0] * ln
-     for i in range(ln):
-         for j in range(ln // 3):
-             if i + j + 1 >= ln:
-                 break
-             fake[i] ^= key[i + j + 1]
+     for i in range(ln - ln // 3):
+         arr = list(range(i + 1, ln))
+         random.shuffle(arr)
+         for j in arr[:ln // 3]:
+             fake[i] ^= key[j]

# Generate the keystream
res = []
for i in range(ln):
t = random.getrandbits(1)
if t:
res.append((t, [fake[i], key[i]]))
else:
res.append((t, [key[i], fake[i]]))

# Shuffle!
random.shuffle(res)

keystream = [v[0] for v in res]
public = [v[1] for v in res]
return keystream, public

### GoodHash 🔥⌗

• Solves: 30/210
• Difficulty: ⭐⭐⭐
• Tags: gcm

The digest for the hash algorithm GoodHash for the message $m$ is given by encrypting 32 null bytes with a known key goodhashGOODHASH with the nonce $m$. It is 48 bytes long, which composes of a 32-byte ciphertext and a 16-byte tag.

We are given a token {"token": "32 hex characters", "admin": false} when connected to the server, along with its corresponding hash $h_0$. The goal is to craft a JSON token token such that token['admin'] equals true, which also has the hash $h_0$.

### Seed Me 🔥⌗

• Solves: 24/210
• Difficulty: ⭐⭐⭐
• Tags: prng, lcg

We are asked a seed for the Java program. the random instance, rng, is defined by rng = new Random(seed). We will get the flag if the 2048-, 4096-, ..., 32768-th output from rng.NextFloat() are never less than $0.9801547$.

### Yet Another PRNG 🔥⌗

• Solves: 14/210
• Difficulty: ⭐⭐⭐
• Tags: prng

The outputs $r_0, r_1, r_2, ... \in [0, 2^{64})$ of the PRNG in the challenge is defined below:

$r_k := 2m_1x_k - m_3y_k - m_2z_k\ \text{mod}\ M,$

where $m_1, m_2, m_3$ are 32-bits and $M$ is a 64-bit known constants. Also, let $a_{ij}$ be 20-bit known constants and for $k \leq 3$,

\begin{cases}\begin{aligned} x_k &:= a_{11} x_{k-3} + a_{12} x_{k-2} + a_{13} x_{k-1} \\ y_k &:= a_{21} y_{k-3} + a_{22} y_{k-2} + a_{23} y_{k-1} \\ z_k &:= a_{31} z_{k-3} + a_{32} z_{k-2} + a_{33} z_{k-1} \end{aligned}\end{cases}.

Note that we are not given $x_k, y_k, z_k$ for $k = 0, 1, 2$. Suppose that we have $r_0, r_1, ..., r_{11}$, and the flag is xor-ed with $r_{12}, r_{13}, ...$. The objective is to recover the flag.

### Yet Another RSA 🔥⌗

• Solves: 12/210
• Difficulty: ⭐⭐⭐
• Tags: rsa

We are given a RSA public key $n, e$ and an encrypted flag $c$. Hereby $n$ is 1024-bit number which is a product of two 512-bit primes $p, q$ (they are both in the form of $a^2 + 3b^2$). It is also known that $d$ is 400-bit long.

Remarkably, the multiply operation is performed under a group $\mathcal{G}$ with

$\mathcal{G} = \mathbb{Z}_n^2 \cup (\mathbb{Z}_n\times\{\varepsilon\}) \cup \{\varepsilon\}^2.$

Also $|\mathcal{G}| = (p^2+p+1)(q^2+q+1)$. The objective is to recover the flag from $c$.

# Note: The challenge used add but I think it would be better to call it multiply.
def multiply(P, Q, mod):
m, n = P
p, q = Q

if p is None:
return P
if m is None:
return Q

if n is None and q is None:
x = m * p % mod
y = m + p % mod
return (x, y)

if n is None and q is not None:
m, n, p, q = p, q, m, n

if q is None:
if (n + p) % mod != 0:
x = (m * p + 2) * inverse(n + p, mod) % mod
y = (m + n * p) * inverse(n + p, mod) % mod
return (x, y)
elif (m - n ** 2) % mod != 0:
x = (m * p + 2) * inverse(m - n ** 2, mod) % mod
return (x, None)
else:
return (None, None)
else:
if (m + p + n * q) % mod != 0:
x = (m * p + (n + q) * 2) * inverse(m + p + n * q, mod) % mod
y = (n * p + m * q + 2) * inverse(m + p + n * q, mod) % mod
return (x, y)
elif (n * p + m * q + 2) % mod != 0:
x = (m * p + (n + q) * 2) * inverse(n * p + m * q + r, mod) % mod
return (x, None)
else:
return (None, None)