TSJ CTF 2022 (I): Cipher Switching Service

Credits. I stole the banner image from TSJ CTF. Thanks!

@blackb6a played TSJ CTF and CODEGATE CTF this weekend. Both of the CTFs had a bunch of epic (and hard-ish) crypto challenges, which made our head scratched for days.

We were two points behind @balsnctf few minutes before the game ends and I found one more flag. It is proud to tell that we won TSJ CTF 🎉!

Anyway, I will compile writeups for (at least) three challenges for TSJ CTF, namely Cipher Switching Service, Signature and Genie. I will go through Cipher Switching Service as the first part of the series.

Fun fact. I have recently moved to Taiwan and today is a public holiday (the peace memorial day) there. That said, I could spend more time playing today and win a CTF made in Taiwan. What a coincidence.

Challenge Summary⌗

When connected to the server, the below encryption keys are generated:

RSA keys $(n, e)$, here $n = pq$ ($p, q$ are both 512 bits) and $e = 65537$; and
ElGamal keys $(p, g, h = g^x\ \text{mod}\ p)$, here $p$ is 1024 bits.

We are given that the flag and the padded flag are of respectively 20 and 96 bytes. We are also given $\text{Enc}_\text{RSA}(\text{padded flag})$. We can call the below functions in a total of 1337 times:

[RSA to ElGamal] Give $c$ and we will obtain $(c_1, c_2) = \text{Enc}_\text{ElGamal}(\text{Dec}_\text{RSA}(c)))$, or
[ElGamal to RSA] Give $(c_1, c_2)$ and we will obtain $c = \text{Enc}_\text{RSA}(\text{Dec}_\text{ElGamal}(c_1, c_2)))$.

The objective is to recover $\text{flag}$.

Solution⌗

Unintended solution alert! The intended solution uses Legendre symbol. I will only cover the solution that could recover the flag in two oracle calls that I found in the contest.

Part I: The homomorphic properties for RSA and ElGamal⌗

Homomorphic property over multiplication for RSA⌗

Let $(n, e)$ be the public key of RSA. Then

\[k^e \cdot \text{Enc}(m) \equiv \text{Enc}(k \cdot m)\ (\text{mod}\ n).\]

Proof.

\[k^e \cdot \text{Enc}(m) \equiv k^e \cdot m^e \equiv (k \cdot m)^e \equiv \text{Enc}(k \cdot m)\ (\text{mod}\ n). \qquad \blacksquare\]

Homomorphic property over multiplication for ElGamal⌗

Let $(p, g, h = g^x)$ be the public key of ElGamal. If $(c_1, c_2)$ be a ciphertext of $m$. Then $(c_1, k \cdot c_2)$ is a ciphertext of $k \cdot m$.

Proof.

Let $m'$ be the corresponding plaintext for $(c_1', c_2') := (c_1, k \cdot c_2)$.

