The place where I put my thoughts on software development, so I can remove them from my mind.

04 January 2009

Cheating in Dragon Quest IV, the programmer's way

Lots of my time has gone into a rather crappy "JRPG" called "Dragon Quest IV" on the Nintendo DS lately. The leveling kept it fun for a while, until last night, just when I reached the supposedly final "boss" (a horrible game concept.) The damn bastard just wouldn't die, and kept on growing arms and heads (huh?) until all my characters were dead, even though I had no trouble getting through any other place in the game, and I was a few levels too high for this point in the game. I'm not a very good gamer since I really hate doing things twice, so a long battle like this would normally be a reason to quit the game and never look at it again.

The nice thing is: I am playing it with an R4DS card, which uses a Micro SD card to store games and save games. I'm a programmer - I can do everything I like with that save game. I could make the characters I play a lot stronger, and all the time I invested in this game wouldn't have been for nothing. Normally the save games are stored on the game cartridge itself, so the game programmers probably wouldn't bother with any kind of encryption schemes, because the save games would be unreachable anyway, so let's find the data and kill the boss. That will teach him not to grow new legs when a programmer is around!

This is what the contents of the SD card look like when inserted into my laptop running Ubuntu. As you can see, next to the game itself (the .nds file) is a .SAV file. Not surprisingly, that contains the save games. The game uses only a few kilobytes of the 512MB that the file is big, which saved me a lot of time. I copied it to my local drive, making a separate copy of it, in case my changes would corrupt the file.

I assumed that R4DS just took the biggest possible save game size (512MB), then gave the games access to all of it, even if they just used a little of it. I also assumed that games normally use some kind of propietary binary format for saving games. Also, I assumed that the R4DS thing itself would not put anything in the file.

So what's in it? For this, I wanted a decent hex editor, one that would also let me change and save files. A quick search turned up the Bless hex editor (which is a shitty religion-related name,) and ghex. Bless came highly recommended, but turned out to have a bug that prevented me from saving files, and started in insert mode, which is completely ridiculous for editing binary files. (Turns out that it's .NET software - forgive them, for they know not what they do.) So ghex it was, which turned out to be quite full-featured and stable.

This is what I saw when I opened the save game with the hex editor (and expanded the screen to show 32 values in a row.) Lots of zero's, and "DQ4 ARTE". The game is Dungeon Quest 4, the title screen says something about "Arte Piazza," so this is clearly a simple header, something that the game could check to see if the save game area hasn't suddenly be replaced by a play from Shakespeare, or whatever. Nothing to see here, let's move on.

This photo is from the Nintendo DS screen, which explains the crappy colors, and the reflection of the camera lens. It shows the saved games I have. They show the name of the main character (Narbrot, nice eh?), some random stats, and the time spent playing. That's 30 hours of missed sleep. The times are quite alike because of an experiment which is explained further down.

There are actually four save games, the fourth is used when suspending the game for a longer time. So let's see if we can find a big area that repeats four times in the save game file. Why not search for "Narbrot" a few times - it has to be in the save game four time, how else would the game track the name for each save game?
Found! And found three more times at around $0860, $4460, $8060 and $BC60. There's a calculator in Ubuntu, and it's easily set to a mode in which it can convert hexadecimal to decimal and the other way around. Now, the most significant bytes of the addresses (the left byte,) is increasing with suspicious regularity, let's see what the steps are...

$0860, $4460, $8060 and $BC60.

08 hex = 8 decimal
44 hex = 68 decimal
80 hex = 128 decimal
BC hex = 188 decimal

So the Narbrot's are 60 times $0100 away from each other, which is 60 x 256 = 15360, which is 3C00 in hex again. So each save file has an identical size, and that size is a bit less than 4KB, for a total of around 16KB. That's a very efficient way to use a 512MB file ;-)

Let's try changing some of Narbrot's lousy statistics:
I tried to find the
number 345 ($0159) first. That failed miserably because, as it turns out, the Nintendo DS works in little endian mode. There's an option for that in ghex, so I turned it on. A little more searching and there it is:
The text at the cursor says 59 01, which is the value we're looking for. There are no more zeroes around it, so I guess the value is stored in two bytes. That would put the maximum at $FFFF, which is 65535. 65535 hit points, that sounds great! Next to it is BF 00, which is 191, which happens to be Narbrot's ma...something points. After that, there is 59 01 BF 00 again, and a good guess will be that one of these is the max value, and the other the current value.

See the bigger pattern on the screen? Lots of FF, then lots of numbers, and then it repeats. It repeats about nine times, which is the number of character in the party. I guess that one of these blocks stores all the state for one character then. The HP and MP for the other players are probably at the same position in their respective blocks.

