Always Has Been
Always Has Been
Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: affine_sbox_detection, gaussian_elimination_gf2, key_equals_plaintext_reduction, linearization_attack, symbolic_bit_propagation
Summary
Walkthrough of the CUSTOM Crypto Always Has Been. Task: a custom SecureHash built on a home-rolled SecureCipher (key-dependent S-box, bit permutation, 100 rounds) digests the 32-byte flag; recover it from a single hex digest. Solution: the S-box is a
Description
Challenge Scenario: To be honest, rolling your own crypto has always been pretty easy.
Provided (password-protected zip, password hackthebox):
securehash.py— a custom hash built on a custom block cipher.output.txt— the hex digest of the flag:61b5649e894a15a053276c0dc828ee64ec2336f809e2dd7d2912c61c8ef02c26.
The flag is read from flag.txt, asserted to be exactly 32 bytes, hashed with the
custom SecureHash, and the resulting digest is written to output.txt. Goal:
recover the flag from the digest.
Analysis
Source overview (securehash.py)
- Constants: a 256-entry
KEY_SBOX, a 256-entry bit-permutationPBOX, andBLOCK_SIZE = 32. SecureCipher(key):self.sbox = [KEY_SBOX[i] ^ key[0] for i in range(256)]— the substitution table depends only on the first key byte.substitute(data): byte-wise lookupsbox[b].permute(data): a bit-level permutation over the 256 bits of the 32-byte block, driven byPBOX(bitnum→ bitPBOX[num], with byte =num//8, bit =7-(num%8)).encrypt(data): per 32-byte block, run 100 rounds ofsubstitute → permute → xor(key). Source comment:# No linear or differential cryptanalysis here!
SecureHash: state starts at 32 zero bytes;updatepads data to a multiple of 32, then for each block doesstate ^= SecureCipher(block).encrypt(block)— the block is used as both the cipher key and the plaintext.
Key observations
-
Single block, key = plaintext = flag. The flag is exactly 32 bytes = one block, so padding is a no-op and there is a single block. With the initial state
0^32, the digest reduces toSecureCipher(flag).encrypt(flag). The unknown flag plays every role: it is the key and the plaintext. -
KEY_SBOXis affine over GF(2). Verified programmatically: for alli, j,KEY_SBOX[i^j] == KEY_SBOX[i] ^ KEY_SBOX[j] ^ KEY_SBOX[0]. ThereforeS(x) = M·x ⊕ cfor an 8×8 bit-matrixMand constantc = KEY_SBOX[0] = 170. The comment "No linear or differential cryptanalysis here!" is a red herring — and the flag itself spells out the joke: "wait...it's all linear?????". -
Every operation is GF(2)-affine. The affine S-box, the constant XOR of
key[0], the linear bit permutationPBOX(no constant), and the full-key XOR are all affine over GF(2). Because data = key = flag, the entire 100-round encryption collapses into a single affine function of the 256 flag bits:output_bits = A · flag_bits ⊕ constThe round count is irrelevant: composing affine maps yields an affine map. An S-box with no GF(2)-nonlinearity provides no security no matter how many rounds wrap it.
Solution
Track each of the 256 output bits as a symbolic linear combination (a 256-bit mask) of the 256 flag bits plus a constant bit. Propagate this symbolic state through all 100 rounds, modelling each affine primitive:
- Affine S-box
S(x) = M·x ⊕ c: applyMto each byte's 8 symbolic bits, addc. key[0]XOR: XOR with the symbolic bits of flag bits 0..7 (sincesboxaddskey[0], folded into the S-box step).PBOXpermutation: relabel symbolic bit positions (pure linear, no constant).- Full-flag XOR: XOR each symbolic output bit with the corresponding flag-bit variable.
Setting state(flag) == OUT yields a 256×256 linear system over GF(2):
A · f = OUT ⊕ const. Solve with Gaussian elimination over GF(2). Free variables exist,
but the single printable/meaningful solution is the flag.
Deriving the affine S-box matrix
python read-only • copy allowedc = KEY_SBOX[0] # = 170, the affine constant S(0) M = [[0]*8 for _ in range(8)] # M[outbit][inbit] for k in range(8): v = KEY_SBOX[1 << k] ^ c # column for input bit k for ob in range(8): M[ob][k] = (v >> ob) & 1 # affinity check: assert all(KEY_SBOX[i ^ j] == (KEY_SBOX[i] ^ KEY_SBOX[j] ^ KEY_SBOX[0]) for i in range(256) for j in range(256))
Symbolic linearization + GF(2) solve (sketch)
python read-only • copy allowed#!/usr/bin/env python3 from securehash import KEY_SBOX, PBOX # constants from the challenge N = 256 # 256 flag bits OUT = bytes.fromhex("61b5649e894a15a053276c0dc828ee64ec2336f809e2dd7d2912c61c8ef02c26") # --- affine S-box S(x) = M*x ^ c over GF(2) --- c = KEY_SBOX[0] M = [[0]*8 for _ in range(8)] for k in range(8): v = KEY_SBOX[1 << k] ^ c for ob in range(8): M[ob][k] = (v >> ob) & 1 # Symbolic bit = (mask over 256 flag vars, constant bit). # Represent the 256-bit state as a list of (int mask, int const). def bit_index(byte, bit): # bit 0..7, MSB-first as in source return byte*8 + (7 - bit) # initial symbolic state: state bit i == flag bit i state = [(1 << i, 0) for i in range(N)] # key[0] symbolic bits = flag bits of byte 0 key0_bits = [state[bit_index(0, b)] for b in range(8)] def xor_sym(a, b): return (a[0] ^ b[0], a[1] ^ b[1]) for _ in range(100): # substitute: per byte apply affine M, then ^ key[0] new = [None]*N for byte in range(32): in_bits = [state[bit_index(byte, b)] for b in range(8)] # MSB-first # reorder to value bit 0..7 (LSB..MSB) val = [in_bits[7-i] for i in range(8)] outv = [] for ob in range(8): acc = (0, (c >> ob) & 1) for k in range(8): if M[ob][k]: acc = xor_sym(acc, val[k]) acc = xor_sym(acc, key0_bits[ob]) # ^ key[0] bit ob outv.append(acc) for b in range(8): new[bit_index(byte, b)] = outv[7-b] state = new # permute: bit num -> PBOX[num] perm = [None]*N for num in range(N): perm[PBOX[num]] = state[num] state = perm # xor(key) == xor(flag): state bit i ^= flag var i state = [xor_sym(state[i], (1 << i, 0)) for i in range(N)] # Build A f = OUT^const over GF(2) rows = [] rhs = [] for i in range(N): mask, const = state[i] target = (OUT[i//8] >> (7-(i%8))) & 1 rows.append(mask) rhs.append(const ^ target) # Gaussian elimination over GF(2) on bitmask rows piv = {} for r in range(N): m, b = rows[r], rhs[r] for col, (pm, pb) in piv.items(): if (m >> col) & 1: m ^= pm; b ^= pb if m: col = (m & -m).bit_length() - 1 piv[col] = (m, b) sol = 0 for col, (m, b) in piv.items(): # back-substitute free vars = 0 val = b mm = m & ~(1 << col) while mm: c2 = (mm & -mm).bit_length() - 1 val ^= (sol >> c2) & 1 mm &= mm - 1 sol |= val << col flag = bytes((sol >> (8*j)) & 0xff for j in range(32)) # adjust bit order as needed print(flag)
Verification against the real cipher
python read-only • copy allowedxor = lambda a, b: bytes([x ^ y for x, y in zip(a, b)]) flag = b"HTB{REDACTED}" sbox = [KEY_SBOX[i] ^ flag[0] for i in range(256)] b = flag for _ in range(100): b = bytes([sbox[x] for x in b]) out = [0]*32 for num in range(256): on = PBOX[num] if b[num//8] & (1 << (7-(num%8))): out[on//8] |= (1 << (7-(on%8))) b = xor(bytes(out), flag) assert b.hex() == "61b5649e894a15a053276c0dc828ee64ec2336f809e2dd7d2912c61c8ef02c26"
Feeding the recovered flag back through the real cipher reproduces the exact target digest, confirming the solution.
Key Takeaways / Lessons
- Mastering affine_sbox_detection, gaussian_elimination_gf2, key_equals_plaintext_reduction, linearization_attack, symbolic_bit_propagation was key to this challenge.
- Always check for common misconfigurations and verify assumptions.
Crafted by XESXOR Research • 2026-06-17 • CUSTOM • Always Has Been • Difficulty: Medium