Reverse-engineering the Synacor Challenge

After finishing Advent of Code in December, I found myself hungering for more puzzles. The Synacor Challenge is a previous set of puzzles by the same author; I decided to check it out.

The core of the challenge is simple: you're given a specification for a fictional processor, and a 59 KB file that should be executed.

(This blog post contains minor spoilers for the rest of the challenge)

After implementing the processor's specification, you're dropped into a text adventure game, which is delightful:

Welcome to the Synacor OSCON 2012 Challenge!
Please record your progress by putting codes like
this one into the challenge website: ImoFztWQCvxj

Executing self-test...

self-test complete, all tests pass
The self-test completion code is: BNCyODLfQkIl

== Foothills ==
You find yourself standing at the base of an enormous mountain.  At its base to the north, there is a massive doorway.  A sign nearby reads "Keep out!  Definitely no treasure within!"

Things of interest here:
- tablet

There are 2 exits:
- doorway
- south

What do you do?

From here, most of the challenges can be solved from within the text adventure game: you can walk around, take items, use them in the right places, and be rewarded with codes.

I don't want to talk much about the problems contained within the text adventure; there are many blog posts about them.

Instead, I'm taking a deeper dive into the binary file itself: how is the text adventure actually implemented?

Thinking outside of the box

Only one puzzle requires you to think outside of the text adventure box.

Late in the game, you acquire a teleporter, which runs a "confirmation algorithm" before teleporting you. You're asked to reverse-engineer the confirmation algorithm and set machine register r7 to the correct value before teleporting.

Here, we have to actually look into the source code! Fortunately, r7 is only used in a few places. The most relevant is a function beginning at memory address 6049, which I'll call f6049:

6049: jt   r0 6057
6052: r0 = r1 + 1
6056: ret
6057: jt   r1 6070
6060: r0 = r0 + 32767
6064: r1 = r7
6067: call 6049
6069: ret
6070: push r0
6072: r1 = r1 + 32767
6076: call 6049
6078: r1 = r0
6081: pop  r0
6083: r0 = r0 + 32767
6087: call 6049
6089: ret

I went through and hand-translated f6049 into actual code:

fn checksum(r0: u16, r1: u16, r7: u16) -> u16 {
    if r0 == 0 {
        r1.wrapping_add(1) & MASK
    } else if r1 == 0 {
        checksum(r0 - 1, r7, r7)
    } else {
        let r1 = checksum(r0, r1 - 1, r7);
        checksum(r0 - 1, r1, r7)
    }
}

