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
|
"""CodeShell.kr — fractured-loom (Reversing, 3200p) solver.
readme.txt: "Input: exactly 64 lowercase hexadecimal characters (32 bytes).
The executable accepts the input only when its eight 64-bit lanes reach the
hidden terminal state. Submit CodeShell{SHA256(raw_input_bytes)}, using
lowercase hex."
Program structure (from the disassembly of `loom`)
--------------------------------------------------
1. fgets(stdin) then strcspn(..., "\\n") == 0x40 -> exactly 64 chars.
2. The 64 hex chars are parsed two at a time (high nibble first) into 32 raw
bytes at rsp+0x40.
3. The initial state is 8 lanes of 64 bits built from those bytes: each 4-byte
big-endian dword is duplicated into a 64-bit lane and XORed with a table:
lane_i = ((dword_i << 32) | dword_i) ^ u64[0x32080 + 8*i]
4. A "loom" program of 0x30000 bytes at .rodata+0x80 = 8192 instructions of
24 bytes: [op(1), A(1), B(1), C(1), imm32(4), Q1(8), Q2(8)].
The real opcode is `op ^ ((Q1 >> 17) & 7)` (3 bits smuggled inside Q1) and
is dispatched through a 7-entry jump table at .rodata+0x20.
op 0: state[A] = (rol64(Q1 ^ state[B], C) ^ imm) + state[A]
op 1: state[A] = rol64(Q1 + state[B], C) ^ imm ^ state[A]
op 2: state[A] = rol64(state[A] ^ Q1, C)
op 3: state[A] = Q2 * state[A] + Q1
op 4: state[A] = Q1 ^ state[B]; state[B] = imm + state[A] (old A)
op 5: byte substitution: with cl = ((Q1 >> 3) & 7) * 8,
state[A] = (state[A] & ~(0xff << cl)) | (SBOX[(state[A] >> cl) & 0xff] << cl)
op 6: t = rol64(state[B], C) ^ state[A];
state[B] = state[B] + Q1 + t; state[A] = t
(op > 6 lands on op 4's handler)
5. Accept requires the final 64-byte state to equal the constant at
.rodata+0x40 (XOR-and-OR reduction over 4 XMM words).
Every op is a bijection on the 512-bit state, so instead of searching we run
the loom BACKWARDS from the terminal constant; the resulting initial state
gives the required input.
"""
import hashlib
import sys
from pathlib import Path
M64 = 0xFFFFFFFFFFFFFFFF
PROG_OFF = 0x2080
PROG_LEN = 0x30000
INS_LEN = 24
TARGET_OFF = 0x2040
LANE_XOR_OFF = 0x32080
SBOX_OFF = 0x320C0
def rol64(x, c):
c &= 63
return ((x << c) | (x >> (64 - c))) & M64 if c else x & M64
def ror64(x, c):
c &= 63
return ((x >> c) | (x << (64 - c))) & M64 if c else x & M64
def decode(data):
sbox = data[SBOX_OFF:SBOX_OFF + 256]
prog = data[PROG_OFF:PROG_OFF + PROG_LEN]
out = []
for i in range(0, len(prog), INS_LEN):
b = prog[i:i + INS_LEN]
op = b[0]
A, B, C = b[1], b[2], b[3]
imm = int.from_bytes(b[4:8], "little")
q1 = int.from_bytes(b[8:16], "little")
q2 = int.from_bytes(b[16:24], "little")
real = op ^ ((q1 >> 17) & 7)
if real > 6:
real = 4
out.append((real, A, B, C, imm, q1, q2))
return out, sbox
def step(op, A, B, C, imm, q1, q2, s, sbox):
sa, sb = s[A], s[B]
if op == 0:
s[A] = ((rol64(q1 ^ sb, C) ^ imm) + sa) & M64
elif op == 1:
s[A] = rol64((q1 + sb) & M64, C) ^ imm ^ sa
elif op == 2:
s[A] = rol64(sa ^ q1, C)
elif op == 3:
s[A] = (q2 * sa + q1) & M64
elif op == 4:
s[A] = (q1 ^ sb) & M64
s[B] = (imm + sa) & M64
elif op == 5:
cl = (q1 >> 3) & 0x38
mask = (~(0xFF << cl)) & M64
s[A] = ((sa & mask) | (sbox[(sa >> cl) & 0xFF] << cl)) & M64
elif op == 6:
t = rol64(sb, C) ^ sa
s[B] = (sb + q1 + t) & M64
s[A] = t
return s
def forward(insns, sbox, state):
s = list(state)
for ins in insns:
step(*ins, s, sbox)
return s
def backward(insns, sbox, state):
"""Invert the loom program: given the final state, return the initial one."""
s = list(state)
inv_sbox = [0] * 256
for i, v in enumerate(sbox):
inv_sbox[v] = i
for ins in reversed(insns):
op, A, B, C, imm, q1, q2 = ins
sa, sb = s[A], s[B]
if op == 0:
s[A] = (sa - (rol64(q1 ^ sb, C) ^ imm)) & M64
elif op == 1:
s[A] = sa ^ imm ^ rol64((q1 + sb) & M64, C)
elif op == 2:
s[A] = ror64(sa, C) ^ q1
elif op == 3:
if q2 & 1 == 0:
raise SystemExit("op3 with even Q2 is not invertible")
s[A] = (((sa - q1) & M64) * pow(q2, -1, 1 << 64)) & M64
elif op == 4:
s[A] = (s[B] - imm) & M64
s[B] = (sa ^ q1) & M64
elif op == 5:
cl = (q1 >> 3) & 0x38
mask = (~(0xFF << cl)) & M64
s[A] = ((sa & mask) | (inv_sbox[(sa >> cl) & 0xFF] << cl)) & M64
elif op == 6:
sb_old = (s[B] - q1 - sa) & M64
s[A] = sa ^ rol64(sb_old, C)
s[B] = sb_old
return s
def main():
path = (sys.argv[1] if len(sys.argv) > 1 else
Path(__file__).resolve().parents[1] / "extracted/fractured-loom/loom")
data = Path(path).read_bytes()
insns, sbox = decode(data)
from collections import Counter
print("op histogram:", dict(sorted(Counter(i[0] for i in insns).items())))
target = [int.from_bytes(data[TARGET_OFF + 8 * i:TARGET_OFF + 8 * i + 8], "little")
for i in range(8)]
xor_tbl = [int.from_bytes(data[LANE_XOR_OFF + 8 * i:LANE_XOR_OFF + 8 * i + 8], "little")
for i in range(8)]
init = backward(insns, sbox, target)
assert forward(insns, sbox, init) == target, "forward/backward mismatch"
dwords = []
for i in range(8):
v = init[i] ^ xor_tbl[i]
lo, hi = v & 0xFFFFFFFF, v >> 32
if lo != hi:
print(f" lane {i}: duplicated-dword pattern broken ({lo:08x} vs {hi:08x})")
dwords.append(lo)
raw = b"".join(w.to_bytes(4, "big") for w in dwords)
print("raw input bytes:", raw.hex())
print("input string :", raw.hex())
print(f"ANSWER CodeShell{{{hashlib.sha256(raw).hexdigest()}}}")
if __name__ == "__main__":
main()
|