PlaidCTF 2019 Everland - Writeup
I played with 5BC in the PlaidCTF 2019, playing mostly misc and reversing. This is a writeup of Everland, a misc challenge that consisted of playing a text based action game and defeating a final boss.
I worked on this challenge alongside @EyalItkin who was 100% awesome.
TL;DR We found two logical bugs. One, allowing us to defeat nearly every enemy by making them hurt themselves. Second, we found a way to defeat the boss with an “instant kill” attack.
Opening the challenge
To start the challenge, we received a source file and a server presumably running a near identical copy of the code.
Connecting to the server brought us the following prompt
Clearly the player has some sort of health and strength and we’re facing off a generic opponent.
Playing around with the game let us understand what options exist in the game and what is the challenge.
The player can forage for new items, providing items that can power up the player and provide new abilities.
We can _use _items, which probably gives us new abilities or restores health,
Last, we can pick to fight. The player can pick different attacks.
If we look at the text output, we can see the opponent attacks us before we can attack him.
Using this information, we could open up the source code and figure out how to get the flag.
The source code of the program is written in Standard-ML, which we surmised from the file extension that was .sml. A quick google lead us to this guide for learning Standard ML, it proved invaluable in understanding the code.
Looking at this function, it looks like we need to defeat all of the enemies, at which point we get the flag by raising an exception that references get_flag. No surprise so far :)
Looking at the source code, we could see that there are 10 enemies and that somewhere there is a function that generates the enemies along with some sort of “boss” event.
Clearly the challenge can be split into two parts
1 - Defeating normal enemies
2 - Defeating the end game Boss.
At this point it was time to actually dig into the code
We started out by simply reading the entire source code and annotating it for ourselves. I’ll go over the more important parts of the code and those that were relevant to the challenge.
Some parts were simple, such as foraging and generally the core game loop. By finding references to forage we found the bottom most function, that receives player input.
Following references rapidly brought us to the code of play_game which was easy to read even without knowing ML.
We don’t really care about the implementation of forage but we can look at the world variable and see it’s initialised in the start function with a small list of items.
By simply playing the game we could see that this list is static and every time forage is picked, the first item is removed. We also guessed (correctly) that the first number affected the users health, the second the users strength and the third was a function pointer that added player capabilities.
Some parts were more complex, for example, the attack flow. We started out by looking at functions that affected health in battles.
This function receives the health and strength of both fighters (we’ll call them my player and their player for reasons that will soon become clear). This function returns two functions: One that reduces the opponents’ health while reducing the attackers’ health by a lesser amount. The other function is effectively a nop.
This and other functions are referenced in a few global variables such as
This variable is referenced in gen_enemies, as part of the “actions” an enemy can do.
To actually understand what the two returned functions are, we turned to the fight function. This function is called from the main function with the following signature.
We can figure out what hero and enemy mean from two directions. One is looking at the data types defined in the source code.
The other is looking at the function signature, as it breaks apart the parameters into smaller variables.
Skipping down to the bit where the player picks his action, we can clearly see that only one of the two functions are used.
In interest of completeness, we’ll go over how the computer opponent picks his actions.
The relevant code is
The code defines a data structure composed of the enemy state and the player state (note the order). It passes this state to a function named state_heuristic along with a variable named e_ms which is the list of enemy actions. The mapping function returns a sequence of options, which are a pair of a score and a (name, function) tuple. This sequence is fed into a fold function that picks the “best” option and returns the appropriate (name,function) tuple.
The state_heuristic function is pretty simple, it simulates running a specific action and quantifies how good the result is.
We compiled the list of possible actions into the following table:
|Action||Who can use it||Effect|
|Kill||Computer opponent only||Opponent health := 0|
|Spear Lunge||Computer opponent only||Opponent health := health * 2 / 3.
My health := health - 10
|Sword Strike||Both||Opponent health := health - 15|
|Full Empower||Both||My strength := strength + 20;
My health := health - 20
|Recuperate||Both||My strength := strength - 20;
My health := health + 10
|Net Capture||Player only||Sets global capture flag to true.
Can only capture an enemy with less than 50 health.
Once captured, we can choose to sacrifice him in one of our future turns
|Stink Out||Player only||Opponent strength := strength - 10|
|Vine Wrap||Player only||Opponent strength := strength - 5;
Opponent health := health - 5
Some trial and error, blind luck and writing up our own simulator told us that by forcing the enemy to constantly use Recuperate would lead the enemy to kill himself by constantly using Spear Lunge which also impacts his own health.
Using this we could defeat all normal enemies. However, the “boss battle” had two significant differences.
1 - The boss skips the first action, giving us a free shot
2 - The boss has only a single action, kill, which instantly kills the player.
To figure this out, we went back and looked at all the special actions. We noticed that upon capturing an enemy, two things happen.
First, we “capture” it and start fighting the next enemy.
Second, we gain an additional action, Sacrifice. This one shot action sets player health to min(200, my health + min(captured health, my strength * 10)) and then reduces the captured enemy health by player health * 10.
Preparing for the Boss
While “Sacrifice” will kill the enemy that we previously captured, we needed it to kill the Boss. After digging through the code, we saw that the boss will be an upgraded version of one of the enemies we defeated. The decision logic picks that the defeated enemy with the highest strength, strengthens it into a “Possessed” version, and makes it the final boss.
Using our simulator, we found out that when we have low strength and full HP (after taking the foraged health potion), our opponent will pick “Full Empower” as his next move. This move increases the enemy’s strength, making him the preferred candidate to be “possessed”.
While possessed, the boss is still linked to the previous “normal” enemy. Combining all of this together, we figured out we need to capture the last “normal” opponent, after we “convince” it to strengthen up. Now when we reach the final boss, we can use the sacrifice action to “instant kill” the opponent and the boss together.
We decided to try this out on two enemies, it worked. We then went and tried this attack on the real server, spoilers, it worked.
Because the real server had 10 enemies, this involved a lot of manual typing. We could have scripted it, but in the heat of the moment we got lazy.
The flag in the end was