News: 11 March 2016 - Forum Rules

Author Topic: Help figuring out checksum of GBA save  (Read 1684 times)

SuperrSonic

  • Jr. Member
  • **
  • Posts: 12
    • View Profile
Help figuring out checksum of GBA save
« on: August 06, 2021, 12:02:56 pm »
I'm working on a sort of save editor that essentially lets one extract the Chao from the Tiny Chao Garden in Sonic Advance/Advance2/Pinball Party, and re-insert or import a new chao from somewhere else. And hopefully other stuff too.

Extracting data from the save is easy enough, the problem comes when trying to change any relevant byte, the game fails to read it.

The saves have the same format across games, here's Sonic Advance 2 with the default egg: https://www.mediafire.com/file/f8ghb6e1lsx4wgh/Sonic_Advance_2_-_6_files.sav

The save is 0x10000 bytes, main game save ends at 0x9FFF, TCG saves start at 0xA000, there are 6 saves in blocks of 0x1000, the game reads one of the bytes on each block to find the highest number which is the current save, then it verifies the checksum, if it fails it tries the previous save.

The first two bytes on each of the 6 blocks is the checksum, the relevant data length used for the checksum is up to 0x856 bytes, after that any bytes can be changed without problem until the next block starts.

I have tried all the simple 16-bit checksum methods, I've tried crc16, crc16-ccitt, reading every two bytes as one value, nothing works. The first 0x56 bytes after the checksum seem to be byte swapped/little endian, while the remaining 0x800 bytes are the chao itself in big endian, these 0x800 bytes can be copied to SA2B or SADX savefiles and are 100% compatible. So this leads me to believe the first 0x56 bytes are calculated differently from the actual chao data.


Any experts out there that may know what else to try? I originally wasn't going to bother with editing the save and just null the save after pulling the chao, but this has the side effect of resetting the ring count to 99999 which breaks one of the points of using my tool.

goldenband

  • Sr. Member
  • ****
  • Posts: 379
    • View Profile
Re: Help figuring out checksum of GBA save
« Reply #1 on: August 06, 2021, 12:38:04 pm »
This is an interesting one! I don't have the skills to help, but this problem seems right in Bisqwit's wheelhouse if he's got the bandwidth/energy for it:

https://www.romhacking.net/community/1354/

He's done analyses of password-based games that use ridiculously arcane methods to compute the password's checksum character(s). While the analogy might not hold, maybe the devs had some incentive to make the checksum computation really obscure, like wanting to keep third-party devices from successfully editing save data.

FAST6191

  • Hero Member
  • *****
  • Posts: 3357
    • View Profile
Re: Help figuring out checksum of GBA save
« Reply #2 on: August 06, 2021, 02:54:28 pm »
I would not necessarily have expected backup saves for GBA Sonic.

Two things to consider at this point

1) Bring the mountain to...
So you have a game that verifies checksums. Treat the checksums as a black box for now and instead alter the game -- in reality it is never going to use the checksum for anything beyond this so find the IF good proceed ELSE goto checksum failed part and nerf that so it always takes the good checksum path. In GBA assembly it will probably be a compare and branch if not equal (change it to jump to the good part regardless). Bonus is the game itself will likely then redo the checksum to valid next time it saves which should allow you to finish up your save editor and then come back to tackle this, or indeed ship it in beta with a patch for the ROM(s) so people can do it themselves.