\[m' \equiv c_2' \cdot c_1'^{-x} \equiv (k \cdot c_2) \cdot c_1^{-x} \equiv k \cdot (c_2 \cdot c_1^{-x}) \equiv k \cdot m \ (\text{mod}\ p). \qquad \blacksquare\]

Part II: Applying the homomorphic properties⌗

One can apply a homomorphic property without knowing the private key. These are what we can do if we have a ciphertext of $m$ (in different cryptosystems)

If we have $\text{Enc}_\text{RSA}(m)$, we can:
- [Homomorphic] compute $\text{Enc}_\text{RSA}(k \cdot m\ \text{mod}\ n)$ for any $k$, and
- [Feature] obtain $\text{Enc}_\text{ElGamal}(m\ \text{mod}\ p)$.
If we have $\text{Enc}_\text{ElGamal}(m)$, we can:
- [Homomorphic] compute $\text{Enc}_\text{ElGamal}(k \cdot m\ \text{mod}\ p)$ for any $k$, and
- [Feature] obtain $\text{Enc}_\text{RSA}(m\ \text{mod}\ n)$.

Note. It is necessary to mention $\text{mod}\ p$ (resp. $\text{mod}\ n$) when converting RSA to ElGamal (resp. vice versa). For example, when $n < m < p$, the below is wrong:

$$\text{Enc}_\text{ElGamal}(m) \xrightarrow{\text{ElGamal to RSA}} \text{Enc}_\text{RSA}(m)$$

As the message space for RSA is $\mathcal{M} := [0, n)$ and since $m \not\in \mathcal{M}$, modulo $m$ will be taken.

Now we are trying to obtain $\text{Enc}_\text{RSA}(am + b)$ for some constants $a$ and $b$ ($a, b \neq 0$). If we are able to get that, then we are not far from recovering $m$ directly.

Why? Obviously, if $c_0$ is the RSA ciphertext of $m_0$, then $x - m_0$ is a factor of $x^e - c_0$ (under modulo $n$). We want to find another polynomial $\text{g}(x)$ under modulo $n$ such that it is divisible by $x - m_0$.

As long as $x^e - c_0$ and $\text{g}(x)$ does not share other common factors than $x - m_0$, we can compute $x - m_0$ from $\text{GCD}(x^e - c_0, \text{g}(x))$. We can then recover $m_0$.

Given that we start with $c_0 := \text{Enc}_\text{RSA}(m_0)$. The below is a flow of operations that we are going to proceed:

\[\begin{aligned} & c_0 = \text{Enc}_\text{RSA}(m_0) \\ & \qquad\xrightarrow{\text{RSA to ElGamal}} \text{Enc}_\text{ElGamal}(m_0\ \text{mod}\ p) \\ & \qquad\xrightarrow{\text{Homomorphic}\ (\times k)} \text{Enc}_\text{ElGamal}(k \cdot m_0\ \text{mod}\ p) \\ & \qquad\xrightarrow{\text{ElGamal to RSA}} \text{Enc}_\text{RSA}(k \cdot m_0\ \text{mod}\ p\ \text{mod}\ n) \\ \end{aligned}\]

There are a lot of modulos which is pretty confusing. Let's assume $n < p$ (that happens most of the cases) and read again:

\[\begin{aligned} & c_0 = \text{Enc}_\text{RSA}(m_0) \\ & \qquad\xrightarrow{\text{RSA to ElGamal}} \text{Enc}_\text{ElGamal}(m_0) \\ & \qquad\xrightarrow{\text{Homomorphic}\ (\times k)} \text{Enc}_\text{ElGamal}(k \cdot m_0\ \text{mod}\ p) \\ & \qquad\xrightarrow{\text{ElGamal to RSA}} \text{Enc}_\text{RSA}(k \cdot m_0\ \text{mod}\ p\ \text{mod}\ n) \\ \end{aligned}\]

Well, that is pretty much the same as the first one. Let me introduce the weirdest assumption in this writeup: $p \leq k \cdot m_0 < p + n$. This implies $0 \leq k \cdot m_0 - p < n < p$. Now back to the flow:

\[\begin{aligned} & c_0 = \text{Enc}_\text{RSA}(m_0) \\ & \qquad\xrightarrow{\text{RSA to ElGamal}} \text{Enc}_\text{ElGamal}(m_0) \\ & \qquad\xrightarrow{\text{Homomorphic}\ (\times k)} \text{Enc}_\text{ElGamal}(k \cdot m_0 - p) \\ & \qquad\xrightarrow{\text{ElGamal to RSA}} \text{Enc}_\text{RSA}(k \cdot m_0 - p) \\ \end{aligned}\]

Sounds good! If we can find an appropriate $k$, we can obtain $\text{Enc}_\text{RSA}(k \cdot m_0 - p)$.

Part III: Finding $k$ and finishing up⌗

Suppose that $m_0 \in [0, n)$. If we pick $k = \lceil p / m_0 \rceil$, then

\[k \cdot m_0 = \lceil p / m_0 \rceil \cdot m_0 \geq p \qquad\text{and}\qquad k \cdot m_0 = \lceil p / m_0 \rceil \cdot m_0 < p + m_0 < p + n.\]

However, we are unable to pick $k$ in such way because we don't even have $m_0$.

Luckily, although we don't have $m_0$, we still have a good estimation of it.

Since it is a padded flag which is 96 bytes long and starts with TSJ (in ASCII, $\text{54535A}_{16} = 5526346$), we have

\[5526346 \times 256^{93} \leq m_0 < 5526347 \times 256^{93}.\]

We can estimate $\tilde{m_0}$ from above and thus compute $k = \lceil p / \tilde{m_0} \rceil$. After all, $x - m_0$ is divisible to the two polynomials below (here $c_1 := \text{Enc}_\text{RSA}(k \cdot m_0 - p)$):

\[\text{f}(x) := x^e - c_0 \qquad \text{and} \qquad \text{g}(x) := (k \cdot x - p)^e - c_1.\]

As said above, we can compute $\text{GCD}(\text{f}(x), \text{g}(x))$ to recover $x - m_0$. Finally we have the flag: TSJ{a_weird_oracle?}.