Toaster Week Part 2: TW_GR_E3_GtI and TW_GR_E4_STW
It occurred to me about a month ago that I never published author writeups for the “Toaster Wars: Going Rogue” CTF problems from PicoCTF 2017 and PlaidCTF 2017, which is particularly troubling since one of them wasn’t actually solved in contest! To remedy this, and in celebration of the release of a new game in the series that inspired these problems later this week, I’ll be posting writeups for all of the Toaster Wars problems over the course of the week.
For day two, I’ll be talking about the harder Toaster Wars problems from PicoCTF 2017: TW_GR_E3_GtI and TW_GR_E4_STW.
Toaster Wars: Going Rogue, Episode 3 – Garnish to Infinity
180 points (Level 3)
Many think the third entry in the Toaster Wars: Going Rogue series didn’t live up to Explorers due to its simplified gameplay, but I liked the new plot and ensemble cast better. Anyway, this one also has a flag that I can’t figure out how to get…
Hint: Clearly, you can’t get to the flag. But perhaps you don’t need to get over to it at all?
This version of the problem is pretty much the same game as before until you get to the fifth floor, when you come across this:
Even though the hint indicates we probably won’t need to, let’s consider possible ways to pick up the flag by simply stepping on it as usual.
The easiest would be to spawn on the same side of the wall as the flag, but unfortunately the config for 5F fixes the player’s start location and the location of the flag:
{
range: [5, 5],
timeLimit: 500,
generate: false,
bgm: "at-the-end-of-the-road",
description: {
map: {
width: 7,
height: 14,
grid: [
// (snip)
],
stairs: {
r: 11,
c: 3
},
known: {
grid: [
// (snip)
],
stairs: {
r: 11,
c: 3
}
}
},
enemies: [],
items: [
createFlag({ r: 2, c: 3 })
],
player: {
location: {
r: 7,
c: 3
}
}
}
}
If we don’t start near the flag, moving to it could also be an option. The generic movement action can only move you one tile at a time in any direction (this can be verified in /server/game.js), so simply walking there won’t work. No attack in the game has a movement effect either. This leaves only items, and conveniently, one of them does have a movement effect:
turmeric: {
name: "Turmeric",
description: "Warps the user to a random location.",
sprite: "turmeric",
effects: [
{
type: "move",
location: "random"
}
]
},
However, the configuration unfortunately doesn’t allow this item to appear randomly as it did in the first two versions of the problem:
items: {
density: 30,
distribution: {
screwdriver: .4,
battery: .3,
paprika: .05,
cayenne: .05,
// turmeric: .05, // Nope :)
oregano: .05,
cinnamon: .05,
peppercorn: .05
}
}
With this plan of attack exhausted, let’s instead follow the hint and try grabbing the flag without moving to it. A good place to start here is a careful inspection of how the logic around picking up items works, which can be found in /server/game.js:
function executeMove(state, entity, action, log){
/* ...a bunch of logic unrelated to items... */
// item check
if(entity.items.length < entity.stats.maxItems){
var itId = -1;
var name = "";
for(var i = 0; i < state.items.length; i++){
if(state.items[i].location.r == entity.location.r && state.items[i].location.c == entity.location.c){
itId = state.items[i].id;
msg.outcome.push({
type: "item/get",
id: state.items[i].id,
item: state.items[i].name
});
break;
}
}
}
entity.items = entity.items.concat(state.items.filter(function(it){ return it.id == itId; }));
state.items = state.items.filter(function(it){ return it.id != itId; });
log.push(msg);
return true;
}
So, in short, when we move to a location and have open space in the bag, we iterate over all of the items, find the id corresponding to the item on that tile if one exists, and then add all items with that id to our bag. So if we can get an item on the ground with the same id as the flag, we can pick up the flag without moving over to it!
But how can we make that happen? Perhaps there’s some way to modify the ids of items in our bag? A search for the string "id = " turns up this interesting result:
socket.on("resortItems", function(){
// logger.warn("[sort]", socket.id);
db.getState(socket.id)
.then(function(state){
if (state.done) {
return;
}
var oldState = censor(state);
state.player.items.sort(function(a, b){
if(a.name < b.name){
return -1;
}
if(a.name > b.name){
return 1;
}
return 0;
});
for(var i = 0; i < state.player.items.length; i++){
state.player.items[i].id = i;
}
state.log = [];
return db.commit(socket.id, state)
.then(sendState(socket, oldState, false));
});
})
This is the implementation of the item sorting feature available in the client; so when we sort our items, it also sets their ids to their indices in the bag. For example, if we have a full bag of 8 items, after sorting they will have ids 0, 1, …, 7. Unfortunately, we can see in /server/config.js that none of these match the id of the flag:
function createFlag(location) {
return {
name: "Flag",
description: "Gives you the flag.",
location: location,
use: 0,
id: 12,
sprite: "flag",
effects: [
{
type: "revealFlag"
}
]
};
}
However, this does mean that if we managed to get 13 items in our bag somehow, we would be able to pick up the flag remotely, since the final in the bag would end up with index 12 after sorting.
Fortunately, the bug we’ve already discovered already gives us a way to do just that! Suppose you have a full bag of 8 items, and there is one more item nearby. If you sort the bag, then drop the first item, then sort the bag again, then drop the first item again, and so on, then all of the items that were in your bag now have id 0. So you can pick up the ninth item, then touch any one of the other eight to pick all of them up at once!
Armed with at least 13 items (not hard at all with how abundant items are in this dungeon), we can pick up the flag on the final floor!
Toaster Wars: Going Rogue, Episode 4 – Super Toaster Wars
200 points (Level 4)
Many saw the fourth installment of Toaster Wars: Going Rogue as a return to grace after the relative mediocrity of the third. I’m just glad it was made at all. And hey, they added some nifty new online scoreboard features, too!
Hint: Ooh, what a nifty scoreboard! If we get a bunch of people playing at once, we can have a race through the dungeon!
It’s once again the same game, but this time with an extra scoreboard feature.
If we try to play the game, everything goes fine until 4F, when suddenly we come across stairs surrounded by walls!
Looking at /server/config.js, this happens because the fourth floor has an unfair flag set to true, which tells the dungeon generator to always surround the stairs with walls. If we can get past it, though, the flag is waiting for us on the fifth floor!
{
range: [4, 4],
timeLimit: 500,
bgm: "creaky-kitchen",
generate: true,
description: {
unfair: true,
map: {
width: 55,
height: 43
},
// ...
}
},
{
range: [5, 5],
timeLimit: 500,
generate: false,
bgm: "at-the-end-of-the-road",
description: {
map: {
width: 7,
height: 14,
grid: [
// ...
],
stairs: {
r: 11,
c: 3
},
known: {
grid: [
// ...
],
stairs: {
r: 11,
c: 3
}
}
},
enemies: [],
items: [createFlag({ r: 2, c: 3 })],
player: {
location: {
r: 7,
c: 3
}
}
}
}
Since the scoreboard was added for this problem specifically, we can probably safely assume it has something to do with the solution. Searching for "scoreboard" in the files we know about turns up a few results, but most notable is this piece of code in /server/game.js related to advancing to the next floor:
if(state.player.location.r == state.map.stairs.r && state.player.location.c == state.map.stairs.c){
db.scoreboard[socket.id].floor++;
prm = generator.generateFloor(db.scoreboard[socket.id].floor)
.then((newState) => {
if(newState.done){
socket.emit("win");
return Promise.all[db.commit(socket.id, {done: true, win: true}), initState];
}
newState.player.items = state.player.items;
newState.player.stats = state.player.stats;
newState.player.stats.modifiers = {};
newState.player.attacks = state.player.attacks;
state = newState;
log[0].outcome.push({
type: "floor",
number: state.map.floor + "F"
});
state.enemies = state.enemies.filter(function(en){
return !en.dead;
});
})
} else {
// ...
}
So the operations taken, in order, are:
- Increment the floor number stored on the scoreboard
- Generate the next floor using the floor number on the scoreboard (asynchronously)
- Update the game state to the generated value
This presents an opportunity for a race! (And suddenly, the hint makes sense!) Suppose that we submit two back-to-back requests to step on the stairs on 3F, A and B, at about the same time; one possible order of steps would be the following:
A1: scoreboard floor number incremented to 4A2: start generating 4FB1: scoreboard floor number incremented to 5B2: start generating 5FA3: state set to the generated state for 4FB3: state set to the generated state for 5F
If we could make this happen, we could skip 4F entirely! While this is technically possible without any further help as-is since generateFloor is asynchronous (so Node has the freedom to switch to a different asynchronous task before computing it), generateFloor also conveiently has delay built into it with a comment lampshading its fairly unnatural inclusion:
function generateFloor(floor){
return new Promise((resolve, reject) => {
setTimeout(() => { // Don't block the main thread
// ...
}, 10);
});
}
So all we have to do is go to the stairs on 3F, submit two requests to move to the stairs at the same time, and hope for the best!
Thanks for sticking around! These problems will get far more complex starting tomorrow, as we will be tackling the first of the three problems from PlaidCTF 2017!