This repo contains my notes on the Pwnage Kingdom challenges from the event, and the symbols for PK3 along with my decoder implementation.
Note: I am not experienced in reverse-engineering; hopefully I haven't made any errors in my explanations
Pretty straightforward task: starting a battle with the trainer causes the game to crash, figure out to skip the battle or the trainer. My first thoughts were to modify the player position on the map, which didn't exactly work. I realized a better method, and that is to put a ret at the start of the StartBattle routine, which caused the battle to not be started in the first place. After what I assume was an error handler message, the challenge was complete.
I set up an access breakpoint on wMapNumber, and looked at when does it get read and where. This lead me to what i assume was a routine that loaded the map after the introductory screen appeared. Initially I went on a wild goose chase, trying to go deep into the routine, even changing the adresses the map was loaded from in hopes of finding the proper map header in RAM. However, I eventually just incremented whatever value wMapNumber had by default, and that completed the challenge. (Although the timing was important for this, because if the value was changed before the event script starts running, it got overwritten, and so the value had to be modified after it is loaded).
This challenge took most of my time during the event (although after finishing it, I wouldn't say it was caused by the actual difficulty of it [which it was, don't get me wrong], but more by my own mistakes).
I started off by running the decryption and using bgb's Logging Mode to find any interesting things. Eventually, I figured out the entry point for the decryption. From there, I went through it op by op, while also making symbols for any routines that were called from within it and discovering their function. I eventually realized that there was 32-bit arithmetic being done on certain values, which uncovered two nested loops, the outer one having a higher amount of iterations than the inner one. The inner one was xor'ing the data blob starting at A567 with values from an LCG, which was initialized with values coming from a second LCG in the outer loop (which I initially did not realize). Using the symbols I made, I found out the a, c coefficients for both generators, and went on to reimplement the decryption routine in C++. However, the program was still highly inefficient, and so the next task was finding a way to improve it.
After a lot of reading on linear congruential generators, I tried attacking the period of the inner loop in hopes of cutting the computation time significantly. This did not work, however I found out that the inner loop does have certain patterns at certain seed values, but I did not do any in-depth analysis with regards to that.
I started to look for any patterns inside the outer loop - and that succeeded. I found out that after 0x40000000, the first seed value of 0x5D0B1C11 repeats once again, which meant that the following generated seeds were also the exact same. Looking at the loops, the inner loop was XOR'ing data with random bytes from an LCG based on the seed from the outer one. That means if the outer seed was the exact same, the values generated by the inner LCG were also the same. Knowing the fact that A xor A == 0, I realized that when the inner loop ran twice for a seed, the end value would remain unchanged, and so those iterations could be skipped. Using my implementation, I searched for the seed that the outer loop ended on, the last seed before the outer generator repeats, and the number of iterations of the outer loop one would have to go through from the seed the loop ended on to the last seed before the pattern repeats. Those values were then given as parameters to the implemented loop, which would decode the data. This turned out to be a huge improvement, as instead of 2 billion iterations, the outer loop would only have to be run 1270 times, which made the algorithm finishable in a tolerable timespan of around 30 minutes.
At least in theory, as along the way I've had many issues with my implementation. Notable is I did not realize that the index pointing at what data blob byte will be xor'd next gets reset on each outer loop iteration, which caused many erroneous decodes. Also, I got the endianness of the parameter values wrong initially.
After finally figuring out an error with the index value (where the incremented index was mod'd with 200 (dec) instead of 200 (hex) (oops), I ran the decoder one last time, and saw a bunch of FF padding, which pointed towards success. In bgb, i loaded the data into memory, and jumped out of the decode function. Going through the cave door, the challenge was completed.
No, just no.
Please no.
(I ran out of time, and knowledge)
TheZZAZZGlitch - For hosting yet another great event
GCL Discord - for immense help and hinting with PK3