ROM Hack Identifying AP checks in commercial roms

[kinder_bueno]

Hello,

I wanted to try to learn cracking nds roms in order to prepare a patch for Mario & Luigi Bowser's Inside Story. I am a professional programmer, but specialized in high level programming languages. Still, I have some basics of assembly language (learned on my university) and already made myself familiar with no$gba debugger. The problem is that I've no idea how to start - I already know that this game requires at least patching arm7, and probably arm9 as well (concluded from checksums comparison of clean and patched rom). I know that I could try to change every if-else implementation and let's say, negate conditions (beq operand <-> bne operand) but there is a lot of them in the code. I suppose that it wouldn't be sufficient anyway - it's quite possible that developers could make it more tricky, e.g. by making use of operands like addeq or addne thus conditionally calculating some memory address. I would really appreciate if someone experienced could share her/his experience with me or give some insight.

 

[FAST6191]

I did have a thread covering some of the things around here once when I was thinking about a project to have an open database of AP fixes for the DS. Could not find it a few months back when I was looking for it though.

Anyway general theory is any means the game can use to detect it is not running on a normal cart will be used to trip such things.

3 approaches seen in ROMs
1) Below 8000h reads
2) Binary checksum
3) Save timing, though this was one particularly rare Japanese game.

4) is not as common as the GBA ( http://gbatemp.net/threads/buying-a-gba-flash-cart-in-2013.341203/page-18#post-4756995 ) and is things like the pokemon games with a pokewalker that had their save bus hidden behind a selection switch which you had to select first (or solder a jumper across from I guess) and stuff like https://gbatemp.net/threads/release-game-hacking-for-learn-with-pokemon-typing-adventure.480825/ and guitar hero (used the GBA slot to have buttons, debounced just the same though so like any controller hack in the end). Not strictly AP but will be things your emulator, flash cart firmware or compatibility layer will get to tangle with.

Choice link
https://gbatemp.net/threads/which-flashcart-for-castlevania-por.343239/page-2#post-4559271


Anyway http://problemkaputt.de/gbatek.htm#dscartridgeprotocol
Officially the games can not read below 8000h in the cart. Flash carts however (some eventually sorted it though more on that later) dutifully returned the relevant data as opposed to the real behaviour which is covered on the link above. Theoretically you could engineer such that it returns some useful data but nobody ever did that I know of
Later games stuck hundreds of such checks in, might have had subtle effects (Phantasy star for instance tweaked drop rates, other games had a kind of demo mode that said thanks for playing after so long...) rather than straight freeze or failure to boot. Later games still would obfuscate checks, stick them in lesser used overlays* and maybe even have enough of the checks that the game was noticeably sped up if you removed them.

*the DS does not have proper dynamic code handling a la DLL files on Windows. To that end it sets aside an area (or areas) and loads up code sections before branching to them. Said overlays, much like the ARM binaries**, can include non opcode data and in rare cases entire games are based around loading and unloading overlays.

**ARM9 is the main one in commercial ROMs, ARM7 is usually used for handling of hardware and are such that you can swap those of similar vintage without ill effect (or in some cases dodging issues with later ones). Homebrew however can vary here and there are many examples of the ARM7 being the main thing the program handles. Said binaries are also present in RAM and means RAM cheats can effect serious changes in games beyond what most think when they think RAM cheats. Some ARM7 stuff can be done though (not sure if this does) and others also find it nice to inject code into (it is a full processor with memory access and not likely to interfere with the main game -- a nicer injection point you could scarcely ask for).

I saw some of the Chinese flash cart makers once have a version of an emulator that noted every read below 8000. No public version of that exists but should not be too hard to tack something on desmume ( https://gbatemp.net/threads/unofficial-desmume-build-unused-memory-finder-tool.349332/ ).

Binary checksums are obvious, and usually only simple things (running a full MD5 or something similar on itself is not that doable so it will be more bytesum level). Quite rare as these things go as well.

 

[kinder_bueno]

Thank you for the long answer :-) I've read part of the specification but cannot figure out how arm9/arm7 attempts to read data from cartridge in assembly - what function does it use to store cartridge protocol instruction which would be sent to cartridge?

 

[FAST6191]

Most hardware on the DS (and GBA and other consoles) will allocate fixed locations in their memory bus to handling things, sadly for various types of hacking the DS does not map its carts to memory like the GBA but that is OK. Confusingly for some these areas of memory also get called registers.

As far as where it goes then in the 4000000 region of memory is what it handles this sort of thing
http://problemkaputt.de/gbatek.htm#dscartridgeioports
The B7 command is what is used.

B7aaaaaaaa000000h (200h) - Get Data
KEY2 encrypted command. The desired ROM address is specifed, MSB first, in parameter bytes (a). Returned data is KEY2 encrypted.
There is no alignment restriction for the address. However, the datastream wraps to the begin of the current 4K block when address+length crosses a 4K boundary (1000h bytes).
The command can be used only for addresses 8000h and up. Addresses 0..7FFFh are silently redirected to address "8000h+(addr AND 1FFh)". DSi cartridges will also reject XX00000h..XX06FFFh in the same fashion (and also XX07000h and up if the DSi cartridge isn't unlocked via command 3Dh).
Addresses that do exceed the ROM size do mirror to the valid address range (that includes mirroring non-loadable regions like 0..7FFFh to "8000h+(addr AND 1FFh)"; some newer games are using this behaviour for some kind of anti-piracy checks).

Offhand I am not sure what each and every game uses (I tend not to pay attention when watching this sort of thing as much as where it is going -- I am usually more concerned with finding data on a cart than defeating AP) but normal DS CPU instructions can not touch memory (only registers and immediates*). That is left to DMA or specific memory read/write instructions on the CPU (slightly off topic but why not http://adshomebrewersdiary.blogspot.com/2012/02/unequivocal-answer.html ), I imagine most will be the CPU instruction but I have been surprised in the past. I have not tangled with any obfuscation that might have been done to these either.

*and even they can get tricky as you obviously can't fit a 32 bit immediate into a 32 bit instruction and most things don't do trailing values. Most assemblers will help you out here but if you are looking at disassembly then it will possibly be multi stage involving boolean operations, shifts (ARM processors do shifting quite well for a reason) with subsequent writes, possibly movn (which inverts things) and other means of inserting/generating a value over a couple of instructions.

 

[kinder_bueno]

Do I understand correctly that commands which are sent to cartridge are stored under addresses 40001A8-40001AF? Are they already KEY2 encrypted as I see them in debugger or do I see raw values? If yes, then I suppose I should write sth similar to that empty memory finder you linked in your first answer, but catching every read below 8000h? And then try to localize those reads in arm9.bin and exchange it with correct, precalculated address?

 

[FAST6191]

We are playing at my limits here (the specifics of the protocol are not my forte as they are of limited use to me when pulling apart games) but I will try.
The commands should be entered raw -- any data returned might have had KEY2 stuff done to it but that is a different matter. As such yeah you could probably fork the code to interrupt on writing to that location, either do some boolean maths maths or "if value between b700000000000000 and b700007FFF000000" then log last 10 instructions to note space.

As far as defeating it when found then you could recalculate what it expects, however I don't think any game uses this trick for a "positive" read of actual data. To that end I would take out the check instead -- most checks will be an IF ELSE type arrangement (or probably CMP and BNE if we are using assembly terms) so you could probably NOP a whole bunch of things to remove reads and force a positive outcome of any checks instead.

 

[kinder_bueno]

Thank you once again :-) I think that M&L Bowser's Inside Story (that's the particular game I would like to crack) has not only below 8000h reads but also some checksums checks - nds-bootstrap implements proper redirection of such reads but still the patched game hangs after save selection, so there has to be more to it - I suppose those checksums - do you have any insight how one could search for them? Should I check every IF ELSE type arrangements or is there something which could make such chunks of code suspicious?

 

[FAST6191]

Some games do have funny saves and I don't know what nds-bootstrap does (still far easier to just get a flash cart from where I sit).

If it is just at boot you could probably step through it until you got there.

IF ELSE is a standard type of loop, also very useful in games*, so you would get any number of false positives if you did that. For a checksum then the routine for it will be nothing like anything else a game does -- nothing else will be scanning across the entire memory space containing the ARM9 binary or whatever. DS games don't have any kind of dynamic recompilation/just in time recompilation**/self modifying code so anything doing more than branching into an area is suspicious. Technically the DS binary can contain non executable code (if you are more familiar with C then think incbin or include http://www.codersnotes.com/notes/the-joy-of-incbin/ ) so not every read/copy is suspicious but again it is not going to be memory (binary area) wide and be more for loading the odd image or piece of text (the wifi error codes are frequently included in plain text in the binary for some reason, makes a nice place to overwrite if you need some space for your own function as well).

*at this point I am probably supposed to reference that classic thought exercise where they try to get people to code a FPS type game in procedural code as opposed to object oriented.

**there is a Lua engine some games use so maybe not there.

 

[kinder_bueno]

How those checksums work at all? What is different when the game is played from cartridge that the game can calculate wrong checksum thus making itself aware that sth is off?

 

[FAST6191]

Not sure of the specifics of the checksum routine for any given game, never mind generally. It will likely be on the simpler side of things though (think bytesum or basic crc rather than something more crypto grade -- if someone wants to engineer a collision then so it goes and anybody at that stage probably could have removed the check easily enough anyway).

Anyway if you removed all those below 8000h checks it will be different, if you put cheats in it* will be different (see also why a lot of these games would work in "clean" modes of various carts which necessarily disabled cheats), if you alter the save patching routines it will be different (why some carts which allowed you to manually select saves and have new games released after the kernel still work just fine where others would be waiting for an update), if your cart wanted all its nice real time save/text guide loading/cheat finding routines to be loaded in* and so forth.

*the DS was more or less a single threaded system with no OS layer. Any cheats then meant you need to hook some aspect of code (usually a vblank) to load them in, or in some cases find the instructions that fiddle with the memory areas and change those instead.

 

[kinder_bueno]

@FAST6191 I've forked desmume and now I have a version which can track to file what instruction under which address was processed - I filter branches and track whether there was a jump or not - is my assumption correct that on desmume we should have correct execution paths (since unpatched roms behave correctly and AP are not triggered) and for every branch that its condition evaluation is ALWAYS true or false (on desmume) I can hardcode it with B[AL] or NOP and thus patch it against AP?

 

[FAST6191]

Pass on a hard answer there as I have not looked at desmume's setup here. Some emulators on other systems do game detection and modify behaviours accordingly. Though I would expect it to behave as expected and work as it should, certainly I have seen some people try hacks over the years and have issues with desmume that flash carts had no such qualms with.

As far as using that as an automated detection and patch direction... I would not be surprised if the overwhelming majority of things could be patched that way. Someone might have obfuscated something (while nothing used it for a positive read that I know of I am far less sure about no obfuscations or something beyond a simple compare) and you do also have the "only did the check after what is normally about 8 hours of play* or something very rare like loading wifi"

*COP The Recruit had something like this.If memory serves it was something like a late game loaded overlay had a slightly obfuscated check.

 

[kinder_bueno]

Could you elaborate little more on how those obfuscations could look like in assembly?

 

[FAST6191]

Not in anything you could construct an elaborate regex for if that is where you are heading.

Two main approaches in assembly at obfuscation. Both subtly different to obfuscation as understood in high level languages (granted I mainly only meet it when I look at those obfuscation contests).
1) Spread processing. The DS may be slow as you like but it is still running at millions of cycles (and then being a RISC machine millions of instructions) per second. No big deal spreading that out over seconds. Someone pressing "next instruction" in a debugger is then in a predicament. Spread your hash function out over many cycles and it is still going to return a result in a matter of seconds (far less time than you need to play a game) -- say you are doing a bytesum, I am sure there are millions of examples of a game keeping a running counter/log of events and that is the same thing really. Stick a few of the instructions in with an otherwise useful loop that someone might dismiss "this function only handles health of the main character, though it has some weirdness in the middle" and it gets even better.

