DiceCTF is an annual CTF competition prepared by @dicegangctf. The challenges are great and we had a lot of fun solving them. I might be compiling writeup for a number of them, which depends if I had time.

Deja vu? I said similar things last year. Until now, part 2 of my writeup series on DiceCTF 2021 does not exist.

I will first cover on a crypto challenge called commitment-issues, which had 16 solves (out of 1127 participating teams). @grhkm2023 and I spent a good 3 to 4 hours working on this challenge.

## Challenge Summary⌗

Define a commitment scheme $\mathcal{C}$ that uses a composite modulus $n$ (which is a product of two 1024-bit primes $p, q$ with $p, q \neq 1\ (\text{mod}\ 5)$). To commit a secret $s$:

1. Generate a random number $r \in [0, n)$,
2. Compute $c_1 := (s + r)\ \text{mod}\ n$ and $c_2 := r^5\ \text{mod}\ n$, and
3. Return $(c_1, c_2)$ as the commitment.

Suppose that $s$ is the RSA signature of the flag (i.e., $m^d\ \text{mod}\ n$, the $m$ is the flag and $n$ serves as the modulus for $\mathcal{C}$ as well). We are given the public key of RSA $(n, e)$ and a commitment $\mathcal{C}(s) = (c_1, c_2)$. The objective is to recover the flag $m$ (flag format being dice{???????????????????????}).

e = 0xd4088c345ced64cbbf8444321ef2af8b

## Solution⌗

We will first write the flag $m$ with $m = m_0 + 256 \cdot x$, where $m_0$ represents the known part (i.e., dice{_________________________} and each _ is a null byte) and $x$ is the unknown part.

Since $c_1 \equiv s + r\ (\text{mod}\ n)$ and $c_2 \equiv r^5\ (\text{mod}\ n)$, we can express $s^k$ in terms of $s$, $s^2$, $s^3$ and $s^4$. These are the $s^k$ for smaller values of $k$:

\begin{aligned} & c_2 \equiv r^5 \equiv (c_1 - s)^5 \equiv {c_1}^5 - 5 {c_1}^4 \cdot s + 10 {c_1}^3 \cdot s^2 - 10 {c_1}^2 \cdot s^3 + 5 {c_1} \cdot s^4 - s^5\ (\text{mod}\ n) \\ & \Longrightarrow s^5 \equiv 5 c_1 \cdot s^4 - 10 {c_1}^2 \cdot s^3 + 10 {c_1}^3 \cdot s^2 - 5 {c_1}^4 \cdot s + ({c_1}^5 - c_2)\ (\text{mod}\ n) \end{aligned}

\begin{aligned} s^6 &\equiv s \cdot \left[5 c_1 \cdot s^4 - 10 {c_1}^2 \cdot s^3 + 10 {c_1}^3 \cdot s^2 - 5 {c_1}^4 \cdot s + ({c_1}^5 - c_2)\right] \\ &\equiv 5 c_1 \cdot s^5 - 10 {c_1}^2 \cdot s^4 + 10 {c_1}^3 \cdot s^3 - 5 {c_1}^4 \cdot s^2 + ({c_1}^5 - c_2) \cdot s \\ &\equiv 5 c_1 \cdot \left[5 c_1 \cdot s^4 - 10 {c_1}^2 \cdot s^3 + 10 {c_1}^3 \cdot s^2 - 5 {c_1}^4 \cdot s + ({c_1}^5 - c_2)\right] \\ &\qquad\qquad - 10 {c_1}^2 \cdot s^4 + 10 {c_1}^3 \cdot s^3 - 5 {c_1}^4 \cdot s^2 + ({c_1}^5 - c_2) \cdot s \\ &\equiv 15 {c_1}^2 \cdot s^4 - 40 {c_1}^3 \cdot s^3 + 45 {c_1}^4 \cdot s^2 - (24 {c_1}^5 + c_2) \cdot s + 5 c_1 \cdot ({c_1}^5 - c_2)\ (\text{mod}\ n) \end{aligned}

We can effectively compute $s^n$ in terms of $s$, $s^2$, $s^3$ and $s^4$ using matrix:

$\left[\begin{matrix}s^{n+4} \\ s^{n+3} \\ s^{n+2} \\ s^{n+1} \\ s^n \end{matrix}\right] = \left[\begin{matrix} 5 c_1 & -10 {c_1}^2 & 10 {c_1}^3 & -5 {c_1}^4 & {c_1}^5 - c_2 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{matrix}\right]^n \left[\begin{matrix}s^4 \\ s^3 \\ s^2 \\ s^1 \\ 1 \end{matrix}\right]$

