CompleteHTTP

We’re provided with two files: complete-http and complete-http.pcapng. Take a glance around, complete-http.pcapng is a Wireshark capture of a few packets of HTTPS traffic and complete-http is a simple .NET web server:

ilSpy view of complete-http.CompleteHttp.Program

// complete-http, Version=0.0.1.0, Culture=neutral, PublicKeyToken=null
// CompleteHttp.Program
using System;
using System.IO;
using System.Net;
using System.Net.Sockets;
using System.Security.Cryptography.X509Certificates;
using System.Threading;
using System.Threading.Tasks;
using CompleteHttp.Crypto;
using CompleteHttp.Tls;

internal static class Program
{
	private static async Task Main(string[] args)
	{
		int num = ((args.Length != 0 && int.TryParse(args[0], out var result)) ? result : 1337);
		using X509Certificate2 certificate = CertificateProvider.CreateCertificate();
		TcpListener listener = new TcpListener(IPAddress.Any, num);
		listener.Start();
		Console.WriteLine($"listening on 0.0.0.0:{num}");
		while (true)
		{
			HandleAsync(await listener.AcceptTcpClientAsync(), certificate);
		}
	}

	private static async Task HandleAsync(TcpClient client, X509Certificate2 certificate)
	{
		using (client)
		{
			client.NoDelay = true;
			await using NetworkStream stream = client.GetStream();
			using TlsConnection conn = new TlsConnection(stream, certificate);
			try
			{
				await conn.HandshakeAsync(CancellationToken.None);
				await conn.ServeApplicationDataAsync(CancellationToken.None);
				await conn.SendAlertAsync(AlertLevel.Warning, AlertDescription.CloseNotify, CancellationToken.None);
			}
			catch (TlsAlertException ex)
			{ // ...
			}
			catch (IOException)
			{
			}
			catch (Exception ex3)
			{ // ...
			}
		}
	}

	private static async Task TrySendAlertAsync(TlsConnection conn, AlertLevel level, AlertDescription description)
	// ...
}

Let’s examine the C# first. Looking at the main program, we quickly determine that this is basically just a super duper simple HTTPS server. We identify await conn.ServeApplicationDataAsync(CancellationToken.None); as the code that serves requests, digging deeper:

public async Task ServeApplicationDataAsync(CancellationToken ct)
{
	StringBuilder buffer = new StringBuilder();
	string text = string.Empty;
	while (!text.Contains("\r\n\r\n", StringComparison.Ordinal))
	{
		var (contentType, bytes) = await ReadRecordAsync(ct);
		switch (contentType)
		{
		case ContentType.Alert:
			return;
		default:
			throw new TlsAlertException(AlertDescription.UnexpectedMessage, $"unexpected {contentType} in application phase");
		case ContentType.ApplicationData:
			buffer.Append(Encoding.ASCII.GetString(bytes));
			if (buffer.Length > 16384)
			{
				throw new TlsAlertException(AlertDescription.DecodeError, "request too large");
			}
			text = buffer.ToString();
			break;
		}
	}
	bool num = text.StartsWith("GET ", StringComparison.Ordinal);
	string text2 = (num ? "200 OK" : "400 Bad Request");
	string text3 = (num ? (Environment.GetEnvironmentVariable("FLAG") ?? "gaslightCTF{fake_flag}") : "bad request");
	byte[] bytes2 = Encoding.UTF8.GetBytes("HTTP/1.1 " + text2 + "\r\nContent-Type: text/plain\r\n" + $"Content-Length: {Encoding.UTF8.GetByteCount(text3)}\r\n" + "Connection: close\r\n\r\n" + text3);
	await WriteRecordAsync(ContentType.ApplicationData, bytes2, ct);
}

Interesting! The code reads up until when a response is expected, checks if its a GET request, and returns the flag. However, it was transmitted over TLS, so the packets are encrypted. Therefore, we can identify the primary roadblock in this challenge as reversing and breaking the TLS encryption used to transmit those packets!

