SECUINSIDE CTF Quals 2014: Crypto 200 "pillow" writeup
This was another algebra-focused crypto challenge (we need more of those!). For this task, we were provided with a compiled Python client that communicates encryptedly with a server along with a packet dump of a conversation between an admin and the server.
Let’s first take a look at the actual public-key cryptosystem: Each party generates two different primes $p$ and $q$, from which the numbers $n=pq$, $\ell=(p-1)(q-1)$, and $m\;\equiv\;\ell^{-1}\mod n$ are derived. The public key is $n$. The private key consists of $\ell$ and $m$.
To encrypt a message $\mathit{plain}\in\lbrace0,\dots,n-1\rbrace$, the following steps are performed: 1. Find a random prime $r$ between $1$ and $n$. 2. Compute the ciphertext as $\mathit{cipher}=(n+1)^\mathit{plain}r^n\bmod n^2$.
(Note that $r$ is chosen as a prime to ensure that it is coprime to $n$, which implies $r^n\bmod n^2\neq 0$ and thus $\mathit{cipher}\neq 0$.)
The following property is essential for the solution:
For all $k\in\mathbb N$, \[ (n+1)^k\;\equiv\;\sum_{i=0}^k\binom kin^k\;\equiv\;nk+1\mod n^2 \text. \] In particular, this implies that $(n+1)^\mathit{plain}\;\equiv\;n\mathit{plain}+1\mod n^2$.
(Decryption, mentioned for the sake of completeness, is a bit more involved: The plaintext is recovered via $\mathit{plain}=m((\mathit{cipher}^\ell\bmod n^2-1)/n)\bmod n$. Since $\varphi(n^2)=\varphi(p^2)\varphi(q^2)=p(p-1)q(q-1)$, it is clear that $\mathit{cipher}^\ell\;\equiv\;(n+1)^{\ell\mathit{plain}}r^{\varphi(n^2)}\;\equiv\;(n+1)^{\ell\mathit{plain}}\mod n^2$. As noted above, this is equal to $n\ell\mathit{plain}+1+\alpha n^2$ for some $\alpha\in\mathbb Z$. Subtract $1$ and divide the result by $n$ to obtain $\ell\mathit{plain}+\alpha n\;\equiv\;\ell\mathit{plain}\mod n$. The last (modular) multiplication yields $m\ell\mathit{plain}\;\equiv\;\mathit{plain}\mod n$.)
The client-server protocol basically works as follows:
- The client C connects to the server S
- S sends a welcome message
- C sends its public key
- S sends its public key
- C sends a request, encrypted with S’s public key
- S sends a response, encrypted with C’s public key
- The connection is closed
Since there is no nonce or any other protection against replay involved, we can simply take the admin’s message from the packet dump and send it to the server. As we can choose our own key pair (instead of also replaying the admin’s key), we can decrypt the server’s response:
Read [secret]
to get flag, just concat flag1 and flag2.
From the task description and the client’s bytecode, we can derive that the decryption of the message sent to the server is of the form
password + 'cat secret\n'.
We do of course not know password, but we can try to modify the
given ciphertext to decrypt to something else (ideally, ending with
flag1 and flag2 instead).
After some trial and error, we obtained the following: For all $k\in\mathbb Z$,
the congruence
\[ (nk+1)\mathit{cipher}\;\equiv\;(n(\mathit{plain}+k)+1)r^n\mod n^2 \]
holds (where the right-hand side is precisely an encryption of
$\mathit{plain}+k$!). This follows easily from the identity shown above:
\[ (nk+1)\mathit{cipher} \;\equiv\; (nk+1)(n\mathit{plain}+1)r^n \]
\[ \phantom{(nk+1)\mathit{cipher}}\;\equiv\; (n^2k\mathit{plain}+n\mathit{plain}+nk+1)r^n \]
\[ \phantom{(nk+1)\mathit{cipher}}\;\equiv\; (n(\mathit{plain}+k)+1)r^n\mod n^2 \text. \]
Thus, if we choose $k$ as the difference of (the encodings of) the strings
'flag1\n\n' and 'secret\n', the
ciphertext $(nk+1)\mathit{cipher}\bmod n^2$ (that we can easily compute) will
decrypt to
password + 'cat flag1\n\n'
using the server’s private key, which is exactly what we want (the same applies
to flag2). The server’s responses to the forged ciphertexts are:
Read [flag1]
The flag is "7h053 wh0 bu1ld b3n347h
Read [flag2]
7h3 574r5 bu1ld 700 l0w."(without quote)