Pokemon Yellow hack recodes the game from within(tasvideos.org)
tasvideos.org
Pokemon Yellow hack recodes the game from within
http://tasvideos.org/forum/viewtopic.php?p=332488&sid=1d8670bd80327418d202b6608e5cd2a9#332488
21 comments
A fantastic talk by Meredith L. Patterson on this very topic at 28c3:
http://www.youtube.com/watch?v=3kEfedtQVOY
http://www.youtube.com/watch?v=3kEfedtQVOY
Wow - excellent link. I've been thinking about this lately. I'm not alone in thinking that languages are going to be important here. This is a great resource for further study! Thanks!
My understanding was that he exploited a buffer overflow in the inventory menu to get the cpu to jump execution to data he had crafted.
Isn't it a little like forcing a shell or repl out of a running program?
More like reimplementing a shell from within a shell and running your program on the latter.
Not really. As I understand, the different layers are:
1. In-game, he can write non-arbitrary but sufficiently powerful machine code to be executed directly. He uses this to write layer two.
2. He can write arbitrary machine code using A, B, start, select. He uses this to write layer three.
3. He can write arbitrary machine code using all the buttons (including d-pad combinations that I assume are physically impossible). He uses this to write the balloons.
All the code that actually gets run is precompiled machine code being executed by the processor. (There's nothing to stop him writing a shell, he just didn't.) He's not exploiting a system which happens to be turing-complete, he's gaining access to a system which was designed to be turing-complete but locked down.
1. In-game, he can write non-arbitrary but sufficiently powerful machine code to be executed directly. He uses this to write layer two.
2. He can write arbitrary machine code using A, B, start, select. He uses this to write layer three.
3. He can write arbitrary machine code using all the buttons (including d-pad combinations that I assume are physically impossible). He uses this to write the balloons.
All the code that actually gets run is precompiled machine code being executed by the processor. (There's nothing to stop him writing a shell, he just didn't.) He's not exploiting a system which happens to be turing-complete, he's gaining access to a system which was designed to be turing-complete but locked down.
Fascinating. I always wondered if this sort of thing was possible when I noticed as a child that pressing multiple buttons at the same time on my parents calculator made the screen show stuff that wasn't actually real numbers (things like a 2 with a part missing, etc.). Likewise seeing which buttons on the VCR have precedence (e.g. if I hold down "play" and press "stop" then what happens? And vice versa?). I always assumed the device wouldn't be designed comprehensively to handle all possible inputs like that, so there was a chance some of them would allow you to do funky unintended stuff.
Given the complexity and freedom of access that a videogame has, I'm not surprised that this hack is technically possible, but it is very impressive that someone's managed to do it!
Given the complexity and freedom of access that a videogame has, I'm not surprised that this hack is technically possible, but it is very impressive that someone's managed to do it!
There's this kind of unintended effects all over the place in tech.
A particularly interesting one for programmers might be the M6502 CPU.
All opcodes on the M6502 are 8 bits. Due to the way it was implemented in order to keep transistor count low, various patterns will trigger specific functionality at specific stages of execution (you can find a javascript emulation of it that displays the execution in excruciating detail as the result of creating a transistor exact clone of the design by decapping an actual 6502 CPU and scanning it...).
These were arranged so that the documented instructions present a suitably useful instruction set. But all of the remaining opcodes still does something that was simply deemed pointless by the designers.
Some have been found useful by demo writers in particular as a way of saving cycles. Some are just totally bizarre and/or unstable. Some does fun stuff like putting more than one value on the memory bus at the same time. Some even locks the CPU up so solid it needs to be power cycled to recover...
Here's an overview of the nitty gritty details from someone who actually knows what they're talking about: http://www.pagetable.com/?p=39
A particularly interesting one for programmers might be the M6502 CPU.
All opcodes on the M6502 are 8 bits. Due to the way it was implemented in order to keep transistor count low, various patterns will trigger specific functionality at specific stages of execution (you can find a javascript emulation of it that displays the execution in excruciating detail as the result of creating a transistor exact clone of the design by decapping an actual 6502 CPU and scanning it...).
These were arranged so that the documented instructions present a suitably useful instruction set. But all of the remaining opcodes still does something that was simply deemed pointless by the designers.
Some have been found useful by demo writers in particular as a way of saving cycles. Some are just totally bizarre and/or unstable. Some does fun stuff like putting more than one value on the memory bus at the same time. Some even locks the CPU up so solid it needs to be power cycled to recover...
Here's an overview of the nitty gritty details from someone who actually knows what they're talking about: http://www.pagetable.com/?p=39
Ha! When I was a kid we had Pong. You know, the hard-wired kind that plugged into your television, and get off my lawn, but this one had three variant games: Pong, basketball, and ... racketball I think. There was a hard three-position switch to switch between games - and if you positioned it just right between positions, you could coax the game into a hybrid game that mixed up the court layouts.
"This script walks from the Viridian City pokemon store to Oak's Lab in the most efficient way possible. The walk-thru-grass function guarantees that no wild battles will happen by manipulating the game's random number generator."
I've noticed similar behavior before in the Fire Emblem series. http://m.ign.com/walkthroughs/520430
I've noticed similar behavior before in the Fire Emblem series. http://m.ign.com/walkthroughs/520430
Most tool-assisted speedruns (TASes) for old-school video games, usually RPGs like Pokemon, include a "manipulates luck" clause. The emulator uses save-states, and if there's a random encounter, the player reverts to an earlier state. Repeat until successful.
Some games have naturally exploitable RNGs too. The GBA RPG Golden Sun and its sequel, for example, had a RNG that was completely reverse-engineered for players to get the top items that normally only randomly drop extremely rarely.
Some games have naturally exploitable RNGs too. The GBA RPG Golden Sun and its sequel, for example, had a RNG that was completely reverse-engineered for players to get the top items that normally only randomly drop extremely rarely.
see also: Nethack RNG trickery: http://taeb-nethack.blogspot.co.uk/2009/03/predicting-and-co...
In one of my least favorite games of all time, Final Fantasy II, it was possible to reset the "steps remaining until random battle" number by entering the menu and healing a character without full HP.
The number was actually stored in the save file, so you could just count steps until you entered a random battle, reload the system, and take n-1 before healing to completely avoid encounters. I expect this was purposeful because the battle system was so tedious and the encounter rate was obnoxiously high.
The number was actually stored in the save file, so you could just count steps until you entered a random battle, reload the system, and take n-1 before healing to completely avoid encounters. I expect this was purposeful because the battle system was so tedious and the encounter rate was obnoxiously high.
The next step is to find a vulnerable seam like this in the real universe.
Yudkowsky Ambition scale (http://news.ycombinator.com/item?id=4510702):
> 10) We think we've figured out how to hack into the computer our universe is running on.
It seems Software Engineering still has a long ways to go as a discipline: games like this fall to exploits by a small community after only a few years, while somehow the universe we live in has survived our civilization (and maybe others) banging on it for billions without any noticeable hiccups. ;)
> 10) We think we've figured out how to hack into the computer our universe is running on.
It seems Software Engineering still has a long ways to go as a discipline: games like this fall to exploits by a small community after only a few years, while somehow the universe we live in has survived our civilization (and maybe others) banging on it for billions without any noticeable hiccups. ;)
I think the issue is most software is not designed with security as a primary concern, so a determined users can produce a convoluted input that breaks a system. Having said that, if you take out buffer overflow exploits, how many games would still be hacked?
He likely did a lot of experimenting to discover which words inserted into memory by this bug did something useful, and which ones crashed the system.
So, no thanks. Go fuck up your own universe, I'm still using this one!
So, no thanks. Go fuck up your own universe, I'm still using this one!
Like throwing yourself at the ground and missing it.
For anyone that don't get the reference: This is from Hitchikers guide to the galaxy, which goes on to spend a few paragraphs describing how to fly by throwing yourself at the ground and missing it. As it says, "clearly, it is the second part, the missing, which presents the difficulties".
By the way, it's also exactly how orbiting works. The Moon and all the satellites are trying to fall down on us constantly, but they go so fast they actually keep on missing :).
That's basically what physics is.
Note that a key part of the hack requires the hardware to reset while a save game write is in progress. This causes the file to have invalid data -- an inventory list count is set to an "impossible" value.
Then, within the game, the invalid-length-list is used to overwrite other arbitrary locations, including a function pointer to an update procedure. Once that's overwritten he can jump to his own code and it's "game over" as in, he completely controls the hardware.
But from what I can see, it wouldn't be possible without the initial hardware resetting during a write. Not that it diminishes the awesomeness, it'd just be a bit purer if it was a software-only hack.
Then, within the game, the invalid-length-list is used to overwrite other arbitrary locations, including a function pointer to an update procedure. Once that's overwritten he can jump to his own code and it's "game over" as in, he completely controls the hardware.
But from what I can see, it wouldn't be possible without the initial hardware resetting during a write. Not that it diminishes the awesomeness, it'd just be a bit purer if it was a software-only hack.
The reset button is software-only. On most games, you can do a reset by holding down all four buttons.
If you're really into this, spend some more time on tasvideos.org
The guys that do these tool-assisted speed runs are incredible. One fellow plays 4 Mega Mans all at once with a single controller doing input for all 4 games at the same time.
This Pokemon hack is insane, but was inspired by a guy who uses it to beat the game in around 2 minutes. That particular speed run abuses the fact that everything in the game has a simple identifier. So, what he does is inserts a warp point into his inventory, drops it in front of himself, and walks through it to the end of the game.
The guys that do these tool-assisted speed runs are incredible. One fellow plays 4 Mega Mans all at once with a single controller doing input for all 4 games at the same time.
This Pokemon hack is insane, but was inspired by a guy who uses it to beat the game in around 2 minutes. That particular speed run abuses the fact that everything in the game has a simple identifier. So, what he does is inserts a warp point into his inventory, drops it in front of himself, and walks through it to the end of the game.
Here's a Chrono Trigger TAS that uses similar types of hacks as this Pokemon one:
http://www.youtube.com/watch?v=OgVVcnGm0eM&sns=em
http://www.youtube.com/watch?v=OgVVcnGm0eM&sns=em
His blog post goes into a little more detail about the actual "code" that runs than the forum post
http://aurellem.org/vba-clojure/html/total-control.html
http://aurellem.org/vba-clojure/html/total-control.html
It's quite interesting:
I built a layer of clojure code on top of the JNI bindings to get
an entirely functional interface to vba-rerecording. This
interface treats state of the emulator as an immutable object, and
allows me to do everything I could do with the lower level C
interface in a functional manner. Using this functional code, I
wrote search programs that take a particular game-state and try
out different combinations of button presses to get any desired
effect. By combining different styles of search with different
initial conditionsOne more aspect to this is how the game becomes interesting because it has bugs, not because it is bug-free.
One popular game bug in the Quake series was "strafe jumping" [1]. It became a canonical movement technique that got ported into other games.
[1] http://en.wikipedia.org/wiki/Strafe-jumping
[1] http://en.wikipedia.org/wiki/Strafe-jumping
Snaking in F-Zero GX or Mario Kart. Especially in the former, it makes the game even crazier than it already is.
Another one is "wavedashing" in Smash Melee. Not really a bug, but certainly strange behavior that became vital in competitive play.
so many exploits in that game..
so many days i'll never get back..
anyone down for a quickie?
Similarly "skiing" in the Tribes series was a glitch in the first game that eventually became the later games' signature maneuver.
Just like the amazing amount of StarCraft glitches, ranging from making ground units fly to completely insine stuff like turning a unit into a trap that crashes the game for every player who looks at it (and after some time crashes the game for everybody). All by legal in-game actions. I can't find a link, but one comprehensive summary back in the old days suggested that at least some of those glitches may be intentional, given how improbable, weird and useful they were.
Anyway, an example list: http://www.entropyzero.org/Glitches.html.
Anyway, an example list: http://www.entropyzero.org/Glitches.html.
I will never forget super-bouncing in Halo 2. Ever.
If you're interested in seeing what happens when you really want to hack the game though glitching/RAM abuse via cheat codes, check out this Let's Play of Pokemon Blue.
http://lparchive.org/Pokemon-Blue/Update%2001/
http://lparchive.org/Pokemon-Blue/Update%2001/
Sigh...
you know, I really could've used those 4 hours.
This is really clever. Figuring out the first bootstrapping program with such a limited instruction set must have been a pain though.
It's hilarious how much the My Little Pony reference derailed their conversation and excitement about the awesome hack.
Or you can just rewrite the game from source code :)
https://github.com/kanzure/pokecrystal
https://bitbucket.org/iimarckus/pokered
(Red is fairly close to being the same as Yellow. But there are definitely differences.)
https://github.com/kanzure/pokecrystal
https://bitbucket.org/iimarckus/pokered
(Red is fairly close to being the same as Yellow. But there are definitely differences.)
Now I might get stuck reading the author's blog all day: http://aurellem.org/
The Cortex project they having going is stellar and there are some great examples of Clojure-java interop.
The Cortex project they having going is stellar and there are some great examples of Clojure-java interop.
I wonder how many job offers this guy's going to get from security companies over the next 24 hours...
Probably not many. He used a buffer overflow exploit (found by someone else) to achieve arbitrary code execution (in a program not designed for security). That is not a trivial task (given the limited number of op-codes he was able to use), but not something that deserves job offers.
I think you overestimate how easy it is to hire people capable of overflowing buffers on their own initiative.
I think you underestimate how easy it is to exploit buffer overflows on systems with no exploit mitigations. Come back when you have ASLR and DEP running on the gameboy.
Just another reminder that anything is possible.
For those that are wondering if something like this is possible outside of computers/video games, I would recommend a study of Lucid Dreaming. If brain hacking is possible, this has to be the best method of entry into the system.
For those that are wondering if something like this is possible outside of computers/video games, I would recommend a study of Lucid Dreaming. If brain hacking is possible, this has to be the best method of entry into the system.
So am I correct in my understanding that this sort of hack is made possible only because the Gameboy uses an 8080 derived chip with Von Neumann architecture? ie. if it used a Z8 (or any other Harvard Arch chip) it wouldn't be possible to "bootstrap" like this?
I have nothing but admiration for people that do this.
Wow!
Wow!
Holy f this completely blew my mind
Beautifully done.
Oh, that's how you beat the game...
wow, this is amazing.
Anyway, there is a rising field ("language-theoretic security") that studies this phenomenon. If this Pokemon example interests you, then you should give it a look.
[1]http://www.cs.dartmouth.edu/~sergey/langsec/