In my first post I mentioned that I love doing Capture-the-Flag (CTF) challenges, so here is a writeup of a challenge I completed recently. This challenge is part of the Google CTF – Beginners Quest, which is a great place to start if you are new to CTFs. In this post I walk through the steps I took to solve the challenge and at the end I include the python file I wrote to find the secret flag.<\/p>\n\n\n\n
This challenge prompts you to download a zip file, which when unzipped contains three files: <\/p>\n\n\n\n
<\/p>\n\n\n\n
Let’s take a look at the python file to see what we can figure out:<\/p>\n\n\n\n
<\/span> 1 <\/span>import<\/span> random<\/span>\n 2 <\/span>\n 3 <\/span>\n 4 <\/span># Gots to get that formatting right when send it to our call center<\/span>\n 5 <\/span>def<\/span> formatNumber<\/span>(n):\n 6 <\/span> n =<\/span> str<\/span>(n)\n 7 <\/span> return<\/span> f'{n[:3]}-{n[3:6]}-{n[6:]}'<\/span>\n 8 <\/span>\n 9 <\/span>\n10 <\/span># This generates random phone numbers because it's easy to find a lot of<\/span>\n11 <\/span># people! Our number generator is not great so we had to hack it a bit to<\/span>\n12 <\/span># make sure we can reach folks in Philly (area code 215)<\/span>\n13 <\/span>def<\/span> generateRandomNumbers<\/span>():\n14 <\/span> arr =<\/span> []\n15 <\/span> for<\/span> i in<\/span> range<\/span>(624<\/span>):\n16 <\/span> arr.<\/span>append(formatNumber(random.<\/span>getrandbits(32<\/span>) +<\/span> (1<\/span> <<<\/span> 31<\/span>)))\n17 <\/span> return<\/span> arr\n18 <\/span>\n19 <\/span>\n20 <\/span>def<\/span> encodeSecret<\/span>(s):\n21 <\/span> key =<\/span> [random.<\/span>getrandbits(8<\/span>) for<\/span> i in<\/span> range<\/span>(len<\/span>(s))]\n22 <\/span> return<\/span> bytes<\/span>([a ^<\/span> b for<\/span> a, b in<\/span> zip<\/span>(key, list<\/span>(s.<\/span>encode()))])\n23 <\/span>\n24 <\/span>\n25 <\/span>def<\/span> menu<\/span>():\n26 <\/span> print<\/span>(\"\"\"<\/span>\\n\\n<\/span>Welcome to the RoboCaller!! What would you like to do?<\/span>\n27 <\/span>1: generate a new list of numbers<\/span>\n28 <\/span>2: encrypt a super secret (in beta)<\/span>\n29 <\/span>3: decrypt a super secret (coming soon!!)<\/span>\n30 <\/span>4: exit\"\"\"<\/span>)\n31 <\/span> choice =<\/span> ''<\/span>\n32 <\/span> while<\/span> choice not<\/span> in<\/span> ['1'<\/span>, '2'<\/span>, '3'<\/span>]:\n33 <\/span> choice =<\/span> input<\/span>('>'<\/span>)\n34 <\/span> if<\/span> choice ==<\/span> '1'<\/span>:\n35 <\/span> open<\/span>('robo_numbers_list.txt'<\/span>, 'w'<\/span>).<\/span>write(\n36 <\/span> '<\/span>\\n<\/span>'<\/span>.<\/span>join(generateRandomNumbers()))\n37 <\/span> print<\/span>(\"...done! list saved under 'robo_numbers_list.txt'\"<\/span>)\n38 <\/span> elif<\/span> choice ==<\/span> '2'<\/span>:\n39 <\/span> secret =<\/span> input<\/span>(\n40 <\/span> 'give me your secret and I<\/span>\\'<\/span>ll save it as \"secret.enc\"'<\/span>)\n41 <\/span> open<\/span>('secret.enc'<\/span>, 'wb'<\/span>).<\/span>write(encodeSecret(secret))\n42 <\/span> elif<\/span> choice ==<\/span> '3'<\/span>:\n43 <\/span> print<\/span>(\"stay tuned for this awesome feature<\/span>\\n\\n<\/span>\"<\/span>)\n44 <\/span> elif<\/span> choice ==<\/span> '4'<\/span>:\n45 <\/span> print<\/span>(\"Thank you for using RoboCaller1337!\"<\/span>)\n46 <\/span> return<\/span>\n47 <\/span>\n48 <\/span>\n49 <\/span>def<\/span> main<\/span>():\n50 <\/span> while<\/span> True<\/span>:\n51 <\/span> menu()\n52 <\/span>\n53 <\/span>\n54 <\/span>if<\/span> __name__<\/span> ==<\/span> \"__main__\"<\/span>:\n55 <\/span> main()\n<\/pre><\/div>\n<\/div>\n<\/div>\n\n\n\nThe two functions that we should focus on are “generateRandomNumbers()” and “encodeSecret()”. The first was used to generate the list of phone numbers in the provided text file and the second was used to create the encrypted file. Presumably, this encrypted file contains the flag so our goal is to figure out how to undo the encryption process.<\/p>\n\n\n\n
The flag was encrypted through the following process:<\/p>\n\n\n\n
- Breaking it into individual letters<\/li>
- Encoding each letter with UTF-8 encoding, and <\/li>
- XOR-ing each letter with a randomly generated value<\/li><\/ol>\n\n\n\n
In order to retrieve the flag we must reverse this process, however this means we need to figure out the values that were randomly generated for the XOR-ing step. So I turned to Google to see if there exists a way to discover the seed used for “random()”.<\/p>\n\n\n\n
My searching informed me that “random()” uses the Mersenne Twister as its pseudo-random number generator (PRNG). And more importantly, it has a vulnerability.<\/p>\n\n\n\n
If you are able to acquire 624 consecutive values from “random()”, then you can correctly predict every additional value that it will generate. Fortunately in the provided python program, “random()” is called 624 times to generate the list of phone numbers, which we are given in “robo_numbers_list.txt”.<\/p>\n\n\n\n
After some searching I found a module that can be installed and used to predict the future values generated by “random()”. I installed and imported the module, fed in the random numbers from “robo_numbers_list.txt”, XOR-ed these values with each value in “secret.enc”, and undid the UTF-8 encoding of each letter. After combining the letters into a single string and printing it, I was able to see the encrypted message:<\/p>\n\n\n\n
CTF{n3v3r_3ver_ev3r_use_r4nd0m}<\/p>\n\n\n\n
Here’s the python program I wrote to uncover this flag:<\/p>\n\n\n\n
\n\n\n\n<\/span> 1 <\/span>from<\/span> mt19937predictor<\/span> import<\/span> MT19937Predictor\n 2 <\/span># https:\/\/github.com\/kmyk\/mersenne-twister-predictor<\/span>\n 3 <\/span>\n 4 <\/span>predictor =<\/span> MT19937Predictor()\n 5 <\/span>\n 6 <\/span># Open the phone number list to retrieve the randomly generated numbers<\/span>\n 7 <\/span>roboNums =<\/span> []\n 8 <\/span>with<\/span> open<\/span>(\"robo_numbers_list.txt\"<\/span>) as<\/span> infile:\n 9 <\/span> for<\/span> file<\/span> in<\/span> infile:\n10 <\/span> roboNums.<\/span>append(int<\/span>(file<\/span>.<\/span>replace(\"-\"<\/span>,\"\"<\/span>).<\/span>strip(\"<\/span>\\n<\/span>\"<\/span>)) -<\/span> (1<\/span> <<<\/span> 31<\/span>))\n11 <\/span>\n12 <\/span># Feed \"random\" phone numbers into the predictor<\/span>\n13 <\/span>for<\/span> num in<\/span> roboNums:\n14 <\/span> predictor.<\/span>setrandbits(num, 32<\/span>)\n15 <\/span>\n16 <\/span># Retrieve the encoded secret message<\/span>\n17 <\/span>with<\/span> open<\/span>(\"secret.enc\"<\/span>, \"rb\"<\/span>) as<\/span> secret:\n18 <\/span> letters =<\/span> list<\/span>(secret.<\/span>readline())\n19 <\/span>\n20 <\/span># Decrypt each letter in the message by XOR-ing it with the \"randomly\"<\/span>\n21 <\/span># generated value used to encrypt it<\/span>\n22 <\/span>answer =<\/span> \"\"<\/span>\n23 <\/span>for<\/span> i in<\/span> range<\/span>(