(This may be a good time to revisit the architecture specification to understand the various instructions. In particular, note that we're using 15-bit unsigned wrapping arithmetic, so adding 32767 is equivalent to subtracting 1)

The function above is called in the following context:

5505: r0 = 4            // set the input value for r0
5508: r1 = 1            // set the input value for r1
5511: call 6049         // call the function, returning in r0
5513: r1  = r0 == 6     // our expected value for r0 is 6
5517: jf   r1 5601      // jump if the value didn't match

In other words, we need to find a value for r7 such that f6049(4, 1) == 6, where the value is returned in r0.

The actual function is a weirdly recursive and would indeed be slow to execute within the Synacor VM, so I rewrote it in Rust. With memoization and a multithreaded solver, I can brute-force the correct value in 1.3 seconds:

/// Finds a value for r7 such that `checksum(4, 1) == 6`
fn find_checksum() -> u16 {
    rayon::ThreadPoolBuilder::new()
        .stack_size(8 * 1024 * 1024)
        .build_global()
        .unwrap();
    (1..32767)
        .into_par_iter()
        .find_any(|i| {
            let mut seen = vec![u16::MAX; 1 << 18];
            checksum(4, 1, *i, &mut seen) == 6
        })
        .unwrap()
}

/// Rust implementation of the teleportation checksum procedure
///
/// The procedure is defined by the function beginning at 6049,
/// taking `r0` and `r1` as inputs and returning a value in `r0`.
///
/// The (r0, r1) -> r0 mapping is memoized in `seen` (using
/// `u16::MAX` to mark empty slots, since it's a 15-bit processor)
fn checksum(r0: u16, r1: u16, r7: u16, seen: &mut [u16]) -> u16 {
    // 3 bits for r0, 15 for r1
    assert!(r0 <= 4);
    let key = (r0 as usize) | (r1 as usize) << 3;
    if seen[key] == u16::MAX {
        seen[key] = if r0 == 0 {
            r1.wrapping_add(1) & MASK
        } else if r1 == 0 {
            checksum(r0 - 1, r7, r7, seen)
        } else {
            let r1 = checksum(r0, r1 - 1, r7, seen);
            checksum(r0 - 1, r1, r7, seen)
        };
    }
    seen[key]
}

This bit of reverse-engineering whetted my appetite, and sent me down the rabbit hole of investigating the rest of the binary.

Finding the input loop

I started out by finding where the adventure game reads input from the user. This is easy, because the in instruction only appears in one place!

Here's the function, along with my notes:

1789: push r0
1791: push r2
1793: push r3
1795: push r4
1797: push r5
1799: r2 = r1 + r0      // end = address + length
1803: r0 = r1           // current address in r0
1806: r5 = 0            // total length is accumulated in r5

1809: r0 = r0 + 1       // address++
1813: r3 = r0 > r2      // if address > end
1817: jt   r3 1838      //      break
1820: in   r4           // read a character into r4
1822: r3  = r4 == 10    // if 'c' == '\n'
1826: jt   r3 1838      //      break
1829: wmem r0 r4        // *address = c
1832: r5 = r5 + 1       // length++
1836: jmp  1809         // loop

1838: wmem r1 r5        // *start = length

1841: r3  = r4 == 10    // if last char == '\n'
1845: jt   r3 1852      //    break
1848: in   r4           // read char
1850: jmp  1841         // loop

1852: pop  r5
1854: pop  r4
1856: pop  r3
1858: pop  r2
1860: pop  r0
1862: ret

The function has two loops:

The function is only ever called in one place, with a length limit of 32 characters, so there's (sadly) no way to trigger a buffer overflow from the adventure game REPL:

2840: r0 = 32       // length limit
2843: r1 = 25988    // target address
2846: call 1789

After this function finishes, the user's input is stored in memory address 25988 as a length-prefixed string: address 25988 is the total length, and 25989.. contain the input characters.

Length-prefixed arrays appear a bunch as we go through the code, so keep them in mind!

An Easter Egg in the self-test routine

While scrolling through the annotated binary, I found this curious output:

1403: out  'n'
1405: out  'o'
1407: out  't'
1409: out  ' '
1411: out  'h'
1413: out  'i'
1415: out  't'
1417: out  'c'
1419: out  'h'
1421: out  'h'
1423: out  'i'
1425: out  'k'
1427: out  'i'
1429: out  'n'
1431: out  'g'
1433: out  '\n' "not hitchhiking"
1435: halt

This is printed if your VM decides that 6 * 9 = 42:

801: r0 = 6 * 9
805: r1  = r0 == 42
809: jt   r1 1403

It's a cute Easter egg, which I may be the first to discover!

Indirect calls and plain-text printing

Looking for how things are printed, I stumbled upon a simple function at memory address 1550:

1550: out  r0
1552: ret

This function prints a single character (passed in r0), then returns.

What's interesting is that this function is never called directly!

It turns out that the VM makes extensive use of indirect calls, e.g.

1520: call r5

An indirect call jumps to the value in a register, instead of a fixed location.

I added instrumentation to log every indirect target while solving the adventure game, then printed this extra info out in my disassembler. The function at 1480 jumped out at me as the place which calls 1550:

1482: push r3
1484: push r4
1486: push r5
1488: push r6
1490: r6 = r0       // start = r0
1493: r5 = r1       // f = r1
1496: rmem r4 r0    // length = mem[start]
1499: r1 = 0        // i = 0

1502: r3 = 1 + r1   // j = i + 1
1506: r0 = r3 > r4  // if j > length
1510: jt   r0 1529  //   break
1513: r3 = r3 + r6  // pos = start + j
1517: rmem r0 r3    // r0 = mem[pos]
1520: call r5 {1550, 1553, 1627, 1641, 1670, 5836, 5868, 5915, 5986}
1522: r1 = r1 + 1   // i += 1
1526: jt   r1 1502  // loop

1529: pop  r6
1531: pop  r5
1533: pop  r4
1535: pop  r3
1537: pop  r0
1539: ret

This function is extremely generic, and took me a while to wrap my head around. It's similar to map or for_each: the input function f (passed in r1) is called on every element in a length-prefixed array (passed in r0).

Here's an example of how it's used:

1540: push r1
1542: r1 = 1550
1545: call 1480
1547: pop  r1
1549: ret

This function is basically just print:

We can update our decompiler to pretty-print calls to 1540 with a known value for r0. For example, here's a section of the orb puzzle:

4268: r0 = 26038
4271: call 1540 "As you enter the room, the symbol on the floor briefly flashes  "
4273: r0 = r1
4276: call 1540
4278: r0 = 26102
4281: call 1540 ".  The orb begins subtly glowing  "
4283: r0 = r1
4286: call 1540
4288: out  '.'

Obfuscated printing

Looking at where else map (1480) is called, I saw another pattern emerging:

4756: r0 = 28383
4759: r1 = 1553
4762: r2 = 4072 + 25103
4766: call 1480

There are many places in the binary where it's called with

Looking at 1553 (and inlining its call to 2147), we see the following:

1553: push r1
1555: r1 = r2
1558: call 2147
    2147: push r1
    2149: push r2
    2151: r2 = r0 & r1
    2155: r2 = !r2
    2158: r0 = r0 | r1
    2162: r0 = r0 & r2
    2166: pop  r2
    2168: pop  r1
    2170: ret
1560: out  r0
1562: pop  r1
1564: ret

The function at 2147 is sneakily performing an XOR operation, which isn't present in our architecture but can be built from other bitwise operations:

fn f2147(a: u16, b: u16) -> u16 {
    // (a | b) & !(a & b)
    a ^ b
}

Looking at how it's used at 1553, each character in the string is XORed with the value in r2, then printed out. In other words, this is a simple form of obfuscation, so that strings aren't visible in plain text.

We can continue to improve our disassembler to recognize this calling convention, and add more string annotations to the output!

3938: r0 = 28361
3941: r1 = 1553
3944: r2 = 2737 + 22709
3948: call 1480 "That door is locked.\n"

At this point, we can begin to make guesses about functions based on the strings that they contain. For example, I'm betting that 3422 is called when the user tries to take an item:

3422: push r0
3424: push r1
3426: push r2
3428: call 5943     // check if item is present?
3430: jf   r0 3479

3433: r1 = r0 + 2
3437: rmem r0 r1
3440: rmem r2 2754
3443: r2  = r0 == r2
3447: jf   r2 3479  // check something else?

3450: wmem r1 0     // success!
3453: push r0
3455: push r1
3457: push r2
3459: r0 = 28068
3462: r1 = 1553
3465: r2 = 380 + 996
3469: call 1480 "Taken.\n"
3471: pop  r2
3473: pop  r1
3475: pop  r0
3477: jmp  3503

3479: push r0   // failure case: item is not present
3481: push r1
3483: push r2
3485: r0 = 28076
3488: r1 = 1553
3491: r2 = 4508 + 20821
3495: call 1480 "You see no such item here.\n"
3497: pop  r2
3499: pop  r1
3501: pop  r0

3503: pop  r2
3505: pop  r1
3507: pop  r0
3509: ret

Data section obfuscation

All of the investigation above was done on an image of the binary after completing the game. Imagine my surprise when I tried disassembling the original image and found that all of the strings were nonsense!

4415: r0 = 26313
4418: call 1540 "\u{5610}\u{258d}\u{7390}\u{4115}\u{cf5}..."

It turns out that the original binary obfuscates strings beyond the xor-based encryption above! I set up a watch point to see when one of the string values changed, and quickly found the relevant section of code:

1745: push r0
1747: push r1
1749: r1 = 6090
1752: rmem r0 r1
1755: push r1
1757: r1 = r1 * r1
1761: call 2147     // xor
1763: r1 = 16724
1766: call 2147     // xor
1768: pop  r1
1770: wmem r1 r0
1773: r1 = r1 + 1
1777: r0  = 29957 == r1
1781: jf   r0 1752
1784: pop  r1
1786: pop  r0
1788: ret

This is a loop that reads every word in a particular memory range, applies an xor-based transform, then writes it back out:

for i in 6090..29957 {
    let mut r0 = mem[i];
    r0 ^= i.wrapping_mul(i) & MASK;
    r0 ^= 16724;
    mem[i] = r0;
}

Interestingly, you can see this encryption by eyeballing the original binary. Address 6090 corresponds to offset 12180 (since each word is 2 bytes), and there's a noticeable phase change:

phase change at offset 12180

Dumping all the strings

After decrypting the data section, we can find strings using a simple heuristic: because strings are stored as length-prefixed arrays, we simply check every single word in memory to see if the following n characters are valid ASCII.

This lets us find all kinds of interesting structures. For example, rooms are organized as name, description, list of exits:

6619: "Dark cave"
6629: "The cave is somewhat narrow here, and the light from the doorway to the south is quite dim."
6721: "north"
6727: "south"

Item strings are stored as name, description:

18084: "tablet"
18091: "The tablet seems appropriate for use as a writing surface but is unfortunately blank.  Perhaps you should USE it as a writing surface..."
18228: "empty lantern"
18242: "The lantern seems to have quite a bit of wear but appears otherwise functional.  It is, however, sad that it is out of oil."
18366: "lantern"
18374: "The lantern seems to have quite a bit of wear but appears otherwise functional.  It is off but happily full of oil."
18490: "lit lantern"

Even the basic command list is here:

25957: "go"
25960: "look"
25965: "help"
25970: "inv"
25974: "take"
25979: "drop"
25984: "use"

There are special strings for the orb puzzle, spliced together at runtime based on game state:

26021: "green"
26027: "red"
26031: "yellow"
26038: "As you enter the room, the symbol on the floor briefly flashes "
26102: ".  The orb begins subtly glowing "
26136: "As you enter the room, the orb briefly flashes "
26184: ".  The number on the floor vibrates strangely beneath your feet."
26249: "  The orb seems to get heavier."
26281: "  The orb seems to get lighter."
26313: "  The orb shatters!\n\n"
26335: "As you approach the vault door, "
26368: "the number on the vault door flashes black."
26412: "  The orb evaporates out of your hands.\n\n"
26454: "the number on the vault door flashes white!"
26498: "  The hourglass has already run out.  It flashes black and flips over, restarting the flow of sand."
26598: "  The hourglass is still running!  It flashes white!  You hear a click from the vault door.  The orb evaporates out of hour hands.\n\n"
26731: "As you "
26739: "leave"
26745: "enter"
26751: " the room, the orb evaporates out of your hands!  It rematerializes on its pedestal.\n\n"
26838: "The vault door is sealed.\n"

Finally, there are two dictionaries of characters. I suspect the first one is used for the normal codes that you encounter during the game, and the second is used for the final (mirrored) code:

25880: "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
25933: "dbqpwuiolxv8WTYUIOAHXVM"

(notice that the second list only contains horizontally symmetric characters!)

Code generation

Following up on the theory that the dictionary at 25880 is used for code generation, here's where it shows up as an argument:

3857: call 1480 "Chiseled on the wall of one of the passageways, you see:\n\n    "
3859: pop  r2
3861: pop  r1
3863: pop  r0
3865: rmem r0 3748
3868: r1 = 25880
3871: r2 = 32767
3874: r3 = 28313
3877: call 1863

Let's see where else 1863 is called:

4766: call 1480 "You find yourself writing \""
4768: pop  r2
4770: pop  r1
4772: pop  r0
4774: r0 = 4242
4777: r1 = 25880
4780: r2 = 32767
4783: r3 = 28411
4786: call 1863

5536: call 1480 "You wake up on a sandy beach with a slight headache.  The last thing you remember is activating that teleporter... but now you can\'t find it anywhere in your pack.  Someone seems to have drawn a message in the sand here:\n\n    "
5538: pop  r2
5540: pop  r1
5542: pop  r0
5544: r0 = r7
5547: r1 = 25880
5550: r2 = 32767
5553: push r3
5555: r3 = 29254
5558: call 1863

5643: call 1480 "You activate the teleporter!  As you spiral through time and space, you think you see a pattern in the stars...\n\n    "
5645: pop  r2
5647: pop  r1
5649: pop  r0
5651: r0 = 0
5654: r2 = 1 + 27115
5658: rmem r1 r2
5661: r0 = r0 + r1
5665: r0 = r0 * 31660
5669: call 2147     // xor
5671: rmem r1 27115
5674: r1 = r1 + 27115
5678: r2 = r2 + 1
5682: r1 = r2 > r1
5686: jf   r1 5658
5689: r1 = 25880
5692: r2 = 32767
5695: push r3
5697: r3 = 29570
5700: call 1863

5767: call 1480 "You gaze into the mirror, and you see yourself gazing back.  But wait!  It looks like someone wrote on your face while you were unconscious on the beach!  Through the mirror, you see \""
5769: pop  r2
5771: pop  r1
5773: pop  r0
5775: rmem r0 3977
5778: rmem r1 3978
5781: call 2147     // xor
5783: rmem r1 3979
5786: call 2147     // xor
5788: r1 = 25933
5791: r2 = 4
5794: push r3
5796: r3 = 29849
5799: call 1863

Judging by the neighboring strings, this is definitely used to print codes! The function seems to take four arguments:

Let's take a look at the function. Be warned, it's the longest one yet!

1863:
1863: push r3
1865: push r4
1867: push r5
1869: push r6

// This is a copy loop which moves data from `r3` to a
// length-prefixed array at location 6147.  When running,
// the length is always 3, so it copies 3 words to memory
// addresses 6148-6150
1871: r6 = 1
1874: r4 = r3 + r6
    1878: rmem r4 r4
    1881: r5 = 6147 + r6
    1885: wmem r5 r4
    1888: r6 = r6 + 1
    1892: rmem r5 6147
    1895: r4 = r6 > r5
    1899: jf   r4 1874

// outer loop
1902: r3 = 0
1905: r4 = 0
    // inner loop, with r4 as our accumulator

    // read a value from the length-prefixed array at 6147,
    // wrapping using the modulo operator:
    // r6 = memory[(r4 % memory[6147]) + 6147 + 1]
    1908: rmem r5 6147
    1911: r5 = r4 % r5
    1915: r5 = r5 + 6147
    1919: r5 = r5 + 1
    1923: rmem r6 r5

    // mutate that value and write it back to the array
    // r6 = r6 * 5249 + 12345
    1926: r6 = r6 * 5249
    1930: r6 = r6 + 12345
    1934: wmem r5 r6

    // xor with the key provided in r0
    1937: push r0
    1939: push r1
    1941: r1 = r6
    1944: call 2147 // r0 = xor(r0, r6)
    1946: r6 = r0
    1949: pop  r1
    1951: pop  r0
    // At this point, our pseudorandom value is in r6

    // Read the length of the character dictionary
    // and find an offset modulo that length, converting
    // the pseudorandom value into an offset into the
    // dictionary
    1953: rmem r5 r1
    1956: r6 = r6 % r5
    1960: r6 = r6 + 1

    // set outer loop termination condition
    1964: r5 = r6 > r2
    1968: jt   r5 1974
        1971: r3 = 1

    // read the character from the dictionary into r6
    1974: r6 = r6 + r1
    1978: rmem r6 r6

    // increment our loop variable
    1981: r4 = r4 + 1

    // write the character from r6 to an array
    1985: r5 = r4 + 6151
    1989: wmem r5 r6

    // exit the loop when we have filled the array
    1992: rmem r5 6151
    1995: r5  = r4 == r5
    1999: jf   r5 1908
2002: jf   r3 1902

2005: push r0
2007: r0 = 6151
2010: call 1540  // print the string that we crafted
2012: pop  r0

2014: pop  r6
2016: pop  r5
2018: pop  r4
2020: pop  r3
2022: ret

This ends up being pretty straight-forward: we're building a string in-memory using a pseudo-random algorithm, seeded with a key that's based on machine state (so it's hard to guess without actually playing the game).

The only part I don't understand is the outer loop: from tracing execution, the jump at 2002 is never taken, so I don't understand the purpose of this loop (or the argument passed in r2).

Remaining questions

At this point, there are two questions remaining:

I've got a few ideas on that front, but this post is long enough already. If a fellow recreational reverse engineer want to take up the challenge, I'd be happy to link to your write-up; just send me an email.

The Annotated Synacor Challenge

To give you a head start, here's my full annotated disassembly.

This annotation shows what strings are printed at various points (handling both plain-text and obfuscated printing), along with my best guesses for functions.