Monday, April 01, 2013

Sega Genesis - Super Battleship - Jolly Roger

Released in February of 1993, this game seemed innocent enough. I received it as a Christmas gift later that year. No matter how many times I tried, I could not beat the 'Jolly Roger' level... I've picked up the game and put it back down numerous times over the last two decades, but never beaten it until today.

Today, I tell you, of the brave soldiers who fought to disrupt the merchant supply lines near Ilocana island. (NOTE: This isn't historically accurate... not even a little)

Jolly Roger

Day 1: It was a cold day in the Pacific Theater aboard the Battleship Africa when we received our orders. Pacific Command had lost their bloody minds. Our orders were to take on a full armada, an entire naval fleet of ships, with a half-stocked battleship, and destroy the merchant fleet supplying the enemy. Moral was low, but our orders clear. Captain Moses ordered all ahead full, and we proceeded East at 24 knots.

Day 2: The enemy fleet comes into range on radar. It's worse than we imagined and they've already spotted us. Two carriers, four destroyers, a handful of cruisers, and sonar picked up what sounds like a submarine headed our way. The enemy is positioned perfectly in deep water between the two islands, there's no time to go around and they're directly between us and the merchant fleet. Still we proceed on our course.

Day 3: The enemy took a pot shot at us, close enough to the ship to spray water on the deck. Had we been closer to land our crew would already have jumped ship, this mission was doomed to fail before it had even started. In order to avoid certain demise, we veer South East and continue at 24 knots.

Day 4: The enemy has closed enough ground to start firing upon us. We manage to outrun them twice, but suffered some damage. Our sonar is out, but we already know the enemy submarine is coming for us, it's only a matter of time. Despair sets in, but we manage to take stock of our armaments. We had 30 shells, 2 missiles  and a dozen depth charges. Barely enough to sink 1/4 of the enemy fleet...

Day 5: We're approaching the shore line of Ilocana Island, the enemy has already trained it's sights on us and the shore batteries are eagerly waiting for us to come into range. It's only a matter of time now, we're trapped between the enemy navy and the islands Eastern harbor.

Day 6: The enemy submarine finally makes its move, we were hit with a torpedo without any warning. We're now without steering and sonar. Even our bow guns, useless as they may be against our underwater foe, were disabled. Unable to return fire, we set course in the only direction our broken rudder would allow. FORWARD!

Day 7: As if invited, we steamed into Ilocana Harbor at full speed, with guns raised and missiles primed. Before the enemy could even fire a shot, we launched one of our two STS missiles across the harbor and annihilated the enemies barracks and communications tower. The island erupted into panic as we continued to bear down on the shore.

Day 8: With the enemies land communications disabled, and our ship blocking the mouth of the harbor, the islanders had no idea what was in store for them. We issued demands for additional missiles and supplies or face additional bombardment. Little did they know we were down to our last one.

Days 9-18: The ruse worked! The enemy islanders began supplying us with missiles in return for sparing their lives. We happily fired them off away from the island sinking enemy ship after enemy ship. Without communications the islanders had no idea reinforcements were so close, we had done it! Or so we thought...

Day 19: The enemy submarine, immune to our onslaught of missiles and shells, had entered the harbor under our very noses. A volley of torpedoes made that quite clear. We had no time to celebrate, only enough time to steam forward in the only way we could. We ran aground.

Day 20: The enemies merchant fleet grew nearer and nearer to their destination while we had idled in the harbor. The submarine had caught us so very off-guard that we didn't even think to deploy our depth-charges. Now useless, they sat below deck, waiting for a lucky torpedo to send us all to our watery graves.

Day 21: Knowing our death was all but certain, we fired our remaining missiles far and wide, the merchant fleet was far enough away, far enough to be faint shadows on a dimly lit radar display, far.. but not far enough. We sank ten of the twelve merchant ships! We had broken the enemies supply line and decimated their fleet. A cheer broke out on deck as the radar tech called out each blip as it disappeared. By the tenth cheer the crew had lost all sense of order. We had been stranded on a foreign shore, our ship all but sunk if not for the rocks we had run upon, our weapons exhausted, and the enemy submarine closing in for it's final kill; but we had already won.


SPOILERS: How to beat the Jolly Roger level: Head southeast at the start of the mission. Hit start to retreat from any battles you encounter. Continue moving diagonally as fast as your can until you reach the shore, there is a small harbor you can enter. Fire a shell or a missile at the troop barracks on land to take over the port. You will now be restocked at the end of each turn. Use every turn you can to fire a single missile at the merchant ships. Aim for the furthest one you can reach. If attacked, return fire with a single missile and sink them. The submarine will hit you every turn but there isn't much you can do but persevere if it keeps its distance. You should be able to sink 10 merchants within 20 turns. Good luck!

Saturday, September 29, 2012

Reverse Engineering

Why?

Reverse engineering a system (for whatever reason) can be fun and challenging. I recently found myself in need of changing the contents of an 8KB file with no format information whatsoever. I had been playing Final Fantasy 6 on my phone during my morning commute and had accidentally killed off a favorite character of mine in a permanent way. I knew I only needed to flip one or two bits to correct this, but which ones?

Part 1 - Tools:

Tools can make or break an attempt at reverse engineering, some can be as simple as a hex table taped to the side of your monitor, or as complex as a full-fledged debugger. I had the advantage of both :)

  • Something to take notes with
  • Programming calculator (even calc.exe will suffice)
  • Backups of whatever it is you're working on
  • Debugger (if available)
  • Some way of testing your changes
  • Some way of generating new changes
  • A diff tool (diff, windiff, etc)

