DiceCTF 2022 (I): commitment-issues

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.

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
N = 0xba8cb3257c0c83edf4f56f5b7e139d3d6ac8adf71618b5f16a02d61b63426c2c275ce631a0927b2725c6cc7bdbe30cd8a8494bc7c7f6601bcee5d005b86016e79919e22da4c431cec16be1ee72c056723fbbec1543c70bff8042630c5a9c23f390e2221bed075be6a6ac71ad89a3905f6c706b4fb6605c08f154ff8b8e28445a7be24cb184cb0f648db5c70dc3581419b165414395ae4282285c04d6a00a0ce8c06a678181c3a3c37b426824a5a5528ee532bdd90f1f28b7ec65e6658cb463e867eb5280bda80cbdb066cbdb4019a6a2305a03fd29825158ce32487651d9bfa675f2a6b31b7d05e7bd74d0f366cbfb0eb711a57e56e6db6d6f1969d52bf1b27b
c1 = 0x75240fcc256f1e2fc347f75bba11a271514dd6c4e58814e1cb20913195db3bd0440c2ca47a72efee41b0f9a2674f6f46a335fd7e54ba8cd1625daeaaaa45cc9550c566f6f302b7c4c3a4694c0f5bb05cd461b5ca9017f2eb0e5f60fb0c65e0a67f3a1674d74990fd594de692951d4eed32eac543f193b70777b14e86cf8fa1927fe27535e727613f9e4cd00acb8fab336894caa43ad40a99b222236afc219397620ca766cef2fe47d53b07e302410063eae3d0bf0a9d67793237281e0bfdd48255b58b2c1f8674a21754cf62fab0ba56557fa276241ce99140473483f3e5772fcb75b206b3e7dfb756005cec2c19a3cb7fa17a4d17f5edd10a8673607047a0d1
c2 = 0xdb8f645b98f71b93f248442cfc871f9410be7efee5cff548f2626d12a81ee58c1a65096a042db31a051904d7746a56147cc02958480f3b5d5234b738a1fb01dc8bf1dffad7f045cac803fa44f51cbf8abc74a17ee3d0b9ed59c844a23274345c16ba56d43f17d16d303bb1541ee1c15b9c984708a4a002d10188ccc5829940dd7f76107760550fac5c8ab532ff9f034f4fc6aab5ecc15d5512a84288d6fbe4b2d58ab6e326500c046580420d0a1b474deca052ebd93aaa2ef972aceba7e6fa75b3234463a68db78fff85c3a1673881dcb7452390a538dfa92e7ff61f57edf48662991b8dd251c0474b59c6f73d4a23fe9191ac8e52c8c409cf4902eeaa71714

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.

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

N = 0xba8cb3257c0c83edf4f56f5b7e139d3d6ac8adf71618b5f16a02d61b63426c2c275ce631a0927b2725c6cc7bdbe30cd8a8494bc7c7f6601bcee5d005b86016e79919e22da4c431cec16be1ee72c056723fbbec1543c70bff8042630c5a9c23f390e2221bed075be6a6ac71ad89a3905f6c706b4fb6605c08f154ff8b8e28445a7be24cb184cb0f648db5c70dc3581419b165414395ae4282285c04d6a00a0ce8c06a678181c3a3c37b426824a5a5528ee532bdd90f1f28b7ec65e6658cb463e867eb5280bda80cbdb066cbdb4019a6a2305a03fd29825158ce32487651d9bfa675f2a6b31b7d05e7bd74d0f366cbfb0eb711a57e56e6db6d6f1969d52bf1b27b
c1 = 0x75240fcc256f1e2fc347f75bba11a271514dd6c4e58814e1cb20913195db3bd0440c2ca47a72efee41b0f9a2674f6f46a335fd7e54ba8cd1625daeaaaa45cc9550c566f6f302b7c4c3a4694c0f5bb05cd461b5ca9017f2eb0e5f60fb0c65e0a67f3a1674d74990fd594de692951d4eed32eac543f193b70777b14e86cf8fa1927fe27535e727613f9e4cd00acb8fab336894caa43ad40a99b222236afc219397620ca766cef2fe47d53b07e302410063eae3d0bf0a9d67793237281e0bfdd48255b58b2c1f8674a21754cf62fab0ba56557fa276241ce99140473483f3e5772fcb75b206b3e7dfb756005cec2c19a3cb7fa17a4d17f5edd10a8673607047a0d1
c2 = 0xdb8f645b98f71b93f248442cfc871f9410be7efee5cff548f2626d12a81ee58c1a65096a042db31a051904d7746a56147cc02958480f3b5d5234b738a1fb01dc8bf1dffad7f045cac803fa44f51cbf8abc74a17ee3d0b9ed59c844a23274345c16ba56d43f17d16d303bb1541ee1c15b9c984708a4a002d10188ccc5829940dd7f76107760550fac5c8ab532ff9f034f4fc6aab5ecc15d5512a84288d6fbe4b2d58ab6e326500c046580420d0a1b474deca052ebd93aaa2ef972aceba7e6fa75b3234463a68db78fff85c3a1673881dcb7452390a538dfa92e7ff61f57edf48662991b8dd251c0474b59c6f73d4a23fe9191ac8e52c8c409cf4902eeaa71714


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

p = (c1 - s)^5 - c2

p /= p.leading_coefficient()
_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'))