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
|
"""CodeShell.kr — infinity-involution (Reversing, 1600p) solver.
contract.txt: "Linux x86-64. The program accepts 64 lowercase hexadecimal
characters on stdin. Submit CodeShell{SHA256(bytes.fromhex(accepted_input))},
lowercase hex." Challenge title: "Find the fixed point".
Program structure (from the disassembly of `involution`)
-------------------------------------------------------
1. fgets(stdin, 0x50) into a 0x20-byte stack buffer; strcspn(..., "\\n") must
be 0x40 -> exactly 64 chars.
2. Those 64 hex chars are parsed into 8 little-endian dwords: state[0..7].
3. A bytecode program of 0x8000 bytes at .rodata+0x20 = 4096 instructions of
8 bytes. Each instruction is [op, A, B, C, imm32]. An LCG
(seed 0x0d5203ce, multiplier 0x19660d, increment 0x3c6ef35f) supplies two
bits per instruction, and the real opcode is `op ^ (lcg & 3)`:
op 0: r8 = imm ^ state[B]; state[A] += r8
op 1: r8 = imm ^ state[A]; state[A] = rol32(state[B], C) ^ r8
op 2: state[A] = rol32(state[A], C) ^ imm
op 3: t = state[A]; r8 = imm ^ state[B]; state[A] = r8; state[B] = t
op > 3: no-op
(`r8` is reloaded from the imm field every instruction, so it is not
carried across instructions.)
4. The program is "accepted" only when all eight state words are zero.
Every op above is a bijection on the 256-bit state, so instead of searching
for an input we run the whole program BACKWARDS from the all-zero state; the
resulting state is the required input. That is the "fixed point" the title
refers to (f(x) = 0 with f invertible).
"""
import hashlib
import sys
from pathlib import Path
M32 = 0xFFFFFFFF
LCG_SEED = 0x0D5203CE
LCG_MUL = 0x19660D
LCG_INC = 0x3C6EF35F
PROG_OFF = 0x2020
PROG_LEN = 0x8000
def rol32(x, c):
c &= 31
return ((x << c) | (x >> (32 - c))) & M32 if c else x & M32
def ror32(x, c):
c &= 31
return ((x >> c) | (x << (32 - c))) & M32 if c else x & M32
def decode(data):
"""Return the list of (op, A, B, C, imm) with the LCG-XORed opcode resolved."""
prog = data[PROG_OFF:PROG_OFF + PROG_LEN]
lcg = LCG_SEED
out = []
for i in range(0, len(prog), 8):
op, a, b, c = prog[i], prog[i + 1], prog[i + 2], prog[i + 3]
imm = int.from_bytes(prog[i + 4:i + 8], "little")
real = op ^ (lcg & 3)
lcg = (lcg * LCG_MUL + LCG_INC) & M32
out.append((real, a, b, c, imm))
return out
def forward(insns, state):
s = list(state)
for (op, A, B, C, imm) in insns:
if op == 0:
r8 = (imm ^ s[B]) & M32
s[A] = (s[A] + r8) & M32
elif op == 1:
r8 = (imm ^ s[A]) & M32
s[A] = (rol32(s[B], C) ^ r8) & M32
elif op == 2:
s[A] = (rol32(s[A], C) ^ imm) & M32
elif op == 3:
t = s[A]
r8 = (imm ^ s[B]) & M32
s[A] = r8
s[B] = t
return s
def backward(insns, state):
"""Invert the program: given the final state, return the initial state."""
s = list(state)
for (op, A, B, C, imm) in reversed(insns):
if op == 0:
r8 = (imm ^ s[B]) & M32
s[A] = (s[A] - r8) & M32
elif op == 1:
s[A] = (rol32(s[B], C) ^ imm ^ s[A]) & M32
elif op == 2:
s[A] = ror32((s[A] ^ imm) & M32, C)
elif op == 3:
old_a = s[B]
old_b = (s[A] ^ imm) & M32
s[A] = old_a
s[B] = old_b
return s
def main():
path = (sys.argv[1] if len(sys.argv) > 1 else
Path(__file__).resolve().parents[1] /
"extracted/infinity-involution/involution")
data = Path(path).read_bytes()
insns = decode(data)
from collections import Counter
print("opcode histogram:", dict(sorted(Counter(i[0] for i in insns).items())))
target = [int.from_bytes(data[0xA020 + 4 * i:0xA024 + 4 * i], "little")
for i in range(8)]
print("target state:", ["%08x" % w for w in target])
start = backward(insns, target)
end = forward(insns, start)
assert end == target, "forward/backward are not consistent"
input_hex = b"".join(w.to_bytes(4, "big") for w in start).hex()
print("accepted input (64 lowercase hex):", input_hex)
blob = bytes.fromhex(input_hex)
print(f"ANSWER CodeShell{{{hashlib.sha256(blob).hexdigest()}}}")
if __name__ == "__main__":
main()
|