Challenge
This challenge is all about algorithm coding, and encryption. The aim of this challenge is to take a comma-delimited string, which represents a 9x9 Sudoku, and parse this string into a form which can be analyzed. The Sudoku should then be analyzed and solved, and returned to its comma-delimited form. This comma-delimited solution would then be hashed using the SHA1 hashing system. The resulting hash should be applied as the key to decrypt the CBC-mode 64bit-block-size Blowfish-encrypted Base64-encoded string provided. The decrypted string is the password for this challenge. Submit it quickly! 这道题的核心是写算法和解密：把一串逗号分隔的字符串当作 9x9 数独解析、求解，再把它还原成同样的逗号分隔形式；对这个结果做 SHA1，把得到的 hash 当作 key，用 CBC 模式、64-bit 分组的 Blowfish 解密题目给的 Base64 密文，明文就是关卡密码。要求快速提交。
题目页面给出：一个 9x9 数独（有向量的题面 + 一份 copy/paste 用的逗号串）、一段 Base64 密文，以及加密算法的 PHP 源码 blowfish.phps。页面还挂了 180 秒倒计时。
Solution
整体链路很直白：解析数独 → 求解 → 回填逗号串 → SHA1 → Blowfish-CBC 解密 → 提交。
真正的难点不在数独，而在 blowfish.phps 是一份魔改过的 Blowfish 实现：它不是标准算法，也没有现成库能直接对上。pycryptodome 的 Blowfish 解不出正确明文，必须逐行复刻这份 PHP。下文先列出从源码中提取的三个关键约定，再给完整脚本。
Step 1: 算法约定
blowfish.phps 开头的两个成员变量直接决定了模式：
public $hashcfg = 1 ; // Key Hashing MD5: 0 SHA1: 1public $encryptmode = 1 ; // Encryption mode: EBC: 0 CBC: 1即 key 用 SHA1、模式用 CBC。继续看 key schedule：
function keys($key){ $key_hash = sha1($key);
//Convert the $key into a 16Byte key $key = $this->_str2long(substr(str_pad($key, 16, $key_hash),0,16));
//XOR Pbox1 with the first 32 bits of the key, XOR P2 with the second 32-bits of the key, for($i=0;$i<count($this->pbox);$i++) { $this->pbox[$i] ^= $key[$i%4]; }}sha1($key) 在 PHP 里默认返回 40 字符的十六进制字符串。题面流程是把 SHA1 的结果当 key 传进来，也就是这个 40 字符的 hex 串；它长度已经 ≥ 16，str_pad 不起作用，于是 substr(...,0,16) 只取 hex 串的前 16 个字符。这 16 个字符会被 _str2long()（unpack('N*')，big-endian 32-bit）拆成 4 个 word 参与 key schedule。
第二处是 round 函数，也是这份实现最不常规之处：
function sbox_round($integer){ //Split $integer into four 8 Bit blocks $b0 = $integer<<24 & 0xFF; $b1 = $integer<<16 & 0xFF; $b2 = $integer<<8 & 0xFF; $b3 = $integer & 0xFF;
$return = ($this->sbox0[$b0] + $this->sbox1[$b1] % 4294967295) ; $return = ($return ^ $this->sbox2[$b2]) + $this->sbox3[$b3] % 4294967295;
return $return;}标准 Blowfish 用右移 >> 取四个字节索引，这里全是左移 <<。在 64 位 PHP（以及 Python）整数语义下，(x << 24) & 0xFF、(x << 16) & 0xFF、(x << 8) & 0xFF 恒为 0，只有 x & 0xFF 这个低字节存活。所以 F 函数退化成一个只用低字节查表的表达式，必须原样照抄，不能用标准 F。
第三处是 CBC 的 IV 和输出格式：
if($this->encryptmode == 1) { $cipher[0][0] = time(); $cipher[0][1] = (double)microtime()*1000000;}IV 取的是时间戳 [time(), microtime()*1000000] 两个整数；更关键的是收尾的打包循环 for($i = 0; $i<count($cipher); $i++)把 $cipher[0]（也就是这个 IV）也写进了输出。所以 base64 解码后的密文里，前 8 字节是 IV，真正的密文 block 从第 3 个 32-bit word 开始。解密时要把第一块当 IV 用。
Step 2: 求解数独
题面的 copy/paste 串按逗号切正好是 81 个字段（行主序），空 cell 就是空字段；求解后按 ",".join(81 个数字) 回填，格式与题面完全一致。这里用最朴素的全解回溯，顺带枚举多个解（题面提示可能有多个解）：
def parse_puzzle(cells): return [[0 if cells[r * 9 + c] == "" else int(cells[r * 9 + c]) for c in range(9)] for r in range(9)]solve_sudoku() 是全解回溯（行优先试填 + 行/列/宫校验），最多收 limit 个解；完整实现见文末 完整脚本。
Step 3: 复刻 Blowfish
把 PHP 的 block_encrypt / sbox_round / keys 逐行翻译成 Python。注意 block_encrypt 本身是标准 Blowfish 加密轮，所以逆过程就是标准解密轮；另外用随机 block 做 enc/dec 往返自检，以确认逆轮写对。逐行翻译后的 Blowfish 类（sbox_round / block_encrypt / block_decrypt / keys 与 PHP 一一对应）见文末 完整脚本。
keys() 里 key 材料只取前 16 字节，self.P[i] ^= kw[i % 4] 之后就是标准的 P-box / S-box 展开循环。
CBC 解密时把第一块取出当 IV（实现见文末 完整脚本 的 blowfish_cbc_decrypt）。
Script
"""HackThisSite Programming Mission 9 — One-Time-Pad Encryption.
Flow: 1. fetch /missions/prog/9/ and parse the comma-delimited 9x9 Sudoku + the Base64 Blowfish ciphertext; 2. solve the Sudoku (backtracking, enumerate every solution); 3. join the solution back into the same comma-delimited form, SHA1 it, and use the resulting SHA1 hex string as the Blowfish key; 4. decrypt the Base64 ciphertext with the *exact* Blowfish variant shipped in blowfish.phps (hashcfg=1 -> SHA1, encryptmode=1 -> CBC-with-prepended-IV); 5. submit the printable plaintext as the challenge password.
The Blowfish class below is a line-for-line Python port of the PHP reference at/missions/prog/9/blowfish.phps. It is NOT stock Blowfish: the round function`F` uses `<<` (not `>>`) when slicing the four S-box indices, and the CBC "IV"is `[time(), microtime()*1e6]` which is emitted as the first ciphertext blockinstead of being transmitted separately. Both quirks must be reproduced.
Run from the CTF workspace root: export HTS_COOKIE='HackThisSite=...'243 collapsed lines
uv run python challenges/hts-prog/9/solve.py"""
import base64import hashlibimport osimport reimport structimport sysimport time
HERE = os.path.dirname(os.path.abspath(__file__))sys.path.insert(0, os.path.abspath(os.path.join(HERE, "..")))from common import session, fetch_level, body_text, submit # noqa: E402
LEVEL = 9FIELD = "password"
# --------------------------------------------------------------------------# Blowfish (PHP blowfish.phps port)# --------------------------------------------------------------------------PBASE = [ 0x243f6a88, 0x85a308d3, 0x13198a2e, 0x03707344, 0xa4093822, 0x299f31d0, 0x082efa98, 0xec4e6c89, 0x452821e6, 0x38d01377, 0xbe5466cf, 0x34e90c6c, 0xc0ac29b7, 0xc97c50dd, 0x3f84d5b5, 0xb5470917, 0x9216d5d9, 0x8979fb1b,]
def _load_sboxes(): """Read the four S-box tables straight out of the challenge's PHP source.""" php = os.path.join(HERE, "blowfish.php") if not os.path.exists(php): raise SystemExit("blowfish.php missing — fetch it from " "/missions/prog/9/blowfish.phps first") src = open(php, encoding="utf-8").read() boxes = [] for name in ("sbox0", "sbox1", "sbox2", "sbox3"): m = re.search(r"\$%s\s*=\s*Array" % name, src) j = m.end() - 1 depth = 0 for k in range(j, len(src)): if src[k] == "(": depth += 1 elif src[k] == ")": depth -= 1 if depth == 0: body = src[j:k] break boxes.append([int(x, 16) for x in re.findall(r"0x[0-9a-fA-F]+", body)]) return boxes
SBASE = _load_sboxes()MASK32 = 0xFFFFFFFF
class Blowfish: """Faithful port of the PHP reference implementation."""
def __init__(self): self.P = PBASE[:] self.S = [b[:] for b in SBASE]
def sbox_round(self, integer): # NOTE: the original uses `<<` here, not `>>`. On a 64-bit interpreter # (x<<24)&0xFF, (x<<16)&0xFF and (x<<8)&0xFF all collapse to 0, so only # the low byte survives. Keep it exactly as written. b0 = (integer << 24) & 0xFF b1 = (integer << 16) & 0xFF b2 = (integer << 8) & 0xFF b3 = integer & 0xFF r = self.S[0][b0] + self.S[1][b1] % 4294967295 r = (r ^ self.S[2][b2]) + self.S[3][b3] % 4294967295 return r
def block_encrypt(self, left, right): vl, vr = left, right for i in range(16): vl ^= self.P[i] vr ^= self.sbox_round(vl) vl, vr = vr, vl vl, vr = vr, vl vr ^= self.P[16] vl ^= self.P[17] return vl, vr
def block_decrypt(self, left, right): vl, vr = left, right vl ^= self.P[17] vr ^= self.P[16] vl, vr = vr, vl for i in range(15, -1, -1): vl, vr = vr, vl vr ^= self.sbox_round(vl) vl ^= self.P[i] return vl, vr
def keys(self, key): """Key schedule; `key` is the raw string the server feeds to keys().""" if isinstance(key, str): key = key.encode() key_hash = hashlib.sha1(key).hexdigest().encode() # PHP sha1() -> hex if len(key) >= 16: material = key[:16] else: material = (key + key_hash * (1 + 16 // len(key_hash)))[:16] kw = list(struct.unpack(">4I", material)) for i in range(18): self.P[i] ^= kw[i % 4] v0 = v1 = 0 for i in range(0, 18, 2): v0, v1 = self.block_encrypt(v0, v1) self.P[i] = v0 self.P[i + 1] = v1 for bi in range(4): for i in range(0, 256, 2): v0, v1 = self.block_encrypt(v0, v1) self.S[bi][i] = v0 self.S[bi][i + 1] = v1
def blowfish_cbc_decrypt(b64_text, key): """Decrypt Base64 CBC-Blowfish where block 0 is the prepended IV.""" bf = Blowfish() bf.keys(key) data = base64.b64decode(b64_text) words = list(struct.unpack(">%dI" % (len(data) // 4), data)) prev = (words[0], words[1]) # emitted IV block out = bytearray() for i in range(2, len(words), 2): pl, pr = bf.block_decrypt(words[i], words[i + 1]) pl ^= prev[0] pr ^= prev[1] out += struct.pack(">II", pl & MASK32, pr & MASK32) prev = (words[i], words[i + 1]) return bytes(out)
# --------------------------------------------------------------------------# Sudoku# --------------------------------------------------------------------------def parse_puzzle(cells): return [[0 if cells[r * 9 + c] == "" else int(cells[r * 9 + c]) for c in range(9)] for r in range(9)]
def solve_sudoku(grid, limit=64): solutions = []
def valid(g, r, c, v): for i in range(9): if g[r][i] == v or g[i][c] == v: return False br, bc = 3 * (r // 3), 3 * (c // 3) for i in range(br, br + 3): for j in range(bc, bc + 3): if g[i][j] == v: return False return True
def backtrack(g): if len(solutions) >= limit: return for r in range(9): for c in range(9): if g[r][c] == 0: for v in range(1, 10): if valid(g, r, c, v): g[r][c] = v backtrack(g) g[r][c] = 0 return solutions.append([row[:] for row in g])
backtrack([row[:] for row in grid]) return solutions
def check_solution(g): want = set(range(1, 10)) for r in range(9): if set(g[r]) != want: return False for c in range(9): if {g[r][c] for r in range(9)} != want: return False for br in (0, 3, 6): for bc in (0, 3, 6): if {g[br + i][bc + j] for i in range(3) for j in range(3)} != want: return False return True
# --------------------------------------------------------------------------# Main# --------------------------------------------------------------------------def parse_page(text): puzzle = re.search(r'copy/paste form: <input type="text" value="([^"]*)"', text).group(1) cipher = re.search(r"Blowfish encrypted string:\s*([A-Za-z0-9+/=]+)", text).group(1) return puzzle, cipher
def main(): s = session() page = fetch_level(s, LEVEL) puzzle, cipher = parse_page(page) cells = puzzle.split(",") if len(cells) != 81: raise SystemExit("expected 81 cells, got %d" % len(cells)) print("[*] puzzle :", puzzle) print("[*] cipher :", cipher)
grid = parse_puzzle(cells) sols = solve_sudoku(grid) print("[*] solutions:", len(sols))
answer = None for idx, sol in enumerate(sols): assert check_solution(sol), "invalid sudoku solution" solstr = ",".join(str(v) for v in sum(sol, [])) digest = hashlib.sha1(solstr.encode()).hexdigest() # The server feeds the SHA1 *hex string* to keys(); keys() keeps the # first 16 characters because the digest is longer than 16 bytes. plain = blowfish_cbc_decrypt(cipher, digest.encode()) printable = all(32 <= b < 127 for b in plain) print("[*] sol #%d sha1=%s -> %r (printable=%s)" % (idx, digest, plain, printable)) if printable: answer = plain.decode().rstrip(" ") # strip space padding break
if not answer: raise SystemExit("no printable plaintext — key derivation wrong")
print("[*] password :", answer) if os.environ.get("HTS_DRY"): print("[*] HTS_DRY set — skipping submission") return time.sleep(3) ok, resp = submit(s, LEVEL, answer, field=FIELD) print("[*] verdict :", ok) print(body_text(resp)[-1200:])
if __name__ == "__main__": main()