# signme - zer0pts CTF 2021
###### tags: `zer0pts CTF 2021` `crypto` `pwn`
## Introduction
### Challenge Overview
We're given the target binary and the source codes.
The program implements an RSA (CRT) signature.
We can sign an arbitrary message padded by PKCS1 v1.5 and after that we have to sign a given message.
Basically it's impossible to break the signature because public key $N$ is 2048-bit, which is too big to factorize.
### Vulnerability
In `get_message` function it allocates a buffer named `msg` for storing our input, then pad the message and finally free all buffers.
```cpp
msg = (char*)malloc(SECURITY_PARAMETER / 8);
...
padded = pad_pkcs1_v15(msg, s, SECURITY_PARAMETER / 8);
...
free(padded);
free(msg); // [0]
```
This doesn't look bad but the vulnerability lies in `pad_pkcs1_v15` function.
```cpp
int i, rlen = n - s - 3; // [1]
...
msg = (char*)realloc(msg, rlen); // [2]
for(i = 0; i < rlen; i++) {
...
msg[i] = mpz_get_ui(r); // [3-a]
}
...
memcpy(&padded[2], msg, rlen); // [3-b]
...
```
Inside this function reallocates `msg` at [2]. The size for this re-allocation is calculated at [1]. However, we can make it zero by giving 1021 as `s` because `n` is 1024.
This is possible as `s` is decided by the size of the buffer, which relies on our input length.
If `rlen` becomes zero, `realloc` frees `msg` in it at [2]. Even though `msg` is freed here, it will be double-freed at [0].
Although there are some lines in which `msg` is used after free such as [3-a] and [3-b], they will never be a problem.
First, the control won't reach [3-a] because the `for` loop won't iterate when `rlen` is zero.
Second, [3-b] will be executed but `memcpy` won't crash when size is zero even if the source address is invalid.
So, we get a double free in the function.
The size of the chunk is `SECURITY_PARAMETER / 8`, which is 0x80.
### Observation
Let's check what happens when we cause the double free.
As these freed chunks are linked to tcache, it will affect chunks with size between 0x79 and 0x88.
The integer values created by gmp are allocated on the heap. Each chunk size is decided by the bit length of the integer.
In `generate_signature` function, there are three 1024-bit integers allocated on the heap. These values use 0x80-byte chunk respectively because 1024/8=0x80.
```cpp
void generate_signature(mpz_t sign, mpz_t m, PrivateKey *priv) {
mpz_t sp, sq, qi;
mpz_init2(sp, SECURITY_PARAMETER);
mpz_init2(sq, SECURITY_PARAMETER);
mpz_init2(qi, SECURITY_PARAMETER);
...
```
Thus, it will cause chunk overlap. Precisely the buffers for `sp` and `qi` overlap. As a result, the value of `sp` is overwritten by the value of `qi` later.
```cpp
mpz_powm(sp, m, priv->d, priv->p);
mpz_powm(sq, m, priv->d, priv->q);
mpz_invert(qi, priv->q, priv->p); // overwrites sp
```
### Fault Attack
The signature should be calculated by the following formula:
$$\sigma = \sigma_q + ((\sigma_p - \sigma_q)q^{-1} \mod p)q \mod N$$
If the double free happens, however, the signature is calculated by the following formula:
$$\sigma' = \sigma_q + ((q^{-1} - \sigma_q)q^{-1} \mod p)q \mod N$$
Remember that $\sigma^e \mod N = M$.
Then, what does $(\sigma')^e \mod N$ calculate?
Let $\Delta$ be the difference between $\sigma_p$ and $q^{-1}$: $\Delta = \sigma_p - q^{-1}$
$\sigma'$ can be written in the following way:
\begin{eqnarray}
\sigma' &=& \sigma_q + (((\sigma_p - \Delta) - \sigma_q)q^{-1} \mod p)q \mod N \\
&=& \sigma_q + ((\sigma_p - \sigma_q)q^{-1} \mod p)q - (\Delta q^{-1} \mod p)q\mod N \\
&=& \sigma - (\Delta q^{-1} \mod p)q \mod N
\end{eqnarray}
Let $\alpha$ be $(-\Delta q^{-1} \mod p)$ for simplicity: $\sigma' = \sigma + q\alpha \mod N$
By binomial theorem, $(\sigma')^e$ can be written as
\begin{eqnarray}
(\sigma')^e &=& {}_e C_0 \sigma^e + {}_e C_1 \sigma^{e-1} (q\alpha) + \cdots + {}_e C_{e-1} \sigma (q\alpha)^{e-1} + {}_e C_e (q\alpha)^e \mod N\\
&=& M + q(a_1 \alpha + \cdots + a_{e-1} q^{e-2}\alpha^{e-1} + a_e q^{e-1}\alpha^{e}) \mod N
\end{eqnarray}
where $a_i (i \in \{1, \cdots, e\})$ is an integer.
Now you may notice that $(\sigma')^e$ can be denoted as $M + q\beta \mod N$ for an integer $\beta$.
This is a transformed form of Bellcore Attack.
As we have $M, \sigma', e, N$, we can find $q$ by the following formula:
$$q = \gcd(M - ((\sigma')^e \mod N), N)$$
After we successfully find $q$, it's easy to sign any messages.
## Exploit
```python=
from math import gcd
from ptrlib import *
sock = Socket("localhost", 10298)
# fault attack
payload = b"A" * (1024 // 8 - 3)
sock.sendlineafter(": ", payload)
r = sock.recvregex("m = ([0-9a-f]+)")
m = int(r[0], 16)
r = sock.recvregex("pubkey = \(([0-9a-f]+), ([0-9a-f]+)\)")
N, e = int(r[0], 16), int(r[1], 16)
r = sock.recvregex("signature = ([0-9a-f]+)")
s = int(r[0], 16) # here we get a broken signature
# factorize N
q = gcd(m - pow(s, e, N), N)
assert N % q == 0
p = N // q
phi = (p-1) * (q-1)
d = inverse(e, phi)
# find signature
r = sock.recvregex("message: ([0-9a-f]+)")
m = int(r[0], 16)
s = pow(m, d, N)
sock.sendlineafter("Signature: ", hex(s)[2:])
sock.interactive()
```
Sign in with Wallet
Connect another wallet