Part 2 - Poking around:

Getting started can be daunting. 8 KB is a tiny file, but massive when you're trying to figure which single bit is the important one. Start by making a map to narrow your search space.
I opened up the save file and found two-thirds of it mostly empty, given that I was only using the first 'save slot' in the game, it was safe to assume saves were made sequentially in the file. I created a second save in slot 2 and verified this.

So now I have a rough idea of where I'm looking. To test the boundaries of each 'save slot' I flipped a single bit and tested the changes... when I went to test, the game claimed I had zero saves! Good thing for backups. Turns out the game also checksums its data to prevent corruption (and likely also tampering as I was attempting).

Knowing that flipping bits randomly definitely wasn't going to work, it was time for differential analysis:
  1. Backup the file
  2. Make a single change in game
  3. Save
  4. Diff the two files
To my surprise, loading and saving the file without changing anything caused several bytes to change! Upon further inspection, the game has a timer which clocks how many seconds the user has been playing for. This corresponded to 3 bytes somewhere in the middle of the save file. It took a few minutes to realize the game stores its values with the least significant bytes first. So 45 23 01 in memory is 012345 in hex. In addition to the timer bits changing, the last 4 bytes of the save slot also changed an equivalent amount... the checksum!

Part 3 - Mapping data:

Once I had a basic understanding of how the file was organized, I began creating a map of the file and assigning names to blocks of memory. Having a debugger to rapidly make changes and test the results was especially helpful.

Guess and check: One technique to speed up mapping is to pick a value in the game, such as amount of money  then searching the whole file for that exact value. Then change it slightly to see if it's correct.

Differential reverse engineering: Another is to change a value several times within the game, saving after each change and backing up the file, then diffing the files to see which location changed each time and by how much.

Pattern matching: Certain data tends follow a logical pattern, such as text, and can easily be searched for. The unix 'strings' command is great for this. Since this game originated in Japan and was later translated to English, the text turned out to be in some other format than ASCII. Text still follows a pattern though, 'A' is usually one less then 'B'. Applying that to one of the games heroes names, I found that the data for each hero in the game is stored at the very front of the file.

Part 4 - Intuition:

Programmers tend to think alike (even across the ocean). Data that belongs together, is usually grouped together. Data that only requires 1 bit to store, is usually compressed into a single byte with related data. A well written piece of software will always attempt to be organized and efficient.

Data that can be stored statically in ROM and referenced with just an index (or pointer) can be tricky to find. In game 'items' are stored in an inventory as pointers in a table, followed by a second table of integer quantities. Moving items around in game made it very easy to see the link between these two tables since each change in game corresponded to 2 changes in the file (separated by exactly 0xFF bytes).

Final thoughts

