//Spell of Restoration

Challenge prompt: “Did you write down the flag on your memo properly?”

Flag format: TSGCTF{...}

This writeup shows how to solve the ROM without guessing, by reversing the 6502 validator and turning it into a small offline solver.

I’ll go top → bottom:

Unpack the provided files
Identify that it’s an NES ROM (iNES header)
Recover the tile→character mapping from the ROM’s screen data + CHR graphics
Reverse the validation routine (including BRK + NMI checks)
Translate it into equations
Solve them with a tiny brute-force-with-pruning solver

All scripts used are included in the solution/ folder:

solution/solve.py (final solver)
solution/disasm_validator.py (py65 disassembly helper)
solution/dump_screens.py (extract text screens / tile mapping)
solution/extract_chr.py (render CHR tiles as ASCII)

>1) Unpacking and quick triage

The challenge ships a tarball with a single ROM.

bash


$ tar -tf spell_of_restoration.tar.gz

spell_of_restoration/

spell_of_restoration/chall.nes

The first 16 bytes of chall.nes show a classic iNES header:

bash


$ hexdump -C chall.nes | head -n 3

00000000  4e 45 53 1a 02 01 01 00  00 00 00 00 00 00 00 00  |NES.............|

00000010  78 d8 a2 ff 9a a9 00 8d  00 20 8d 01 20 a9 00 8d  |x........ .. ...|

00000020  10 40 20 d5 80 20 d5 80  20 db 80 20 0a 81 a9 00  |.@ .. .. .. ....|

NES\x1a identifies it as iNES.
The PRG/CHR size bytes are 02 01 (normally 32KB PRG and 8KB CHR).

However, this ROM is a CTF build and actually includes only 1KB CHR data (64 tiles). That’s still enough for the game’s font and UI.

>2) Extracting the on-screen character set (tile mapping)

2.1) Dump the pre-baked screens

NES games often store title/menu screens as nametable buffers (tile IDs) in PRG ROM, then copy them into the PPU.

In this ROM, the title screen is stored at $E010, and a game screen at $E410.

Run:

bash


$ python3 solution/dump_screens.py | sed -n '1,40p'

== Start Screen @ E010 ==

00:                                

01:                                

02:   .??????????????????????????.  

03:   ?                          ?  

04:   ? ???? ???? ????? ???? ??? ?  

05:   ? ?       ?   ?   ?    ?   ?  

06:   ? ???    ?    ?   ???? ? ???  

07:   ? ?     ?     ?      ? ?  ??  

08:   ? ???? ????   ?   ???? ?????  

09:   ?                          ?  

10:   .??????????????????????????.  

11:          ?TYPE A CORRECT FLAG/  

...

The important part is:

The string contains CORRECT FLAG/ — that lets us identify the tile for /.

The game screen contains a grid of tiles 1..48 laid out visibly. That’s the selectable “memo keyboard”.

2.2) Establish the alphabet and digits

From the title strings (and the grid layout), it’s clear the font uses:

Tile 1..26 → A..Z
Tile 27..36 → 0..9

This is also confirmed by decoding various UI strings (e.g., TSGCTF( on the title screen uses tile IDs 20 19 7 3 20 6 49 which maps to TSGCTF().

2.3) Identify punctuation tiles from known UI strings

From the title screen:

Tile 48 is / (from CORRECT FLAG/)
Tile 49 is ( and tile 50 is ) (from TSGCTF( and the matching closing parenthesis)

Next, we render the CHR tiles to identify the remaining punctuation glyphs.

Run:

bash


$ python3 solution/extract_chr.py

You’ll get 64 tiles printed as ASCII art.

Key identifications (visual):

Tile 37 looks like ! → used in “INCORRECT FLAG DETECTED!”
Tile 43 looks like +
Tile 44 looks like -
Tile 47 looks like =
Tile 39 looks like #
Tile 41 looks like %

(For contest writeups, it’s totally fine to show a screenshot / snippet of the ASCII-rendered tiles; the included script is reproducible.)

>3) Finding the validator in PRG ROM

3.1) Disassembly tooling

This is a 6502 ROM. I used py65 (quick and good enough for this task).

Install:

bash


$ python3 -m pip install --user py65

Then disassemble the region that contains the validation:

bash


$ python3 solution/disasm_validator.py | sed -n '1,80p'

82D6: 86 16    STX $16

82D8: C0 00    CPY #$00

82DA: F0 08    BEQ $82e4

82DC: AA       TAX

82DD: BD 10 E8 LDA $e810,X

82E0: 88       DEY

82E1: 4C D8 82 JMP $82d8

...

