Tuesday, November 15, 2011

Map-Hack Tutorial


Map-Hack is a cheat for strategy games such as Warcraft or Starcraft, Dice n’ Slice games like Diablo or 3d shooters games like modern warfare. The cheat as most cheats is done in order to give an unfair advantage to the player who uses it. In case of Warcraft a map that usually looks like the one in the top left corner:



under cheating condition, would look like this:



or even better, like this:



Zoomed in:



The idea behind it, is to give more information on the map than what is found in the regular game play. Information like which gold mines are wealthier, and which enemy creatures are deadlier.
To create this kind of cheat one would have to go through two phases:

  1. Research, in which you need to figure out how and where the map data is stored in memory, and how to find where it is stored every time the game restarts.
  2. Developing, in which you write a code or a script to change the map data in real time.

In this tutorial I would only display the research phase up to the point of proof of concept.
To perform this research I need an Interactive Python Interpreter. This would bring up the question of which version of Python should I use.




  • Games are for Windows. So I'm gonna use Python for Windows (Better use the one from Python.org than Active-State Python).
  • I'm about to research a 32bit process so it is better, although not a must, to use 32bit Python.
  • The tool-chain I wrote is not ported to Python 3.x just yet, because I'm lazy, so Python 2.7 or 2.6 would have to serve me this time.
  • As for the Interactive Interpreter, I prefer the Dreampie.
The tool-chain is an external module, which helps in the task of memory research. The module is called NativDebugging, and is freely available at the following SVN: http://dreampie.sourceforge.net/. Install from source simply by:

python setup.py install

Or just get the installer from http://www.4shared.com/file/jE4xjHDb/NativDebugging-10win32.html? .
My NativDebugging module can be used as is, but it has extra GUI features if the PyQT module is found, so download it from:
http://www.lfd.uci.edu/~gohlke/pythonlibs/#pyqt
and double click to install.

Now that I have got the entire environment set, let's get the party started. Let's start with something easy that everyone likes: Minesweeper (AKA: Winmine).



Important note: Use the old version of the minesweeper as many internal structures are different in the new Windows Vista version that looks like this:



I start by launching the game, and getting its' process id. There are many ways to get the process id, either to use the task manager or with the following command line:

tasklist /Fi "IMAGENAME eq winmine*"

Or from Python using the NativDebugging module.

>>> from NativDebugging.Win32.MemoryReader import *
>>> findProcessId('winmine')
[('winmine.exe', 376L)]
>>>

Next I want to tell the NativDebugging module what is the target.

>>> m = attach(376)
>>> 

I need to get details about where in the 4GB virtual address space memory is allocated. The m.getMemoryMapByQuery method suits for the job.

>>> memMap = m.getMemoryMapByQuery ()

This operation might take some time, depending on how much memory is really used by the target process.
I start the search of the place in memory where the board of the game is set, using the technique called differential search. Differential search is a search in which one starts with a picture of all the memory, and slowly filters out things that are not what he is looking for, until he is left with a single result. In this example I'm looking for the top left square of the board. Setting up a new search is done as following:

>>> from NativDebugging.Win32.DifferentialSearch import *
>>> ds = DifferentialSearch(memMap, m)
>>> 

Now I simply, change the value of the square by uncovering it



Next I filter out any memory address that  has not been changed:

>>> ds.removeUnchangedMemory()

The first filter can take up to few minutes, again depends on how much memory is used by the target process. If I wait for a little while, some of the memory would change by itself, so I can remove any memory that changed:

>>> ds.removeChangedMemory()

I continue by causing more changes to the first square and invoking the removeUnchangedMemory method.
To check how many potential memory addresses are left the "len" method on the DifferentialSearch object can be used. Filtering process is repeated until only one or two places in memory are left.
If you are following the process to this point, and all was done correctly your Python Interpreter should now look something like this:


(Click on the picture to enlarge it)

Now I can get the address that was found simply by looking at the DifferentialSearch object or by retrieving its' data in index 0.

>>> ds
0: 0x01005360: 10404040
>>> ds[0]
16798560L

I save the address that was found in a new var to be used latter:

>>> board = ds[0]

The memory can be examined in various ways, here are few examples:



One can also try to write over the memory to see how the game behavior is changing.
The most useful way to look at memory dumps of maps is using the mapDisplay method, which hopefully, would show up in a new QT window as following:



All of the display parameters are accessible from both the GUI and the python object that was created with the creation of the display. I now play with the line size until the following result is reached:



