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
|
"""CodeShell.kr — generic solver for the opcode-picnic binary family.
Family members seen so far (all 14472-byte stripped x86-64 PIE ELFs built from
the same generator, differing only in constants):
binary len rounds seed expected table
01 opcode-picnic 28 4 0x9f80c83a 0x2040
02 switchyard 28 ? ? 0x2040
03 glass-register 33 11 0x4a9a4ce9 0x2060
04 threaded-echo 32 17 0x8747b8df 0x2040
05 dead-branches 32 23 0x5996dc4d 0x2040
06 blackbox-vm 33 37 0xce9ca13f 0x2060
Structure (from the disassembly of 04, identical in shape everywhere):
strlen(argv[1]) == LEN else exit(2)
r10d = 0 ; i*0x45d9f3b accumulator
for i in 0..LEN-1:
b = input[index[i]] ; index[] = reversed table at 0x2020
eax = (i*0x45d9f3b) ^ SEED
r8 = 0; r13 = 0; edi = 0
repeat ROUNDS times:
n = edi + i
edx = rol32(eax,13) ^ (eax >> 7)
eax = eax ^ edx ^ r8
cl1 = (edi & 3) * 8
r8 += 0x7f4a7c15
edx = (eax >> cl1) ^ b
cl2 = (n % 7) + 1
esi = (eax >> 19) + r13
r13 += 0xb
edx = (edx & ~0xff) | rol8(edx & 0xff, cl2)
esi = esi + edx
edi += 1
acc = esi & 0xff
must equal expected[i] ; else ebx &= 0
ebx must be all ones, and the chained accumulator r15d != r13d
(the final `je rejected` is inverted: equal => rejected).
Because each round's result depends only on (i, b), every byte can be brute
forced independently in 0..255.
"""
import sys
from pathlib import Path
M32 = 0xffffffff
def rol32(x, c):
c &= 31
return ((x << c) | (x >> (32 - c))) & M32 if c else x & M32
def rol8(x, c):
c &= 7
return ((x << c) | (x >> (8 - c))) & 255 if c else x & 255
def round_byte(i, b, seed, rounds):
"""The 8-bit accumulator for byte index i holding value b.
Note the self-reference: `esi` starts as the input byte and is then
overwritten by the accumulator each round, so round k uses the accumulator
of round k-1 (this is the "threaded" part of the family). Only the low
byte of the shifted value enters the accumulator, not the full word.
"""
eax = ((i * 0x45D9F3B) & M32) ^ seed
r8 = r13 = 0
edi = 0
esi = b & 0xFF
for _ in range(rounds):
edx = (rol32(eax, 13) ^ (eax >> 7)) & M32
eax = (eax ^ edx ^ r8) & M32
r8 = (r8 + 0x7F4A7C15) & M32
edx = ((eax >> ((edi * 8) & 31)) ^ esi) & M32
n = (edi + i) & M32
rem = n - 7 * (n // 7)
esi = ((eax >> 19) + r13 + rol8(edx & 0xFF, (rem + 1) & 7)) & M32
r13 = (r13 + 0xB) & M32
edi += 1
return esi & 0xFF
def solve(binary, length, rounds, seed, idx_off, exp_off):
data = Path(binary).read_bytes()
index = list(data[idx_off:idx_off + length])
expected = list(data[exp_off:exp_off + length])
if sorted(index) != list(range(length)):
print(f" warning: index table is not a permutation of 0..{length-1}")
out = bytearray(length)
ambiguous = 0
for i in range(length):
hits = [b for b in range(256) if round_byte(i, b, seed, rounds) == expected[i]]
if len(hits) != 1:
ambiguous += 1
print(f" byte {i:2d}: {len(hits)} candidates {hits[:6]}")
out[i] = hits[0] if hits else 0
text = bytearray(length)
for i in range(length):
text[index[i]] = out[i]
return bytes(text), ambiguous
FAMILY = {
"01_opcode_picnic_JsAiqDC.bin": (28, 4, 0x9F80C83A, 0x2020, 0x2040),
"02_switchyard_lqFsLaz.bin": (30, 7, 0x37326173, 0x2020, 0x2040),
"03_glass_register_Ytqr6gK.bin": (33, 11, 0x4A9A4CE9, 0x2020, 0x2060),
"04_threaded_echo_eboZwXv.bin": (32, 17, 0x8747B8DF, 0x2020, 0x2040),
"05_dead_branches_EIpI3C4.bin": (32, 23, 0x5996DC4D, 0x2020, 0x2040),
"06_blackbox_vm_p1pFD61.bin": (33, 37, 0xCE9CA13F, 0x2020, 0x2060),
}
def main():
root = Path(__file__).resolve().parents[1] / "assets/challenge-files"
for name, (length, rounds, seed, io, eo) in FAMILY.items():
if rounds is None:
continue
text, amb = solve(root / name, length, rounds, seed, io, eo)
print(f"{name}: {text!r} ambiguous_bytes={amb}")
if __name__ == "__main__":
sys.exit(main())
|