After our paper release, and only when quality control has been passed, we will make an electronic release named pocorgtfol3.pdf It is valid as PDF, ZIP, and PostScript; please read it with Adobe Reader, unzip, and gv.
We begin on page 604 with the story of how STAR RAIDERS by Doug Neubauer for the Atari 400 was taken apart by Lorenz Weist, from a mere ROM cartridge dump to annotated and literate 6502 disassembly. By a stroke of luck, Lorenz was able to read Doug’s original source code for the game after completing his reverse engineering project, giving him the rare opportunity to confirm his understanding of the game’s design and behavior.
On page 645, James Forshaw introduces us to a nifty little trick for simplifying reliable exploitation of race condition vulnerabilities. Rather than spin up a dozen attempts to improve racetrack odds, he instead induces situations with pathological performance penalties to Windows NT system calls, stunning the threads of execution that might interfere with his exploit for twenty minutes or more!
Micah Elizabeth Scott continues to send us brilliant articles that refuse to be described by a single abstract, so let’s just say that on page 659 she explains a USB magic trick in which her Face Whisperer board—combining the Facedancer and the Chip Whisperer—is able to reliably glitch the USB stack of an embedded device to dump its firmware. Or, we could say that on page 659 she explains how to use undocumented commands from that firmware dump to program the Harvard device by ROP. Or, we could say that on page 659 she shows you to read RFID tags with a Wacom tablet. These tricks are all the same article, and you’d be a fool not to read it.
In PoC‖GTFO 10:8, Travis Goodspeed jailbroke the Tytera MD380 radio to allow for firmware extraction and patching. Since then, a lively open source project has sprung up, with fancy new features and fixes to old bugs. On page 676, he describes how to rip the AMBE audio codec out of the radio firmware, transforming it into a command line audio processing tool that runs on any Linux workstation. Similar tricks can be used to quickly toss together emulators for many ARM and PowerPC embedded systems, re-using their library functions, or fuzzing their parsers in the familiar environment of an everyday laptop.
Evan Sultanik is back with a safe cracking adventure that could only be expressed as a play in three acts, narrated by our own Pastor Manul Laphroaig. Speaking parts are available for Alice Feynman, Bob Schrute, Havva al-Kindi, and the ghost of Paul Erdöos. You’ll find Evan’s script on page 687.
Matt Knight has been reverse engineering the PHY of LoRa, a low-power protocol for sub-GHz wireless networking over long distances. On page 702 you will find not just the protocol details that allowed him to write an open source receiver, but, far more importantly, you will also find the methods by which he reverse engineered this information from captured packets, vague application notes, and the outright lies of the patent application.
Pastor Manul Laphroaig, your friendly neighborhood evangelist of the gospel of the weird machines, has a sermon for you on page 734. He reminds us that science takes place neither on stage in front of a live studio audience nor in committees and government offices, but over a glass of fine scotch that’s accompanied by finer conversation of practitioners. In the same way that we oughtn’t put Tim the “Tool Man” Taylor in charge of vocational education, we ought to leave the teaching of science to those who do it, not those who talk about it on TV.
Geoff Chappell is an old-school reverse engineer, an x86 archaeologist who has spent the past twenty-four years reading Windows binaries to identify all the forgotten features and corner cases that the rest of us might take for granted.1 On page 740, he introduces us to the mystery of Microsoft’s Shim Database Compiler, an unpublished tool for compiling driver shims that doesn’t seem to be available to the outside world. Geoff shows us that, in fact, the tool is available, wrapped up inside of a GUI as QFixApp.exe or CompatAdmin.exe. By patching the program to expose its intact WinMain(), he can recover the long-lost ShimDBC.exe for compiling Windows driver compatibility shims from XML!
Evan Sultanik and Philippe Teuwen have teamed up on page 757, to explain the inner workings of pocorgtfol3.pdf, which you can rename to read as pocorgtfol3.zip or pocorgtfol3.ps.
13:2 Reverse Engineering Star Raiders
by Lorenz Wiest
STAR RAIDERS is a seminal computer game published by Atari Inc. in 1979 as one of the first titles for the original Atari 8-bit Home Computer System (Atari 400 and Atari 800). It was written by Atari engineer Doug Neubauer, who also created the system’s POKEY sound chip. STAR RAIDERS is considered to be one of the ten most important computer games of all time.2
The game is a 3D space combat flight simulation where you fly your starship through space, shooting at attacking Zylon spaceships The game’s universe is made up of a 16 × 8 grid of sectors Some of them contain enemy Zylon units some a friendly starbase The Zylon units converge toward the starbases and try to destroy them. The starbases serve as repair and refueling points for your starship. You move your starship between sectors with your hyperwarp drive The game is over if you have destroyed all Zylon ships, have ran out of energy, or if the Zylons have destroyed all starbases.
At a time when home computer games were pretty static—think SPACE INVADERS (1978) and PAC MAN (1980)-STAR RAIDERS was a huge hit because the game play centered on the very dynamic 3D first-person view out of your starship’s cockpit window.
The original Atari 8-bit Home Computer System has up to 48 KB RAM and uses a Motorola 6502 CPU. The same CPU is also used in the Apple II, the Commodore C64 (a 6502 variant), and the T-800 Terminator.3 Several proprietary Atari custom chips provide additional capabilities to the system. STAR RAIDERS shows off many of them: 5 Players (sprites), mixed text and pixel graphics modes, dynamic Display Lists, a custom character set, 4-channel sound, Vertical Blank Interrupt and Display List Interrupt code. Even the BCD mode of the 6502 CPU is used.
I have been always wondering what made STAR RAIDERS tick. I was especially curious how that 3D first-person view star field worked, in particular the rotations of the stars when you fly a turn. So I decided to reverse engineer the game, aiming at a complete, fully documented assembly language source code of STAR RAIDERS.
In the following sections I’ll show you how I approached the reverse engineering effort, introduce my favorite piece of code in STAR RAIDERS, talk about how the tight memory limits influenced the implementation, reveal some bugs, point at some mysterious code, and explain how I got a grip on documenting STAR RAIDERS. From time to time, to provide some context to you, I will reference memory locations of the game, which you can look up in the reverse engineered, complete, and fully documented assembly language source code of STAR RAIDERS available on GitHub.4
Getting Started
STAR RAIDERS is distributed as an 8 KB ROM cartridge, occupying memory locations $A000 to $BFFF.
The obvious first step was to prod a ROM dump with a disassembler and to apply Atari’s published hardware and OS symbols to the disassembly. To my surprise this soon revealed that code and data were cleanly separated into three parts:
$A000 – $A149 Data Part 1
$A14A – $B8DE 6502 Code
$B8DF – $BFFF Data Part 2
This separation helped me to get an overview of the code, as I could create a disassembly in one go without sifting slowly through the bytes of the ROM, deciding which were instructions and which were data.
Closer inspection of the code part revealed that it was composed of neatly separated subroutines. Each subroutine handles a specific task. The largest subroutine is the main game loop GAMELOOP ($A1F3), shown in Figure 13.1. What I expected to be spaghetti code, given the development tools of 1979 and the substantial amount of game features crammed into the 8K ROM, turned out to be surprisingly structured. Table 13.1 lists all subroutines of STAR RAIDERS, as their function emerged during the reverse engineering effort, giving a good overview how the STAR RAIDERS code is organized.
Figure 13.1: Simplified Call Graph of Start Up and Game Loop<
br />
Table 13.1: Star Raiders Subroutines
Figure 13.2 shows the “genome sequence” of the STAR RAIDERS 8 KB ROM: The 8,192 bytes of the game are stacked vertically, with each byte represented by a tiny, solid horizontal line of 8 pixels. This stack is split into strips of 192 bytes, arranged side-by-side. Alternating light and dark blue areas represent bytes of distinct subroutines.5 Alternating light and dark green and purple areas represent bytes of distinct sections of data. (Lookup tables, graphical shapes, etc.) When data bytes represent graphical shapes, the solid line of a byte is replaced by its actual bit pattern (in purple color).
There are a couple of interesting things to see:
The figure reflects the ROM’s separation into a data part (green and purple), a code part (blue), and one more data part (green and purple).
The first data part contains mostly the custom font, shown in strips 1 and 2.
The largest contiguous (dark) blue chunk represents the 1246 bytes of the main game loop GAMELOOP ($A1F3), in strips 3 to 10.
At the beginning of the second data part are the shapes for the player sprites, in strips 34 to 36.
The largest contiguous (light) green chunk represents the 503 bytes of the game’s word table WORDTAB ($BC2B), in strips 38 to 41.
A good reverse engineering strategy was to start working from code locations that used Atari’s published symbols, the equivalent of piecing together the border of a jigsaw puzzle first before starting to tackle the puzzle’s center. Then, however, came the inevitable and very long stretch of reconstructing the game’s logic and variables with a combination of educated guesses, trial-and-error, and lots of patience. At this stage, the tools I used mostly were nothing but a text editor (Notepad) and a word processor (Microsoft Word) to fill the gaps in the documentation of the code and the data. I also created a memory map text file to list the used memory locations and their purpose. These entries were continually updated, often discarded after it turned out that I had taken a wrong turn.
A Programming Gem: Rotating 3D Vectors
What is the most interesting, fascinating, and unexpected piece of code in STAR RAIDERS? My pick would be the very code that first interested my in this code: subroutine ROTATE ($B69B), which rotates objects in the game’s 3D coordinate space, shown on page 621. And here is why: Rotation calculations usually involve trigonometry, matrices, and at least a few multiplications. But the 6502 CPU has only 8-bit addition and subtraction operations. It does not provide multiplication or division operations, and certainly no trig operation! So how do the rotation calculations work?
Let’s start with the basics: The game uses a 3D coordinate system with the position of our starship at the center of the coordinate system. The locations of all space objects (Zylon ships, meteors, photon torpedoes, starbase, transfer vessel, Hyperwarp Target Marker, stars, and explosion fragments) are described by a position vector relative to our starship.
Figure 13.2: Genome Sequence of the STAR RAIDERS ROM
A position vector is composed of an x, y, and z component, whose values I call the x, y, and z coordinates with the arbitrary unit,
Each coordinate is a signed 17-bit integer number, which fits into three bytes. Bit 16 contains the sign bit, which is 1 for positive and 0 for negative sign. Bits 15 to 0 are the mantissa as a two’s-complement integer.
Some example bit patterns for coordinates:
The position vector for each space object is stored in nine tables. (Three coordinates, with three bytes for each coordinate.) There are up to 49 space objects used in the game simultaneously, so each table is 49 bytes long.
XPOSSIGN XPOSHI XPOSLO
($09DE..$0A0E) ($0A71..$0AA1) ($0B04..$0B34)
YPOSSIGN YPOSHI YPOSLO
($0A0F..$0A3F) ($0AA2..$0AD2) ($0B35..$0B65)
ZPOSSIGN ZPOSHI ZPOSLO
($09AD..$09DD) ($0A40..$0A70) ($0AD3..$0B03)
With that explained, let’s have a look at subroutine ROTATE ($B69B). This subroutine rotates a position vector component (coordinate) of a space object by a fixed angle around the center of the 3D coordinate system, the location of our starship. This operation is used in three of the game’s four view modes (Front view, Aft view, Long-Range Scan view) to rotate space objects in and out of the view.
Rotation Mathematics
The game uses a left-handed 3D coordinate system with the positive x-axis pointing to the right, the positive y-axis pointing up, and the positive z-axis pointing into flight direction.
A rotation in this coordinate system around the y-axis (horizontal rotation) can be expressed as
where ry is the clockwise rotation angle around the y-axis, x and z are the coordinates before this rotation, and the primed coordinates x' and z' the coordinates after this rotation. The y-coordinate is not changed by this rotation.
A rotation in this coordinate system around the x-axis (vertical rotation) can be expressed as
where rx is the clockwise rotation angle around the x-axis, z and y are the coordinates before this rotation, and the primed coordinates z' and y' the coordinates after this rotation. The x-coordinate is not changed by this rotation.
Subroutine Implementation Overview
A single call of subroutine ROTATE ($B69B) is able to compute one of the four expressions in Equations 13.1 and 13.2. To compute all four expressions to get the new set of coordinates, this subroutine has to be called four times. This is done twice in pairs in GAMELOOP ($A1F3) at $A391 and $A398, and at $A3AE and $A3B5, respectively.
The first pair of calls calculates the new x and z coordinates of a space object due to a horizontal (left/right) rotation of our starship around the y-axis following the expressions of Equation 13.1.
The second pair of calls calculates the new y and z coordinates of the same space object due to a vertical (up/down) rotation of our starship around the x-axis following the expressions of Equation 13.2.
If you look at the code of ROTATE ($B69B), you may be wondering how this calculation is actually executed, as there is neither a sine nor cosine function call. What you’ll actually find implemented, however, are the following calculations:
Joystick Left
Joystick Right
Joystick Down
Joystick Up
CORDIC Algorithm
When you compare the expressions of Equations 13.1–13.2 with expressions of Equations 13.3–13.6, notice the similarity between the expressions if you substitute6
sin(ry) → 1/64
cos(ry) → 1
sin(rx) → 1/64
cos(rx) → 1
From sin(ry) = 1/64 and sin(rx) = 1/64 you can derive that the rotation angles ry and rx by which the space object is rotated (per game loop iteration) have a constant value of 0.89°, as arcsin(1/64) = 0.89°.
What about cos(ry) and cos(rx)? The substitution does not match our derived angle exactly, because cos(0.89°) = 0.99988 and is not exactly 1. However, this value is so close that substituting cos(0.89°) with 1 is a very good approximation, simplifying calculations significantly.
Another significant simplification results from the division by 64, as the actual division operation can be replaced with a much faster bit shift operation.
This calculation-friendly way of computing rotations is also known as the CORDIC algorithm. (COordinate Rotation DIgital Computer.)
Minsky Rotation
There is one more interesting mathematical subtlety: Did you notice that expressions of Equations 13.1 and 13.2 use a new (primed) pair of variables to store the resulting coordinates, whereas in the implemented Equations 13.3–13.6, the value of the first coordinate of a coordinate pair is overwritten with its new value and this value is used in the subsequent calculation of the second coordinate? For example, when the joystick is pushed left, the first call of this subroutine calculates the new value of x according to first expression of Equation 13.3, overwriting the old value of x. During the second call to calculate z according
to the second expression of Equation 13.3, the new value of x is used instead of the old one. Is this to save the memory needed to temporarily store the old value of x? Is this a bug? If so, why does the rotation calculation actually work?
Have a look at the expressions of Equation 13.3. The other Equations 13.4–13.6 work in a similar fashion.
x := x + z/64
z := –x/64 + z
If we substitute 1/64 with e, we get
x := x + ez
z := –ex + z
Note that x is calculated first and then used in the second expression. When using primed coordinates for the resulting coordinates after calculating the two expressions we get
or in matrix form
Surprisingly, this turns out to be a rotation matrix, because its determinant is (1 × (1 – e2) – (–e × e)) = 1.7
This kind of rotation calculation is described by Marvin Minsky in AIM 239 HAKMEM8 and is called “Minsky Rotation.”
Subroutine Implementation Details
To better understand how the implementation of this subroutine works, we must again look at Equations 13.3–13.6. If you rearrange the expressions a little, their structure is always of the form:
TERM1 := TERM1 SIGN TERM2/64
or shorter
TERM1 := TERM1 SIGN TERM3
where TERM3 := TERM2/64 and SIGN := + or – and where TERM1 and TERM2 are coordinates. In fact, this is all this subroutine actually does: It simply adds TERM2 divided by 64 to TERM1 or subtracts TERM2 divided by 64 from TERM1.
When calling this subroutine the correct table indices for the appropriate coordinates TERM1 and TERM2 are passed in the CPU’s Y and X registers, respectively.
PoC or GTFO, Volume 2 Page 33