Can you tell where all the mines are placed?

The interesting part in case of minesweeper is that, the map is always found in the same place in memory, so if I start a new game, and update the data (using w.updateData()), I might get something like:



In real games, the principle is quite the same, though it takes more time. The main difference is that the map is usually allocated dynamically so one would also have to find a global pointer to it, to be able to locate the map in memory quickly. I have an example of the same process done on the WarCraft II strategy game, but this blog post is long enough as it is. So maybe next time.

Future TODOs:

  • I believe that the search function could be much faster, I would love to have some help in optimizing the code.
  • The GUI has lots of room for improvements.
  • I need to write an installer, and to create a Python 3.x branch.



Cheers,
Assaf

Saturday, September 17, 2011

Bejeweled autopilot

The idea behind the Bejeweled game is as following:
An average game status looks like this:

The player is allowed to switch between any two neighboring gems in order to create a series of three or more gems of the same color. If the player does so, the gems are destroyed, points are given, gems are falling down to fill the empty spaces, and new gems are coming from the top to fill the vacuum. The problem is that the player has just about one minute to destroy as many gems as possible, and it’s hard to find series of gems that quick.
What I did to solve this problem was to write a small Python script to capture the screen, find the best next move and simulate mouse clicks to execute it. One of the problems I faced while writing the script was identifying the kinds of gems, while the bustards kept on moving, rotating n’ glowing in different kinds of effects that usually inform the player about special bonuses. I tried to scan a 4x4 pixels square in the middle of any square, to get a color value out of this small square, and to compare it against a table I made manually in order to decide which gem it is.
I found out, that in many cases bots scripts alter the game to change all the graphics to something more OCR friendly. But I didn’t want to do that, as I’m trying to perfect the technique of writing a bot, and not to mix the two game cheating vectors. Therefore, I didn’t want to put any patches on the game, just writing a bot.
The next problem I faced was Python itself, as I found out that it’s quite slow to scan an image or to compare two images with the Python Image Library (PIL). Though, it is possible that I’m miss-using the library. Please, I would like to hear any ideas on how this part could be done better from Python, without extending Python with a custom C library.
One lessen I learnt the hard way during writing of this very script, was that it’s very important to find the time to write a code for finding the location of the game on the screen, so in case I scroll the page down a little, or just open the bookmarks tools bar, it won’t be using the hard coded position of the game and miss figure where the gems are.
Even thought, I successfully set myself on the top score among all of my friends, but not world wide best just yet. I found out that many fine tunings on the scripts, such as what strategy to prefer, weather to aim for bonuses first, try to destroy a longest chain of gems at once, or save bonuses for later, have immense effects on scoring. Please, I would love to hear from the readers of this blog about any ideas on how to improve the script, or how you would write one in case you had to.

The script is aviable on my SVN at https://xp-dev.com/svn/Cheats

Cheers,
Assaf

Friday, September 2, 2011

Wonder Cheat 3

Recently I had a major nostalgic emotional burst which took me all the way to the Sega Master System ™ I had in my childhood. One of the games I remember the most from this 22 years old console is the Wonder Boy III, the Dragon’s Curse. So I fired up the Meka emulator and downloaded the ROM, and sat down for few hours of unlimited fun.



During the search for the ROM I found out that there was another version of the game with slightly better graphics for the TurboGrafx-16 console (AKA PC-Engine) which is called the Dragon’s Curse.

For the readers who never heard of WB3 or the Sega Master System, I shall explain, in short, the game’s look n’ feel. The game is some kind of a combination of RPG with a platforming action game. You need to get different kinds of swords, shields and armors by either finding them in treasure chests throughout the game, or buying them in shops found in the city. Besides the gear, the player has to collect gold, potions, magics and power ups. The game has about 6 levels that the player has to finish, while at the end of each one there is a boss that has to be destroyed. When a boss is beaten, the character in the game transforms into some kind of a new animal-human creature that possesses a special ability that helps him get to the next level. The characters are Hu-man, Lizard-man (Can shoot fire), Mouse-man (Very short, and able to climb some walls), Piranha-man (Can swim), Lion-man (Can punch up), Hawk-man (Can fly).


Bosses:


The part that I find interesting about this game is the way save games were implemented in time before Flash memory. During the game there was a place in town where the player could get a 14 characters long code that if entered in the main menu, would take him back to the same status as he was in the time of getting the code.


