Category Archives: Game Hacking

Shortcut To The Treasure

Followup: Some Reddit readers tackled this challenge and conquered it. Read up on it here.

Back in the glory days of the old 8-bit Nintendo Entertainment System, I used to read my Nintendo Power magazine issues religiously. One issue that stood out to me, and that I never forgot about, is one that briefly mentioned Treasure Master (volume 26, July 1991, Robin Hood: Prince of Thieves issue).

This will be the first NES game where you can actually win prizes by playing it to the finish! The Game Pak will be released in the fall, and everyone will have time to master it. When you finish the game, you’ll reach a point where you can enter a speical password. In February of 1992, American Softworks will reveal the password that will allow you to play a secret portion of the game. The first person to finish the secret level and call in will win a $25,000 bond. Many of those who finish later will still be eligible for prizes– the sooner you finish, the better the prize. As you can imagine, the code is top secret, and the password system has been proven uncrackable by MIT and the CIA. (emphasis added)

click for larger image

So the gimmick for this substandard, side-scrolling, run & jump game was that players would buy it, play it, and build up skill in a few months. Then, after everyone has had a chance to get really good at the game, the company would release a password that would unlock a secret stage. Play through this stage and you could win big prizes.

Naturally, the part about the uncrackable code caught my attention. I didn’t even realize the CIA provided such a vetting service. Anyway, I didn’t hear anything else about the game again. Many years passed and I saw the game in a used video game shop. I figured it was time to revisit the uncrackable code issue since I know a little more about computers and codes now. And I also know better than to accept an uncrackable code claim at face value.

How uncrackable is the code? The introductory blurb from Nintendo Power raises some questions, many of which can be answered by the Treasure Master instruction manual. The full details of the contest are provided. Apparently, the password was to be announced on MTV on April 11, 1992, probably during a commercial. Players would enter the password, along with their game cartridge’s unique serial number, in order to unlock the special levels of the game. Upon completion of the levels, the game would return a special winning number that the player could give to the operator on the other end of a 1-900 phone number to try to win a prize.

To be fair, the official manual doesn’t mention the uncrackable code nonsense. The James Bond material highlighted in the Nintendo Power preview can probably be attributed to some Marketing/PR flunkie at American Softworks working more closely with the magazine than their own engineering department.

Also, Nintendo really wants you to know that they have nothing to do with the contest:

Threat Model
Continue reading →

Important Strides In Compression Technology

After completing gcfuse and xbfuse, I am hungry for more game-related filesystem hacking. I set my sights on another format — I wondered what lay in hiding on those universal media discs (UMDs) that the Sony PlayStation Portable uses.

Universal Media Disc (UMD) for the Sony PSP

You probably don’t have the tools or the know-how to rip sectors off of these discs by yourself. If you happen to come across a pre-ripped image in the shadier portions of the internet, you may find that the rip has an extension of .cso. This stands for compressed ISO. Would you be surprised to learn that there is not a lot of documentation about this format out there? There are some closed but free Windows tools out there to convert between ISO and CISO and some other formats. What knowledge is out there indicates that the format offers 9 different compression levels. So does stock zlib.

Internally, a CISO format begins with a ‘CISO’ signature and eventually starts in with an enormous table of indices. These seem to be absolute offsets into the file. My first theory was that they are individual files. Combined with the above zlib speculation, I figured that each file was zlib compressed. That’s when I enlisted the help of the fellow who recently implemented native zlib functionality in FFmpeg — Mans Rullgard.

What he managed to figure out was that each index in the table actually references a 2-kilobyte sector. Further, the offset has its high bit cleared to indicate that the sector is the last of a file (a UMD has a max capacity of 1.8 GB which can be expressed in only 31 bits). Thus, the deltas between the indices imply the length of the sector, which is almost alway 2048 bytes, except for (statistically) the last sector of the file. So this leads us to the revolutionary compression technology on display here–

Do not store the final sectors of individual files with implicit zero-padding. (Not true; read further analysis in the comments.)

Hey, it counts as compression. The technique exploits a characteristic inherent in a specific type of data. It seemed a bit silly at first, in a “would that actually make a difference?” kind of way. But the math does work. At least for the few representative samples observed, the CISO image is about 75% of the size of the “uncompressed” image. If a disc uses its full 1.8 GB, then 1,800,000,000 bytes / 2048 bytes/sector = 878907 sectors. 878907 sectors * 4 index bytes/sector = 3515628 bytes. It’s 3.5 MB, but not nearly enough to blow the 2 GB limit necessary to make this format work in the worst case scenario.

