DiceCTF 2021 had an assortment of challenges and most of them are tough. Although the five crypto challenges which looked unoriginal, I was only able to solve garbled during the contest and I liked the challenges very much. After the CTF, I have found writeups from various sources and learnt a lot. In this writeup, only plagiarism and benaloh will be covered. However, I haven't look at the remaining questions yet, and they are definitely on my to-do list.

I may or may not have a part two for the remaining problems in the game, depending on my schedule and my laziness.


Challenge Summary

Seven teams ended up solving it during the contest period.

This challenge is highly referenced (or, copied) from decrypt message in RuCTF Quals 2014. In short, we are given a RSA public key: a 2048-bit $n$, $e = 1048577$ and two ciphertexts $c_1$ and $c_2$ of two related messages: $m_1 = m\ ||\ \text{``Blex''}$ and $m_2 = m\ ||\ \text{``Kane''}$. The objective is to recover $m$.


I wasn't even playing CTFs in 2014 back then. However, I recalled that 2019rearrange in TetCTF 2020 had a similar idea. Suppose that we are given $e_1, e_2, u_1, u_2, c_1, c_2$ and $n$ and we are going to find $m$ satisfying $c_i \equiv (m + u_i)^{e_i}\ (\text{mod}\ n)$ for $i = 1, 2$.

The idea is rather straight forward: If we define two polynomials $p_1, p_2$ over $\mathbb{Z}_n[x]$

\[p_i(x) := (x + u_i)^{e_i} - c_i,\]

then $p_1(m) = p_2(m) = 0$. In particular, $x - m$ will be a common factor of $p_1(x)$ and $p_2(x)$. For small $e$'s, we can use Euclidean algorithm to compute GCD of polynomials. The time complexity would be $\mathcal{O}(e^2)$.

Euclidean algorithm is too slow. The degree is reduced by 40K after 2 days.

Well, @RBTree_ said that he is able to use Euclidean algorithm to solve the challenge. His solution takes 36 hours on a 144-core machine...

$. Captured from Cryptohack Discord server.

After the CTF, I learned that the existence of a faster algorithm1 that computes GCD in $\mathcal{O}(e\log^2e)$. It is easy to implement in Sage, and I can compute the GCD in 100 minutes (for $e = 1048577$ and 2048-bit $n$).



Challenge Summary

Five teams ended up solving it during the contest period.

This challenge is based on Benaloh cryptosystem with $r = 17$ and a predictable random $u$ used for encryption.


This writeup is referenced from defund's writeup.

Part I: Background - Benaloh cryptosystem

For anyone (including me) who is not familiar with Benaloh cryptosystem, I'll write down how the keys are generated and messages are encrypted.

Key generation

Suppose that the block size is $r$, i.e., each message block is a value in $[0, r)$.

  1. Pick primes $p = rp' + 1$ and $q$ such that $\gcd(p', r) = \gcd(q - 1, r) = 1$.
  2. Compute $n = pq$ and $\varphi(n) = (p-1)(q-1)$.
  3. Pick $0 \leq y < n$ with $y^{\varphi(n)/r} \not\equiv 1\ (\text{mod}\ n)$.
  4. Compute $x = y^{\varphi(n)/r}\ \text{mod}\ n$.

The public key is $(y, n)$ and the private key is $(\varphi, x)$.

Message encryption

Suppose that we want to encrypt a message $0 \leq m < r$.

  1. Pick a random $0 \leq u < n$.
  2. Compute $c = y^mu^r\ \text{mod}\ n$.

The ciphertext for $m$ is $c$.

Part II: What makes this challenge vulnerable

The flag is broken down into 34 blocks $m_1, m_2, ..., m_{34} \in [0, 16)$, where $m_{2k-1}$ and $m_{2k}$ are derived from the $k$-th byte. We are given 34 ciphertext blocks $c_1, c_2, ..., c_{34}$. In particular, the $u$ used for the $k$-th block (denoted as $u_k$) is predictable. They are generated by a LCG and defined as $u_{k+1} = (au_k + c)\ \text{mod}\ n$ for some constants $a, c$ and $u_1 := u$. Hence,

\[c_k = y^{m_k}\left[a^ku + c(a^{k-1} + a^{k-2} + ... + 1)\right]^{17}\ \text{mod}\ n.\]

Moreover, knowing the prefix of the flag being dice{, we know $m_1, m_2, ..., m_{10}$. Hence, for $k = 1, 2, ..., 10$, we have

\[v_k := \frac{c_k}{y^{m_k}}\ \text{mod}\ n.\]

Part III: What is Gröbner basis?

With the following ten congruences, is it possible to recover $a, c$ and $u$ for the LCG?

\[ \begin{cases}\begin{aligned} v_1 &\equiv u^{17} \\ v_2 &\equiv (au + c)^{17} \\ v_3 &\equiv \left[a^2u + c(a + 1)\right]^{17} \\ ... \\ v_{10} &\equiv \left[a^9u + c(a^8 + ... + a + 1)\right]^{17} \end{aligned}\end{cases}\ (\text{mod}\ n). \]

From defund's writeup, it is described that Gröbner basis is the tool we need. I searched a bit and found a YouTube video talking about it.

Suppose that we have a set of polynomials $p_1(x), p_2(x), ..., p_s(x)$ over $\mathbb{F}^k$. Let's assume that $\alpha_1, \alpha_2, ...$ are the common roots of $p_i(x) = 0$, i.e., $p_i(\alpha_k) = 0$ for all $i = 1, 2, ..., s$.

In our case, $p_i: {\mathbb{Z}_n}^3 \rightarrow \mathbb{Z}_n$ is $p_i(x, y, z) := \left[x^iz + y(x^{i-1} + … + x + 1)\right]^{17} - v_i$. Also, $(a, c, u)$ is a common root of $p_i(x, y, z) = 0$ for all $i = 1, 2, …, 10$.

In short, Gröbner basis consists of a set of polynomials with the same common roots. Remarkably, the polynomials usually have smaller degrees.

There are more references2 those I have not looked into.

Part IV: Computing a Gröbner basis

I am able to compute a Gröbner basis with two minutes on my PC with the following code excerpt.

n, y = ...
cs = ...

Zn = Zmod(n)
P.<a, c, u> = PolynomialRing(Zn)

#     d___  i___  c___  e___  {____
ms = [6, 4, 6, 9, 6, 3, 6, 5, 7, 11]
vs = [c * pow(y, -m, n) % n for m, c in zip(ms, cs)]

I = ideal([
    (a^i * u + c * ((a^i - 1) // (a - 1)))^17 - vs[i]
    for i in range(10)

B = I.groebner_basis()
# [ u^17 + 639...272, a + 166...006, c + 275...023*u ]
Note: I am able to obtain the same basis with the same amount of time, given only four vectors instead of ten.

We know $u^{17}$, $a$ and $\frac{c}{u}$ from the basis. It is sufficient for us to decrypt the flag, since everything on the right hand side below are known.

\[y^{-m_k} = {c_k}^{-1}{u^{17}\left[a^k + \frac{c}{u}(a^{k-1} + a^{k-2} + ... + 1)\right]^{17}}\ \text{mod}\ n.\]