Meaning these 14 characters encode the full status of the game, including amount of Gold, Lives, Potions, Gear and more. The characters are either numbers 0 to 9, or capital ABC, excluding few characters such as I, O & Q, for the reason that they look too much like 1 and O, which could be quite confusing. Besides that, not every combination of characters is valid, meaning there must be some kind of a checksum. I remember that many years ago, every time I got bored playing the game I was trying to brute-force codes, with very little success. I was always very curious about this mechanism, and I had a belief that somewhere, there is some kind of a very special code that would turn the game upside down.
During the last week I decided to finally cope with this old craving, and finally reverse engineer the secret behind this coding system. First I had to find out which CPU is used by the Sega Master System to know how to load the game in IDA. Wikipedia mentioned, rightfully, that the Z80 is the main CPU of the console, and loading the ROM file into address zero seemed to work just fine. Second, I had to find the relevant code, so I searched the Internet for some special codes that might lead me to the right place. I found out that there is one very special code that is WE5T 0NE 0000 000, which is the name of the company who made the game. This special code could not possible encode a game status, so it must get a special treatment in the code. Searching for the string (without the spaces) through the entire file took me to the following code:

Xrefs took me to:


From reversing I found that every character tributes exactly five bits to the data, that comes to be total of 70 bits (5 * 14) which turn into total of 9 bytes of data. Two bits of the 9 bytes are index to a xoring table that is then xored to the 9 bytes. After the xoring, all the bytes are added together to form a checksum that is compared to the first 7 bits (which are not used in the addition). If the first 7 bits match, the code is valid and is passed to another function that sets the game state.
I’ve written a full functional code decoder / encoder in Python, and is available for download from the following link:
http://xp-dev.com/svn/Cheats/


Links:
For more information about Wonder Boy III and The Draogon’s Curse follow the links below.
http://www.geocities.jp/monsterworld2/Wonderboy_Land.htm
http://hg101.kontek.net/wonderboy/wonderboy.htm
http://retro.ign.com/articles/930/930245p3.html
I would like to thank them for the pictures I took from these sites without asking for permission, hope it’s ok.

Cheers,
Assaf.

P.S.
The Dragon’s Curse has something different in the coding system, I would have to reverse it too. Does anyone know how to reverse the PC-Engine’s ROMs?

Thursday, May 5, 2011

Snaky Cube


The following is a puzzle that I’ve encountered at the Kubiot (Cubes) restaurant in Tel-Aviv.
The target of the puzzle is to make a 4x4x4 cube out of this snake like shape. The small cubes are connected to each other with a cord so it’s only possible to rotate them, but not to change their position. This puzzle is a larger version of a similar puzzle that makes a 3x3x3 cube.

 Where the target is to get to this:

The guy at the restaurant said that he would give a free meal to anyone who solves it on the spot. Don’t be fooled by the 3x3x3 version of the puzzle, this one is a hard task indeed, given the fact that for a guy who knew the solution beforehand, it took about 15 minuets to set it right. So I decided to go “pirate” on this one, and take the picture that you saw at the top.
My mile stones are:
  1. Writing a script to solve it at home.
  2. Memorizing the solution.
  3. Collecting my ~10$ prize.
 1. Brute-forcing to solution.
Python to the rescue.
I entered all the information about the puzzle has lengths of straight lines that could not be rotated.:
data = [3,1,2,1,1,3,1,2,1,2,1,2,1,1,1,1,1,1,1,1,2,2,1,1,1,1,1,2,3,1,1,1,3,1,2,1,1,1,1,1,1,1,1,1,3,1]
My approach is to build a 4x4x4 array of zeros and try to fill it with squares. I defined a Point3D class for the millionth time. And set-up the cube.
Two small questions that came up during the writing:
1. Does anyone know about a simple implementation of Point3D in Python, so I won’t have to write it again.
2. Does anyone know about a simpler way to define the 4x4x4 cube other then:

cube = []
for x in xrange(4):
    ll = []
    for y in xrange(4):
        l = []
        for z in xrange(4):
           l.append(0)
        ll.append(l)
    cube.append(ll)

Now I define all the valid moves in the puzzle, and include recursively the next valid moves, as it depends on the last move.

XDirectionP = (Point3D( 1,  0,  0), [])
XDirectionM = (Point3D(-1,  0,  0), [])
YDirectionP = (Point3D( 0,  1,  0), [])
.
.
.

XDirectionP[1].append(YDirectionP)
XDirectionP[1].append(YDirectionM)
XDirectionP[1].append(ZDirectionP)
XDirectionP[1].append(ZDirectionM)
YDirectionP[1].append(XDirectionP)
.
.
.

