# Crypto in CTF: Q4 2021

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:

**[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.**[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:

**[Sign]**We will be given a signature of`Baba`

. The nonce $k$ is around 80 bits.**[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)
```