Would anyone be interested in helping out via a distributed computing setup? It would involve you running a program in the background on your computer that would be processing codes. It would also communicate with a server to keep track of what has been done.
Sure
Projects:
Tetris DS
Genesis Toys: Let the Toy Wars Begin
For what it's worth, you may look at re-purposing the code on the tcrf.net page. It seems to be well set-up for tracking blocks such that it is easy to distribute randomized 32-bit blocks to people to process in the background. It's also parallelizable if you set up the RANDOM1 option so that individual instances of the program execute on different "long blocks" as he calls them. I have about 23 instances running right now and piping the results to a separate folder. I have a separate program parse out codes that actually result in useable program code, but it's probably better if that's built into the program.
EDIT: I'm using a modified version of that code which checks for valid opcodes throughout the decoded string. It's compiled for 64-bit and takes approximately 5 seconds to cover a 65k space. Across 23 instances, this means that it takes about 4 hours to cover a 32-bit space. Assuming there's only one likely code (hint: there's more than one), we are likely to stumble across it in a little less than a million years at that rate. Progress!
FPGA implementation is still coming along, but I need to decide if it's better to keep it small and plan to have a lot of simultaneous cores or pipeline the hell out of it and maintain high throughput. I'll probably make both to compare, but we'll see.
EDIT2: Just to make sure my thought process in the final checking portion is correct, does it make sense to establish a "machine code chain" on the decoded string? I've made an array of how many bytes all of the opcodes are (with 0 for invalid/undocumented opcodes) that I use in iterating through the string until I find an invalid opcode. Code example is below:
I'm fairly certain this should be correct unless they put a data table somewhere in the space. Are there any issues with checking in this manner? I may be getting caught up in some endian shenanigans that I'm not considering.
Omnigamer and I have been busy making progress. Omnigamer has integrated the code from tcrf.net into my code to make a hybrid/frankencode version. The code from tcrf used a number of 128-bit processor tweaks to speed up calculations, among other things.
It also goes through the 64-bit space in a different way than my code. Instead of keeping the first four bytes the same and changing the last four, it keeps the last four constant and cycles through the first four. Omnigamer made a good point that in a way it makes sense. Since changing the first four bytes changes the processing much more dramatically than changing the last four, by cycling the first four bytes you get more diversity faster. One downside is that you are less likely to find multiple codes that work. That method also ends up repeating a large number of calculations, wasting time that could be saved. With my code I made an attempt to avoid redundant calculations by eliminating duplicate results after every step.
With my code alone Omnigamer was getting 771 seconds for a 24-bit block of codes. With his new hybrid code that time has been reduced to 154 seconds. He has put his code up on the googlecode project if anyone wants to look through it.
I've been working on a way to skip the redundant calculations all together by predicting when they will happen. I have came up with a method of tracking each binary bit through the processing, allowing me to see where they end up. I end up with a large number of boolean equations that can be reduced and evaluated. As the processing gets further along bits either become constant or are eliminated, which reveals duplicate results. Right now my code can frequently do 4 algorithms of look ahead before the decision for the next algorithm becomes equations that need to be evaluated. That evaluation will turn into a recursive algorithm to try all possibilities. Once I have this code able to look ahead 16 algorithms (1 step) I'm confident this method will be faster than processing an entire 32-bit block for 1 step. Depending on how fast it is running at that point I may be able to do more steps of look ahead.
Right now we're focusing on optimizing the processing (software/FPGA/CUDA/etc). Once we have the processing fairly optimized we'll work on a distributed computing solution that you guys can run. Stay tuned!
A note on the "frankencode" version, it is very much memory-dependent, and there is likely a memory leak somewhere such that it becomes unstable. There may yet be other bugs too; processing time actually increases as the incrementer starts to affect bytes 4 and 5. Somehow it was finding less and less collisions at this point, even though the hash table was still consistent... so either there really were 12M new unique values per byte, or I'm not setting up something right.
In any case, summary is to try at your own risk, and it's probably better to wait until micro500 has the redundant calculations worked out.
1. How's it going?
2. How exactly did they manage to make it so complex to find out the code? :o
3. How did they manage to make the 2nd prize world unplayable even by cheating there? Just how strong is the anti-cheating mechanism?
We've been spending time on getting a server set up so people can help out by donating computing time. I've decided to use BOINC since it makes it very easy for users to join in and help out. I've spent the last month figuring out how to set it up and get our application running with it, and Omnigamer is working on the actual server we will be using. There is still a lot to do, so we'll let you know when that is all ready for the public.
Yesterday I worked on the brute forcing code a bit. I cleaned it up and broke it out into smaller pieces. I still have a little more work to do before I'm ready to prepare it for BOINC. This will be the first application we deploy. It will be slower than some of the other ideas we've come up with, but it will work well enough to at least get us started and allow us to test the server. Afterwards we'll go back to application development and get some of our faster ideas deployed.
jlun2 wrote:
2. How exactly did they manage to make it so complex to find out the code? :o
The best way to think of this code is as a one-way hash. The password you enter is hashed in such a way that, given the final result, it is nearly impossible to work backwards to find the password you entered. The processing behind this hash function is 27 rounds of 16 algorithms, for a total of 432 bit-twiddling steps being applied. After processing the password you enter, the resulting 128 bytes are used to decrypt a chunk of ROM by XORing with it to produce machine code. However, we have no idea what the resulting machine code will be since it is unique to that level. There are 2^64 (18,446,744,073,709,551,616) possibilities to try, and we have to try them all until one of them produces valid-looking machine code.
The guys who made the game had it easy. Since they just XOR the result with ROM, all they had to do was pick a random password, run the insane processing routine they came up with, get the 128 byte result, and XOR it with the machine code they wanted to encrypt. They would then store that result in the ROM, and later when someone played through the game the same password would decrypt that machine code correctly.
jlun2 wrote:
3. How did they manage to make the 2nd prize world unplayable even by cheating there? Just how strong is the anti-cheating mechanism?
The encrypted machine code is unique to that level, and judging by the machine code used in the known prize world we assume it will set up some specific variables and run certain functions, but we have no idea what those will be. I cheated there by changing the map ID while I was in the carnival world. I think that worked because the machine code for the carnival world set up some things correctly for both prize worlds, enough that the secret world would display, but without running the correct machine code the music was wrong and level was generally broken. I had tried changing the map ID while I was in other worlds with no luck.
I was completely unaware something like this existed, pretty cool!
2^64 is a daunting space to check. Even if only 0.00001% gave you something that looked like valid machine code, just checking those cases to see which actually work is still daunting.
What is the machine code the first prize code generates? Can it be used as a guide to reason out what the resulting other machine code would be, for example the last instruction might be returning to a specific place in the rom?
A very interesting challenge, I will definitely be keeping track of it, good luck!
There are 2^64 (18,446,744,073,709,551,616) possibilities to try, and we have to try them all until one of them produces valid-looking machine code.
When do you think you will finish? If you can test 2^32 possibilities per second, it will take you over a century to finish.
I don't have a good time estimate yet unfortunately. Our hope is that crowd computing will help reduce the time significantly. One thing that helps us is that we don't actually have to fully test every single possibility. If we keep thinking of this processing as a hash function we can say that this function has very poor collision avoidance, meaning that many inputs results in the same output. There are actually a large number of passwords that will correctly unlock the prize world. It's possible to detect when the processing becomes redundant before you completely process the input, meaning that you can stop processing it and save some computing time. The code in the repository does that right now and it saves a large amount of time. I also came up with a strategy to predict these collisions before you even start processing so that they can be avoided even quicker. We also have plans to implement a CUDA/openCL processor which should be pretty fast, and Omnigamer has plans for a dedicated FPGA processor that should be even faster. Combining all these together should hopefully turn checking the whole 2^64 space into a reality.
Alyosha wrote:
What is the machine code the first prize code generates? Can it be used as a guide to reason out what the resulting other machine code would be, for example the last instruction might be returning to a specific place in the rom?
Here is the decrypted machine code (badly) commented by me if you're interested. If I remember right, the game constantly jumps back into this memory, usually every frame, so its not just a one-time thing to unlock the level. The decrypted memory has to pass a simple checksum where the last 2 bytes are compared to a rolling sum of the rest of the memory. From some testing it seems like most results fail on that check. After that the game immediately jumps to the first memory address, so the first few bytes and onward has to be valid machine code, at least until the first jump of some kind. This will help us make a heuristic validator to hopefully figure out if the code is interesting or not. We'll do more analysis as we get a large sample size of false-positive results back.
And if you're interested in helping out we could always use extra programmers. Let me know and we can certainly find something for you to do!
Joined: 12/8/2012
Posts: 706
Location: Missouri, USA
And to think an NES game seemingly has better encryption than most government websites :p
Looking forward to seeing this code get cracked!
"But as it is written, Eye hath not seen, nor ear heard, neither have entered into the heart of man, the things which God hath prepared for them that love him." - 1 Corinthians 2:9
I managed to figure out the working code for the second Bonus world.
Here is a savestate:
https://www.dropbox.com/s/7j3de93jsb8al1s/Treasure%20Master%20%28U%29%20HACKED_latest.zip?dl=0
The savestate works on a completely unmodified rom. Basically after I worked out what the code should be, micro500 was able to make it pass the internal checksum after the last step to make it run just as if it was input from the beginning.
However, finding out the pass code that let's you play the level through a normal play through of the game is quite another matter. Micro500 will be working on working backwards from the end code to what the original input was, but there is no garauntee it is possible, and a brute force search might still be needed.
In the mean time, enjoy playing this challenging level unseen for 20 years!
A big thanks to Alyosha for working so hard on reverse engineering the game and figuring out how what the encrypted machine code should look like! I'm hoping to be able to work backwards from that to determine the correct 8-byte payload to generate it.
There are 8 bit twiddling algorithms involved with the processing. Of those 8 algorithms, 2 of them pull a bit off the RNG and add it to the working code, and repeat that 128 times. Working backwards that would mean we now know 128 bits from the RNG. There are only 2^16 possible ways to seed the RNG, so if we check each possibility it should be obvious when we've found a match, giving us the RNG seed for that algorithm. The RNG is seeded once per round, so working backwards again we should be able to find the seed for the round. The seeds for each round are generated from a much simpler process based on only the first 4 bytes of the payload, so once I know the RNG seed for the round I'll have a shorter list of possible payloads to try.
3 of the algorithms pretty much just move bits around, so those shouldn't be hard to deal with. One algorithm will be a bit tougher, and the remaining 2 algorithms use addition which is much harder to reverse. I'm still working on a strategy for those.
Alyosha is only very confident about ~30 bytes of the machine code we have matching what the developers wrote. It's hard to say right now if that will be enough information to try this method. My goal is to work backwards one algorithm at a time until I hit one of the two algorithms that provide data on the RNG, but after a certain depth in the search the complexity will become too great. I estimate this will be around 8-9 algorithms back, but I'll know more as I get my code working.
Joined: 11/13/2006
Posts: 2821
Location: Northern California
Oh hell yes. I'm checking this place out right now.
I think I've gotten through most of it through trial and error, but I've reached what appears to be a complete dead end. I don't see any alternate paths or items or anything...
EDIT: Nevermind, found the way through. The level can be completed.
EDIT2:
Link to video
It's a really interesting level!
TASvideos Admin and acting Senior Judge 💙 Currently unable to dedicate a lot of time to the site, taking care of family.
Now infrequently posting on BlueskywarmCabin wrote:
You shouldn't need a degree in computer science to get into this hobby.
Oh hell yes. I'm checking this place out right now.
I think I've gotten through most of it through trial and error, but I've reached what appears to be a complete dead end. I don't see any alternate paths or items or anything...
EDIT: Nevermind, found the way through. The level can be completed.
http://i.imgur.com/p22Oswv.pnghttp://i.imgur.com/HeXsbRc.png
EDIT2:
https://www.youtube.com/watch?v=D9kvPXlQAX8
It's a really interesting level!
That is most likely the prize code for a second competition that was planned but never happened.
An interesting side note. There are unused Pizza Hut sprites in the game data that show up in the pallets for the carnival world and the game intro screen, so possibly they were originally a contest sponsor.
https://code.google.com/p/treasure-master-hack/wiki/Bonus_world_2_code_analysis
Here is the machine code if anyone is interested. The difficulty as micro500 noted is that not all of it is necessarily exactly as originally programmed. I put the level end trigger in a seemingly likely but still aribtrary spot. Also the code that resets the spring flag can also be changed and still work.
In some of his replies on twitter, Steven Ruddy originally (a couple years ago) mentioned that he might still have the passcode that loads bonus world 2 in his archives, but never responded with a firm yes or no if he found it or not. So that is another loose end.
If you finished the prize world there was a challenge-response to verify that you actually did it. The basic idea is that you would call the phone number, give them that code, and then they would give you a 3 character challenge code. If you press start on that screen another section of data comes up where you can type in the 3 characters they gave you and it would give you a 3 character response. The person on the phone would then verify those characters and award you with your prize. The long code on screen is generated from a few things including the bytes in the working code that unlocked the prize world, your lives, your score, and the serial number you typed in at the beginning of the game.
The two previously posted keys that enable access to the first prize world have different input distance: the second key is slower to input then the first one revealed on MTV. This is due to a longer total input distance of the second key that appears to be 163 movements of the rotating wheel with characters one has to choose symbols from on the password input screen vs. 154 movements needed for the first key. Thus, the shortest input distance is 154.
Joined: 6/23/2009
Posts: 2227
Location: Georgia, USA
Thanks, but that does not seem to really be a prize world. It's a weird glitched version of a minigame you have to play in the main prize world, and it has a time limit. With that time limit, I don't think you could accomplish much of anything interesting in that area, but maybe someone with TAS experience with this game could check it out.
Used to be a frequent submissions commenter. My new computer has had some issues running emulators, so I've been here more sporadically.
Still haven't gotten around to actually TASing yet... I was going to improve Kid Dracula for GB. It seems I was beaten to it, though, with a recent awesome run by Hetfield90 and StarvinStruthers. (http://tasvideos.org/2928M.html.)
Thanks to goofydylan8 for running Gargoyle's Quest 2 because I mentioned the game! (http://tasvideos.org/2001M.html)
Thanks to feos and MESHUGGAH for taking up runs of Duck Tales 2 because of my old signature!
Thanks also to Samsara for finishing a Treasure Master run. From the submission comments:
Shoutouts and thanks to mklip2001 for arguably being the nicest and most supportive person on the forums.
Right, the title is a bit misleading. The effects and garbage showing up though may have some alternative uses though, which is the main thing I was pointing to.
Thanks, but that does not seem to really be a prize world. It's a weird glitched version of a minigame you have to play in the main prize world, and it has a time limit. With that time limit, I don't think you could accomplish much of anything interesting in that area, but maybe someone with TAS experience with this game could check it out.
The title was merely a joke. Sorry, I should have pointed that out.
You can break the timer if you die right before the time runs out, then you can do whatever you want after that.
I did some running through it for a while and eventually you loop back to the minigame from the left side. The screen locks once you bring it all the way on screen, so there's probably not much more you can do.
I was made aware of the search for the second password for this game and decided to give it a shot, since I currently have access to my university supercomputer.
Maybe I can use that to finally solve this.
I have read this topic, the page on tcrf.net about this and been looking at the code on micro500's github.
I was hoping to be able to get some more details here.
Where should I pick up with this?
The repo contains a few different approaches and not too much documentation about them.
So far I've been mainly looking at the bruteforce code.
From my understanding so far, I would use tm_avx_full or something similar to find potential codes and then check everything that finds with process_code.
tm_avx_full has an IV array for byte0 - byte3. My understanding is I would keep changing these values until I find something?
byte4 is always 0 in the code, is that proven to be the case, or is that another number I would adjust while searching?
My plan going forward would be to move the project to using cmake to be able to test different compilers and stuff.
I also want to do a few modifications to the code to use more modern language features and maybe make the code a bit more safe (no more new :).
I also got some ideas for some improvements to the implementation, including a potential avx512 implementation that I wanna test.
And the MPI parallelize the thing and run it on the supercomputer if I manage to finish all that before I loose access.
Any additional info on this problem and the past work that has been done, as well as any further help would be very appreciated.
PS: Nec-nec-nec-necropooooost
Joined: 6/23/2009
Posts: 2227
Location: Georgia, USA
Henny022 wrote:
I was made aware of the search for the second password for this game and decided to give it a shot, since I currently have access to my university supercomputer.
Maybe I can use that to finally solve this.
I have read this topic, the page on tcrf.net about this and been looking at the code on micro500's github.
I was hoping to be able to get some more details here.
Where should I pick up with this?
The repo contains a few different approaches and not too much documentation about them.
So far I've been mainly looking at the bruteforce code.
From my understanding so far, I would use tm_avx_full or something similar to find potential codes and then check everything that finds with process_code.
tm_avx_full has an IV array for byte0 - byte3. My understanding is I would keep changing these values until I find something?
byte4 is always 0 in the code, is that proven to be the case, or is that another number I would adjust while searching?
My plan going forward would be to move the project to using cmake to be able to test different compilers and stuff.
I also want to do a few modifications to the code to use more modern language features and maybe make the code a bit more safe (no more new :).
I also got some ideas for some improvements to the implementation, including a potential avx512 implementation that I wanna test.
And the MPI parallelize the thing and run it on the supercomputer if I manage to finish all that before I loose access.
Any additional info on this problem and the past work that has been done, as well as any further help would be very appreciated.
PS: Nec-nec-nec-necropooooost
I don't have any ability to study this game technically or TAS it, but I'm definitely interested in any progress you'd make! Someone else who used to post in this thread might be more helpful though.
Used to be a frequent submissions commenter. My new computer has had some issues running emulators, so I've been here more sporadically.
Still haven't gotten around to actually TASing yet... I was going to improve Kid Dracula for GB. It seems I was beaten to it, though, with a recent awesome run by Hetfield90 and StarvinStruthers. (http://tasvideos.org/2928M.html.)
Thanks to goofydylan8 for running Gargoyle's Quest 2 because I mentioned the game! (http://tasvideos.org/2001M.html)
Thanks to feos and MESHUGGAH for taking up runs of Duck Tales 2 because of my old signature!
Thanks also to Samsara for finishing a Treasure Master run. From the submission comments:
Shoutouts and thanks to mklip2001 for arguably being the nicest and most supportive person on the forums.
EDIT2:
Link to video
It's a really interesting level!
