247CTF - Multiplication Tables

Posted on Edited on In Views: Disqus: Word count in article: 1.1k Reading time ≈ 4 mins.

Recover the private key used to download the flag over a TLS encrypted connection.

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
❯ tshark -r multiplication_tables.pcap
    1   0.000000 192.168.10.111 → 192.168.10.159 TCP 66 17865 → 8443 [SYN] Seq=0 Win=64240 Len=0 MSS=1460 WS=256 SACK_PERM
    2   0.000051 192.168.10.159 → 192.168.10.111 TCP 66 8443 → 17865 [SYN, ACK] Seq=0 Ack=1 Win=29200 Len=0 MSS=1460 SACK_PERM WS=128
    3   0.000319 192.168.10.111 → 192.168.10.159 TCP 60 17865 → 8443 [ACK] Seq=1 Ack=1 Win=1051136 Len=0
    4   0.000620 192.168.10.111 → 192.168.10.159 TLSv1 571 Client Hello
    5   0.000640 192.168.10.159 → 192.168.10.111 TCP 54 8443 → 17865 [ACK] Seq=1 Ack=518 Win=30336 Len=0
    6   0.000815 192.168.10.159 → 192.168.10.111 TLSv1.2 756 Server Hello, Certificate, Server Hello Done
    7   0.001210 192.168.10.111 → 192.168.10.159 TLSv1.2 61 Alert (Level: Fatal, Description: Certificate Unknown)
    8   0.001328 192.168.10.111 → 192.168.10.159 TCP 60 17865 → 8443 [FIN, ACK] Seq=525 Ack=703 Win=1050368 Len=0
    9   0.001398 192.168.10.159 → 192.168.10.111 TCP 54 8443 → 17865 [FIN, ACK] Seq=703 Ack=526 Win=30336 Len=0
   10   0.001542 192.168.10.111 → 192.168.10.159 TCP 60 17865 → 8443 [ACK] Seq=526 Ack=704 Win=1050368 Len=0
   11   0.006428 192.168.10.111 → 192.168.10.159 TCP 66 17866 → 8443 [SYN] Seq=0 Win=64240 Len=0 MSS=1460 WS=256 SACK_PERM
   12   0.006479 192.168.10.159 → 192.168.10.111 TCP 66 8443 → 17866 [SYN, ACK] Seq=0 Ack=1 Win=29200 Len=0 MSS=1460 SACK_PERM WS=128
   13   0.006706 192.168.10.111 → 192.168.10.159 TCP 60 17866 → 8443 [ACK] Seq=1 Ack=1 Win=1051136 Len=0
   14   0.007056 192.168.10.111 → 192.168.10.159 TLSv1 571 Client Hello
   15   0.007081 192.168.10.159 → 192.168.10.111 TCP 54 8443 → 17866 [ACK] Seq=1 Ack=518 Win=30336 Len=0
   16   0.007274 192.168.10.159 → 192.168.10.111 TLSv1.2 756 Server Hello, Certificate, Server Hello Done
   17   0.007777 192.168.10.111 → 192.168.10.159 TLSv1.2 244 Client Key Exchange, Change Cipher Spec, Encrypted Handshake Message
   18   0.008344 192.168.10.159 → 192.168.10.111 TLSv1.2 280 New Session Ticket, Change Cipher Spec, Encrypted Handshake Message
   19   0.008984 192.168.10.111 → 192.168.10.159 TLSv1.2 654 Application Data
   20   0.009527 192.168.10.159 → 192.168.10.111 TLSv1.2 100 Application Data
   21   0.010039 192.168.10.159 → 192.168.10.111 TLSv1.2 446 Application Data, Application Data, Application Data, Application Data, Application Data, Application Data, Application Data
   22   0.010293 192.168.10.111 → 192.168.10.159 TCP 60 17866 → 8443 [ACK] Seq=1308 Ack=1368 Win=1049600 Len=0
   23   0.012247 192.168.10.111 → 192.168.10.159 TCP 60 17866 → 8443 [FIN, ACK] Seq=1308 Ack=1368 Win=1049600 Len=0
   24   0.012278 192.168.10.159 → 192.168.10.111 TCP 54 8443 → 17866 [ACK] Seq=1368 Ack=1309 Win=32640 Len=0