Let’s look at how the connection was established back in Wireshark:

Frame 7: Packet, 114 bytes on wire (912 bits), 114 bytes captured (912 bits) on interface lo0, id 0
Null/Loopback
Internet Protocol Version 4, Src: 127.0.0.1, Dst: 127.0.0.1
Transmission Control Protocol, Src Port: 1337, Dst Port: 55246, Seq: 1, Ack: 136, Len: 58
Transport Layer Security
    [Stream index: 0]
    TLSv1.2 Record Layer: Handshake Protocol: Server Hello
        Content Type: Handshake (22)
        Version: TLS 1.2 (0x0303)
        Length: 53
        Handshake Protocol: Server Hello
            Handshake Type: Server Hello (2)
            Length: 49
            Version: TLS 1.2 (0x0303)
            Random: 0592b9ce2974e72c59eb8032ef4d8846701ba9159df67b86245964c2deef69dc
            Session ID Length: 0
            Cipher Suite: TLS_RSA_WITH_AES_128_CBC_SHA (0x002f)
            Compression Method: null (0)
            Extensions Length: 9
            Extension: renegotiation_info (len=1)
            Extension: extended_master_secret (len=0)
            [JA3S Fullstring: 771,47,65281-23]
            [JA3S: c3310668bb105ecf18dd132480752254]

We see TLS_RSA_WITH_AES_128_CBC_SHA as the cipher suite. Something like TLS_RSA instead of TLS_ECDHE is problematic because it lacks forward secrecy. This means that if we manage to recover the server’s private key, we can obtain the premaster secret and decrypt the flag. Let’s go back to the server and carefully inspect how it generates the private key.

private static async Task Main(string[] args)
{
	int num = ((args.Length != 0 && int.TryParse(args[0], out var result)) ? result : 1337);
	using X509Certificate2 certificate = CertificateProvider.CreateCertificate(); // <--- X509 certificate generated here
	TcpListener listener = new TcpListener(IPAddress.Any, num);
	listener.Start();
	Console.WriteLine($"listening on 0.0.0.0:{num}");
	while (true)
	{
		HandleAsync(await listener.AcceptTcpClientAsync(), certificate);
	}
}

public static X509Certificate2 CreateCertificate()
{
	System.Numerics.BigInteger bigInteger = CompleteHttp.Crypto.BigInteger.genPseudoPrime(1024, PublicExponent); // <--- custom prime generator
	System.Numerics.BigInteger bigInteger2;
	do
	{
		bigInteger2 = CompleteHttp.Crypto.BigInteger.genPseudoPrime(1024, PublicExponent); // <--- why custom??? very very very bad idea
	}
	while (bigInteger2 == bigInteger);
	if (bigInteger < bigInteger2)
	{
		System.Numerics.BigInteger bigInteger3 = bigInteger2;
		bigInteger2 = bigInteger;
		bigInteger = bigInteger3;
	}
	using RSA rSA = RSA.Create();
	rSA.ImportParameters(BuildParameters(bigInteger, bigInteger2));
	CertificateRequest certificateRequest = new CertificateRequest("CN=complete-http", rSA, HashAlgorithmName.SHA256, RSASignaturePadding.Pkcs1);
	DateTimeOffset utcNow = DateTimeOffset.UtcNow;
	return certificateRequest.CreateSelfSigned(utcNow.AddDays(-1.0), utcNow.AddYears(1));
}

