Slani Kreker (Salty Cracker)

Task description

Što napraviti s presoljenim krekerom? (What do you do with an over-salted cracker?)

How the flag got encrypted

A generator script builds a random text where each of fourteen specific letters (e, t, a, o, i, n, s, r, h, l, d, c, u, m) appears some number of times, picks five of those letters (in order) and five arithmetic operations (add one, double, or triple), applies each operation to its letter’s count in the generated text, and concatenates the five results. If that concatenation comes out to exactly twelve digits, it becomes the PIN, which is the flag’s content.

The PIN then goes through a chain:

pad = PBKDF2_HMAC_SHA256(",".join(letters), b'STATIC_SALT', 10000)[:16]
h = XOR(MD4(PIN), pad)
h_bridged = AES_ECB_encrypt(MD5(hex(k_bridge)), h)          # k_bridge: 0–255
ciphertext = AES_ECB_encrypt(MD5(hex7(k_right)), h_bridged)  # k_right: 0–0xFFFFFFF

The generated text and the final ciphertext are both handed over; the five chosen letters, the five operations, and both AES keys are not.

Why the salt is the actual weakness

PBKDF2 exists specifically to make brute-forcing a derived key expensive, and a random, per-use salt is what forces an attacker to redo that expensive work for every single guess. Here the salt is b'STATIC_SALT', fixed and identical no matter what the five letters or operations turn out to be. That means the PBKDF2 computation itself, over every possible choice of five letters and five operations, can be done once, in bulk, ahead of time, rather than repeated per candidate.

Step 1: counting what’s actually in the text

Counting occurrences of each of the fourteen tracked letters in the provided text, and applying each of the three operations to each count, gives a small table of candidate digit-group values. A valid PIN needs exactly twelve digits from five concatenated groups, which works out to exactly two three-digit groups and three two-digit groups; filtering all P(14, 5) = 240,240 ordered letter choices times 3^5 = 243 operation combinations down to only those producing exactly 12 digits leaves about 21.7 million valid candidate PINs, each with its own computable h = XOR(MD4(PIN), PBKDF2_pad), since the pad depends only on the letter ordering. Computing all 21.7 million pads in parallel (32 worker processes) took about 100 seconds.

Step 2: brute-forcing the two AES keys

k_bridge has only 256 possible values, trivial on its own. k_right has about 268 million, the actual bottleneck, and testing every combination of the two against every one of the 21.7 million candidate h values directly would be 268 million times 21.7 million times 256, far too much.

A meet-in-the-middle approach splits this in half instead:

1. Precompute, once, decrypting from the ciphertext side: for every one of the 268 million k_right values, decrypt the ciphertext with it, keeping the result (h_bridged[kr]) in a hash table keyed by its first 8 bytes. Written in C with OpenSSL and OpenMP, this took about 40 seconds. A plain sorted array and binary search was tried first and discarded, since random access into a 3.2 GB array caused heavy cache misses; an open-addressing hash table at roughly 50% load factor brought average lookups down to about 1.5 memory accesses each.
2. For each of the 21.7 million candidate h values, times each of the 256 k_bridge values: encrypt forward from h instead, and check whether the first 8 bytes match anything in the precomputed table. On a prefix match, verify the full 16 bytes by actually recomputing. That’s 5.6 billion lookups total, but each one is an O(1) hash table probe rather than a full decryption, and with 32 threads it completed in about 51 seconds.

The code

Step 1, generating every candidate PIN and its matching h value:

from itertools import permutations, product
from hashlib import pbkdf2_hmac

OPS = [lambda n: n + 1, lambda n: n * 2, lambda n: n * 3]
counts = {letter: text.count(letter) for letter in "etaoinsrhldcum"}

candidates = {}
for letters in permutations(counts, 5):
    pad = pbkdf2_hmac('sha256', ",".join(letters).encode(), b'STATIC_SALT', 10000)[:16]
    for ops in product(range(3), repeat=5):
        pin = "".join(str(OPS[o](counts[l])) for l, o in zip(letters, ops))
        if len(pin) == 12:
            h = bytes(a ^ b for a, b in zip(md4(pin.encode()), pad))
            candidates[h] = pin

Step 2, the meet-in-the-middle brute force (sketch; the real version is threaded C using OpenSSL’s AES and a 536M-slot open-addressing hash table):

// precompute: for every k_right, decrypt the ciphertext once, store h_bridged[0:8] -> k_right
for (uint32_t kr = 0; kr < 0x10000000; kr++) {
    aes_ecb_decrypt(md5_key_from(kr, 7), ciphertext, h_bridged);
    hashtable_insert(table, h_bridged, 8, kr);
}

// search: for every candidate h and every k_bridge, encrypt forward and probe the table
for each (h, pin) in candidates:
    for (int kb = 0; kb < 256; kb++) {
        aes_ecb_encrypt(md5_key_from(kb, -1), h, h_bridged_candidate);
        if ((kr = hashtable_lookup(table, h_bridged_candidate, 8)) != NOT_FOUND
            && aes_ecb_decrypt_full_matches(kr, ciphertext, h_bridged_candidate))
            report(pin, kb, kr);
    }

The match

k_bridge = 50, k_right = 200958939
h = 3aaa4dd36ff804d691b68c3102840331  →  PIN = 671021594162

Verified end to end through the entire chain, computing MD4("671021594162"), XORing with the recovered PBKDF2 pad, and running both AES layers forward, reproduces the given ciphertext exactly.

Result

CTF2026[671021594162]

The one design choice that made this feasible

Every brute-force step here (21.7 million PBKDF2 computations, 268 million AES decryptions, 5.6 billion table lookups) is large but was still finishable within a few minutes on ordinary multi-core hardware specifically because the static salt let the slowest, most expensive piece (PBKDF2) be precomputed entirely in bulk, rather than recomputed once per candidate key, the exact protection a per-use salt is meant to provide.