Writeup · 31 Nights of Root

Palimpsest

reversingmediumsolvedFlag: r00t{REDACTED}

Overview

The prompt: “Can you scrape back the intended message? The palimpsest executable should help get the flag and then the check should verify whether that flag is correct.”

We get a custom layered file format (PLMS v2), a pile of documentation and a Python “extractor”, and three ELF binaries. The theme is a palimpsest: text scraped off and written over, with the old writing still showing through. Here the real parsing logic sits under misleading documentation.

The solve has four parts:

  1. Show that the supplied docs and layer_extractor.py are decoys.
  2. Reverse palimpsest to learn how it really parses manuscript.pls.
  3. Recompute the 20-byte XOR of all layers, and confirm it with the binary.
  4. Decode the expected string inside check, and relate it to the XOR result.

Files provided

File Role
manuscript.pls PLMS v2 container: 7 layers of 20 bytes each
palimpsest x86-64 PIE ELF. Parses the manuscript, XORs the layers, compares to stdin
check x86-64 PIE ELF. fgets + strcmp against an obfuscated flag string
validator Decoy sibling of check (VALID / INVALID -- formula mismatch)
layer_extractor.py Decoy extractor that follows the wrong header field
revision_log.txt Decoy: claims xref at offset 20 and says to ignore the reserved field
revision_metadata.txt Decoy: claims per-layer SHA256 key masking

Prerequisites / Setup

  • Python 3 (struct, hashlib)
  • radare2 (r2), objdump, readelf
  • The extracted files in the working directory

Recon

Step 1 — Hardening

Goal: Confirm the binaries are stripped PIE x86-64 ELFs with no canary.

checksec --file=check
checksec --file=palimpsest
RELRO           STACK CANARY      NX            PIE      Symbols
Partial RELRO   No canary found   NX enabled    PIE      No Symbols

Both binaries are stripped PIE x86-64 ELFs with no canary. Memory corruption is not the point of the challenge, so this only confirms we are reading logic, not exploiting it.

Step 2 — Inspect the manuscript hex dump

Goal: Read the PLMS v2 container header.

00000000: 504c 4d53 0714 0000 0030 0200 0002 0000  PLMS.....0......
00000010: 0000 0000 0000 0001 0203 0405 0614 0024  ...............$
...
00000230: 0105 0400 0206 03                        .......

Reading the header:

Offset Bytes Meaning
0 50 4c 4d 53 magic PLMS
4 07 num_layers = 7
5 14 00 00 00 “xref_offset” = 0x14 (20)
9 30 02 00 00 “reserved” = 0x230 (560)
13 02 version
14..19 zeros flags
20..26 00 01 02 03 04 05 06 an identity permutation (decoy xref)
27 14 00 first layer: length 0x14, then 20 bytes of data

Layers are length-prefixed (uint16 LE, always 0x14), so the seven layers occupy offsets 27 to 181. After that comes a long run of zero padding, then a tiny 7-byte block at the very end of the file (0x230):

01 05 04 00 02 06 03

That block is a permutation of 0..6. It is the real cross-reference table, and its location matches the “reserved” field at offset 9 (0x230), not the “xref_offset” field at offset 5.

Exploitation

Step 3 — Recognize the decoy documentation

Goal: Confirm that the text files and layer_extractor.py lead away from the real logic.

revision_log.txt claims:

  • the xref is at offset 20 (xref_offset field),
  • the order is [0,1,2,3,4,5,6],
  • the reserved field at offset 9 “is used only during write operations … Readers must ignore it.”

revision_metadata.txt claims each layer is masked with SHA256(str(i))[:4] and says raw XOR “produces invalid output”. layer_extractor.py follows the log and prints a garbage buffer.

Both claims fail against the binary. The first because the binary uses the reserved field. The second because the binary does no per-layer key unmasking at all. A hint that the log is hollow: the log’s own recovery text tells readers to ignore the one field the binary actually reads.

Exploitation

Step 4 — Reverse palimpsest (radare2)

Goal: Recover the real parsing logic from main.

r2 -A palimpsest
[0x000013d0]> afl
[0x000013d0]> pdf @ main

Only main (763 bytes) matters. The annotated flow:

; usage check
cmp edi, 1 ; jle -> "Usage: %s <manuscript.pls>"

; open file, read 27-byte header
fopen(argv[1], "rb")
fread(hdr, 1, 0x1b, f)             ; header is 27 bytes
cmp dword [hdr], 0x534d4c50        ; 'PLMS'  else "Bad magic"

eax  = dword [hdr + 9]             ; the "reserved" field  -> saved as `offset`
r13d = byte  [hdr + 4]             ; num_layers

; read layers
for (i = 0; i < num_layers && i != 7; i++) {
    fread(&len, 2, 1, f)
    if (len != 0x14) fail
    fread(layer[i], 1, 0x14, f)    ; stride 0x14 in a stack array
}

Then the integrity check on the reserved field:

; CRC32 (poly 0xEDB88320, init 0xFFFFFFFF), bitwise, 8 shifts per byte
eax = ~crc & 0x1ff
eax += 0x100                       ; result is in 0x100..0x2ff
cmp [offset], eax                  ; reserved must equal this, else exit 1

So the reserved field is not free bookkeeping. It is validated against a CRC32-derived value, and then used as the seek target:

fseek(f, offset, SEEK_SET)         ; offset = 0x230
fread(order, 1, 7, f)              ; real xref: [1, 5, 4, 0, 2, 6, 3]

Then the XOR stage:

acc = layer[order[0]]              ; copy 20 bytes (16 via xmm + 4 scalar)
for k in 1..6:
    acc ^= layer[order[k]]         ; pxor for 16 bytes, byte loop for last 4

And finally the comparison:

fread(buf, 1, 0x14, stdin)         ; exactly 20 raw bytes from stdin
return memcmp(acc, buf, 0x14) != 0 ; exit code 0 on match, 1 otherwise

Key takeaways from the reversing:

  • palimpsest prints nothing. Its only output is the process exit status (0 = your 20 bytes equal the XOR result).
  • There is no key unmasking. The metadata file’s SHA256 scheme does not exist.
  • The permutation does not matter: XOR is commutative and associative, so the result is just layer[0] ^ layer[1] ^ ... ^ layer[6] in any order. The order block is a red herring that only exists to make the decoy-vs-real xref distinction look important.

Step 5 — Recover the 20-byte message

Goal: Parse the manuscript and XOR all layers; order doesn’t matter.

Since the order and the CRC don’t change the answer, a simple parser is enough:

import struct

d = open("manuscript.pls", "rb").read()
assert d[:4] == b"PLMS"

n = d[4]                                   # 7 layers
real_xref = struct.unpack_from("<I", d, 9)[0]   # reserved field = 0x230
order = list(d[real_xref:real_xref + n])   # [1, 5, 4, 0, 2, 6, 3]

off, layers = 27, []
for _ in range(n):
    (ln,) = struct.unpack_from("<H", d, off)
    off += 2
    layers.append(d[off:off + ln])
    off += ln

acc = bytearray(layers[order[0]])
for i in order[1:]:
    for j in range(len(acc)):
        acc[j] ^= layers[i][j]

open("recovered.bin", "wb").write(acc)
print(len(acc), "bytes written")
python3 solve.py
./palimpsest manuscript.pls < recovered.bin ; echo "exit=$?"
20 bytes written
exit=0

Exit status 0 confirms the 20 recovered bytes are exactly what palimpsest expects.

Step 6 — Reverse check

Goal: Decode the flag embedded in check.

check reads one line with fgets, strips the trailing newline, and strcmps it against a stack buffer. That buffer is built at startup by a byte-wise XOR decode loop:

10e0: xor eax, 0x5c        ; al ^= 0x5c
10e3: add rcx, 1           ; dst++
10e7: add rdx, 1           ; src++
10eb: mov [rcx-1], al
10ee: movzx eax, byte [rdx]
10f1: test al, al
10f3: jne 10e0

The loop starts with eax = 0x2e (which is the first byte of the encoded data, .) and a source pointer at 0x2020 in .rodata. Decoding therefore means XORing every non-null byte starting at 0x2020 with 0x5c:

d = open("check", "rb").read()
blob = d[0x2020:].split(b"\x00")[0]
print(bytes(b ^ 0x5c for b in blob).decode())
r00t{REDACTED}

Running the decoded string back through the binary:

echo 'r00t{REDACTED}' | ./check
CORRECT

Flag

r00t{REDACTED}

Verified with ./check (prints CORRECT), and independently by the SHA256 relationship below:

import hashlib
msg = open("recovered.bin", "rb").read()
print(hashlib.sha256(msg).hexdigest()[:24])

The first 24 hex characters of SHA256(msg) are exactly the hex tail of the flag. So the intended chain is:

flowchart LR
    A[manuscript.pls] --> B[read real xref via reserved field @9]
    B --> C[XOR all 7 layers]
    C --> D[20-byte message]
    D --> E[SHA256, first 24 hex chars]
    E --> F["r00t{REDACTED}"]
    G[check: XOR 0x5c decode] --> F

Both routes land on the same string, which gives independent confirmation: reversing palimpsest yields data whose hash matches the flag stored in check.

Lessons / Takeaways

  • Trust the binary, not the docs. When a challenge ships “documentation” and a “reference implementation” alongside a compiled program, assume the prose is hostile until you’ve diffed it against the disassembly. Here, three separate files each pointed at the wrong header field.
  • Fields labelled “ignore me” are prime suspects. The “reserved” field at offset 9 held the real xref pointer and was CRC-validated. Check what every header field is actually used for.
  • Look for algebraic shortcuts. The XOR of all layers is independent of the order, so the elaborate permutation block never needed to be parsed correctly for the answer.
  • Silent programs communicate through exit codes. palimpsest prints nothing; echo $? after piping candidate bytes was the oracle.
  • Cheap string obfuscation falls to one-liners. Single-byte XOR (0x5c) with an unobfuscated key constant in the loop is trivially recovered statically. strings already revealed the encoded blobs.
  • Decoy siblings: validator exists to eat time. If two binaries share a skeleton, decode both quickly and discard the one whose output is nonsense.
  • Unresolved item: the exact CRC32 region validated against the reserved field. It is worth a short debugging session if you want a complete parser, but it isn’t needed to solve the challenge.

Techniques

  • XOR Obfuscation
  • Custom File Format Parsing
  • CRC32
  • Static Analysis with radare2
  • Decoy Documentation

References