public static System.Numerics.BigInteger genPseudoPrime(int bits, System.Numerics.BigInteger publicExponent)
{
	if (bits % 32 != 0)
	{
		throw new ArgumentException("bit length must be a whole number of limbs", "bits");
	}
	CompleteHttp.Crypto.BigInteger bigInteger = new CompleteHttp.Crypto.BigInteger();
	System.Numerics.BigInteger bigInteger2;
	// below code should correctly implement math described in RFC 8017 § 3.2 (https://datatracker.ietf.org/doc/html/rfc8017#section-3.2)
	// if so, then where is the problem?
	do
	{
		bigInteger.genRandomBits(bits); // <--- is the problem here..?
		bigInteger.bignumLimbs[0] |= 1u;
		bigInteger2 = bigInteger.ToBigInteger();
	}
	while (!System.Numerics.BigInteger.GreatestCommonDivisor(bigInteger2 - 1, publicExponent).IsOne || !IsProbablePrime(bigInteger2));
	return bigInteger2;
}

public void genRandomBits(int bits)
{
	// oh...
	int num = bits / 32;
	byte[] array = new byte[num];
	rngProvider.GetNonZeroBytes(array);
	Array.Copy(array, 0, bignumLimbs, 0, num);
	bignumLimbs[num - 1] |= 2147483648u;
	dataLength = num;
}

let’s step through this.

private readonly uint[] bignumLimbs = new uint[70];

...

int num = 1024 / 32; // = 32 is supposed to be the limb count
byte[] array = new byte[num]; // we allocate a 32 BYTE array, which is 32 * 8 = 256 bits, NOT 1024
rngProvider.GetNonZeroBytes(array); // fill this 32 byte array with cryptographically secure random NON-ZERO bytes
Array.Copy(array, 0, bignumLimbs, 0, num); // we copy the byte[] array into uint[], more on this later
bignumLimbs[num - 1] |= 2147483648u; // set the 32nd high bit high
dataLength = num;

when we try and copy the byte[] array into a uint[] array, Array.Copy will automatically perform a lossless widening copy operation, padding the extra space so that each output element maps to exactly one input element, NOT the other way around.

What this means is that if we have a 32 array of bytes 0x43 0x43 ... 0x43 and we try and copy it into our uint[] bignumLimbs, they become 0x00000043 0x00000043 0x00000043 0x00000043 and the remaining bytes are dropped.

[num - 1] references the last uint in the array, which is actually the most significant uint. |= 2147483648u sets the very first bit high. We know that this uint[] is little endian because in public static System.Numerics.BigInteger genPseudoPrime(int bits, System.Numerics.BigInteger publicExponent), bigInteger.bignumLimbs[0] |= 1u; should make the number odd by forcing the last bit high.

The resulting number only has 32 bits of entropy, and those bytes also can’t be zero, decreasing entropy slightly further. For those who prefer math:

$$p_0 \dots p_{30}, q_0 \dots q_{30} \in [1, 255]$$ $$p_{31}, q_{31} \in [\text{0x80000001}, \text{0x800000ff}]$$ $$B = 2^{32}$$ $$p_0 + p_1 \cdot B + p_2 \cdot B^2 + \dots + p_{31} \cdot B^{31} = p$$ $$q_0 + q_1 \cdot B + q_2 \cdot B^2 + \dots + q_{31} \cdot B^{31} = q$$ $$\lambda(n)=\operatorname{lcm}(p-1,q-1)=\frac{(p-1)(q-1)}{\gcd(p-1,q-1)}$$

Armed with this knowledge, we can simply brute force the factorization of such small numbers:

extract the certificate bytes from the handshake

from cryptography import x509
from cryptography.hazmat.primitives.asymmetric import rsa
from cryptography.hazmat.primitives import serialization
from math import gcd

