Reverse engineering old games is always plenty of fun, there are so many different and unusual approaches available. One thing I've found particularly effective is to add custom hacks and patch to the emulator itself.
For instance, when cracking the password algorithm of the original Crash Bandicoot, I came across a stack-based virtual machine for Naughty Dog's Lisp-based GOAL language. Since the game used a custom archive format for all its data and I really didn't want to start figuring that format out, so instead I patched the PCSX emulator to print out each executed virtual machine instruction and related state as they were executed: https://github.com/dezgeg/crash-bandicoot-password-cracking/...
I wrote the GOOL code that you reverse engineered. It was probably only 8 lines of lisp code or so. The basis of the algorithm was simple modular exponentiation used to scramble the game state bits:
h(x) = g^x mod p
where x was the entire game state packed into 24 bits or so. I mapped the output bit pattern to a button sequence -- every two bits mapped to one of { circle, square, triangle, x } -- to produce the output "password".
I don't remember the values for the generator g or the prime p, and no longer have the source code.
This kind of construction is very common in cryptography, and was suggested to me by Carl de Marcken, who wrote much of the lisp code at ITA Software.
Wow, what a coincidence to hear from the original author!
I never looked at (or even located) the actual password generation code, but only worked on the password verification code,
as it's way easier to do it in that direction. What I initially did was to use the PCSX emulator's cheat finder feature
to locate the memory address of the variable that holds the length of the entered password, then placed a memory breakpoint on that
address in the NO$PSX emulator, which then lead to the discovery of the virtual machine.
After some reverse engineering of the VM's instruction set and programming the VM tracer, as I knew
the address of the VM instruction that incremented the password length counter, I could mash
one button for 24 times, and then look at the differences in the instruction traces when the final password character was entered.
The function make() in the JS is my implementation of the password generator, i.e. inverse of check(), which
wasn't too hard to figure out. I never did bother to find a closed-form expression for the inverse of `mixAndPermute()` function,
so maybe that's where the modular exponentiation hides, but I personally don't have enough number theory-fu to crack that.
Interesting... it looks from your code like maybe I broke the bitmap into chunks and separately permuted each chunk -- probably to make things faster on the (incredibly slow) PS1 CPU.
It's a weird experience for me to try to figure out what I did 20 years ago, without access to the original source. You have almost certainly put more time and thought into reverse engineering it than I did in writing it, and at this point probably know more than I do about how it works. :) Somebody at Naughty Dog must have the code -- maybe they can post a snippet...
(I also play the Crash games with my kids and hardly remember even the levels I worked on... it's like playing a new game! Maybe I am just amnesiac...)
mixAndPermute is actually 'RSA' encryption; the modulus factors as 43 * 47 and the public exponent is 5. Inverting it is a matter of computing x^773 mod 2021.
For instance, when cracking the password algorithm of the original Crash Bandicoot, I came across a stack-based virtual machine for Naughty Dog's Lisp-based GOAL language. Since the game used a custom archive format for all its data and I really didn't want to start figuring that format out, so instead I patched the PCSX emulator to print out each executed virtual machine instruction and related state as they were executed: https://github.com/dezgeg/crash-bandicoot-password-cracking/...