nsa-codebreaker Hard

Task 5 - Going on the Offensive

cryptanalysis aes ecb meet-in-the-middle reverse-engineering key-derivation openssl

This is part of a series on the 2025 NSA Codebreaker Challenge. Start from the beginning.

Challenge

The file appears to be obfuscated… The team is now interested in identifying the adversary’s command-and-control server. Analyze the extracted shared library to decrypt the malware’s communications and recover the C2 server URL.

Objective: Submit the C2 server URL.

Provided files:

  • extracted.so – the shared library extracted from the malware in Task 4
  • key.pem – 2048-bit RSA public key

Wrong Turns

Before digging into the crypto, I tried the obvious: submitting C2 URLs I already knew from earlier tasks.

https://203.0.113.42/module          ← Task 4's C2 IP
https://203.0.113.108:26535/module   ← Task 2's DNS-poisoned IP

Both wrong. This task wasn’t about reusing existing intelligence – it required breaking the malware’s encryption to uncover a new C2 endpoint.

Reversing the Comms Class

The extracted.so is the shared library that Task 4’s malware downloads and dlopens. It links only against libcrypto.so.3 (not libssl) and exports 13 methods of a C++ Comms class: gen_key, connect_to_server, recv_rsa_pubkey, send_aes_keys, rsa_encrypt, send_message, is_correct_response, application_handshake, and full_handshake. Loading it in IDA revealed how the class handles all encrypted communication with the C2 server.

Constructor: Double AES-128-ECB

The Comms::Comms constructor sets up the encryption:

Comms::Comms():
    encA = EVP_EncryptInit_ex(..., EVP_aes_128_ecb, keyA)
    encB = EVP_EncryptInit_ex(..., EVP_aes_128_ecb, keyB)
    decA = EVP_DecryptInit_ex(..., EVP_aes_128_ecb, keyA)
    decB = EVP_DecryptInit_ex(..., EVP_aes_128_ecb, keyB)

Four OpenSSL contexts, two keys. Encryption chains as EncA then EncB; decryption reverses as DecB then DecA. This is textbook double encryption – and it has a textbook weakness.

The Key Generation Catastrophe

Each key is generated by gen_key → generate_key, and this is where the malware author made a critical mistake:

  1. Read 32 bytes from /dev/random (good so far)
  2. Compute H = HMAC(SHA3-256, key="ABCD1233321", data=random32) (still okay)
  3. XOR the upper 16 bytes of the random data with the first 16 bytes of H (fine)
  4. Extract the high 64 bits of the result
  5. Right-shift by 38 bits (0x26)
  6. Write the shifted value back as the key, zero-pad the rest

Step 5 is the catastrophe. A right-shift by 38 bits on a 64-bit value leaves only 26 bits of entropy. The resulting key looks like:

keyA = [4 bytes of data] 00 00 00 00 00 00 00 00 00 00 00 00

Each AES-128 key has an effective keyspace of 2^26 – about 67 million possibilities. That’s brute-forceable on a laptop.

Meet-in-the-Middle Attack

Double encryption with two independent keys is vulnerable to a classic meet-in-the-middle attack. Instead of searching 2^26 × 2^26 = 2^52 combinations, MITM reduces it to 2^26 + 2^26 = 2^27 operations plus a lookup table.

Known Plaintext

The protocol uses a magic/version header followed by command strings. From the binary’s string checks, the first 16-byte block of a connection acknowledgment is:

P = de c0 de c0 ff ee 52 45 51 43 4f 4e 4e 5f 4f 4b
                       R  E  Q  C  O  N  N  _  O  K

The corresponding ciphertext block (captured from the malware’s communications):

C = bb 39 35 59 c5 82 af a5 0b 2e 57 c2 cf 5b 2d c7

The Attack

Since encryption is C = EncB(EncA(P)), there exists an intermediate value M = EncA(P) = DecB(C). The attack finds both keys by meeting at M:

Phase 1 – Build the forward table:

For each stateA in [0, 2^26):
    keyA = LE64(stateA) || 8×0x00
    X = AES_ECB_Encrypt(keyA, P)
    Store tag(X) → stateA in hash table

Phase 2 – Probe from the ciphertext side:

For each stateB in [0, 2^26):
    keyB = LE64(stateB) || 8×0x00
    Y = AES_ECB_Decrypt(keyB, C)
    If tag(Y) found in table:
        Verify full 16-byte match
        → recovered (stateA, stateB)

Implementation

I built the A-side table in chunks of 2^22 states to keep memory reasonable, using 8-byte tags for compact storage with full 16-byte verification on tag collisions. The B-side probing ran in parallel across CPU workers.

One pitfall: the key packing format. I had to try two variants:

  • dup=False: LE64(state) || 8×0x00 (the correct one)
  • dup=True: LE64(state) || LE64(state) (incorrect but worth trying)

Results

The MITM attack found a hit:

stateA = 28,495,123
stateB = 41,530,460

keyA = 13 cd b2 01 00 00 00 00 00 00 00 00 00 00 00 00
keyB = 5c b4 79 02 00 00 00 00 00 00 00 00 00 00 00 00

Decrypting the server’s response packet with DecB → DecA:

de c0 de c0 ff ee 68 74 74 70 73 3a 2f 2f 31 39
38 2e 35 31 2e 31 30 30 2e 31 36 36 2f 6d 61 74
74 65 72 6d 6f 73 74 2f 2d 6a 4c 4d 54 75 75 5a
56 6a 79 57 50

After the 6-byte magic/version header, the ASCII reads:

https://198.51.100.166/mattermost/-jLMTuuZVjyWP

Verification Script

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from Crypto.Cipher import AES

keyA = bytes.fromhex("13cdb201000000000000000000000000")
keyB = bytes.fromhex("5cb47902000000000000000000000000")

def dec_block(c):
    y = AES.new(keyB, AES.MODE_ECB).decrypt(c)
    return AES.new(keyA, AES.MODE_ECB).decrypt(y)

def dec_all(ct_hex):
    ct = bytes.fromhex(ct_hex)
    assert len(ct) % 16 == 0
    return b"".join(dec_block(ct[i:i+16]) for i in range(0, len(ct), 16))

Answer

https://198.51.100.166/mattermost/-jLMTuuZVjyWP

A Mattermost instance – a self-hosted chat platform. The adversary is using it as their C2 communication channel, which is clever: Mattermost traffic over HTTPS looks like normal enterprise chat traffic, making it hard to flag at the network level.

Note: 198.51.100.0/24 is another RFC 5737 documentation range (like 203.0.113.0/24 from earlier tasks). The challenge consistently uses reserved IP space for adversary infrastructure.

Takeaways

  • Key derivation can silently destroy entropy. The malware reads 32 bytes from /dev/random and runs it through HMAC-SHA3-256 – all sounds secure. But one right-shift by 38 bits collapses 128-bit keys to 26-bit keys. Always trace the full key derivation path.
  • Double encryption doesn’t double the security. Double AES with independent keys should provide 2^256 security. MITM reduces it to 2×2^128. But when each key only has 26 bits, MITM turns it into 2×2^26 – trivially brute-forceable.
  • ECB mode enables block-wise attacks. Each 16-byte block encrypts independently, so you can attack one block at a time with known plaintext. CBC or GCM would have made this significantly harder.
  • Protocol framing gives you known plaintext. The c0 de c0 de ff ee magic header + REQCONN_OK string are predictable. Real protocols should avoid fixed plaintext in encrypted streams, or at minimum use authenticated encryption modes.