In particular, since $m = s^e\ \text{mod}\ n$, we have the below modular congruence:

$m \equiv A \cdot s^4 + B \cdot s^3 + C \cdot s^2 + D \cdot s + E\ (\text{mod}\ n)$

for some constants $A, B, C, D$ and $E$. Since $m = m_0 + 256 \cdot x$, we can easily write

$x \equiv A_1 \cdot s^4 + B_1 \cdot s^3 + C_1 \cdot s^2 + D_1 \cdot s + E_1\ (\text{mod}\ n), \quad [\dagger]$

for some constants $A_1, B_1, C_1, D_1$ and $E_1$ (can be computed with the matrix approach). Unfortunately, the equation has $200 + 4 \cdot 2048 = 8392$ bits of unknown while had only 2048 bits of information.

How do we deduce that $200 + 4 \cdot 2048$? Each of $s, s^2, s^3$ and $s^4$ is a 2048-bit unknown and $m$ has 200 bits of unknown (it matches the regex dice\{.{25}\}).

We can exploit the matrix to its extreme to squeeze more data. For example, we can write $x^2 \equiv A_2 \cdot s^4 + B_2 \cdot s^3 + C_2 \cdot s^2 + D_2 \cdot s + E_2\ (\text{mod}\ n)$ and that only adds 400 bits of unknown (which comes from $m^2$) when combining with $[\dagger]$. Essentially, we can add

$x^k \equiv A_k \cdot s^4 + B_k \cdot s^3 + C_k \cdot s^2 + D_k \cdot s + E_k\ (\text{mod}\ n)$

for all $k = 1, 2, ..., 10$ because the unknown size is only $200k < 2048$ bits. After all, we have $(200 + 400 + ... + 2000) + 4 \cdot 2048 = 19192$ bits of unknown and $10 \cdot 2048 = 20480$ bits of information. We can recover the information via LLL on the below matrix:

$\left[\begin{matrix} A_1 & A_2 & & A_{10} & 1 & 0 & & 0 \\ B_1 & B_2 & & B_{10} & 0 & 1 & & 0 \\ C_1 & C_2 & ... & C_{10} & 0 & 0 & \ddots & 0 \\ D_1 & D_2 & & D_{10} & 0 & 0 & & 0 \\ E_1 & E_2 & & E_{10} & 0 & 0 & & 1 \\ n & 0 & & 0 & 0 & 0 & & 0 \\ 0 & n & & 0 & 0 & 0 & & 0 \\ & & \ddots & & & & \ddots & \\ 0 & 0 & & n & 0 & 0 & & 0 \\ \end{matrix}\right]$

With that, we have the flag: dice{wh4t!!-wh0_g4ve_u-thE-k3y}.

### Solution script⌗

e = 0xd4088c345ced64cbbf8444321ef2af8b

m0 = int.from_bytes(b'dice{' + b'\0'*25 + b'}', 'big')
# m = m0 + 256*x, with 0 <= x < 2^200

Zn = Zmod(N)
P.<s> = PolynomialRing(Zn)

p = (c1 - s)^5 - c2

_e, _d, _c, _b, _a, _ = (-p).coefficients() # s^5 = _a s^4 + _b s^3 + _c s^2 + _d s + _e

A = Matrix(Zn, [
[_a, _b, _c, _d, _e],
[ 1,  0,  0,  0,  0],
[ 0,  1,  0,  0,  0],
[ 0,  0,  1,  0,  0],
[ 0,  0,  0,  1,  0],
])

b11, b12, b13, b14, b15 = map(int, (A^e)[4])

b11 = int(pow(256, -1, N) * b11)
b12 = int(pow(256, -1, N) * b12)
b13 = int(pow(256, -1, N) * b13)
b14 = int(pow(256, -1, N) * b14)
b15 = int(pow(256, -1, N) * (b15 - m0))

x = b11 * s^4 + b12 * s^3 + b13 * s^2 + b14 * s + b15

weights  = [2**(2048 - 200*k) for k in range(1, 10+1)]
weights += [2**2048, 1, 1, 1, 1]

B = Matrix(15, 15)

for j in range(10):
coefficients = (x^(j+1) % p).coefficients()

for i in range(5):
B[i, j] = coefficients[i]

B[j+5, j] = N

for i in range(5):
B[i, i+10] = 1

Q = diagonal_matrix(weights)

B *= Q
B = B.LLL()
B /= Q

for row in B:
if row[10] < 0: row = -row
if row[10] != 1: continue

x0 = int(row[0])

print(x0.to_bytes(25, 'big'))