Any system can be reverse engineered regardless of how large, complex, or foreign it may be. If I had the source code to this game, tracking down this bit would have taken minutes rather than hours. Closed source projects require more time to understand than their open source counterparts, but they aren't any more secure.

Here is an almost complete mapping of the saved game format for Final Fantasy 6: http://r4v3n.net/files/ff6_saved_game_v1.txt


Tuesday, April 20, 2010

I still exist.

Currently working with a number of fun technologies (Xen, Gentoo, Virtualization, TPM, Vt-X, and Vt-D. Researching ways to measure how resilient the security of a computer system is.

I've also learned how to dance recently.

This blog started out as a way to report my progress on Google Summer of Code.
I worked on adding memcache support to MySQL's query cache.
Since then I've completed my Masters in Computer Science and am pursuing my Phd.

Saturday, September 06, 2008

And with one final click, the project is complete.
I've uploaded the source of my project to Google Code.
This whole project has been quite the experience.

I plan on continuing this blog, don't expect timely updates though.
I'm doing Grad work full-time at WPI (www.wpi.edu) as well as some part time work.

Sunday, August 10, 2008

IT WORKS!!!

And not a moment too soon.
I've finished my day job for the summer and have been pouring over the code the last few days trying to isolate the last two bugs.
I've also received word that I don't have 8 days left, I have 1...so I'm a bit rushed but still hopeful.

As part of my bug fixing for the hit code (which works beautifully now) I was able to remove all of the unnecessary mutex locking from within the cache. This is a nice speed boost as there is no longer any need to lock and unlock when working with the cache. It just works (tm).

I have a fairly rough implementation of the invalidate code that looks something like this:

if(anything changed) {
nuke_the_cache();
}

It works, and it allows for multiple instances to use the same cache.
My next task is to make this a bit more refined (per table invalidation) by using 'namespacing' within memcache. The idea works like this:
For each table, store a "0" in memcache with 'db_name:table_name' as the key.
Each time a table changes, increment that key.
When formulating the key for a query result, include each relevant get('db_name:table_name') in the key hash.

The nice thing about this approach is no matter how much data is in the cache,
invalidating is always O(n) where n is the number of tables involved.
The previous query_cache could slow down a MySQL instance in a write-heavy environment due to searching for and invalidating entries in the cache when a table changed.
With this implementation, everything is non-blocking and when a table changes a quick call to 'memcached_increment()' is all that's needed. Memcached will remove stale entries after they've expired, since once the namespace has changed they will never be read again.

It looks like I will not have time to refactor this into a plug-in during the summer of code timeline. But I've met and exceeded most all of my other goals so I'm not too worried.
I'll have a tarball, a diff, and hopefully a checkin with bzr done tomorrow to prepare for my final review.

Best of luck to all!
We're almost done!

Monday, July 07, 2008

IT WORKS!!!

I've been stressing for the first day of midterm review and accomplished quite a bit.
I've managed to work out some of the bugs to the point that it now caches!
It doesn't hit yet but I might just be able to pull that off by the end of the week.

I've hit my milestone and I'm much more confident about the review this week.
I haven't heard back on my pre-review review from my mentor, but with July 4th holiday weekend I really can't blame him, I celebrated too.

Went to a local amusement park and visited with my friend Eric who I haven't seen much of.
Definitely need to brush up on my air-hockey skills after this project is completed.

Just eight more weeks to completion!

Thursday, July 03, 2008

I finally got the Eclipse debugger to play nicely with MySQL!!!

Steps:
make clean
./configure --with-debug (and I modified my flags with -g as well, tho it's not required)

then under Eclipse I did a 'make all'
used --gdb --one-thread when running
be sure to close the 'registers' pane or else MySQL will crash and require a kill -9

I can now step through my code and see it in action,
it really is doing just what I thought it should!
(tho I found the MySQL GUI tools do a lot of things I didn't know about)

I'll be submitting an early review to my mentor tonight.
I'm not too familiar with submitting a diff so I'll probably attach the full source files as well in case I mess it up.
As of tonight I have surpassed 100 hours working on this project!
In a way I wish all this really was for JUST a t-shirt, adding money to the mix is both an incentive and a curse. I can always continue working on the project, even if I don't make the cut though... :)
I just hope my results add up to the effort I've put in.