82E7: A2 00    LDX #$00

82E9: B4 03    LDY $03,X

82EB: 88       DEY

82EC: 94 03    STY $03,X

...

Two huge observations:

$82D6 is the core “crypto primitive”.

- It takes an input A and an exponent Y.

- It repeatedly applies an S-box from $E810 exactly Y times.

In math:

- Let S(x) be the byte table at $E810.

- Then the routine computes $S^Y(A)$.

$82E7 decrements every input byte once (DEY; STY $03,X).

That means if the player selects tiles 1..48, the validator uses values 0..47 internally.

3.2) Constants and S-box

The S-box is at $E810 (256 bytes).
The constants are at $E910..$E91F (16 bytes).

You can confirm via hexdump or programmatically; the solver script reads them directly.

>4) Understanding the structure: main checks + BRK + NMI

The validator does not just run straight-line checks.

It does:

A chain of comparisons in the mainline
Triggers BRK intentionally
Uses the NMI/IRQ handler to compute intermediate values

Here’s the key part of the control flow:

After some checks, it runs:

```

8395: BRK

...

83BD: BRK

...

845B: JMP $83FF

```

The BRK/interrupt handler ($846F..) checks a “mode” byte in $18:

bash


$ python3 solution/disasm_validator.py | sed -n '200,320p'

846F: A4 18    LDY $18

8471: C0 0F    CPY #$0f

8473: F0 45    BEQ $84ba

8475: C0 0C    CPY #$0c

8477: F0 19    BEQ $8492

8479: C0 04    CPY #$04

847B: F0 01    BEQ $847e

...

So there are three NMI stages (Y=4, Y=12, Y=15) that must all pass.

This is the main reason naive “just solve the CMP chain” attempts fail.

>5) Translating the ROM into equations

5.1) Notation

Let the post-decrement input bytes be:

p0..p15 where pi ∈ [0..47].

Let the S-box exponentiation function be:

F(a, y) = S^y(a).

Let constants be:

C0..C15 = bytes at $E910..$E91F.

5.2) The subtle but crucial “flag register exponent” detail

The ROM uses:


LDA #$00

CLV

CLD

CLC

PHP

PLA

TAY

That does not set Y=0. It sets Y to the packed CPU status register value.

For 6502, after that sequence, the value is 0x36.

Similarly, after LDA #$01; CLV; CLD; CLC; PHP; PLA, the status value is 0x34.

Those values are used as exponents to F(·,Y).

This detail is why many “almost right” solvers get no solutions.

5.3) Mainline equations

From the disassembly, each CMP is an equation. Example:

The first check around $830E..$8314 enforces:

F(p11, p14) ^ p9 == C11 and F(p9, sx(p15)) ^ p1 == C9, etc.

The solver in solution/solve.py implements the full set exactly as derived.

5.4) BRK + NMI equations

The BRK points set up registers and then the NMI handler validates extra properties.
These become additional constraints (nmi1_ok, nmi2_ok, nmi3_ok in the solver).

>6) Solving strategy

The search space is 48^16 which is enormous, but the constraints are very strong.

The trick is:

Precompute F[a][y] for all bytes and exponents (256×256 table).
Solve in the same order the ROM checks, so you prune early.

In practice, the NMI stage 3 constraint reduces p15 to a single value immediately.

>7) Final solver and output

Run the full solver:

bash


$ python3 solution/solve.py

[+] Solved tile IDs (1..48):

[1, 13, 2, 28, 19, 9, 27, 15, 41, 39, 28, 7, 31, 13, 5, 37]

[+] Decoded message:

AMB1SI0O%#1G4ME!

[+] Flag:

TSGCTF{AMB1SI0O%#1G4ME!}

So the flag is:

TSGCTF{AMB1SI0O%#1G4ME!}

>8) Notes / pitfalls (what I got wrong first)

If you are learning from this:

Off-by-one in F(a,y): make sure F(a,0)=a and F(a,1)=S(a).
The decrement loop ($82E7) means the validator works on tile_id - 1.
BRK/NMI is part of the validator. If you ignore it, you’ll “solve” something the ROM never accepts.
The status-register exponent (0x36 and 0x34) is extremely easy to miss.

>9) References

iNES file format overview:

- https://www.nesdev.org/wiki/INES

6502 CPU status register bits:

- https://www.nesdev.org/wiki/Status_flags

py65 (6502 tools used for quick disassembly):

- https://github.com/mnaberez/py65

>Appendix: all solver code

All code is included as files (recommended for reproducibility):

solution/solve.py
solution/disasm_validator.py
solution/dump_screens.py
solution/extract_chr.py