Solving the 2016 NSA Codebreaker Challenge – Task 5

Task 5 was more complex than the previous tasks, especially since there was no clearly defined way to solve it. I spent more time than I’d like to admit going down a bottomless rabbit hole, before adjusting tactics and fairly quickly discovering the solution. The gist of this task is that the keygen to generate the keys used in the previous two tasks has been discovered and we now need to figure out how to use it to generate keys for all IEDs.

Task 5 – Disarm Capability, Part 3
Great job! We used the code you provided to remotely disarm the IED, which was later found along a route frequented by military transport vehicles. These actions undoubtedly saved the lives of many service members. After disarming the IED, forward-deployed forensic analysts were able to recover several deleted files from the device. The most promising one appears to be the key generator program used to produce device specific keys like the one you recovered in Task 3 and used to generate a one-time code for the IED disarm command in Task 4. If you can find a weakness in how these keys are generated, then we could exploit this to generate valid one-time codes for any IED and remotely disarm it.

Analysts just alerted us of 2 additional IEDs within a few miles radius of military forces. The serial numbers are provided below. We need you to provide valid one-time codes for each one ASAP so we can disarm the devices.

UPDATE: Recent intelligence suggests that the terrorists are using Linux to generate the keys.

Serial Number of Device 1: 1379564839
Serial Number of Device 2: 31376699

The first method I attempted was to try and reverse engineer the generation of the secret value. The keygen takes a master key and serial number as input, and outputs the key file, so something like this: Keygen(MasterKey, Serial) = Secret (apologies to my CompSci and math professors, I’m sure there’s a better way of writing this). We know the Secret value we want to generate, and the Serial number, so I was hoping it would be able to feed in a Master Key value and see how it the Secret was generated off of it (by following along in IDA), and reverse that process, but I wasn’t able to, and I’m pretty sure the code was purposefully obfuscated to make this quite hard to do. In my next post I’ll dig into this more.

The second method I attempted, and was successful with, was to think about how the Secret values output by the keygen varied with time.

generated key varies with time

This indicates that the Secret’s generation is based at least somewhat on the system’s current time. A fairly standard way to seed this is a call to srand with a seed value of time(0).

srand(time(0))

time(0) returns the epoch time in seconds. srand will always generate the same sequence of values when given an identical seed.

Generally speaking, the pseudo-random number generator should only be seeded once, before any calls to rand(), and the start of the program. It should not be repeatedly seeded, or reseeded every time you wish to generate a new batch of pseudo-random numbers.

Standard practice is to use the result of a call to time(0) as the seed. However, time() returns a time_t value, and time_t is not guaranteed to be an integral type. In practice, though, every major implementation defines time_t to be an integral type, and this is also what POSIX requires.

From http://en.cppreference.com/w/c/numeric/random/srand

Thus if we can figure out what time our known Secret value was generated, we could use that knowledge to generate Secrets for our two new serial numbers. The only clear path to doing this is to brute force it and generate values at every second until we find the time that would have generated a value equal to our original key. To do this, I utilized libfaketime. With libfaketime you can spawn a process with a fake date and time, without monkeying with your system time.

make date think it was 15 days ago

I wrote up some javascript to do the looping. Not the prettiest code ever, and Node might not have been the best, but it worked.

Now, this wasn’t the fastest process ever, we’re generating a file and reading from it repeatedly, so I think it was only doing ~1000 attempts per second. Considering there’s 86,400 seconds in a day, that could take a while to scan through all the possible days. To make things go a little faster, I fired up some DigitalOcean droplets. Much faster than starting up AWS EC2 instances, and are really quite inexpensive. I think I spent $0.45.

droplets at work

I ended up spawning three of these, in addition to the process running in my VM locally. I would have spawned more, but then I found the answer. My original key was generated at an epoch time of 1473008047, or Sept 4, 2016 @ 16:54:07 GMT. With that time I was able to generate keys for the other two serial numbers and provide the OTPs requested.

Update: The first part of my attempts to solve Task 6 has been posted.

This entry was posted in Crypto, Infosec, Puzzles and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *