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.
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.
R5900 Debuggerwhich is good information find the checksum and edit your question with the assembly code.