CERT = "308202af30820197a003020102020856a5b736f1bc88dc300d06092a864886f70d01010b05003018311630140603550403130d636f6d706c6574652d68747470301e170d3236303831313132323233385a170d3237303831323132323233385a3018311630140603550403130d636f6d706c6574652d6874747030820121300d06092a864886f70d01010105000382010e003082010902820100400000b30000677980006876800121f90001a6ec8002597080022c028002a19a8002cae68002d8848002f1bf8002d772000331d180038f5100039aef0003b3ac0003f52e800439a50003ef180003978480043d4e0003c2d60003c9300003e6e28003f2cc800414660004ea0c80053cb8000585e880056948000524af8004bf6f000506050005006a000493bc000479bb00047163000370d8000364e500037cca00033b65000345010002fb4600027bc10002441e000216c60001bbb40001bf1f0001a3ee0001a8410001476b000163ce000181100001027f00018669000188d40001021400013ff8000092f1000066210000795e00003c5c00003651000036330203010001300d06092a864886f70d01010b0500038201010003c971ec71d0dfa0d05badc52f747e4cc501eb6e3de14b9826aa8b5288912ce28344e5e721df71afb7be1acf38533a8d1f6fbb1a02b1460c7c4d5cc32558041b7ad0b3923b9a722f93d82f9b54f04ecfe4d8e1f42ebe43f6c0f3c1bce0292be3c3743cbc74b5584158924076fdc587c94c1b6c9e1fd2795359159fb32df205a86c97505d3b71a5d1177be4fbdced41b2eddeb749dbcc1f24c253805e0ef31a28bbcc462dfca7e5e10a82a1e8499a7b5ee2e7798bd80577ab8066a29d4100b9517ccf7da6126dce7473b5222ae7d9143b6a61abfa0195fb5fceed35894ce65da823d49b02a0c3a85b69918db77e0401c07f61a63d55455bdcbf6a10a1d9156fee"

pubkey = x509.load_der_x509_certificate(bytes.fromhex(CERT)).public_key().public_numbers()
n, e = pubkey.n, pubkey.e

BASE = 1 << 32
limbs = [(n >> (32 * i)) & (BASE - 1) for i in range(64)]

def recover_limb(candidates, i, _range):
    if i == 0:
        return [([p0], [limbs[0] // p0], 0) for p0 in _range if limbs[0] % p0 == 0 and limbs[0] // p0 in _range]

    next_candidates = []
    for limbs_p, limbs_q, carry in candidates:
        # see math
        mid = sum(limbs_p[j] * limbs_q[i - j] for j in range(1, i))
        p0_inv = pow(limbs_p[0], -1, BASE)

        for p_limb in _range:
            q_limb = ((limbs[i] - carry - mid - limbs_q[0] * p_limb) * p0_inv) % BASE
            if q_limb not in _range: continue

            total = carry + mid + limbs_q[0] * p_limb + limbs_p[0] * q_limb
            if total % BASE == limbs[i]:
                next_candidates.append((limbs_p + [p_limb], limbs_q + [q_limb], total // BASE))

    return next_candidates

# recover limbs
candidates = []
for i in range(0, 32):
    candidates = recover_limb(candidates, i, range(0x00000001, 0x00000100) if i < 31 else range(0x80000001, 0x80000100))

# recover p and q
p = q = None
for p_limbs, q_limbs, _ in candidates:
    p = sum(limb << (32 * i) for i, limb in enumerate(p_limbs))
    q = sum(limb << (32 * i) for i, limb in enumerate(q_limbs))
    if p * q == n: break
if p * q != n:
    print("failed to recover p and q")
    exit()

# see math
exp = pow(e, -1, (p - 1) * (q - 1) // gcd(p - 1, q - 1))
privkey = rsa.RSAPrivateNumbers(p=p, q=q, d=exp, dmp1=exp % (p - 1), dmq1=exp % (q - 1), iqmp=pow(q, -1, p), public_numbers=rsa.RSAPublicNumbers(e, n)).private_key()

with open("key.pem", "wb") as f:
    f.write(privkey.private_bytes(serialization.Encoding.PEM, serialization.PrivateFormat.TraditionalOpenSSL, serialization.NoEncryption()))

print(f"wrote privkey")

Running it, we calculate the server’s private key:

Loading this into Wireshark, we can view the packet containing the server’s response and extract the flag.

viewing the flag

gaslightCTF{gu3s5_y0u_n33d_l0ng_sl33v35_ev3n_in_5umm3r?}