Last month was Defcon and with it came the usual rounds of  competitions and CTFs. With work and family I didn’t have a ton of time to dedicate to the Defcon CTF so I decided to check out the Red Team Village CTF. The challenges for the qualifier ranged pretty significantly in difficulty as well as category but a couple challenges kept me grinding. The first was the fuzzing of a custom C2 server to retrieve a crash dump, which I could never get to crash (Feel free to leave comments about the solution). The second was a two part challenge called “Seeding” in the programming category that this post is about.

Connecting to the challenge service returns the following instructions:

We are also provided with the following code snippet from the server that shows how the random string is generated and how the PRNG is seeded.

The challenge seemed pretty straight forward. With the given seed and code for generating the random string, we should be able to recover the key given enough examples. The thing that made this challenge a little different than other “seed” based crypto challenges I’ve seen is that the string is constructed using random.choice() over the key rather than just generating numbers. A little tinkering with my solution script shows that the sequence of characters generated by random.choice() varies based on the length of the parameter provided, aka the key.

This means the first objective we have is to determine the length of the key. We can pretty easily determine the minimal key length by finding the complete keyspace by sampling outputs from the service until we stop getting new characters in the oracle’s output. However, this does not account for multiples of the same character in the key. So how do we get the full length of the key? We have to leverage the determinism of the sequence generated by random. If we relate random.choice() to random.randint() we see they are actually very similar except that random.choice() just maps the next number in the random sequence to an index in the string. This means if we select a key with unique characters, we should be able to identify the sequence generated by the PRNG by noting the indexes of the generated random characters in the key. It also means these indexes, or key positions, should be consistent across keys of the same length with the same seed.

Applying this logic we create a key index map using our custom key and then apply it to the sample fourth iteration string provided by the server to reveal the positions of each character in the unknown key. Assuming the key is longer than our keyspace, we will replace any unknown characters with “_” until we deduce them from each sample string.

Now we have the ability to derive a candidate key based on the indexes we’ve mapped given our key and the provided seed. Unfortunately this alone doesn’t bring us any closer to determining the unknown key length. What happens if we change the seed? If we change the seed we get a different set of indexes and a different sampling of key characters.

In the example above, you’ll notice that no characters in our derived keys conflict. This is because we know that the key length is 10, since we generated it. What happens if we try to derive a candidate key that is not 10 characters long using the generated 4th iteration random string from a 10 character key?

It appears if the length of the key used to generate the random string is not the same length as our local key, then characters in our derived keys do not match for each index. This is great news because that means we can find the server key length by incrementing our key length from the length of our key space until our derived keys don’t conflict.

Unfortunately, this is where I got stumped during the CTF. When I looped through the different key lengths I never got matching derived keys for the server key. After pouring over my code for several hours I finally gave up and moved on to other challenges. After the CTF was over I reached out to the challenge creator and he confirmed my approach was the right one. He was also kind enough to provide me with the challenge source code so I could troubleshoot my code. Executing the python challenge server and running my solution code yielded the following output.

So what gives??? Now it works??? I chalked it up to some coding mistake I must have magically fixed and decided to go ahead and finish out the solution. The next step is to derive the full server key by sampling the random output strings from different seeds. I simply added a loop around my previous code with an exit condition when there are no more underscores (“_”) in our key array. Unfortunately when I submitted the key I got an socket error instead of the flag.

Taking a look at the server code I see the author already added debugging that I can use to troubleshoot the issue. The logs show a familiar python3 error in regards to string encoding/decoding.

Well that’s an easy fix. I’ll just run the server with python3 and we’ll be back in business. To my surprise re-running my script displays the following.

This challenge just doesn’t want to be solved. Why don’t my derived keys match-up anymore? This feels familiar. Is it possible that different versions of python affect the sequences produced by random for the same seed?

Well there ya have it. Depending on the version of python you are running you will get different outputs from random for the same seed. I’m going to assume this wasn’t intentional. Either that or the author wanted to inflict some pain on all of us late adopters 🙂 Finishing up the solution, and running the server and solution code with python3 finally gave me the flags.

Even with all of the frustration I’d say it was a very satisfying challenge and I learned something new. Feel free to download the challenge and give it a go. Shout outs to @RedTeamVillage_, @nopresearcher, and @pwnEIP for hosting the CTF and especially the challenge creator @waldoirc.