We haven't had that spirit here since nineteen twenty-four...

September 25, 2019 5:39 AM

THERE IS A TAVERN HERE. INSIDE THE TAVERN, YOU SEE VALIS. SELECT AN OPTION:
- GO (N)ORTH
- GO (E)AST
- (R)EVERSE ENGINEER A CUSTOM CPU FROM A SINGLE PROGRAM

Robert Xiao writes up how he and his teammates from Carnegie Mellon's Plaid Parliament of Pwning figured out how to beat an old-style text adventure game the hard way: by analyzing the binary of its program — written for a wholly-custom CPU.

This task was part of this year's DragonCTF Teaser. What's a CTF challenge? It's a competition for computer students and professionals where the goal is to Capture The Flag by solving tasks related to information security. For example, you might be given a program that asks for a password and need to figure out what that password is or how to bypass the password check. If you solve it, you can get a "flag" that proves you've done so. Sara Aladham works out an example of how this might be done as part of her beginner's guide to CTFing.

There are a number of CTF challenges throughout the world and many teams that compete in them; CTFtime keeps track of many of them.

How do you construct a CTF challenge? Check out the source code of the CPU challenge!

posted by metaquarry (15 comments total)

(CTF challenges previously)
posted by metaquarry at 5:47 AM on September 25, 2019

YOUR CHOICE: T

YOU ENTER THE TAVERN AND APPROACH VALIS.

- HEY, I WAS WONDERING IF YOU COULD HELP ME FIND THE FLAG?
- THE FLAG? MAYBE, BUT FIRST, I NEED A REDBULL.
- I... I DON'T HAVE A REDBULL.
- WELL THEN, MAKE YOURSELF USEFUL AND FIND ONE.


I spot an anachronism, for something that supposedly dates to the '60s.
posted by Aardvark Cheeselog at 6:31 AM on September 25, 2019 [2 favorites]

Wow, this is not only impressive reverse-engineering but a very well written and entertaining summary of both the process and experience of doing it.
posted by meinvt at 7:11 AM on September 25, 2019

I assume the framing story that this is an old program is just that. Still quite an accomplishment, though someone’s notional old 60’s computer is likely to not be nearly as strange as a real old machine.
posted by Gilgamesh's Chauffeur at 7:13 AM on September 25, 2019 [1 favorite]

Cool framing, OP!
posted by stinkfoot at 7:14 AM on September 25, 2019

I spot an anachronism

When you choose to talk to VALIS, it's probably best to ignore minor anachronisms. Pulling that thread will only lead to oddities in the timeline and eventually the hierarchy of fictional realities.
posted by mubba at 7:20 AM on September 25, 2019 [13 favorites]

I am really enjoying articles like this one and the one in the Entombed post the other day, looking a long way back to when I had the time and energy to get into some 6502 assembly language or cracking a game.
I have worked on a 5-bit machine, the IBM 3036. (actually two 5-bit machines multiprocessing)
posted by MtDewd at 9:00 AM on September 25, 2019 [1 favorite]

Here’s a 30m talk about the subject if you’re interested in more.

I’m glad their custom cpu challenges are getting better. Some early ones were rough...
posted by yeahwhatever at 11:45 AM on September 25, 2019

The answer is: EGRESS
posted by humboldt32 at 12:47 PM on September 25, 2019

For Gilgamesh's Chauffeur and MtDewd:
PDP-8: 12 bit words, 12 bit instructions
PDP-1: 18 bit words, 18 bit instructions
PDP-10: 36 bit words, 36 bit instructions.
Burroughs Large Systems: 51 bit memory, 3 tag bits plus 48 bit data. variable instruction length.
CDC-6400: 60 bit words, 15 or 30 bit instructions
Cray-XMP: 64 bit words, 16 bit instructions
posted by Metacircular at 1:22 AM on September 26, 2019

I assume the framing story that this is an old program is just that.

Yes. The intro starts the backstory with Here’s the description for the CPU Adventure problem, with a cute fictional backstory

I'd seen discussion of various CTFs but didn't realize there was a whole genre of 'figure out what the hell this mystery processor is doing" CTFs. Cool!
posted by rmd1023 at 6:50 AM on September 26, 2019

In re "old machines are weird," one of the oddest commercially-successful computers was the IBM 1401, at least that I'm familiar with. It used BCD (6-bit character set with alphas and things crammed in) in indefinite-length strings as its data format, even for arithmetic, and supported memory-to-memory arithmetic operations on indefinite-length fields.

I wonder if it would have been any harder to figure out the puzzle if it had been running on a 1401 emulator? The non-contiguous-alphabet thing from BCD would have been an extra fillup, anyway.

Also, my bad for not reading the article carefully enough to notice that it was definitely a fictional machine. It was a really nicely-done puzzle and an impressive solution.
posted by Gilgamesh's Chauffeur at 12:03 PM on September 27, 2019 [1 favorite]

Oh yeah, one thing that is mind-blowing about old machines: there wasn't such a thing as an illegal instruction. All instruction patterns, even if not intentionally, did something and programmers (being people) found uses for the something and consequently manufacturers had to continue supporting something even if it was just unintentional behavior due to their initial implementations.

Just like eating the first oyster or making the first pair of pants, it required a genius-level insight to realize that there was a good reason to prohibit using part of the instruction space.
posted by Gilgamesh's Chauffeur at 12:08 PM on September 27, 2019 [1 favorite]

The 6502 was still like that; there's a lot of “undocumented instructions” that are really just the other rows of whatever table decodes the documented instructions. Most of them aren't terribly useful, but occasionally someone found a use for one in a tight loop or something.
posted by acb at 8:26 AM on October 2, 2019

old machines: there wasn't such a thing as an illegal instruction.
I guess that depends on what you mean by old.
The worst mainframe bug I ever saw (and I saw it on 3 occasions) was on an IBM 3033 (1978), where a control line from the PSCF (storage control) to the instruction pre-processor would become disconnected (due to poor packing for shipment).
This would result in random occurrences of the instruction stream filling with x'FF's. FF is an illegal 360/370 instruction, and like any other unassigned op code, resulted in a Program Check with an Operation Exception (interrupt code 0001)
Just checked my IBM 1401 (1959) Manual of Instruction as well: 'An invalid Op code, or an incorrectly interpreted Op code ... will turn on the Op register check latch... The check latch stops the machine and lights the Op register check light.'

I do think it's fun that the 6502 would try to do undocumented operations, but by the time I read about them, I was past playing with 6502 ML.
It looks like some are actually useful, given the small RAM: e.g. SLO {adr} = ASL {adr} + ORA {adr} , combining 2 commands.
posted by MtDewd at 10:01 AM on October 2, 2019