Honestly, I haven’t had this much fun collaboratively cracking a file format since a bunch of us got together back in the day and worked out Nullsoft Video (NSV)… and then the official spec was released anyway.

There are still a number of mysteries:

None of this explains the advertised compression levels feature. I am starting to think that perhaps the entire index table can be zlib compressed, but that it simply wasn’t done for the observed samples.
There is no real filesystem data present. It stands to reason that the original UMD must have some notion of a filesystem since some utility knew where the files lived and how long they were. The Wikipedia article claims that these discs use an ISO-9660 filesystem. I generally know what ISO-9660 filesystem data looks like, and I’m not seeing it here. There isn’t much familiar, except for some PNG files which are difficult to interpret, leading to…
Is the filesystem fragmented? That would be highly uncharacteristic of a filesystem built to live on an optical, read-only medium. But cursory investigations have indicated that there might be some fragmentation.
Exactly what is the usage model for these images? Real-time access from a memory stick, I hope? Because Mans determined that stock bzip2 performs better than CISO on a raw image.

Here are the format details we have worked out so far. If anyone knows the original author of the CISO format, send him over here. In my experience, people who design these types of formats are not necessarily trying to keep anything secret; they just haven’t gotten around to writing up and publishing a formal description, and have no compelling reason to release their tools’ source code into a Windows world where most people can’t compile anyway.

Continue reading →

xbfuse

Well, you knew this was coming– xbfuse. This is a program that leverages the wonderful FUSE paradigm to mount a Microsoft Xbox disc filesystem — the so-called XDVD filesystem — under Linux. I hammered out the bug mentioned in yesterday’s post (sure enough, a 64-bit offset was being demoted to a signed 32-bit quantity at one point, and that matters for filesystems this large). This is what the program looks like in action:

$ xbfuse Halo-3.iso mnt/

$ ls -al mnt/
total 4
dr-xr-xr-x  6 melanson melanson       0 2007-11-07 20:00 .
drwxr-xr-x 47 melanson melanson    4096 2007-11-10 17:31 ..
dr-xr-xr-x  2 melanson melanson       0 2007-11-07 20:00 bink
-r--r--r--  1 melanson melanson 8929280 2007-11-07 20:00 default.xex
dr-xr-xr-x  5 melanson melanson       0 2007-11-07 20:00 maps
dr-xr-xr-x  2 melanson melanson       0 2007-11-07 20:00 $SystemUpdate
dr-xr-xr-x  2 melanson melanson       0 2007-11-07 20:00 waves
-r--r--r--  1 melanson melanson  561152 2007-11-07 20:00 WaveShell-Xbox.dll
-r--r--r--  1 melanson melanson  724992 2007-11-07 20:00 WavesLibDLL.dll

$ ls -al mnt/bink/
total 0
dr-xr-xr-x 2 melanson melanson        0 2007-11-07 20:00 .
dr-xr-xr-x 6 melanson melanson        0 2007-11-07 20:00 ..
-r--r--r-- 1 melanson melanson 77940860 2007-11-07 20:00 attract_1_60.bik
-r--r--r-- 1 melanson melanson 61324440 2007-11-07 20:00 attract_2_60.bik
-r--r--r-- 1 melanson melanson 72829508 2007-11-07 20:00 attract_3_60.bik
-r--r--r-- 1 melanson melanson 69631000 2007-11-07 20:00 credits_60.bik
-r--r--r-- 1 melanson melanson 21163412 2007-11-07 20:00 intro_60.bik

$ fusermount -u mnt/

So Halo 3 uses Bink files, some very high resolution ones, rather than any Xbox-specific multimedia formats, like XMV. Actually, Bungie (the company behind Halo) may have a history with Bink, as I seem to recall that the FMV for the PC demo version of Halo was also Bink (or at least one promotional file).

I actually just thought to look up whether there are other options for mounting Xbox filesystem images under Linux. The format certainly seems to be of much greater interest than, say, GameCube filesystem images. I did find a project called Mount ISO Image that is supposed to be able to handle XDVD filesystems. Though I can’t really figure out if it’s a KDE application, a script, or a KDE script.

