gaslightCTF — crypto: CompleteHTTP

Challenge: CompleteHTTP Category: crypto Author: William Tu / sportshead Flag: gaslightCTF{gu3s5_y0u_n33d_l0ng_sl33v35_ev3n_in_5umm3r?}

Description

How do you make RSA fashionable?

The attachments are a 72 MB .NET single-file executable complete-http (a self-contained HTTPS server) and a complete-http.pcapng capturing a TLS 1.2 connection made to 127.0.0.1:1337. We have to read the server's encrypted HTTP response — which contains the flag — out of the pcap.

1. What the server does

complete-http is a .NET 10 single-file bundle. The managed assembly complete-http.dll is embedded in the PE; it was extracted at file offset 0xe1de00 and decompiled with ilspycmd. The relevant parts:

Program.cs starts a TlsConnection server on port 1337 and hands the connection to ServeApplicationDataAsync.
ServeApplicationDataAsync reads an HTTP request and answers:

bool isGet = text.StartsWith("GET ", StringComparison.Ordinal);
string status = isGet ? "200 OK" : "400 Bad Request";
string body = isGet
    ? (Environment.GetEnvironmentVariable("FLAG") ?? "gaslightCTF{fake_flag}")
    : "bad request";

so the HTTP response body is the flag, and the whole TLS session is custom — a from-scratch implementation (CompleteHttp.Tls) that only supports one cipher suite: TLS_RSA_WITH_AES_128_CBC_SHA.

2. The crypto bug: `genRandomBits`

The server's RSA keys are produced by CertificateProvider.CreateCertificate, which calls the project's own BigInteger.genPseudoPrime(1024, 65537). Look at BigInteger.genRandomBits:

public void genRandomBits(int bits)
{
    int num = bits / 32;                       // 1024 / 32 = 32
    byte[] array = new byte[num];              // 32 random BYTES
    rngProvider.GetNonZeroBytes(array);        //    each 1..255
    Array.Copy(array, 0, bignumLimbs, 0, num); // copied into 32 uint limbs!
    bignumLimbs[num - 1] |= 2147483648u;       // top limb forced bit 31
    dataLength = num;
}

The bug is the Array.Copy between a byte[32] and a uint[70]: Array.Copy converts element-wise, so every 32-bit limb receives just one random byte (0..255). The number that results is only ~256 bits of entropy instead of 1024, and it has a rigid structure:

limbs 0..30: one random byte each,
limb 31: 0x80000000 OR a random byte,
genPseudoPrime additionally forces limb[0] |= 1 (the number is odd).

So each prime looks like (in hex) 800000XX 000000YY 000000ZZ ... — every other 3 bytes are 00.

p = 0x800000fe 00000048 000000eb 00000094 ... 0000004b
q = 0x80000068 0000004b 000000ae 000000f6 ... 000000b9

3. Recovering `p` and `q` from `n`

The modulus n (2047 bits) was pulled out of the RSA certificate in the ServerHello. Write

p = (0x80000000 + a) · 2^992 + P,      P = Σ_{i=0}^{30} c_i · 2^(32i)
q = (0x80000000 + b) · 2^992 + Q,      Q = Σ_{i=0}^{30} d_i · 2^(32i)

with a, b, c_i, d_i ∈ [1, 255] and c_0 odd. Since two bytes multiply to at most 255·255 < 2^32, the low digits of n = p·q in base 2^32 have no carries:

digit_k(n) = Σ_{i=0}^{k} c_i · d_{k-i}          (k = 0..30)

This is a digit-by-digit constraint on byte pairs. A simple backtracking search fixes (c_k, d_k) at each step (for k=0 we enumerate factor pairs of n mod 2^32, afterwards solve the linear equation in c_k), producing 66 candidates for the low 31 limbs:

B = 1 << 32
digits = []
x = n
while x:
    digits.append(x & (B - 1))
    x >>= 32