2) The GBA can use all sorts of methods. I have never seen one of the really complicated ones like you might for the DS (between web stuff and other things you could end up in the MD5/SHA1 range, though was usually considerably more sedate) and usually it is a custom CRC16 with initial bytes and whatnot different to the boring and basic ones (some hex editors, like hex workshop, will give you the option to fiddle with things here; I had some settings I used for DS headers once) or something even more basic like bytesums, parity and the like.
Sounds like you know what the data being checked is (not sure if that has its own separate hash for that segment or does the whole save) and presumably can find where it lands in memory, which tends to be where it stays as well (though easy enough to find if it has a temporary landing spot - take a valid save, find the eventual location of it in memory, reset/load earlier savestate, take a break on write to that location you found and then note where it came from).
A hash iterating over the entire save segment is usually fairly obvious in assembly regardless of what it is. If you can understand it then great, if not then again you can return to the black box idea and just implement whatever it does in your program (who cares if it takes 10 seconds doing what is effectively the worst emulation job/porting effort in history...).
You can also poke the black box a bit if you want -- increase a byte by one as it is saving (hopefully there are no millisecond accurate timers or anything to cause fun, that or you hold the timer with a cheat) and compare the difference, avalanche effects would be expected with a proper hash and the entire thing would be radically different, for a bytesum or something basic then less change expected.

SuperrSonic

  • Jr. Member
  • **
  • Posts: 12
    • View Profile
Re: Help figuring out checksum of GBA save
« Reply #3 on: August 07, 2021, 05:06:56 am »
I tried seeing how much it would change if only 1 value is increased and it did change a lot, sometimes it would give me a greater number other times not.

Patching the rom to remove the verification would be good enough, but actually doing it is beyond me.


EDIT: OK, I've decided to go a bit off the original idea and just rely on mGBA's auto-savestates, a savestate contains the GBA ram of course, so I make the tool modify this state and when the user starts the game again they can select "save & exit" so the next time they enter the TCG the changed stuff will be there.

This way allows supporting the various standalone TCGs that have no save feature.
« Last Edit: August 08, 2021, 07:38:19 am by SuperrSonic »

phonymike

  • Jr. Member
  • **
  • Posts: 69
    • View Profile
Re: Help figuring out checksum of GBA save
« Reply #4 on: August 08, 2021, 06:17:57 pm »
I'd be interested in figuring out the checksum if it's something you'd use.

SuperrSonic

  • Jr. Member
  • **
  • Posts: 12
    • View Profile
Re: Help figuring out checksum of GBA save
« Reply #5 on: August 08, 2021, 09:32:14 pm »
I would use it, and I would certainly prefer modifying the save correctly and not have to rely on a compressed savestate format that may change in the future, and also limits the users.

I haven't written anything for it yet.

KingMike

  • Forum Moderator
  • Hero Member
  • *****
  • Posts: 7260
  • *sigh* A changed avatar. Big deal.
    • View Profile
Re: Help figuring out checksum of GBA save
« Reply #6 on: August 09, 2021, 01:16:20 am »
Yes, disabling checksum check in game seems like an okay thing for debugging purposes, but a very sloppy and potentially buggy thing to leave in a finished mod.
While checksums can prevent modding, they do have a benefit of checking that the save function is working correctly.
"My watch says 30 chickens" Google, 2018

FAST6191

  • Hero Member
  • *****
  • Posts: 3357
    • View Profile
Re: Help figuring out checksum of GBA save
« Reply #7 on: August 09, 2021, 05:33:44 am »
Does the save function fail that much in games, especially by the GBA era, that it is needed for more than anti cheat and kids turning off during saving? I would also say for this game the worst that would probably happen is losing the chao garden data which... yeah.

Equally if it is going to be a problem then you probably know the jump location of "checksum passes" location, not the worst thing to fiddle branches at a later point while adding a basic checksum of your own (even a bytesum will probably do).

Back on topic as it were.
Anyway sounds like it might be something more on the real checksum side of things which tends to mean busting out the debugger. It is not the worst beginner project as you have a fairly defined goal, borders (you know the limits or at least the maximum limits of the data it cares about), most of it is going to be fairly boring procedural code rather than getting too radical with interrupts, and a nice tangible end result for it all as you get yourself the checksum/editor working. Compared to a lot of things where you have no fixed starting location, a bunch of hidden data/variables to contend with, probably a whole bunch to step through once you are there, abstraction because it is a game where anything can happen at any time and then almost a dream.