Vulnerability

The TLS certificate is transmitted in the handshake and reveals the public key. If the RSA modulus has been factored previously, the private key can be recovered.

Solution

Step 1: Extract the Certificate from PCAP

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#!/usr/bin/env python3
import glob
import os

from cryptography import x509
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa
from cryptography.hazmat.primitives.asymmetric.rsa import RSAPrivateKey, RSAPublicKey
from scapy import dadict
from scapy.all import *
from scapy.all import Raw, load_layer, rdpcap
from scapy.layers.inet import IP, TCP
from scapy.layers.tls.all import TLS
from scapy.layers.tls.cert import Cert
from scapy.layers.tls.handshake import TLSCertificate

PCAP_FILE = "/home/kita/Downloads/multiplication_tables.pcap"
KEYS = "/home/kita/Downloads/keys/"

load_layer("tls")


def find_cert(pcap_path):
    packets = rdpcap(pcap_path)
    cert_list = []

    for pkt in packets:
        if pkt.haslayer(Raw):
            raw = pkt[Raw].load
            try:
                tls_parsed = TLS(raw)
                tls_cert_layer = tls_parsed.getlayer(TLSCertificate)
                if tls_cert_layer:
                    print("[-] Found TLS Certificate.")
                    cert = tls_cert_layer.certs
                    for _, x509_wrapper in cert:
                        cert_list.append(x509_wrapper)
                        print("[-] Extracted a TLS Certificate.")
                else:
                    print("[-] Found TLS packet.")
            except Exception as e:
                print(f"[-] Error: {e}")
                continue
    return cert_list


def find_matching_private_key(target_modulus: int, keys_directory: str) -> str | None:
    print(f"[*] Searching for matching private key in {keys_directory} ...")

    for key_file in glob(os.path.join(keys_directory, "*")):
        try:
            with open(key_file, "rb") as f:
                private_key = serialization.load_pem_private_key(
                    f.read(), password=None, backend=default_backend()
                )

            # 类型守卫
            if isinstance(private_key, rsa.RSAPrivateKey):
                priv_modulus = private_key.private_numbers().public_numbers.n
                if priv_modulus == target_modulus:
                    print(f"[!] BINGO! Matching key found: {key_file}")
                    return key_file
        except Exception:
            pass  # 静默忽略无法解析的非私钥文件

    print("[-] No matching key found.")
    return None


def get_modulus(cert_obj):
    assert isinstance(cert_obj, Cert)
    pubkey_bytes = cert_obj.pubKey.der

    try:
        public_key = serialization.load_der_public_key(pubkey_bytes)

        if not isinstance(public_key, rsa.RSAPublicKey):
            print("[-] Not an RSA public key.")
            return None

        # 3. 提取 Modulus (N)
        return public_key.public_numbers().n

    except ValueError as e:
        print(f"[-] Failed to parse public key: {e}")
        return None


def get_exponent(cert_obj):
    assert isinstance(cert_obj, Cert)
    pubkey_bytes = cert_obj.pubKey.der

    try:
        public_key = serialization.load_der_public_key(pubkey_bytes)

        if not isinstance(public_key, rsa.RSAPublicKey):
            print("[-] Not an RSA public key.")
            return None

        # 3. 提取 Exponent (e)
        return public_key.public_numbers().e

    except ValueError as e:
        print(f"[-] Failed to parse public key: {e}")
        return None


def check_pcap(pcap_path):
    packets = rdpcap(pcap_path)
    packets.show()
    for pkt in packets:
        pkt.show()
        if pkt.haslayer(Raw):
            raw = pkt[Raw].load
            try:
                print(raw.decode())
            except Exception as e:
                print(f"[-] Error: {e}")
                continue


if __name__ == "__main__":
    cert_list = find_cert(PCAP_FILE)
    print(cert_list)
    for cert_obj in cert_list:
        modulus = get_modulus(cert_obj)
        exponent = get_exponent(cert_obj)
        print(modulus)
        print(exponent)

    # if modulus:
    #     key_path = find_matching_private_key(modulus, KEYS)
    #     print(key_path)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[-] Found TLS packet.
