1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
| """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 block
instead of being transmitted separately. Both quirks must be reproduced.
Run from the CTF workspace root:
export HTS_COOKIE='HackThisSite=...'
uv run python challenges/hts-prog/9/solve.py
"""
import base64
import hashlib
import os
import re
import struct
import sys
import 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
LEVEL = 9
FIELD = "password"
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):
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()
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])
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)
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
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()
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(" ")
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()
|