My general approach
Find the save data in memory. Can either grab the save data and search a RAM dump after it is loaded, or save data is in a fixed location/uses a given protocol so easy to set breakpoints for (plus GBA ROMs can have their save stuff found easily enough -- the same thing with the ASCII strings that works for save type for flash cart and emulator save determination/patching also yields some instructions if you were really bored). The compare save data and RAM dump probably being my first choice as it could be some time between save being grabbed and something done with it (think grab it and only check when you actually need it when the player goes to load it for real). Only trouble tending to be compressed saves (rare but not unknown) or expanded save data (should happen after verification but you never know... or actually you would know as the debugger will tell you if you seek such info).
Hashing tends to be a bulk data function iterated over the area it cares about (one hash for the whole save, current save + backup, individual segments... varies by game, about the only thing not covered will be the hash itself* if it is a real hash function -- the whole unpredictability thing getting in the way there). Might be several thousand instructions even for a high score table on a puzzle game but most of those will be read location from counter (you should have a range at this point from the stuff above for your break on read breakpoints), basic maths operation (maybe some boolean or bitwise operations for extra spice), fiddle with counter, repeat until end/counter is done (probably a WHILE loop if you want to think in such terms).
Once it is all there you might have the final maths operation get a nice result. You can look up the various hashing methods out there and their final results (usually some fun with XOR, inverting or similar) if you want, though it will mostly be for intellectual curiosity.
Compare to hash value stored (probably at start of save), do pass/fail accordingly.

If playing a bit more fast and loose then if you know the hash location then you might set a read for that and then work backwards a bit; some games might grab the hash value from the save first of all (silly on a NES, the GBA does generally have enough free registers that you could stash a 32 bit value there for safekeeping for a few hundred cycles when the game is probably doing nothing but worrying about the save, though it is still dubious programming**) but most will grab it at the end. If at the end you can hopefully go backwards enough to see the iterated function part, any capstone twiddling and you basically have it all there (the iterated part again tending to be a basic thing, just done however many times it needs). Similarly the counter part in the more traditional approach should also allow you to skip to the good bit (if counter = 0/full/whatever then jump to this location means you know exactly where to jump to once the iteration part has been completed).

*if you want to hash your list of hashes, or indeed do a signature (which is basically a form of encryption) you have the basis for HMAC (hashed message authentication system) wherein rather than doing computationally expensive (and potentially cryptographically troubling -- see encryption with known messages or all 00 messages) signatures for every file in your list you do a nice and computationally quicker hash on the lot and sign the list of hashes (files change, hashes change, signature of small list of hash files fails and you have your file assurance). Most modern consoles doing a variation on this theme.

**for really secure stuff then having data where someone might swap it, or read your keys, out is not a great plan and thus you might have it live on the stack or in a register, though that is also not without troubles -- see dumping of various blu ray and hd dvd keys from PC player memory dumps back when).

phonymike

  • Jr. Member
  • **
  • Posts: 69
    • View Profile
Re: Help figuring out checksum of GBA save
« Reply #8 on: August 10, 2021, 10:42:59 pm »
Hey got it working! It was more advanced than I expected but simple to implement. I don't know if you'd call this encryption but it's got a table of 16 bit values (256 of them) and some xor'ing going on. I wrote some C code that will calculate individual cropped 4KB files, or all 6 from the 64KB .sav file (stating at location 0xA000). Also has the commented assembly code from the game.

Download it here.

Code: [Select]
#include "crypt_table.h"

uint16_t checksum = 0xFFFF;

for (int i = 0x855; i >= 0; i--) {
    uint8_t upper = checksum >> 8;

    uint8_t nextByte = getc(fpSave);

    uint8_t pointer = checksum ^ nextByte;
    checksum = cryptTable[pointer & 0xFF] ^ upper;
}

return ~checksum; // invert the result

SuperrSonic

  • Jr. Member
  • **
  • Posts: 12
    • View Profile
Re: Help figuring out checksum of GBA save
« Reply #9 on: August 11, 2021, 07:11:14 am »
Wow, thank you so much!! This had been eating at me for weeks. I just tested it on SA1, SA2 and Pinball Party, all working perfectly.

This looks really complex, I'll be sure to make good use of it and hopefully others find it valuable too.