Reversing a multi-threaded x86-64 ELF to brute-force a scheduling puzzle based on an ARX-like mixing construction.
The building is closed, but the work is not finished. Complete the remaining assignments before morning.
The provided artifact, night_shift.bdsec, is a stripped x86-64 ELF (PIE, statically linked against pthread). Running it produces:
========================================
NIGHT SHIFT
========================================
The building is closed.
Eight assignments remain.
shift code>
It reads a line of input, and either prints The shift report was rejected. or (on success) The morning report has been approved. followed by a decrypted flag.
file night_shift # ELF 64-bit LSB pie executable, x86-64, dynamically linked, stripped
strings night_shift # confirms pthread_create/join/mutex/cond usage, "shift code>", etc.
objdump -d -M intel night_shift
Key observations from the disassembly and .rodata:
strtok_r is " \t\r\n\0" — input tokens are whitespace-separated.strtoul(token, &endptr, 10), and rejected unless:
*endptr == '\0'),<= 4,rbp == 8 check).0 1 2 3 4 0 1 2.main() spawns 5 threads via pthread_create, each given a small struct { shared_state_ptr, worker_id } with worker_id = 0..4 in creation order.| Offset (from struct base) | Meaning |
|---|---|
| +0x58 | state word A (32-bit) |
| +0x5c | state word B (32-bit) |
| +0x60 | state word C (32-bit) |
| +0x64 | state word D (32-bit) |
| +0x68..0x87 | round_array[8] (32-bit each) — one output per round |
| +0x88 | accumulator E (32-bit) |
| +0x8c..0x93 | the 8 input digits, verbatim |
| +0x98 | current round index (0..8, shared counter) |
| +0xa0 | "done/error" flag |
Every thread loops: lock mutex → check if digit_array[round_idx] == my_worker_id → if yes, run my mixing function and advance round_idx, broadcast, unlock; if no, pthread_cond_wait and retry.
In other words: the 8 digits you type are not "data" being hashed — they are a schedule. Each digit says which of the 5 threads gets to execute at that step. Since a thread's mixing function is fixed by its worker_id, the digit sequence effectively picks an ordered sequence of 8 mixing operations (with repeats allowed, since values 0–4 can repeat across the 8 slots) to apply to a shared 4-word state (A, B, C, D) plus an accumulator E.
This is basically a keyed/permutation-dependent hash construction: same 8 "rounds" happen no matter what, but which function runs in which slot is fully controlled by the user's input.
I originally assumed A=B=C=D=E=0 at the start (based on a memset-like zeroing loop in main() before the thread struct is used). Instrumenting with gdb proved this wrong: at address 0x11c5-0x11e0, after the zero loop, the code loads a 16-byte constant from .rodata @ 0x2170 into A,B,C,D, and hardcodes E = 0x811c9dc5 (the FNV-1a offset basis):
movdqa xmm0, [rip+0x...] ; load 16 bytes from 0x2170
mov dword [rsp+0x118], 0x811c9dc5 ; E init
movups [rsp+0xe8], xmm0 ; A,B,C,D init
Reading those 16 bytes from .rodata:
A0 = 0x13579bdf
B0 = 0x2468ace0
C0 = 0x0badf00d ; "0bad f00d" — a little author's joke
D0 = 0xc001d00d ; "c001 d00d"
E0 = 0x811c9dc5 ; FNV-1a 32-bit offset basis
The active thread computes a common per-round seed before dispatch:
r15c = worker_id * 0x45d9f3b # fixed per-thread constant
seed = (round_idx + 1) * 0x9e3779b9 # golden-ratio prime, position-dependent
seed ^= r15c
M = triple32(seed) # see below
triple32 is Chris Wellons' public-domain 32-bit integer hash (avalanche mixer):
def triple32(x):
x &= 0xFFFFFFFF
x ^= x >> 16
x = (x * 0x7feb352d) & 0xFFFFFFFF
x ^= x >> 15
x = (x * 0x846ca68b) & 0xFFFFFFFF
x ^= x >> 16
return x
A jump table at .rodata @ 0x2020 dispatches on worker_id (0-4) to one of five code blocks. Each block updates a different subset of (A,B,C,D); everything then falls through to a shared tail that always recomputes Mix2 (stored into round_array[round_idx]) and updates the accumulator E.
Reconstructed per-branch logic (all arithmetic mod 2³²; rol/ror = 32-bit rotate):
if digit == 0:
A' = rol(A ^ M, (round_idx + 3) & 31)
C' = (((B ^ 0x13579bdf) + C) + round_idx)
B' = B ; D' = D
elif digit == 1:
B' = rol((B + D + M), 5)
D' = D ^ rol(A, 9)
A' = A ; C' = C
elif digit == 2:
A' = A + round_idx + 0x6d2b79f5
C' = rol((C ^ B) ^ M, 13)
B' = B ; D' = D
elif digit == 3:
D' = triple32(M + D + A)
B' = ((round_idx * 17) ^ B) ^ 0xc001d00d
A' = A ; C' = C
elif digit == 4:
D' = D + round_idx - 0x5a5a5a5b
A' = rol(M + D, 7) ^ A
B' = B + rol(C, 3)
C' = C ^ rol(A, 11) # uses ORIGINAL A, not A'
Shared tail (runs after every branch, using whichever A',B',C',D' the branch produced):
edi = rol(B', 5)
r8 = rol(C', 11)
esi = ror(D', 15)
ecx = (worker_id << 24) ^ round_idx ^ A'
edi ^= ecx
r8 ^= edi
esi ^= r8
Mix2 = triple32(esi) # -> round_array[round_idx]
e2 = (worker_id << 8) ^ E ^ round_idx
E' = rol((Mix2 ^ e2) * 0x1000193, 7) ^ 0xa53c9e17 # FNV-prime multiply + rotate + xor
I verified this instruction-by-instruction against live execution using gdb (breaking right before the round counter increments, at 0x18c9, and dumping A,B,C,D,E from the shared struct each time). This caught one real transcription bug (I'd swapped which register xor'd with which in the digit == 2 branch); after the fix, simulated state matched the debugger's ground truth exactly for arbitrary test sequences.
After all 8 rounds, main() checks the final state against hardcoded constants:
(A | (B << 32)) == 0x75a2cc729c8a97dc # -> A == 0x9c8a97dc, B == 0x75a2cc72
(C | (D << 32)) == 0x4969e73d1d87ef0f # -> C == 0x1d87ef0f, D == 0x4969e73d
E == 0x4455cee8
round_idx == 8 # trivially true for any 8-token input
With correct init values and corrected branch logic, the whole 8-round computation is cheap to simulate. Since each of 8 positions can be 0–4, there are only 5^8 = 390,625 possible schedules — trivial to brute force in pure Python in well under a second:
import itertools
for seq in itertools.product(range(5), repeat=8):
A, B, C, D, E = INIT_A, INIT_B, INIT_C, INIT_D, INIT_E
round_array = [0]*8
for i, d in enumerate(seq):
A, B, C, D, E, round_array[i] = do_round(A, B, C, D, E, i, d)
if (A, B, C, D, E) == (TARGET_A, TARGET_B, TARGET_C, TARGET_D, TARGET_E):
print(seq); break
This found a unique solution:
seq = (2, 0, 4, 1, 3, 0, 2, 4)
i.e. the shift code is:
2 0 4 1 3 0 2 4
$ echo "2 0 4 1 3 0 2 4" | ./night_shift
...
shift code> The morning report has been approved.
BDSEC{0rd3r_h1d3s_b3tw33n_th3_l1n3s}
The binary itself decrypts and prints the flag once the state checks pass — it does so by XORing a 36-byte ciphertext blob (.rodata @ 0x2040) with a keystream derived from round_array[], E, and the digit sequence itself, run through another triple32-style avalanche. Since the schedule check and the decryption both depend on the same final internal state, finding the correct schedule via the state-matching brute force was sufficient — no separate keystream reversal was needed to find the code, only to understand why it works.
memset-style zeroing loop right before the state struct's use looked like standard stack hygiene; the actual initial values were loaded from .rodata immediately after and easily missed on a fast read.xor r8d,edi vs xor r9d,ecx). Installing gdb in the sandbox and diffing live register/memory state against the Python re-implementation caught a real bug that pure static analysis missed.