Undo Five/Nine (Crypto 300, Lisbon CTF)

Last week I had the opportunity to participate in the on-site Bsides Lisbon CTF. I teamed up with some workmates and we tried to solve some of the challenges.

One of the challenges I was working on was "Crypto 300: Undo Five/Nine". I didn't take notes on the description, but basically they gave a piece of PHP code "snip.php" and two other files: "readme.txt" and "readme.txt.fsociety".

A quick look at "snip.php" helps us to understand how the other two files were used or generated:

$crypted = fopen($file . ".fsociety", "w");
$fp = fopen($file, "r+");
$clear = fread($fp, 2048);
// destroy original file
destroy_file($fp,strlen($clear));

// generate unique key
$key = gen_aes_key();
$aes = new Crypt_AES(CRYPT_AES_MODE_ECB);
$aes->setKeyLength(128);
$aes->setKey($key);

// create encrypted file
$clear = $aes->encrypt($clear);
fwrite($crypted,$clear,strlen($clear));

As we can see, it seems this PHP script read a plaintext secret from "readme.txt" and destroys it somehow. Then an encryption key is generated and the plaintext is encrypted using AES-128 in ECB mode. The encrypted secret is then stored in "readme.txt.fsociety".

So it seems we should be able to recover that encrypted message somehow. Since key is not stored, it was obvious that we were facing some kind of weakness in that key generation. Let's have a look:

function gen_aes_key() {

 $key = "";

 for ($i = 0;$i < 16;$i++)

   $key.= chr(mt_rand(0, 255));

 return $key;

}

Well, that makes sense. "mt_rand" function generates a random value via the Mersenne Twister Random Number Generator. This function, as its documentation warns, is not secure for cryptographic purposes. I googled for a while, and I found more information about this issue, where we can find the following information:

"Common misuses of mt_rand() include generation of anti-CSRF tokens, custom session tokens (not relying on PHP's builtin sessions support, which uses a different PRNG yet was also vulnerable until recently), password reset tokens, passwords, database backup filenames, etc. If one of these items is exposed and another is generated later without the web application or server reseeding the PRNG, then an attack is possible where the seed is cracked from the item generated earlier and is then used to infer the unknown item generated later."

It seems we should have at least another call to "mt_rand" and to have access to its results in order to be able to exploit this issue, but we only have an encrypted message, and a destroyed file. Let's have a look to the piece of code that destroys that file:

function destroy_file($fp,$len) {

  $random = "";

  for ($i = 0;$i < $len;$i++)

    $random.= chr(mt_rand(0, 255));

  fseek($fp, 0);

  fwrite($fp, substr($random, 0, $len));

  fclose($fp);

}

Bingo! It was overwritten using "random" values generates with the same function, which means that if we can obtain the seed, we could regenerate all the stream and grab the encryption key.

Let's do it! I was reading the seed cracker documentation for a while. It wasn't as easy as I initially thought, since this tool has several modes of operation, but I finally understood that the proper syntax was as follows:

$ ./php_mt_seed [first_num] [first_num] 0 255 [second_num] [second_num] 0 255 ...

But I had a bunch of bytes, so I decided to generate it using a few lines of PHP code:

$fp = fopen("readme.txt", "r+");

$clear = str_split( fread($fp, 2048) );

foreach ($clear as $v) {

    echo ord($v) . ' ' . ord($v) . " 0 255 ";

}

This code generated of the parameter that I needed. In a minute or two, I got an answer: "844114388". Now we need to regenerate all the stream based on this seed. Let's go back to a piece of PHP code:

mt_srand(844114388);

for ($i = 0;$i < 64;$i++)

    echo chr(mt_rand(0, 255));

When we generate this stream, we will see a number of bytes that should be the same to the information we can found in "readme.txt". After those bytes, we should have the encryption key (16 bytes).

$ php gen.php  | xxd

00000000: 7b36 0ee9 f9b9 1cfe d0bb d0e6 1311 5828  {6............X(

00000010: fcfe 84a6 7453 03f6 85b6 e270 76c3 41f8  ....tS.....pv.A.

00000020: aec4 9ca5 f658 dda4 20f2 1c9f 5d14 b5b1  .....X.. ...]...

00000030: beb5 1669 3135 31f9 30bc 9438 d0ac d0d6  ...i151.0..8....

So let's see if we can decrypt the file:

$ openssl enc -aes-128-ecb -d -K "f658dda420f21c9f5d14b5b1beb51669" -in readme.txt.fsociety
flag{the_darkarmy_is_now_on_to_you}

Bang! We got it! Unfortunately, I wasn't able to submit this flag. Why? First because, for some reason, I had in mind that "snip.php" was generating integers and then they were being truncated, so I spend around an hour reading the tool and trying to modify it. Second, because I got a syntax error on my code 10 seconds before CTF's deadline, so I wasn't able to fix it and to submit the flag. Anyway, I enjoyed the CTF :)