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.

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.

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.

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.

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}\mathrm{mod}p)q\mathrm{mod}N$$

If the double free happens, however, the signature is calculated by the following formula:

$${\sigma }^{\prime }={\sigma }_q+((q^{-1}-{\sigma }_q)q^{-1}\mathrm{mod}p)q\mathrm{mod}N$$

Remember that

${\sigma }^e\mathrm{mod}N=M$.
Then, what does

$({\sigma }^{\prime }{)}^e\mathrm{mod}N$ calculate?

Let

$\mathrm{\Delta }$ be the difference between

${\sigma }_p$ and

$q^{-1}$:

$\mathrm{\Delta }={\sigma }_p-q^{-1}$

${\sigma }^{\prime }$ can be written in the following way:

$$\begin{array}{rcl}{\sigma }^{\prime }& =& {\sigma }_q+((({\sigma }_p-\mathrm{\Delta })-{\sigma }_q)q^{-1}\mathrm{mod}p)q\mathrm{mod}N\\ & =& {\sigma }_q+(({\sigma }_p-{\sigma }_q)q^{-1}\mathrm{mod}p)q-(\mathrm{\Delta }{q}^{-1}\mathrm{mod}p)q\mathrm{mod}N\\ & =& \sigma -(\mathrm{\Delta }{q}^{-1}\mathrm{mod}p)q\mathrm{mod}N\end{array}$$

Let

$\alpha$ be

$(-\mathrm{\Delta }{q}^{-1}\mathrm{mod}p)$ for simplicity:

${\sigma }^{\prime }=\sigma +q\alpha \mathrm{mod}N$
By binomial theorem,

$({\sigma }^{\prime }{)}^e$ can be written as

$$\begin{array}{rcl}({\sigma }^{\prime }{)}^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\mathrm{mod}N\\ & =& M+q(a_1\alpha +\cdots +a_{e-1}{q}^{e-2}{\alpha }^{e-1}+a_e{q}^{e-1}{\alpha }^e)\mathrm{mod}N\end{array}$$

where

$a_i(i\in \{1,\cdots ,e\})$ is an integer.
Now you may notice that

$({\sigma }^{\prime }{)}^e$ can be denoted as

$M+q\beta \mathrm{mod}N$ for an integer

$\beta$.

This is a transformed form of Bellcore Attack.
As we have

$M,{\sigma }^{\prime },e,N$, we can find

$q$ by the following formula:

$$q=gcd(M-(({\sigma }^{\prime }{)}^e\mathrm{mod}N),N)$$

After we successfully find

$q$, it's easy to sign any messages.

Exploit

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()