def factor_pairs(x):
    return [(a, x // a) for a in range(1, 256)
            if x % a == 0 and 1 <= x // a <= 255]

c = [0] * 31; d = [0] * 31
solutions = []

def rec(k):
    if k == 31:
        solutions.append((list(c), list(d)))
        return
    if k == 0:
        for cc, dd in factor_pairs(digits[0]):
            if cc % 2 == 1:                 # p must be odd
                c[0], d[0] = cc, dd
                rec(1)
        return
    known = sum(c[i] * d[k - i] for i in range(1, k))
    target = digits[k] - known               # = c_k*d_0 + c_0*d_k
    for ck in range(1, 256):
        num = target - ck * d[0]
        if num > 0 and num % c[0] == 0:
            dk = num // c[0]
            if 1 <= dk <= 255:
                c[k], d[k] = ck, dk
                rec(k + 1)

rec(0)   # -> 66 low-limb candidates

For each candidate the only remaining unknowns are the two top bytes a, b — a 256×256 brute force — and exactly one combination satisfies p · q == n:

for carr, darr in solutions:
    P = sum(carr[i] << (32 * i) for i in range(31))
    Q = sum(darr[i] << (32 * i) for i in range(31))
    for a in range(1, 256):
        pa = ((0x80000000 + a) << 992) + P
        for b in range(1, 256):
            qb = ((0x80000000 + b) << 992) + Q
            if pa * qb == n:
                print(pa, qb)    # -> the real p, q

The whole recovery takes under a second. This is why the textbook attacks (Fermat, Pollard rho, Wiener) all fail: n is not a product of two full-size random primes, it is a product of two highly structured ~256-bit numbers.

4. Decrypting the premaster secret

With p, q known, d = e^{-1} mod (p−1)(q−1). The ClientKeyExchange record holds the RSA-encrypted premaster secret (256 bytes):

n = p * q                     # 2047-bit modulus
d = pow(e, -1, (p-1) * (q-1)) # e = 65537
m = pow(int.from_bytes(pms_enc, 'big'), d, n)

The decrypted value is PKCS#1 v1.5 padded; because the server's .NET BigInteger strips the leading 0x00, the block is 0x02 || PS || 0x00 || PMS. The 48 bytes after the separator are the premaster secret, which begins 03 03 (the TLS client version):

PMS = 0303 3fbee976 3593ed9e 2e63cc1d 52907df0 29993dbe 77598440 5f2ef38d 8b8b3abb ca5be748 20eb215e cd28b7e3 5a4d

5. Deriving the TLS keys

From the decompiled TlsConnection the key schedule is standard TLS 1.2, with two twists:

The client offered the extended master secret extension (type 23) and the server accepted it, so the master secret is derived from the transcript hash instead of the client/server randoms:

if (_extendedMasterSecret)
    _transcript.GetCurrentHash() -> Prf.Compute(premasterSecret, "extended master secret", hash, 48)
else
    Prf.Compute(premasterSecret, "master secret", clientRandom || serverRandom, 48)

The key block is PRF(master, "key expansion", serverRandom || clientRandom, 72) and is split as:

_pendingRead  = new ConnectionState(kb[0..20],  kb[40..56]);  // client write MAC, client write AES key
_pendingWrite = new ConnectionState(kb[20..40], kb[56..72]);  // server write MAC, server write AES key

Prf is the ordinary TLS 1.2 PRF (P_SHA256(secret, label || seed)), reproduced in Python with hmac + SHA-256.

The transcript (all handshake messages up to and including ClientKeyExchange, each prefixed with its 4-byte type/length header) is rebuilt from the pcap records:

ClientHello(1) + ServerHello(2) + Certificate(11) + ServerHelloDone(14) + ClientKeyExchange(16)

6. Decrypting the records

The record protection (RecordProtection) is AES-128-CBC with a random 16-byte IV prepended to the ciphertext, TLS-style padding, and an HMAC-SHA1 over seq_num(8) || content_type(1) || 0x0303 || plaintext_len(2) || plaintext:

def unprotect(mac_key, enc_key, seq, ctype, ct):
    iv, body = ct[:16], ct[16:]
    pt = AES_CBC_decrypt(enc_key, iv, body)
    pad = pt[-1]
    pt = pt[: len(pt) - pad - 1]      # strip TLS padding
    plain, mac = pt[:-20], pt[-20:]
    # verify hmac.new(mac_key, struct.pack(class="hljs-string">&#039;>Q&#039;, seq) + bytes([ctype]) + bclass="hljs-string">&#039;\x03\x03&#039;
    #                      + struct.pack(class="hljs-string">&#039;>H&#039;, len(plain)) + plain, sha1)

Sequences reset to 0 after each ChangeCipherSpec. Decrypting the four post-CCS records on both directions (all MACs verify):

client → server (client write keys)

Finished:  14 00000c <12-byte verify_data>
AppData:   GET / HTTP/1.1\r\nHost: 127.0.0.1:1337\r\nUser-Agent: curl/8.18.0\r\nAccept: */*\r\n\r\n
Alert:     01 00                        (close_notify)

server → client (server write keys)

Finished:  14 00000c <12-byte verify_data>
AppData:   HTTP/1.1 200 OK
           Content-Type: text/plain
           Content-Length: 56
           Connection: close

           gaslightCTF{gu3s5_y0u_n33d_l0ng_sl33v35_ev3n_in_5umm3r?}
Alert:     01 00                        (close_notify)

Flag

gaslightCTF{gu3s5_y0u_n33d_l0ng_sl33v35_ev3n_in_5umm3r?}

TL;DR

The server is a hand-rolled TLS 1.2 HTTPS server; the pcap contains the whole session with cipher suite TLS_RSA_WITH_AES_128_CBC_SHA.
The custom BigInteger.genRandomBits fills a byte[32] and Array.Copys it into 32 uint limbs — each limb ends up being a single random byte. The "1024-bit" primes are really ~256-bit, with every other 3 bytes zero.
Factor n by backtracking over the low 32-bit digits (no carries at the bottom) plus a 2^16 brute force of the two top bytes → recover p, q.
Compute d, decrypt the PKCS#1 premaster secret, derive the master secret (EMS variant) and the AES-128-CBC + HMAC-SHA1 key block with the TLS 1.2 PRF.
Decrypt the post-CCS application records; the HTTP response body is the flag.

GaslightCTF 2026 - CompleteHTTP Writeup