2) Odd instructions. I don't know if you have ever looked into Return Oriented Programming; basically as systems gained the ability to designate areas of memory for execution and gate off the others hackers turned around, took control of the return from branch function, scanned any given program for fragments that result in instructions (all computing is adding and all that). Kind of this. You use odd and esoteric takes on instructions, maybe have to do something for a result, then invert it to use with the next instruction but in the end you still get your computing done.

In any case for the below 8000h stuff it will have to go through the cart read stuff we discussed earlier so no worries there. Checksums on the binary area in software is easier to obscure but if they are going to spread it then it will likely need some kind of interrupt (possibly in a vblank) or odd check to trigger it.

Interesting link at this point

 

[kinder_bueno]

Thank you for a lot of materials - I will have to read/watch them carefully :-)

Speaking of overlays - I've already observed that under the same address the ARM9 CPU in desmume processed different instructions throughout the time - is that memory overloaded with overlay?

 

[FAST6191]

The overlays have a known location where they are going. The links in a later post for that free memory finder build cover such things. But yes if you noticed the same location doing different instructions then it is most likely an overlay. Typically they are quite late in the main WRAM memory but not always.

Theoretically it could be self modifying code (most of computing agreed that was a bad plan some time in the 90s, today only malware does it), a just in time compiler (some games do have interpreted languages like Lua at their core, possibly also Javascript) or a dynamic recompiling emulator (not sure there are any for the DS as that is a technique seen more for the PS1/N64 on up and does not do much good on older systems than those, certainly don't expect it in a game).
Back on the GBA, and still present to an extent on the DS, there was WRAM for the CPU. Everything on the GBA was on the cart and in the normal memory bus but if you needed that little bit more speed you could copy a sort of decent function to that area and run it.

 

[kinder_bueno]

Thanks for the answer :-)

