# Always Has Been - HTB Challenge Writeup ## Challenge Overview

Category	Difficulty
Crypto	Hard

We're given a custom hash function implementation and a target digest. The challenge is to reverse the hash and recover the original 32-byte flag by exploiting the algebraic structure of the cipher. ### Challenge Files - `securehash.py` - Custom block cipher + hash wrapper implementation - `output.txt` - Target digest (64 hex characters) - Goal: Recover the 32-byte flag that produced this digest ## Initial Analysis ### Understanding the Hash Function From `securehash.py`, the hash function operates as follows: **Initial State:** ```python state = b"\x00" * 32 # 32 null bytes ``` **Flag Constraint:** ```python assert len(flag) == 32 # Exactly one block ``` **Digest Computation:** The hash processes exactly one 32-byte block with no padding: ```python digest = state XOR E_key(block) ``` Where: - `key = block` (the message is used as its own encryption key) - `state` starts as all zeros This simplifies to: **`digest = E_k(k)`** where `k = flag` ### Problem Formulation Let `F(k) = E_k(k)` be our function (32-byte input → 32-byte output). Given `output = bytes.fromhex(output.txt)`, we need to solve: **`F(flag) = output`** ## Vulnerability Analysis ### Key Observation: Affine Structure The cipher performs 100 rounds, each consisting of: 1. **`substitute(block)`** - S-box substitution 2. **`permute(block)`** - Bit permutation 3. **`block ^= key`** - XOR with key #### Why This Is Exploitable **`permute()` is linear:** - Just a bit permutation (P-box) - Bit permutations are linear over GF(2) **`substitute()` is affine:** ```python sbox[b] = KEY_SBOX[b] ^ key[0] ``` - `KEY_SBOX` provides an affine mapping on bytes - XOR with `key[0]` is also affine - Affine + Affine = Affine **Critical Finding:** Since affine maps compose to affine maps, even after 100 rounds, `F(k)` remains an **affine function** of the 256-bit vector `k`. This means there exists: - A 256×256 binary matrix `A` - A constant vector `b` Such that: **`F(k) = A*k ^ b`** ## Exploitation Strategy ### Step 1: Recover Matrix A and Vector b Since we have the full implementation, we can evaluate `F(·)` locally: **Compute constant vector:** ```python b = F(0) ``` **Compute each column of A:** ```python for i in range(256): e_i = unit_vector(i) # Single 1-bit at position i A[:, i] = F(e_i) ^ b ``` This extracts the complete affine transformation. ### Step 2: Solve the Linear System Given `A*flag ^ b = output`, we rearrange to: ``` A*flag = output ^ b ``` This is a standard **Gaussian elimination over GF(2)** on a 256-variable system. **Challenge-Specific Detail:** In this instance, matrix `A` has rank 255, resulting in a 1-bit nullspace. This means there are exactly **two candidate solutions**. Only one will match the flag format `HTB{...}`. ## Complete Exploit Script ### Implementation Overview The exploit performs the following steps: 1. **Load Challenge Files** - Parse `securehash.py` and extract SBOX/PBOX constants 2. **Build Affine System** - Evaluate `F(·)` on basis vectors to extract matrix `A` and vector `b` 3. **Convert to Row Form** - Transform column representation for Gaussian elimination 4. **RREF Solve** - Reduce to row echelon form and back-substitute 5. **Extract Solutions** - Find particular solution + nullspace basis 6. **Validate Flag** - Check candidates against `HTB{...}` format ```python #!/usr/bin/env python3 from __future__ import annotations from dataclasses import dataclass from pathlib import Path import argparse import itertools import types BLOCK_SIZE = 32 def xor(a: bytes, b: bytes) -> bytes: return bytes([x ^ y for x, y in zip(a, b)]) def b2i(b: bytes) -> int: return int.from_bytes(b, "big") def i2b(x: int) -> bytes: return x.to_bytes(32, "big") def bit_for_col(col: int) -> int: # Column 0 is MSB, column 255 is LSB. return 1 << (255 - col) def bit_for_row(row: int) -> int: # Row 0 is MSB, row 255 is LSB (same convention as big-endian bytes->int). return 1 << (255 - row) @dataclass(frozen=True) class Challenge: KEY_SBOX: list[int] PBOX: list[int] @classmethod def load_from_securehash(cls, path: Path) -> "Challenge": mod = types.ModuleType("securehash") code = path.read_text(encoding="utf-8") # Avoid executing the challenge's file-reading footer. code = code.split("\nflag = open", 1)[0] exec(code, mod.__dict__) return cls(KEY_SBOX=mod.KEY_SBOX, PBOX=mod.PBOX) class SecureCipher: def __init__(self, chal: Challenge, key: bytes): self._chal = chal self.key = key self.sbox = [chal.KEY_SBOX[i] ^ key[0] for i in range(256)] def substitute(self, data: bytes) -> bytes: return bytes([self.sbox[b] for b in data]) def permute(self, data: bytes) -> bytes: out = [0] * BLOCK_SIZE for num in range(256): outnum = self._chal.PBOX[num] inbyte = num // 8 inbit = 7 - (num % 8) outbyte = outnum // 8 outbit = 7 - (outnum % 8) if data[inbyte] & (1 << inbit): out[outbyte] |= 1 << outbit return bytes(out) def encrypt_block(self, block: bytes) -> bytes: for _ in range(100): block = self.substitute(block) block = self.permute(block) block = xor(block, self.key) return block def F(chal: Challenge, k: bytes) -> bytes: # For a single-block message and state=0, the digest is just E_k(k). return SecureCipher(chal, k).encrypt_block(k) def build_affine_system(chal: Challenge) -> tuple[list[int], int]: """ Returns (cols, b): - b is 256-bit int for F(0) - cols[i] is i-th column of A as a 256-bit int (MSB-first) """ b = b2i(F(chal, b"\x00" * 32)) cols: list[int] = [0] * 256 for col in range(256): e = i2b(bit_for_col(col)) cols[col] = b2i(F(chal, e)) ^ b return cols, b def cols_to_rows(cols: list[int]) -> list[int]: """ Convert column form to row form. rows[r] is a 256-bit mask of which input bits affect output bit r. """ rows: list[int] = [0] * 256 for r in range(256): out_bit = bit_for_row(r) mask = 0 for c in range(256): if cols[c] & out_bit: mask |= bit_for_col(c) rows[r] = mask return rows def rref_solve(rows: list[int], rhs_bits: list[int]) -> tuple[int, list[int], list[int], list[int]]: """ Perform elimination over GF(2) and produce RREF. Returns: - rank - rows (mutated to RREF) - rhs_bits (mutated to match) - where: where[col] = pivot_row index or -1 if free """ rows = rows[:] rhs_bits = rhs_bits[:] where = [-1] * 256 r = 0 pivots: list[tuple[int, int]] = [] for col in range(256): bit = bit_for_col(col) pivot = None for rr in range(r, 256): if rows[rr] & bit: pivot = rr break if pivot is None: continue rows[r], rows[pivot] = rows[pivot], rows[r] rhs_bits[r], rhs_bits[pivot] = rhs_bits[pivot], rhs_bits[r] where[col] = r pivots.append((r, col)) # eliminate below for rr in range(r + 1, 256): if rows[rr] & bit: rows[rr] ^= rows[r] rhs_bits[rr] ^= rhs_bits[r] r += 1 if r == 256: break rank = r # back eliminate (make RREF) for rr, col in reversed(pivots): bit = bit_for_col(col) for up in range(0, rr): if rows[up] & bit: rows[up] ^= rows[rr] rhs_bits[up] ^= rhs_bits[rr] # consistency check (0 = 1) for rr in range(256): if rows[rr] == 0 and rhs_bits[rr]: raise ValueError("No solution (inconsistent system).") return rank, rows, rhs_bits, where def extract_particular_and_nullspace( rows: list[int], rhs_bits: list[int], where: list[int] ) -> tuple[int, list[int]]: """ From an RREF system, return: - x_particular with all free vars = 0 - nullspace basis vectors (as 256-bit ints) """ free_cols = [c for c in range(256) if where[c] == -1] # particular: free vars set to 0 => pivot var equals rhs bit x0 = 0 for col in range(256): rr = where[col] if rr != -1 and rhs_bits[rr]: x0 |= bit_for_col(col) basis: list[int] = [] for fc in free_cols: v = bit_for_col(fc) # free var = 1 # For each pivot row, pivot var = coefficient of this free var (since rhs=0 for nullspace). for col in range(256): rr = where[col] if rr == -1: continue if rows[rr] & bit_for_col(fc): v |= bit_for_col(col) basis.append(v) return x0, basis def is_flag_candidate(b: bytes) -> bool: if len(b) != 32: return False if not (b.startswith(b"HTB{") and b.endswith(b"}")): return False # Typical HTB flags are printable ASCII; keep this check permissive. return all(0x20 <= x < 0x7F for x in b) def main() -> int: ap = argparse.ArgumentParser() ap.add_argument("--securehash", default="securehash.py", help="Path to securehash.py") ap.add_argument("--output", default="output.txt", help="Path to output.txt") ap.add_argument("--show-all", action="store_true", help="Print all solutions (if nullity is small)") args = ap.parse_args() chal = Challenge.load_from_securehash(Path(args.securehash)) ct = bytes.fromhex(Path(args.output).read_text().strip()) if len(ct) != 32: raise SystemExit("Expected 32-byte output (64 hex chars).") cols, b = build_affine_system(chal) rows = cols_to_rows(cols) rhs = b2i(ct) ^ b rhs_bits = [1 if (rhs & bit_for_row(r)) else 0 for r in range(256)] rank, rref_rows, rref_rhs_bits, where = rref_solve(rows, rhs_bits) nullity = 256 - rank x0, basis = extract_particular_and_nullspace(rref_rows, rref_rhs_bits, where) # Enumerate solutions if small nullspace; otherwise, try a few and hope format check hits. if nullity <= 16: combos = itertools.product([0, 1], repeat=nullity) else: combos = itertools.islice(itertools.product([0, 1], repeat=min(nullity, 20)), 1_000_000) found: list[bytes] = [] for choice in combos: x = x0 for i, bit in enumerate(choice): if bit: x ^= basis[i] cand = i2b(x) if args.show_all: found.append(cand) elif is_flag_candidate(cand): print(cand.decode("ascii")) return 0 if args.show_all: for cand in found: tag = "FLAG" if is_flag_candidate(cand) else "cand" try: s = cand.decode("ascii") except UnicodeDecodeError: s = cand.hex() print(f"[{tag}] {s}") return 0 raise SystemExit("No flag-like solution found. Try --show-all.") if __name__ == "__main__": raise SystemExit(main()) ``` ## Running the Exploit ### Basic Execution ```bash python3 solve.py ``` **Expected Output:** ``` HTB{...} ``` ### Advanced Usage To enumerate all solutions when nullspace is small: ```bash python3 solve.py --show-all ``` ### Custom File Paths ```bash python3 solve.py --securehash /path/to/securehash.py --output /path/to/output.txt ``` ## Key Takeaways ### Vulnerability Summary **Algebraic Weakness in Custom Cryptography:** The challenge demonstrates why custom crypto implementations without proper analysis are dangerous. Despite using: - 100 rounds of encryption - Substitution-Permutation Network (SPN) structure - Block cipher mode The entire system collapses to a **linear system over GF(2)** because: - Affine S-boxes compose to affine functions - Linear permutations remain linear - No non-linear mixing between rounds ### Attack Complexity - **Precomputation:** 256 hash evaluations (< 1 second) - **Matrix solving:** Gaussian elimination on 256×256 matrix (instant) - **Total runtime:** < 2 seconds ## References - [Linear Cryptanalysis](https://en.wikipedia.org/wiki/Linear_cryptanalysis) - [Algebraic Attacks on Block Ciphers](https://www.iacr.org/cryptodb/data/paper.php?pubkey=3153) - [Boolean Functions in Cryptography](https://www.cs.miami.edu/home/burt/learning/Csc609.062/docs/boolean.pdf)