Tags: go factoring tls rsa crypto wireshark
Rating: 5.0
# Hard Copy
## 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](./dist/printer.go) for my printer and a recent [network traffic dump](./dist/capture.pcap).
## Setup
Participants should be given [`./dist/printer.go`](./dist/printer.go) and [`./dist/capture.pcap`](./dist/capture.pcap).
## Solution
At a high level, the participant needs to exploit two vulnerabilities:
1. Weak RSA prime generation in `printer.go`, and
2. Weak cipher chosen in TLS traffic.
The printer's source code reveals a custom RSA key generation function. This function essentially
- Chooses a random 1028-bit prime for `p`,
- To find `q`, it starts with the value of `p`, flips the third most significant bit, and then finds the next prime in ascending or descending order depending on whether `q` is greater than or less than `p`.
- Takes the usual approach to constructing a private key from `p` and `q`.
This method of generating RSA primes is not secure because the approximate difference between `p` and `q` can be easily guessed. This difference can be used to factor the public key modulus, `N`, into `p` and `q`. There are two methods of doing this that I'm aware of: Fermat's factorization method and a method based on the quadratic formula. Both of these approaches are implemented in the solver script at [`./solver/solver.go`](./solver/solver.go).
Additionally, the packet capture file reveals that the TLS session is using [`TLS_RSA_WITH_AES_256_GCM_SHA384`](https://ciphersuite.info/cs/TLS_RSA_WITH_AES_256_GCM_SHA384/) which is weak cipher suite. This key exchange algorithm does not provide forward secrecy, which means an attacker can decrypt the entire communication stream given the private key.
The rest of this section describes the steps to exploit the weak prime and weak cipher suite vulnerabilities to recover the flag:
1. [Extract the printer's certificate from the packet capture file](#extract-the-printers-certificate-from-the-packet-capture-file)
2. [Factor the RSA modulus and recover the private key](#factor-the-rsa-modulus-and-recover-the-private-key)
3. [Decrypt the TLS traffic and recover the flag](#decrypt-the-tls-traffic-and-recover-the-flag)
### Extract the printer's certificate from the packet capture file
1. Open `capture.pcap` in Wireshark.
2. Select the packet with a label that begins with, "Server Hello, Certificate, "
- This is the part of the TLS handshake that contains the server's certificate.
3. Find the certificate and right-click -> Export Packet Bytes...
4. Save the certificate as `cert-recovered.der`.
5. Run the following command to convert the certificate to PEM format: `openssl x509 -inform der -in cert-recovered.der -out cert-recovered.pem`
### Factor the RSA modulus and recover the private key
Run `go run ./solver`. This will generate `key-recovered.pem`. This actually uses two different methods to factor the RSA modulus and recover the private key, one involving Fermat's factorization method, and other using the quadratic formula. For a detailed description of how this works, see the comments in the solver source code. These descriptions are copied from the solver source code below for convenience:
#### Fermat's method
> According to Fermat's method, we can represent N as the difference of two
> squares, a^{2} and b^{2}:
>
> N = a^{2} - b^{2}
>
> Another way of writing this is
>
> N = (a + b)(a - b)
>
> We know that N is a product of two primes. Let p = (a + b) and
> q = (a - b). Then the difference between p and q is
>
> p - q = (a + b) - (a - b)
> = 2b
>
> Fortunately, we can make a pretty good guess as to the difference between
> p and q. Recall q is generated by flipping the third most significant bit
> of p and then searching for the next prime in ascending or descending
> order, depending on whether q is greater than or less than p. Therefore,
> we know the difference between p and q must be at least 2^{1024 - 3}.
>
> Using this value, we can guess the value of b:
>
> 2b = 2^{1024 - 3}
> b = 2^{1024 - 4}
>
> Substituting this back into the original equation gives us a starting
> value for a:
>
> N = a^{2} - (2^{1024 - 4})^{2}
> a^{2} = N + (2^{1024 - 4})^{2}
> a = sqrt(N + (2^{1024 - 4})^{2})
>
> We then use this value for a as a starting value in fermat's
> factorization method.
#### Quadratic formula method
> Since we know the approximate difference between p and q is 2^{1021}, we
> can represent N as
>
> N = p*q
> N = p*(p + 2^{1021} + k)
> N = p^2 + (2^{1021} + k)*p
>
> for some small k. When we subsitute values for k, this becomes a
> quadratic equation:
>
> p^2 + (2^{1021} + k)*p - N = 0
>
> Therefore, we try successive values for k until we are able to solve the
> equation.
### Decrypt the TLS traffic and recover the flag
1. In Wireshark, go to Preferences -> RSA Keys.
2. Select "Add new keyfile..." and select `key-recovered.pem`.
3. Restart Wireshark, and re-open `capture.pcap`.
4. Now, decrypted traffic should be visible. In the display filter menu, type "ipp" and press Enter. This will filter to just the IPP traffic.
5. Select the packet with label "IPP Request (Print-Job)"
- This is the request containing the actual file to print.
6. Find the data and right-click -> Export Packet Bytes...
7. Save the file as `flag-recovered.pdf`.
- This is actually a "HP Printer Job Language data" file, but on macOS the Preview app will recognize it as a PDF. On other platforms you might have to edit the file and delete the `@PJL` headers.
8. The PDF contains the flag!
## References
- [Fermat Attack on RSA](https://fermatattack.secvuln.info/): This challenge was loosely based on this real-world vulnerability.
- [Breaking RSA - Computerphile - YouTube](https://www.youtube.com/watch?v=-ShwJqAalOk): Good video for understanding RSA and Fermat's factorization method.
- [Wireshark TLS Decryption](https://wiki.wireshark.org/TLS#tls-decryption): How to decrypt TLS traffic with Wireshark.
- [How to Use the Internet Printing Protocol](https://www.pwg.org/ipp/ippguide.html): Good resource for understanding the basics of IPP.
