NERV Center — CTF Writeup

Category: Crypto / Pwn Author: Brendan Dolan-Gavitt (moyix) Description: Get into the server, Shinji. Or Rei will have to do it again.

Overview

NERV Center is a stripped x86-64 Linux binary that implements an Evangelion-themed server with RSA-based authentication. The server generates a 1024-bit RSA key on each connection, and the flag is only accessible after authenticating by signing a random challenge. The flag is then sent encrypted with AES-256-GCM, with the AES key RSA-encrypted using the session's public key.

The intended exploit chain is:

1. Pwn: Overflow the fd_set used in select() to gain write control over the stored RSA public key modulus
2. Crypto: Choose the overwritten key bits to make the modulus prime, allowing trivial private key computation

Reverse Engineering

Server Architecture

The binary is a forking TCP server (default port 2000). On each control connection it:

• Forks a child process
• Generates a fresh 1024-bit RSA keypair (RSA_generate_key_ex)
• Stores the 128-byte modulus at offset 0x270 in a session struct (calloc(1, 0x2f0))
• Opens a sensor port (starting at 2001) that accepts many simultaneous connections via select()
• Presents a menu: Authenticate, Print public key, Halt/Resume sensors, MAGI status, Help, Exit

Authentication requires signing a 32-byte random challenge with RSA-SHA256 (PKCS#1 v1.5). Upon success, an authenticated menu offers "Send flag," which encrypts flag.txt with AES-256-GCM and RSA-encrypts the AES key with the session's public modulus.

Session Struct Layout

Offset  Size   Field
0x000   4      Sensor listen socket fd
0x004   4      Control connection fd
0x008   4      Auth status (0=unpriv, 1=admin)
0x010   8      Max open files
0x018   8      Connection array pointer
0x028   40     Mutex (pause)
0x050   48     Condition variable
0x080   48     Condition variable
0x0B0   4+4    Sensor state + ack flag
0x0B8   40     Mutex (fd_set protection)
0x0E0   128    read fd_set
0x168   128    write fd_set
0x1F0   128    except fd_set    <-- overflow source
0x270   128    RSA modulus N    <-- overflow target

The select() Loop

The sensor thread runs a tight loop:

while (1) {
    usleep(100);
    lock(fd_set_mutex);
    // Clear fd_sets (indices 0-15 only = 128 bytes each)
    // FD_SET for listen socket and ALL connected sensor fds
    select(max_fd + 1, &read_fds, &write_fds, &except_fds, &timeout);
    unlock(fd_set_mutex);
    // ... process results
}

The file descriptor limit is set to 1088 (setrlimit(RLIMIT_NOFILE, 1088)), so fds can range from 0 to 1087. The sensor connection array also holds up to 1088 entries.

Vulnerability: fd_set Overflow

On Linux x86-64, fd_set is 128 bytes (1024 bits), supporting fds 0–1023. When the code does FD_SET(fd, &except_fds) for fd >= 1024, it writes beyond the 128-byte fd_set boundary:

except fd_set:  0x1F0 — 0x26F  (fds 0-1023, cleared each cycle)
RSA modulus:    0x270 — 0x2EF  (fds 1024-2047 map here)

For fd 1024: fds_bits[16] is at offset 0x1F0 + 128 = 0x270 — the first byte of the RSA modulus.

Fds 1024–1087 map to the first 8 bytes (64 bits) of the 128-byte modulus. The clearing loop only covers indices 0–15 (the legitimate fd_set range), so the overflow area at 0x270+ is not cleared by the application code.

However, select() itself is called with nfds = max_fd + 1 > 1024, so the kernel reads and writes the overflow area too. After select() returns:

• Bits for fds with exceptions (TCP OOB data) → set to 1
• Bits for fds without exceptions → set to 0

This gives us precise write control over the top 64 bits of the RSA modulus.

Exploitation

Step 1: Exhaust File Descriptors

Open ~1077 TCP connections to the sensor port. The first sensor connection gets fd 11 (fds 0–10 are used by stdio, Rosetta, listen socket, and control connection). The last gets fd 1087, producing 64 overflow fds (1024–1087).

for i in range(1077):
    s = socket.socket()
    s.connect((host, sensor_port))
    # Parse "This is sensor ID <fd>." from welcome message

Step 2: Free Server-Side File Descriptors

All 1088 fds are now in use. The flag handler needs fopen("flag.txt") which requires a spare fd. Send QUIT commands on ~15 low-numbered sensor connections while the sensor thread is still running — this causes the server to close() those fds.

for s, fd in conns:
    if fd < 1024 and freed < 15:
        s.sendall(b'QUIT\n')

Step 3: Choose a Prime Modulus

Read the current public key (menu option 2) to learn the original modulus N. Extract the bottom 960 bits:

bottom_960 = N & ((1 << 960) - 1)

Search for a 64-bit value top64 such that N' = top64 * 2^960 + bottom_960 is prime. Constraints:

• (top64 >> 56) & 0xFF != 0 — the first key byte must be nonzero (server validation)
• N' must be odd — guaranteed since the original N is odd (product of two odd primes)

By the prime number theorem, roughly 1 in 710 candidates is prime. Starting from 0x0100000000000001 and stepping by 2, a prime is typically found within a few hundred iterations.

c = 0x0100000000000001
while True:
    n_prime = c * (1 << 960) + bottom_960
    if is_probable_prime(n_prime):  # Miller-Rabin
        break
    c += 2

Step 4: Set Key Bits via TCP OOB Data

Convert top64 to the set of fds that need OOB data. The key is stored big-endian at address 0x270, but the fd_set word is little-endian:

key_bytes = top64.to_bytes(8, 'big')  # [MSB, ..., LSB]
for byte_idx in range(8):
    for bit in range(8):
        if key_bytes[byte_idx] & (1 << bit):
            oob_fds.add(1024 + byte_idx * 8 + bit)

Send a single OOB byte on each needed connection:

for fd in oob_fds:
    fd_to_socket[fd].send(b'X', socket.MSG_OOB)

After the next select() cycle, the kernel sets exception bits for fds with OOB data and clears the rest. The modulus at 0x270 now contains our chosen top64 in its first 8 bytes.

Note: Docker's port forwarding strips TCP OOB data. The exploit must run inside the container or on the same host.

Step 5: Freeze the Key

The key oscillates between two states each select() cycle:

• During FD_SET: all 64 overflow bits set (all sensor fds are connected)
• After select(): only OOB exception bits set (our desired value)

Use menu option 3 ("Issue sensor system halt") to pause the sensor thread. It halts after completing the current select() cycle, freezing the key in the correct post-select state. Verify by printing the public key:

ctrl.sendall(b'3\n')  # Halt sensors
# ... then print key to verify

Step 6: Authenticate

Since N' is prime, compute the private exponent directly:

d = pow(65537, -1, n_prime - 1)  # φ(p) = p-1 for prime p

The server's RSA_verify(NID_sha256, challenge, 32, sig, siglen, rsa) passes the raw challenge bytes as the digest (it does not hash them again). Create a PKCS#1 v1.5 signature:

digest_info = DER_SHA256_PREFIX + challenge_bytes  # NOT sha256(challenge)!
padded = b'\x00\x01' + b'\xff' * pad_len + b'\x00' + digest_info
signature = pow(int.from_bytes(padded, 'big'), d, n_prime)

Step 7: Decrypt the Flag

Request "Send flag" from the authenticated menu. The server encrypts with AES-256-GCM and RSA-OAEP:

Format: [64-bit ciphertext_len][ciphertext][16-byte GCM tag][12-byte IV][RSA(aes_key)]

Decrypt the RSA-OAEP layer (SHA-1 MGF1) to recover the 32-byte AES key, then decrypt the ciphertext:

aes_key_padded = pow(rsa_ciphertext, d, n_prime)
aes_key = oaep_unpad(aes_key_padded)
flag = AES_GCM_decrypt(key=aes_key, iv=iv, ciphertext=ct, tag=tag)

Key Insights

1. fd_set is a fixed-size bitmap. Using select() with fds >= FD_SETSIZE (1024) causes out-of-bounds memory access. The binary raises the fd limit to 1088 but doesn't use poll()/epoll().

2. select() writes back results, zeroing bits for non-ready fds. This turns the overflow from a simple "set bits" primitive into precise byte-level write control via TCP OOB exceptions.

3. A prime modulus breaks RSA. Normal RSA has N = p·q with secret factorization. If N is prime, φ(N) = N−1 is trivially computable, yielding the private key immediately.

4. The sensor halt freezes the key. Without halting, the key oscillates every millisecond between "all bits set" (during FD_SET) and "OOB bits only" (after select). Halting the sensor thread after a select cycle captures the desired state.

5. File descriptor exhaustion. Opening enough connections to reach fd 1087 uses all 1088 allowed fds. The flag handler's fopen() then fails with EMFILE. Sending QUIT on low-numbered connections before halting frees server-side fds for file operations.

Solve Script

See exploit.py.