I took a slightly different approach to writing this one. All in all, I suppose the result is much simpler than gcfuse. The GameCube filesystem is an odd beast and required a lot of custom hacks to parse all of the data structures. However, writing xbfuse scared me more because I had to write 2 mutually recursive functions: After loading the volume descriptor, call xbfs_recurse_directory(), which then calls xbfs_recurse_file_subtree(), which calls not only itself, but also xbfs_recurse_directory() when a file entry happens to be a directory. I thought about writing xbfuse in such a way that it would traverse the data structures on demand when loading a file, since the data structures are laid out to be conducive to binary searching. I also thought about only loading the first level of the directory tree, and loading other levels on demand. But in the end, I just went with the full tree load at the outset and finally squashed the 64 -> 32-bit bug and the program seems to work quite well.

What next? Wii discs seem to use a different format than the GameCube discs and I would like to find out what that is. Plus, I am still dogged by the slightly custom Dreamcast ISO-9660-style format. There is a lot of interesting Sofdec media on those Dreamcast games. And it only takes about 26 hours to rip the contents of a Dreamcast disc onto your PC, provided that you have the right serial cable.

Related Posts:

Xbox Multimedia, Finally!

At long last, I wrote that FUSE driver for the Microsoft Xbox DVD filesystem. I will hopefully get around to releasing it, just as soon as I can test it a little bit more. I am not completely confident with the new driver but that might be because the filesystem that I was using to test the program appears to have a number of problems and might be corrupted (or it could very well be that Xbox 360 games use a slightly different filesystem layout than Xbox games, or that I’m not correctly handling 32-bit thresholds on large filesystem images). When I started studying other smaller Xbox filesystems, things seemed to go quite smoothly.

So did I finally find some samples of the fabled XMV format? Yes! At long last. Far and away, however, the Bink format appears to dominate, at least on the sample of games that I surveyed.

I found 4 Xbox games that include XMV media: Thrillville, Xiaolin Showdown, Monopoly Party, and Lego Star Wars 2: The Original Trilogy. You can find samples at the usual place. The last game on that list surprised me– Lego Star Wars is an aggressively multi-platform franchise. While the disc only encodes the intro movie as an XMV file (and in both PAL and NTSC variations), this would imply to me that versions for other platforms are encoded in that platform’s preferred SDK format, i.e., MPEG-2 for PS2, THP or H4M for GameCube, and who knows for Windows. Typically, cross-platform games take the easy way out using portable middleware solutions like Bink.

A little bird once told me that XMV was on the horizon for Xbox multimedia and that it would be straight ASF files with WMV2 video and MS ADPCM audio. If that’s true, then it looks like the WMV2 puzzle was solved just in time. These XMV files certainly are not stock ASF files. Curiously, the most notable signature is ‘Xbox’ spelled, ahem, in little endian notation in bytes 12-15: ‘xobX’. Width and height are encoded at bytes 20-23 and 24-27, respectively. I see sample rate data at bytes 40-43. I tried to find framerate data by comparing the headers of the PAL vs. NTSC Lego SW demo movies. I was hoping to find fields with 50 or 25 for PAL and 60 or 30 for NTSC. No such luck. However, I have also read that the movies are 29.97 fps, so the framerate data might be encoded as floating- or fixed-point numbers.

The Lego Star Wars 2 game has lots of interesting stuff to peruse. Since it is LucasArts software, it should be no surprise that human-readable scripts play a role. Indeed, there is a whole directory of scripts, such as this simpler file scripts/Attack.scp:

state Base {
        Conditions {
                if GotOpponent == 1 goto StartAttack
        }
        Actions {
                BreakFormation
        }
}

state StartAttack {
        Conditions {
        }
        Actions {
                KeepWeaponOut
                SetState "Attack"
        }
}

state Attack {
        Conditions {
                if GotOpponent == 0 goto Base
        }
        Actions {
                EngageOpponent "goalrange 1.5" "firerange 3"
        }
}

Thrillville is also from LucasArts and has various markings to indicate that the Lua language is involved, as in other LucasArts titles such as Grim Fandango.

Lego Star Wars 2 also contains a large number of .wavm files. These could be headerless PCM or ADPCM data. What was that FFmpeg incantation for converting headerless, raw PCM to a container format, manually specifying parameters?

One more item– Call of Duty 3. This uses a format with the extension XBV and it begins with the signature ‘AFMV’. I don’t have many other clues on it, but I have thrown together a MultimediaWiki page on the matter and uploaded some samples, as is customary.