Another question came to my mind - how do I know where is the last instruction in decompressed game's arm9.bin? Locating the first instruction is no brainer (I can take it from debugger) but what about the last one?

 

[FAST6191]

I don't entirely follow. There is no set executable memory area for the DS. Some header viewers like ndsts ( http://www.no-intro.org/tools.htm ) will give you source, copy to and size, and you can probably get similar data from crystaltile2. If you mean when does the executable part of the arm9.bin stop and what is just included data/incbin type things then afraid you get to find that yourself for any given game. I don't even have any sort of "usually it is" type things here as I am normally more concerned with finding given instructions or functions and then some space to add my own stuff than fully mapping ARM9.bin files.

If you are continuing with your emulator fork then on older devices with emulators like fceux and some snes stuff there are function/area logging capabilities. In ROM hacking at least the idea is you get to a point in the game good for you, start the logging, do everything you can but the thing you want, set the logging to "watch this" and then do the thing you want. Any new functions called at that point will presumably be the one you want. I imagine you could do something similar with this, however being a game (as opposed to a linear spreadsheet convertor or something) then getting all the functionality to be used might be tricky.

 

[kinder_bueno]

What I want to achieve:
1. I have prepared a list of hundres checks which I want to turn into BAL or NOP
2. I want to iterate over them and patch arm9.bin