Here's Torneko, the extremely unfunny comic relief guy who thinks his job is more important than his wife:
And yes, a few character blocks further, I found 00 00 00 00 4F 01 00 00, 4F 01 being 335. Hmmm, it would be funny to give him lots of MP, which he can't use, because he lacks spells :-)

Back to Narbrot. I typed FF FF over all four numbers I just found. Very subtle, I know. I copied the .sav file back to the SD disk and put it in the Nintendo DS. Alas, on starting the game, Dragon Quest sees that the save game has been tampered with, and deletes it! AAARGH! Well, maybe I was a little too rough. Let's try it again, but now I'll keep the values under 999, which is $03e7 hex. Damn! Detected again!

How did it do that? Well, there seems to be some kind of checksum stored somewhere. But where, and in what way is it calculated? There's a trick for figuring that out: make two save games that differ only very little, then compare them. The differences should be the ones that you made, and another one: the checksum.
This is what I did:
The blue guy is the "save priest" who will save your game for you. Since the save games contain a "time played" field somewhere (30 hours in my case) I thought I would just wait around for a minute and press save again, and again. I should have three save games that only differ in time, and in checksum.

Right, but how am I going to compare this? Not by hand, that would take long, and it would be very inaccurate. At first I wanted to write a nice program to do this for me, but it's such a common task that the tools must be out there somewhere. Let's find a binary diff utility. Google got me to vbindiff, and it's availble in Ubuntu, and it seems to work OK, and that makes it good enough, and.

vbindiff wants to compare two files. Oops! We only have one, and we want to compare parts of it. Let's turn the separate save games in the .sav file into real files. I thought that the dd tool (which always shows up in very complex, low level unix tasks) could help me here. A quick google gave me the man page (yeah yeah, "man dd" would have been more effective.) Looks like I can specify an input file (the .sav file,) an output file, a block size, I can skip a few blocks to the save game I want, then I can specify how many blocks the save game is in size.

Now where exactly are the save games located? We've got the size ($3C00) but not the start position. Well, when looking through the file from the start with the hex editor, there's the DQ4 ARTE header I mentioned, followed by many, many zeroes, until we meet the word "arte" at $0400. Sounds like a header, and it's at a very nice, rounded address. Is this the start address? The next save game should be at $0400 + $3C00, which is $4000 according to the calculator. There we find another "arte". Just before it is a big block of filler FF's. It's pretty certain that these numbers are correct.

The start addresses for the save games are: $0400, $4000, $7C00 and $B800. Since they all have the same least significant byte (00), I think that would be nice to use as the block size for dd. Take $100 for the block size, and the first save game will start after four blocks, the next after $40 (64 decimal,) and so on. $100 is 256 decimal. A save game is $3C00 bytes long, and that's $3C blocks, which is 60 decimal. So let's go dd:

dd if=awfullylongname.SAV of=savegame1.bin bs=256 skip=4 count=60
dd if=awfullylongname.SAV of=savegame2.bin bs=256 skip=64 count=60 dd if=awfullylongname.SAV of=savegame3.bin bs=256 skip=124 count=60 dd if=awfullylongname.SAV of=savegame4.bin bs=256 skip=184 count=60

That gives us four save game files! Now launch vbindiff on two of them:

Oooooh nice, differences in red, just what I wanted! There's a byte that has increased by 12, and (not all in the screenshot) there are a bunch of other fields that, when added together, have also increased by 12! So, is the first byte the checksum, a simple addition of all bytes in the save game? In that case, if I add 1 to the checksum, and 1 to the most significant byte of the maximum HP of Narbrot, the addition should still work, and the game should think that it is a valid save game, and Narbrot will have 256 hit points extra because I increased the most significant byte.
Woops! I changed the wrong value, butyou get the idea :-) The checksum has been defeated, and I can now easily change HP and MP for all characters. The cheat is complete :-)

Ofcourse, I could have done a lot more. To edit HP and MP freely, it would be useful to figure out which range of bytes are added to calculate the checksum (maybe all $3C00 bytes?) and how big the checksum is - we've now changed only one byte, but it's probably a two or four byte value. It would also be nice to improve the other statistics, but as far as I can see, the values on screen are not the same as in the save game file. Some trial and error is neccessary there. Editing the name of the main character is really easy - you can just overwrite it. The other names are missing, though. They are probably hard coded.

(I've edited a few more save games in my life time. I think I started with an editor in BASIC for save games for Champions of Krynn on the Commodore 64! No fancy hex editors and diff utilities then, just peeking and poking. Yes children, life was hard in the old days!) (I still couldn't win the damn gamn though, probably because all stats were stored in bytes, and I couldn't make them ludicrously high.)

(I don't feel like proofreading such a long post, so just write a comment if something doesn't make sense, ok? No need to tell me I'm a moron.)

Latest saved links

About Me

My photo
Nieuwegein, Netherlands

ohloh

Syntax Highlighter