Attacking the hashing function in Tony Hawk's Pro Skater 2
32bits.substack.comVery cool article, love these.
> This brute force approach would work for short codes, but not for long ones. To generate all of the length 10 sequences would require computing about a billion hashes (8^10). That would work on my laptop, but length 11 codes (8 billion hashes) would be take a while, and 12 (68 billion hashes) would be a stretch.
We live in the future though. 68 billion hashes is absolutely possible on a laptop.
Also, the hash function shown should be easier to do than a „real“ cryptographic hash, right? The hash function looks pretty simple compared to something that’s artificially designed to take a lot of time to compute.
Yeah, for sure. It's as expensive to generate the permutations as it is to do the hashing in this case!
And another thing I noticed: because the hash is built Button by button, you can reuse part of the state when checking sequences. So if you’re checking a 10 button sequence, you get all subsequences of that almost for free (just need a comparison after every step). Getting to 18 buttons of length is still a lot of calculation though.
Good point - the dictionary attack produces some permutations that are too long, but it doesn't matter because you get the effect as soon as the final character of the correct code is entered.
Neat discovery. I would argue that this isn't really a dictionary attack because by taking permutations of words, you are not searching for actual words like STUD. Straightforward brute force may be cleaner, faster, and avoid duplicates.
Breaking simple (non-cryptographic) hashes is usually a great use case for an SMT solver like Microsoft's Z3. Unfortunately the approach is mostly defeated by the mapping of the input buttons to a set of arbitrary constants, so it resorts to considering a large number of disjunct possibilities---basically a very fancy brute force.
Nonetheless, I took a stab at it and I was indeed able to find the solution TXTUDUTXTUDUTXTUDU -- but I had to cheat and tell it the code repeats 3 times.
https://gist.github.com/rgov/e2d8f6831288ca739d5c51b0c9f4005...
Really cool! I'll play with this to see if I can come up with some missing hashes for Tony Hawk 3.
In this case it's probably smarter to resort to brute force.
Here's a C program that will run a lot faster than the Python. On my M1 Max MacBook Pro, I can evaluate all 9-button combos in 5.2 seconds. Each extra button should increase the runtime by a factor of 8. Allowing up to n repetitions should multiply the runtime by n. So you should be able to evaluate virtually all combinations in like 20 minutes without further acceleration.
https://gist.github.com/rgov/f471423e13e955c074ba9bac36c961b...
These things can sometimes be attacked with a theorem prover like z3. I think I remember the final microcorruption CTF challenge being like that.
If you feel like a challenge, Tony Hawk's Pro Skater 3 has some hashes with unknown inputs. The function is the same as the one in the article, and one target is 1eca8e89ad2dc1d6.
Try: TRIANGLE, UP, X, SQUARE, UP, X, CIRCLE, UP, X
Wow, nice work!
The other missing ones are: A75CA25CF4498F87 8FE0C6AA7CE60CEC B343B58CF0B72493 E0B20BEDFA0AC685 EFCC5A6FD62EC6D8
I tried up sequences of up to 10 buttons with up to 5 repetitions and then 11 buttons with no repetitions.
Curious to know what they do!1ECA8E89AD2DC1D6 = TUXSUXCUX A75CA25CF4498F87 = TDTRUTDTRU 8FE0C6AA7CE60CEC = RLRLSLRRLRLSLR B343B58CF0B72493 = SSSCCSC E0B20BEDFA0AC685 = RCDXLSUTDX EFCC5A6FD62EC6D8 = no solution foundExcellent - these seem indeed to work. I'll try to figure out what they do.
I'll write up the results eventually. I sent you a note about crediting your contribution here. Many thanks!