So I will have to identify somehow which instructions are to be patched in arm9.bin and which are stored somewhere else (overlays, is there even any other place than overlays and arm9.bin?). I cannot find anywhere what part of arm9.bin is loaded into memory, but I suppose it is loaded entirely, but from debugger I can make out that the first executed instruction from arm9.bin is at other offset, it is not a beginning of the arm9.bin (what is on the beginning of arm9.bin then?). So I need to know what instruction from my list already "exceeds" arm9.bin. In general I would like to know general structure of arm9.bin (if something like this even exists).

 

[FAST6191]

Yes the entire ARM9.bin is loaded into memory and remains loaded at all points until it is shut off. Offhand I am not sure what the part of the ARM9 between the start of file and first instruction will typically be (no header section or anything like the GBA), however as boot up is fairly unusual in the scheme of the program I imagine the first instructions are more for setting up IO, clearing memory and all the other startup stuff.
Given overlays have a pre designated memory section. Multiple overlays may be loaded at once, and it is also possible that one overlay uses up a whole section where at other points two overlays might be.

All this will be in the header and similar sections, ndsts will likely tell you what goes. Crystaltile2 will also have some things.

I should also note that games can and do compress the ARM9.bin in the ROM. The compression used by the binaries is a different type of compression compared to the standard "type 10,11 or 40 LZ" aka BIOS compressions. In this case it is a type of backwards LZ aka BLZ aka DS binary compression. https://www.romhacking.net/utilities/826/ has the ability to handle it. I should also note that while crystaltile2 can handle the compression as well its file viewer sometimes lies about compression being there. Obviously you are not going to want to patch the binary in the ROM without first decompressing it if it is compressed.

With that said the binary area can be considered "arm9 location in memory + size" and any stuff you do for the overlays. The first instruction/execute address is fairly meaningless in this. If you happen to map the contents of the ARM9 or can otherwise demonstrate an area does not have any instructions in it then good for you, pending that though you kind of have to treat the whole area as CPU instructions in waiting. Nobody has ever shown any kind of layout that is common between ARM9.bin files. There might well be, or might well be for ROMs of a similar vintage.
At the same time though I have seen games load literally everything through overlay files (there were thousands in the end), have a large chunk of their script in the ARM9, wifi error messages are so common I look for them as a place to stash my additions to such things, I have seen level data in ARM9s and I have seen graphics in there as well. so I am not expecting much. If you were thinking maybe it is kind of like the Microsoft PE (exe,dll, xbe, xex...) or ELF formats then don't.