SquareCTF 2022: Hard Copy

This post explains how I beat the capture-the-flag crypto challenge “Hard Copy” during SquareCTF 2022, as part of the Polygl0ts team.

Description

I printed a hard copy of the flag, but then I lost it. Will you help me recover it? Here’s the source code for my printer and a recent network traffic dump.

As implied, the challenge links to some source code and a packet capture. There is no interactive component.

Looking at the packet capture, we note that TLS 1.2 is in use and that key exchange is done using the RSA premaster method.

Looking at the source code, we see that the server uses a custom key generation method, which is as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


const bits = 2048

var bigOne = big.NewInt(1)
var bigTwo = big.NewInt(2)

p, err := rand.Prime(rand.Reader, bits/2)
if err != nil {
	return fmt.Errorf("failed to get prime: %w", err)
}

q := new(big.Int)
q.Xor(p, new(big.Int).Lsh(bigOne, bits/2-3)) // ensure q is not close to p
for {
	if q.ProbablyPrime(20) {
		break
	}
	switch q.Cmp(p) {
	case -1:
		q.Sub(q, bigTwo)
	case 1:
		q.Add(q, bigTwo)
	case 0: // should never happen
		return fmt.Errorf("failed to get prime: p == q")
	}
}

Solution

Spoiler

Since the key generation method is custom, we should scrutinize it closely. It produces an RSA modulus in such a way that the difference between both prime factors is equal to $2^{1021}$ plus a small (even) amount. In other words $$ \lvert p-q \rvert = d + 2k $$ where $d = 2^{1021}$ and $k$ is a non-negative integer that is, cryptographically speaking, small.

This reminded me of the Fermat attack on RSA, which works when $p$ and $q$ are close: $$\lvert p-q \rvert = 2k$$ It is performed by setting unknowns $a = \frac{p+q}{2}$ and $b = k = \frac{\lvert p-q\rvert}{2}$ so that $$n = a^2 - b^2$$ Then, since $b^2$ is small, it takes $\sqrt{n}$ as an lower bound approximation of $a$ and follows sequences $a_i = \sqrt{n}+i$ and $B_i = {a_i}^2 - n$ until $B_i$ is a square number, at which point it is likely that $b = \sqrt{B_i}$ and $a = a_i$.

Can we generalize this attack to our case? It turns out so if we keep $a=\frac{p+q}{2}$ and let $b=\frac{d}{2}+k$: It still holds that $n = a^2-b^2$. For the initial approximation, we use $$a \ge \sqrt{n+\left(\frac{d}{2}\right)^2}$$ since $b^2$ is no longer small but $b^2-\left(\frac{d}{2}\right)^2$ is.

I wrote my implementation of this modified Fermat algorithm in Go just because.

After recovering the RSA private key, we can give it to Wireshark to allow decrypting the captured traffic. This allows us to recover a printer job for a PDF file which contains the flag.