Always Has Been - HackTheBox Challenge Writeup

Challenge Information

Description

To be honest, rolling your own crypto has always been pretty easy.

The challenge ships a custom, “hardened” hashing scheme (securehash.py) built entirely from scratch — a homebrew S-box, a fixed bit permutation, and a hundred rounds of key mixing, plus a comment bragging that “No linear or differential cryptanalysis here!” The provided artifact is a single 64-character hex digest, and the goal is to recover the original 32-byte input (the flag) that produces it.

Solution

Artifact recovery

The extracted challenge directory only contained a 0-byte output.txt, which looked broken at first glance. Listing the contents of the distributed zip (unzip -l) showed the real files inside had non-zero sizes — meaning the archive was password-protected and staging extraction had silently failed. Re-extracting with the standard HackTheBox archive password recovered the real files:

unzip -o -P hackthebox challenge.zip

This produced two files:

• output.txt — a 64-character hex digest (the hash output)
• securehash.py — the homebrew hash implementation

Cracking the “custom crypto”

securehash.py computes the digest as:

# Simplified reconstruction of the challenge's hashing scheme
state = bytes(32)              # 0^32
state = xor(state, encrypt(flag, key=flag))   # state = 0^32 XOR E_flag(flag)
digest = state

Because the flag is exactly 32 bytes — one full block — the key and the plaintext being encrypted are the same value. That means the digest is really just E_k(k): the cipher encrypting its own key.

Each of the 100 rounds inside encrypt() does three things:

# One round of the custom cipher
for i in range(32):
    sbox[i] = KEY_SBOX[i] ^ key[0]     # "S-box" — really just XOR with key[0]
state = permute(state, FIXED_PERMUTATION)   # a fixed 256-bit bit permutation
state = xor(state, key)                     # key mixing

The comment in the source claims immunity to linear and differential cryptanalysis — but the “S-box” isn’t a real S-box at all. It’s a lookup table XORed with a single key byte:

# Verifying the S-box is affine (GF(2)-linear) by brute force
for i in range(65536):
    a = i >> 8
    b = i & 0xFF
    assert (KEY_SBOX[a] ^ KEY_SBOX[0]) ^ (KEY_SBOX[b] ^ KEY_SBOX[0]) == \
           KEY_SBOX[a ^ b] ^ KEY_SBOX[0]
# Holds for all 65536 pairs -> S-box construction is GF(2)-linear (affine)

Since KEY_SBOX[i] ^ KEY_SBOX[0] is linear over GF(2) for every input, the “S-box” step is nothing but an affine map. Combined with the fixed bit permutation (also linear) and the XOR key mixing (affine), the entire 100-round cipher is affine over GF(2) — the exact opposite of what the source comment claims.

Building the linear model

Because the linear component T = P ∘ Lin_S (permutation composed with the S-box’s linear part) doesn’t depend on the key at all — the key only shifts the S-box by a constant — the whole cipher collapses to a closed-form affine equation:

hash = (T^100 + M)(k)  XOR  M(P(c_vec))

where:
  M      = T^0 + T^1 + T^2 + ... + T^99      (sum of all round-linear-maps, over GF(2))
  c_vec  = (170 XOR key[0]) repeated 32 times

T^100 and M are both 256×256 GF(2) matrices that can be precomputed once (they’re entirely key-independent). The only remaining unknown is a single byte, key[0], which appears both as the affine offset and inside c_vec.

Solving the system

# For each of the 256 possible values of key[0]:
#   1. Build c_vec = (170 ^ guess) * 32
#   2. Form the linear system (T^100 + M)(k) = digest XOR M(P(c_vec))
#   3. Solve over GF(2) via Gaussian elimination
#   4. Enumerate the nullspace for all solutions (system may be underdetermined)
#   5. Keep only solutions whose k[0] byte matches the guessed value

candidates = []
for guess in range(256):
    c_vec = bytes([170 ^ guess] * 32)
    rhs = xor(digest, apply(M, permute(c_vec)))
    A = matrix_sum(T_pow(100), M)          # (T^100 + M), 256x256 over GF(2)
    for k in solve_gf2_nullspace(A, rhs):
        if k[0] == guess:
            candidates.append(k)

This produced two surviving candidates for the 32-byte key (i.e. the flag). Re-encrypting each candidate through the original securehash.py and comparing against the target digest identified the correct one and confirmed it decodes to a valid, readable flag.

Key Steps

1. Recovered the password-protected challenge archive with unzip -P hackthebox.
2. Read securehash.py and identified state = 0^32 XOR E_flag(flag) — a self-encrypting single-block hash.
3. Brute-forced all 65,536 S-box input pairs to prove KEY_SBOX[i] ^ KEY_SBOX[0] is GF(2)-linear, exposing the “S-box” as a disguised affine map.
4. Derived a closed-form affine expression for the 100-round cipher: hash = (T^100 + M)(k) XOR M(P(c_vec)), with T/M precomputable and key-independent.
5. Brute-forced the single unknown byte key[0] (256 guesses), solving a 256×256 GF(2) linear system and enumerating its nullspace for each guess.
6. Filtered candidates by self-consistency (k[0] == guess), yielding two surviving 32-byte candidates.
7. Verified by re-running the original hash function on each candidate and matching against the target digest.

Tools Used

• Python (custom GF(2) linear algebra: Gaussian elimination, nullspace enumeration, matrix exponentiation)
• unzip (password-protected archive recovery)
• Manual cryptanalysis of a homebrew cipher (linearity testing, affine-cipher reduction)

Key Learnings

• A cipher’s individual components can each look nonlinear at a glance (a lookup table, a permutation, a keyed XOR) while still composing into something fully affine over GF(2) — always test claimed nonlinear primitives (like S-boxes) for linearity before trusting them.
• Hashing by “encrypt the input with itself as the key” (E_flag(flag)) collapses a stream/block cipher into a known-plaintext-equals-key scenario, which is a serious design smell — recovering the key becomes equivalent to recovering the plaintext.
• Once a cipher is proven affine, the whole system reduces to solving a linear system over GF(2); any small residual keyspace (here, a single byte) can just be brute-forced around the linear solve.
• “Rolling your own crypto” bugs often hide in claims made directly in the source comments — the challenge’s own assertion of immunity to linear cryptanalysis was the exact property that broke it.
• Corrupted or 0-byte artifacts from challenge staging are often just password-protected zips extracted incorrectly — always check unzip -l for real file sizes before assuming data loss.