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.

## plagiarism⌗

### 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$.

### Solution⌗

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$). dice{Any_sufficiently_advanced_CTF_challenge_is_indistinguishable_from_computational_number_theory} ## benaloh⌗ ### 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. ### Solution⌗ 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$ufor 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 polynomialsp_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.$

dice{gr:obner!_!}