Reverse-engineering a tough-to-crack video game save-file checksum

Question

Been trying to figure this one out for a while now, and would be eternally grateful for anyone with more experience in checksum algorithms lending a hand.

I've been trying to alter save files for an old Playstation 2 game for a long time, now. However, this save is protected by what appears to be a triple, bi-directional checksum.

The game, if you're curious, is Fire Pro Wrestling Returns.

Fortunately, I have mapped out a considerable amount of the save data, and much of it is something that the player can easily affect themselves (since much of it is user-created characters), which has helped considerably.

The data I have already is as follows:

The save data itself without the checksum is 888 kilobytes exactly, of which the final 400 bytes appears to be null padding to round out the file size.

Following these 888 kb, there is a total of 4580 bytes worth of checksum, divided into three blocks.

Experiments altering save data through the game and resaving, following by comparing the save files, has shown that the checksum works as follows:

The first block is 3552 bytes, consisting of 888 4-byte checksums, one each for the 888 kilobytes of save data. This has been tested and verified by altering individual bytes. It also seems that they are not working off each other - there are a few blocks towards the end where I was able to make two blocks identical to each other, and they had the same checksum. So hopefully this means that each block is calculated in a vacuum rather than depending on previous results.

The second block is 1024 bytes, and seems to be a cross-directional checksum of the main save data (so that the first byte of this checksum is a checksum of the first byte of each of the 888 "1 kb blocks" of save data). I've tested and seemingly verified this theory by altering a single byte in various places and be able to predict completely which checksum bytes would alter as a result.

The third block is another 4-byte checksum. Since the first block of checksums are checksums turning 1024 bytes of data into a 4-byte checksum, and the entire second block of checksums is 1024 bytes, I'm guessing here that this is a final corruption check by doing a checksum check on the second checksum block, using the same algorithm as block 1.

So, basically it appears that there are two checksum algorithms at work, one of which I have full control of the in-data for, and the second where I have limited input since not all of the save file is easily manipulated and this takes from all parts of it.

Here are some examples of the 4-byte checksum generated by different blocks of data in block 1:

BB 6B 82 F3 = all zeroes  
68 8D C8 0C = 01 followed by all zeroes  
B4 D9 DC B4 = 02 followed by all zeroes  
DF 5F 6E 0D = all zeroes with 01 at 0x60  
78 DF C3 08 = all zeroes ending with 01 

My problem there is that looking at it in binary, hexadecimal or decimal I just haven't found any discernable pattern. I've started looking into trying to reverse engineer the assembler of it and seeing if I can find the algorithm that way, but that's not exactly a simple task considering the size of the software (and the PS2 multi-core architecture which may or may not be involved).

I've done less work on mapping the second checksum, but what I have there is attempts where I've altered a single byte inside by either adding or subtracting one, and noting that in most cases, the checksum has only changed by one step (though in different directions), but for now I'm focused on the first algorithm since that's the one that feels like the bigger head scratcher.

If providing more experimental data helps, I can happily do that. =)

And while the end result is definitely why I started working on this, I'm interested not primarily in a solution but rather in understanding the methods for how to reach it.

UPDATE:
Thanks to some awesomely helpful comments I've gotten some debugging setup, though I'm not sure I've found the right code... I logged everything while loading a savegame (since it'd need to build the checksum for comparison while loading) and looking for repeated blocks of code with subroutines.

Finding the RIGHT assembly to quote is really the biggest trouble I'll have after all this help, while I'm trying to learn how to figure this out...