The main recursion is as following:

def nextMove(pos, dataLeft, currentDirections):
    global cube
    global highestLevel

    if 0 == len(dataLeft):
        return True
    length = dataLeft[0]
    for move in currentDirections:
       newPos = pos + (move[0] * length)
       if isValidLocation(newPos):
           if tryToSetCubes(pos, move[0], length, len(dataLeft)):
               if nextMove(newPos, dataLeft[1:], move[1]):
                   return True
               clearCubes(pos, move[0], length)
    return False

Apparently this solution, is good enough it took %d seconds to solve it, no extra improvements were required... That’s sad, I kinda’ hoped for something more advanced.

2.
I’ve translated the result into a string of first letters of the valid moves (Left, Right, Up, Down, In, Out), just to get the 46 letters string “RULODRIULOLILURORIRODLOLUIUODIROUIRDODILDROLUR”.
Next I called my good friend Werner, to manifest a sentence out of the string so it would be easier to memorize. The genius came up with the following:
“Recently, upon learning of dental recovery, Ian Underwood laughed out loud. In laughing, underwood remarked, optimal recovery is realized. ordinarily, during laughing out loud, universal imagery unfolds. Or does it? Regardless of universal imagery, rarely do old dying imbeciles laugh. Don't ruin our laughter, Underwood remarked.”

3.
Here I returned to the restaurant with two of my good friends who helped me with acting like I’m going trail n’ error to solution, and it’s doing very well, but have no clue of what am I doing. On setting the very last move to the solution, a crack sound has echoed the place, leaving me with a baffled look at what had happened.


Alas!!!, I shouted out loud, realizing that not only am I not going to get a free meal, but I will probably have to buy them a new puzzle. Fortunately, they told me not to worry, and that it happens all the time, they would replace the cord by next week, so I could try again then.

Now three weeks later and they still didn’t fix it! I started to look-up this puzzle to check where they bought it, and I found the following web site:
http://www.gaya-game.co.il/
Or more specifically:
http://www.gaya-game.co.il/?categoryId=31183&itemId=60119

Thursday, March 31, 2011

CruiseControl Reporting, Attention & Posting (CRAP)

Few posts ago, I told the readers of this very blog about a device I bought from Dealextreme (1, 2) for notifying about incoming E-Mails, and how I patched the program that came with it. To freshen your memory, the USB device is a envelop shaped box, that can glow in eight different colors. The device is identified by Windows as a regular HID device, which means that no drivers are required for most OSs. The colors are generated by an RGB LED, that probably supports many other color variations (Requires hardware modifications).


Since then I’ve made a small open source Python project for controlling this device and making it useful.
Someone told me he used this device as a good start for his project of smart home gadget. As a public service, I attach here some images of the device from within.






It seems like, there is some room on this board to add more LEDs or something, please tell me if you manage to figure out more details about it. If you want to use this board to connect it to some external device, you can remove the LED (it's the white square at the middle), and weld something else instead. I couldn't figure out what kind of a chip the black one is, and whether it's possible to reprogram it. I would open another device next week, hopefully to answer few of these questions.

Recently, I’ve made a compiling / building notification system at my workplace, so I would know whom to feed to the sharks, when the build fails. Here’s a picture of the system.


I’ve added the source for this system (Everything but the CuriseControl password ;) under the XP-Dev SVN project (CControlLED.py).
Please feel free to use it, and share your own projects.

BTW, the chip in this LED box is most probably: http://www.sonix.com.tw/sonix/product.do?p=SN8P2212

Friday, March 4, 2011

Looking Into the Eye of the Bits

During the past four years I've been developing tools for research and implementation of a new type of software analysis. I've discussed these tools on a various occasions such as RECon2010, Nullcon2011 and DC9723.
The purpose of these tools is to recover internal implementation details using only passive memory analysis, and without requiring any disassembly.
These tools are now available under GPL license on the following links:
https://github.com/assafnativ/NativDebugging

The latest version of the presentation + WP is available in the SVN of pymint:
https://github.com/assafnativ/NativDebugging/tree/master/docs

For more details on the subject you are more than welcome to visit the websites of the kind conferences which gave me the place to mumble about my work:
http://nullcon.net/speakers/bakkar/
http://recon.cx/2010/speakers.html#memory
http://wiki.dc9723.org/wiki/Meetings

I'm currently looking for more places to spread my word, if you know of such, please contact me.