Naughty List Challenge Write-Up – X-MAS CTF
As the last post of the year, I decided to do something chill and a bit “off-topic” from my usual content. As the festivities are approaching, I have a bit more free time to dedicate to different stuff, like helping some friends with CTFs and such.
I’ve decided to post about this specific challenge because since it wasn’t the most complex nor the one with the most shenanigans to flex about, it likely wouldn’t get any write-ups. But it’s a perfect entry-level challenge, showing a real-world example of a subtle “logic bug” that can be inadvertently introduced by programmers. I enjoyed it very much and I don’t want it to get lost in the interweb; hat tip to the organizers: HTsP team.
Naughty List
The challenge began with the following prompt:
“PinkiePie managed to get on the Naughty List this year. Use your skills to get him out of this situation and he might reward you!”
The following C++ source code was available to inspect:
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <unordered_map>
#define ELF_MAX_NAUGHTY_COUNT 16
std::unordered_map<std::string, std::string> naughty_list{
{"PinkiePie", "Very naughty"}};
void menu()
{
std::cout << "1. Ask PinkiePie for the flag" << std::endl;
std::cout << "2. Query naughty list" << std::endl;
std::cout << "3. Add to naughty list" << std::endl;
}
void ask_pinkiepie()
{
bool pinkiepie_naughty = false;
auto it = naughty_list.begin();
for (int i = 0; i < ELF_MAX_NAUGHTY_COUNT; i++)
{
if (it->first == "PinkiePie")
{
pinkiepie_naughty = true;
break;
}
++it;
if (it == naughty_list.end())
{
break;
}
}
if (pinkiepie_naughty)
{
std::cout
<< "PinkiePie will not tell you the flag if he is on the naughty list"
<< std::endl;
}
else
{
std::cout << "PinkiePie is satisfied. Here is your flag!" << std::endl;
std::ifstream flag_file{"/flag.txt"};
std::cout << flag_file.rdbuf() << std::endl;
}
}
bool is_naughty(const std::string &name) { return !(naughty_list[name] == ""); }
void add_to_list(const std::string &name)
{
if (naughty_list.size() == ELF_MAX_NAUGHTY_COUNT)
{
std::cout << "Adding this many people requires authorization from Elf "
"Resources.";
return;
}
else
{
naughty_list.insert({name, "Naughty"});
}
}
int main()
{
int choice;
while (true)
{
menu();
std::cin >> choice;
switch (choice)
{
case 1:
{
ask_pinkiepie();
}
break;
case 2:
case 3:
{
std::string name;
std::cout << "Name: ";
std::cout.flush();
std::cin >> name;
if (choice == 2)
{
if (is_naughty(name))
{
std::cout << name << " is naughty!" << std::endl;
}
else
{
std::cout << name << " is not naughty!" << std::endl;
}
}
else if (choice == 3)
{
add_to_list(name);
}
else
{
std::cout
<< "Tampering alert triggered. This incident will be reported!"
<< std::endl;
}
}
break;
default:
{
exit(1);
}
}
}
}
This C++ program is a simple command-line application that allows the user to perform several actions:
- Ask PinkiePie for the flag: if the “PinkiePie” entry is present in the
naughty_listunordered map, the program will output a message saying that PinkiePie will not tell you the flag. Otherwise, the program will open the fileflag.txtand output its contents. - Query the naughty list: the user is prompted to enter a name, and the program will check whether the name is present in the
naughty_listunordered map. - Add a name to the naughty list: the user is prompted to enter a name, and the program will add the name to the
naughty_listunordered map with the value “Naughty”. However, if the unordered map is already at its maximum size (defined by the constantELF_MAX_NAUGHTY_COUNT), the program will prevent adding a new item.
Table of Contents
C++ unordered map
The entire challenge revolves around the C++ unordered map.
An unordered map is an associative container that contains key-value pairs with unique keys. Internally, the elements are not sorted in any particular order but are organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. – en.cppreference.com
I’ve made an instrumented version of the source code to print the content of the map:
template<typename K, typename V>
void print_map(std::unordered_map<K, V> const &m)
{
for (auto const &pair: m) {
std::cout << "{" << pair.first << ": " << pair.second << "}\n";
}
}
[Truncated]
case 1:
{
ask_pinkiepie();
print_map(naughty_list);
}
[Truncated]
Playing a bit with it, adding 10 elements and printing the content of the list, a “weird” pattern began to appear:
{11: Naughty}
{10: Naughty}
{9: Naughty}
{8: Naughty}
{7: Naughty}
{6: Naughty}
{4: Naughty}
{5: Naughty}
{3: Naughty}
{1: Naughty}
{2: Naughty}
As you can see, the elements in the list occupy a “random” spot; the “unordered” keyword in the unordered_map‘s name should tell you something…
Unordered associative data structures don’t give you any guarantee on element order. Rehashing invalidates the iterator and might cause the elements to be re-arranged in different buckets but it doesn’t invalidate references to the elements.
In the case of “Insert”/”Erase” operations, depending on different factors, iterators are invalidated when rehashing occurs.
With that in mind, it was evident that I needed to push the “PinkiePie” element “out of the list”.
Removing PinkiePie
Since the check for “PinkiePie” presence is made only on the first 16 elements of the list:
#define ELF_MAX_NAUGHTY_COUNT 16
[Truncated]
for (int i = 0; i < ELF_MAX_NAUGHTY_COUNT; i++)
{
if (it->first == "PinkiePie")
{
pinkiepie_naughty = true;
break;
}
++it;
if (it == naughty_list.end())
{
break;
}
}
If we can find a way to add enough elements to the list, causing the elements to be re-arranged in a way that “PinkiePie” doesn’t sit in the first 16 spots, the program will happily print out the flag.
The main problem is that we cannot have more than 16 elements in the list as the check, in the add_to_list() function, will prevent us from adding more items:
if (naughty_list.size() == ELF_MAX_NAGHTY_COUNT){
The square bracket operator
Luckily enough, the is_naughty() function use the square bracket operator:
bool is_naughty(const std::string &name) { return !(naughty_list[name] == ""); }
The function uses the square bracket operator ([]) to access the value associated with the key name in the map. If the key is present in the map, the operator returns the corresponding value. If the key is not present in the map, the operator will insert a new entry into the map with the key name and the default value for the value type (an empty string in this case).
For example, if the naughty_list unordered map is initially empty and the is_naughty() function is called with the parameter “Rudolph”, the function will insert a new entry into the map with the key “Rudolph” and the default value (in this case an empty string): {"Rudolph", ""}
It’s important to note that the behaviour of the square bracket operator is a general feature of C++, including maps and unordered maps. If you want to check whether a key is present in an unordered map without modifying the map, you can use the count()/find()/contains() member functions instead.
POC
I’ve then proceeded to add all the items possible via the add_to_list() function, and then, using the is_naughty() to add enough items to cause the “PinkiePie” item to be “pushed out” of the first 16 spots:
PinkiePie is satisfied. Here is your flag!
X-MAS{PiNKi3pi3_wiLl_n07_r3C3IV3_C04l_7hI5_y34R}
