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)