[-] Found TLS Certificate.
[-] Extracted a TLS Certificate.
[-] Found TLS packet.
[-] Found TLS packet.
[-] Found TLS Certificate.
[-] Extracted a TLS Certificate.
[-] Found TLS packet.
[-] Found TLS packet.
[-] Found TLS packet.
[-] Found TLS packet.
[-] Found TLS packet.
[[X.509 Cert. Subject:/C=AU/O=247CTF/OU=net125/CN=127.0.0.1, Issuer:/C=AU/O=247CTF/OU=net125/CN=127.0.0.1], [X.509 Cert. Subject:/C=AU/O=247CTF/OU=net125/CN=127.0.0.1, Issuer:/C=AU/O=247CTF/OU=net125/CN=127.0.0.1]]
150140677816147665104219084736753210294673482912091623639530125054379822052662632476220418069658373540642718111649733795871151252404840997598533258881471779382418788567883517594075575444723340506445280678466322096113052425236787558022472785685579744210805862764465110689084328509029822107730392445215781001579
65537
150140677816147665104219084736753210294673482912091623639530125054379822052662632476220418069658373540642718111649733795871151252404840997598533258881471779382418788567883517594075575444723340506445280678466322096113052425236787558022472785685579744210805862764465110689084328509029822107730392445215781001579
65537

Step 2: Factor the Modulus

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#!/usr/bin/env python3
import json
import sys
import urllib.error
import urllib.request


def query_factordb(number: str):
    url = f"http://factordb.com/api?query={number}"
    headers = {"User-Agent": "ArchLinux-PowerUser/1.0"}

    try:
        req = urllib.request.Request(url, headers=headers)
        with urllib.request.urlopen(req) as response:
            data = json.loads(response.read().decode("utf-8"))

            status = data.get("status", "Unknown")
            factors = data.get("factors", [])

            print(f"[*] Target : {number}")
            print(f"[*] Status : {status}")

            if factors:
                result = " * ".join([f"{base}^{exp}" for base, exp in factors])
                print(f"[*] Factors: {result}")
            else:
                print("[!] No factors returned.")

    except urllib.error.URLError as e:
        print(f"[!] Network Error: {e.reason}")
    except ValueError:
        print("[!] JSON parsing failed. Did FactorDB change their API?")


if __name__ == "__main__":
    if len(sys.argv) != 2:
        print("Usage: ./fdb.py <number>")
        sys.exit(1)

    query_factordb(sys.argv[1])
1
2
3
4
❯ python factor.py 150140677816147665104219084736753210294673482912091623639530125054379822052662632476220418069658373540642718111649733795871151252404840997598533258881471779382418788567883517594075575444723340506445280678466322096113052425236787558022472785685579744210805862764465110689084328509029822107730392445215781001579
[*] Target : 150140677816147665104219084736753210294673482912091623639530125054379822052662632476220418069658373540642718111649733795871151252404840997598533258881471779382418788567883517594075575444723340506445280678466322096113052425236787558022472785685579744210805862764465110689084328509029822107730392445215781001579
[*] Status : FF
[*] Factors: 11443069641880629381891581986018548808448150675612774441982091938562801238612124445967724562059877882869924090566492089872161438646198325341704520958011761^1 * 13120664517031861557695339067275706831429518210212092859212127044658713747906482358428924486662467583986570766086011893335839637764790393666582606794678939^1

Step 3: Compute the Private Key

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.PublicKey import RSA

p = 11443069641880629381891581986018548808448150675612774441982091938562801238612124445967724562059877882869924090566492089872161438646198325341704520958011761
q = 13120664517031861557695339067275706831429518210212092859212127044658713747906482358428924486662467583986570766086011893335839637764790393666582606794678939
e = 65537

n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

key = RSA.construct((n, e, d, p, q))
with open("private_key.pem", "wb") as f:
    f.write(key.export_key())
print("Key forged successfully.")

Step 4: Import and Use in Wireshark

Import the generated private key into Wireshark to decrypt the TLS traffic and recover the flag.

Key Insight

This challenge demonstrates why factorization of RSA moduli is critical—if a modulus can be factored, the entire RSA cryptosystem is broken for that key pair. FactorDB maintains a public database of previously factored numbers.

247CTF{ca0289c6804acd4812ee8f375515245e}