What is the algorithm?

[Meerkov]

So, there is all this stuff about brute forcing etc etc.

But what is the desired output, and what is the algorithm used to hash?

The best reference I found was https://pastebin.com/DM7c9zjR

[micro500]

I responded to your post on TASVideos, but I'll add more here. The output we can expect from this process is a byte array that passes a checksum and correctly loads the second prize world. I don't think I have the processing algorithm very well documented (adding that to my todo list...), but I'd recommend browsing here to understand the algorithm better.

The algorithm is custom made, has multiple stages, and oftens drops bits which makes it difficult to reverse engineer. I have done some analysis on how reverse engineering could possibly be done, but it would require having some level of confidence in what the final output should look like, which we do not have. Alyosha's attempt to create a functional machine code output was successful in loading the level, but there were a lot of unknowns and guesses that we can't be sure how accurate it is, making reverse engineering more difficult.

[Meerkov]

I think the most important thing to document is:

1) What is the final output of the password, after running the algorithm, and before loading the level? 2) What occurs to load the level as a result? It was mentioned that it's run as bytecode. Can you analyze that bytecode to explain how the level loading process occurs? 3) Can you compare that to the result from Alyosha's attempt?

The big question is whether the final result that Alyosha came up with is even correct (because the level end is placed in an odd spot). Being able to understand how the final code differs from the known-correct code will help provide confidence, or will help determine if there is a mistake.

Once you know the correct resulting code, then sure, you can use brute force or anything else you want to try to get a working input password. But the first problem is simply understanding if the final code is correct.

[micro500]

1. The result after all of the processing is an 83 byte long array of bytes which is 6502 assembly.
2. If that array of bytes passes a basic checksum the processor jumps into it, regardless of if it is valid 6502 assembly (invalid opcodes, nonsensical code, infinite loops, instructions which trash the execution state, etc). This 83 byte block of code is repeatedly used throughout the level, so it is not just a level loading routine, but we think it is critical to making parts of the level function. Because the final step to get these 83 bytes is an XOR operation the encryption is essentially a perfect encryption/one-time pad, and we can have no idea what the correct value without the developers telling us the password.
3. Alyosha's attempt was an educated guess on what the assembly output could look like. We have some ideas on how the game wants to jump into this block of code, what pieces of the level do not function if we fill in the block of code wrong, but that attempt is not guaranteed to be correct. In a few places some of the chosen instructions could be swapped around with no affect on the code's functionality. Also, as you noted, the level end was placed in an arbitrary location. This was a choice by Alyosha and again is not guaranteed to be correct. Without knowing what the correct output is we have nothing to compare to Alyosha's attempt.

Alyosha's attempt was a major feat to get the level functional and has some good guesses at how things may have been programmed. In that attempt were some assumptions about how the assembly code is likely structured, but again due to the perfect encryption we can't be sure how close we are. The best we can do is check for those assumptions:

• The assembly code uses no invalid opcodes
• All addresses where the game wants to jump into the code are valid

The intention for bruteforcing is to check those things and only reporting on successes, which would mean they are more likely to be a valid block of assembly code. For bruteforcing I am not assuming I know what the expected output is, instead trying to find anything that looks maybe correct. In my testing the hit rate on these assumptions is very low due to the random nature of the algorithm output, so this does not lead to a large quantity of false positives.

These assumptions could of course be incorrect. The developers could have left invalid code in that block, or maybe parts of the level were incomplete and did not function as we thought. If any of our assumptions are wrong then bruteforcing becomes a lot more difficult, meaning we might need to test every resulting block of assembly as executable code in context which is not feasible.

Also note above I said we can't know if a result we find is correct due to the perfect encryption. It is possible (but highly unlikely) that we could find another block of assembly that comes out of the algorithm which passes the checksum, matches all of our assumptions, makes the level function (or at least does not crash the game), but is not the same block of code the developers programmed. Again, this is highly unlikely, but speaks to the fact that this is indeed a perfect encryption where we can't be sure we found the actual intended result.

If we wanted to try a reverse engineering attack, then yes we would need a reasonable guess at what the final assembly code output should look like. From there I have investigated some methods to work backwards from there, but as with any hashing-type algorithm like this reversing is non-trivial. There are also issues around the final output being 83 bytes while the algorithm operates on 128 bytes which increase the unknown space and add more complexity. Given that Alyosha's code included a lot of guess work it would be difficult to use that as the basis for attempting to reverse that code. The more unknowns involved expands the search space further, possibly to the point that bruteforcing is a better attack.

To summarize, we can't be sure we know what the expected output is. We have guesses, but they are just guesses. We may be able to do some reverse engineering from those and get lucky, but bruteforcing should also guarantee we find a valid result.