For example, this block is repeated 104 times in my log (which is a partial load, not the entire thing, since I didn't have much time this morning before work), though I need to translate it into pseudocode to see if it's relevant:

0012f5d4 0c04c77c: JAL    , 00131df0, 001c0b04 (ra),  
0012f5d8 24a5ffff: ADDIU  , 00000000_00000004 (a1), 00000004 (a1), ffff (65535),  
00131df0 30820008: ANDI   , 00000000_00002000 (v0), 00000000_0000211c (a0), 0008 (8),  
00131df4 10400008: BEQ    , 00000000_00000008 (v0), 00000000_00000000 (r0), 00131e18,  
00131df8 30820010: ANDI   , 00000000_00000008 (v0), 00000000_0000211c (a0), 0010 (16),  
00131dfc 10400004: BEQ    , 00000000_00000010 (v0), 00000000_00000000 (r0), 00131e10,  
00131e00 00051040: SLL    , 00000000_00000010 (v0), 00000003 (a1), 01 (1),  
00131e04 00451021: ADDU   , 00000000_00000006 (v0), 00000006 (v0), 00000003 (a1),  
00131e08 03e00008: JR     , 0012f5dc (ra),  

EDIT AGAIN TO ADD:

One plan when I get the time to sit down with it, hopefully tonight, is to take a save file I know works, and then introduce an error into the third checksum of the first block, then run the load-up sequence with the debugger again to see where it fails and see if that can narrow down the first checksum block and the routines involved.

Answer 1

Like others I would recommend trying to get the assembly code that computes the checksum. If you obtain that the rest is easy.

However sometimes that can be very hard to obtain, so here are some tips on reverse-engineering checksums without any code.

1. Remember that a checksum algorithm is a design choice made by engineers, so think about the constraints and practices that may have contributed to this choice.

   • It is older hardware so efficiency may have been a concern - nobody wants to wait 2 minutes to save/load a game. This means bitshifts, XORs and lookup tables are much more likely than complex branching, multiplication, division, or anything involving floating-point numbers. It is also likely that the algorithm makes a single pass through the data.
   • The algorithm may be identical to, or a variation of, checksum algorithms in other games by the same studio or same programmers.
   • The algorithm may be an off-the-shelf algorithm (like MD5 - which was designed in 1991 and therefore predates the game)
   • The algorithm may be based on checksumming guidelines published by Sony or published in a book on game design or some such
   • Obviously the date the game was published is critical in investigating this area

2. Get familiar with the most important checksum/hash algorithms, particularly ones that were in vogue when the game was published.

   • Strictly speaking the algorithm is a hash function, because small changes in the plaintext completely change the hash value
   • Try various hash functions that existed at the time the game was created (e.g. MD5) on your data, and see if it matches. Be careful of bugs in your code when you do this (e.g. silly errors like sending the string '\x00' into the hash function instead of a NUL byte)
   • Understanding how common hash functions work helps you guess how unknown ones may work. If this algorithm was developed in-house, it is likely to be simpler than the major hash functions of the day - or it may be exactly the same as, say, MD5 but use different constants. That would be quite hard to reverse-engineer, particularly if you can't automatically run through millions of test cases.
   • Many hash algorithms (including MD5 and SHA-1) make a single pass over the data. Both MD5 and SHA-1 process the message in 64-byte chunks
   • Assuming this is true of the algorithm we are reversing, this means that changes to the last two chunks of the message are likely to yield the most information, since the effects of changes to early chunks are likely "garbled" pretty quickly. For instance, you may want to make a 1-bit change in the last chunk of the message and see the XOR difference it makes, then make a 1-bit change to the second-last chunk of the message, and once again make the same 1-bit change in the last chunk, and see the XOR difference it makes. Or you can make lots of 1-bit changes to the last chunk and see if there is any pattern to it. Note that MD5 and SHA-1 both append an extra bit to the end of the message, which in this case would add a whole extra chunk to the end which would complicate matters.

3. Maybe someone's done it already?

   • Googling the all-0s hash value you provided, I found this: http://www.fireproclub.com/forum/viewtopic.php?f=12&t=1860
   • It doesn't look like they figured it out but maybe someone else has (and possibly put it in an open-source tool), or you can contact programmers on the game team, and ask them, etc.

Happy reversing!