Thursday, 27 June 2013

MWR Hackfu Challenge 2013

This year I entered the MWR Challenge 2013 and won a place at Hackfu! Unfortunately, I was unable to attend due to a scheduling conflict, but I did still get a free T-shirt. I had a blast completing the challenge, and thought I'd share my solution.


There is a great narrative that accompanies these challenges, but I'll not mention that here so as to not give away any spoilers!

Challenge 1

You're given a zip file that contains an image file and a text file explaining how the image file can be mounted. The mounted image file contains a TrueCrypt volume and a text file stating that the password to this volume is very secure - unlike the password for the previous (now deleted) TrueCrypt volume, which was "password1".

Using Autopsy, a GUI for TSK (The Sleuth Kit), it was possible to recover deleted files on the image. A file called old-zip was recovered. This zip file contained a TrueCrypt volume called truecrypt-volume-old. This volume can then be mounted using the password "password1". Unfortunately, this volume is empty aside from a text file suggesting that you find a way to use this volume to your advantage.

Autopsy was used again, but this time to forensically analyse the mounted TrueCrypt volume. You will need to run Autopsy with Administrator privileges to do this. Deleted files required to complete the remaining challenges were recovered.


Several deleted text files were also recovered from the "files" directory. There were instructions, in "start-here_your-orders.txt" on how to complete the challenges. Upon completing each challenge you are provided with a fragment of the passphrase needed to decrypt the "epilogue-crypt.txt" file. The first fragment is at the top of the "start-here_your-orders.txt" file - "WNzr7BaH-y7_".

Challenge 2

You are given an encrypted file, intercepted-file.bin, and told that it can be decrypted by simply XORing the key with the file's contents. You are told that pi is used as a one-time pad. The only problem is that the key does not start from the beginning of pi. You are told that it starts at a certain offset. For example, if pi ~ 3.141592653589793238462643383279502884197169 and the offset is 5 then the one-time pad for decryption is 592653589793238462643383279502884197169. You are also told that the decrypted file will be a zip file.

I wrote a Perl script to brute-force the key. pi.txt contains pi to 100,000 places and was downloaded from the University of Illinois' website. Some massaging was needed to remove spaces and new lines. The script below attempts to decrypt the file using incremental offsets of pi until the file output is a zip file.

#!/usr/bin/perl

use File::LibMagic ':easy';

open F, "intercepted-file.bin" or die $!;
binmode F;
my ($buf, $data, $n, $total);
while (($n = read F, $data, 4) != 0) {
        $total += $n;
        $buf .= $data;
}
close(F);

open F, "pi.txt" or die $!;
binmode F;
my ($other_buf, $other_total);
while (($n = read F, $data, 500) != 0) {
        $other_total += $n;
        $other_buf .= $data;
}

for (my $offset = 0; $offset < $other_total-$total; $offset++) {
        my $key = substr $other_buf, $offset,$total;

        my $zip_file = $buf ^ $key;

        if (MagicBuffer("$zip_file") =~ /Zip archive data/) {
                print "$offset\n";
                open F, ">file_$offset.zip" or die $!;
                print F $zip_file;
                close F;
                exit;
        }
}

The script found that the key was 9679 and wrote the decrypted zip file to disk. The zip file contained a text file that contained the second part of the passphrase needed to decrypt "epilogue-crypt.txt" - "-Y2j_Q4EQdtJ".

Challenge 3

You are given the following message:

e4 e5 f4 exf4 Bc4 Qh4+ Kf1 b5 Bxb5 Nf6 Nf3 Qh6 d3 Nh5 Nh4 Qg5 Nf5 c6 g4 Nf6 Rg1 cxb5 h4 Qg6 h5 Qg5 Qf3 Ng8 Bxf4 Qf6 Nc3 Bc5 Nd5 Qxb2 Bd6 Qxa1+ Ke2 Bxg1 e5 Na6 Nxg7+ Kd8

You are told that if you can discover how it ends and the result then you will be able to decrypt a zip file in the same directory.

Searching for the message in Google yields many search results relating to chess. It appears that the message is written using chess notation and the aim is to find the moves that will complete the game.

r1bk2nr/p2p1pNp/n2B4/1p1NP2P/6P1/3P1Q2/P1P1K3/q5b1 w - - 1 22

I found a chess board editor online and entered the chess moves. I played out the game and the remaining moves are Qf6+ Nxf6 Be7. White sacrifices his Queen, but wins by using his remaining knights and bishop to put black in checkmate. This series of moves is known as the immortal game and appears in the film Blade Runner.



We can now answer the two questions. How does it end? "Be7". What was the result? "checkmate". Therefore, the password to decrypt the zip file is "Be7checkmate". The decrypted zip file contains a text file with the next part of the passphrase - "De3qUNa_AU-F".

Challenge 4

You are given a Linux command line program, findthepassword32, and told that it has a very simple purpose. It takes one argument, and returns one of two messages. If the argument entered is the password to decrypt the salvaged-file.zip file it will return "Well done, you have the password :)" and if the argument entered is not the password then the message returned is "Boo! Try again...". Your task is to reverse engineer the program to find out what the password is.

Using the free version of IDA I was able disassemble the executable. I won't go into how I specifically reverse engineered the program. Instead I'll explain at a very high level how it works and leave it to the reader to compare my explanation to the disassembled code.

Rather than compare contiguous bytes of the entered password to the actual stored password (i.e. 0, 1, 2, 3...) the program compares bytes of the entered password to the actual stored password in a random order. In this case the bytes are compared in the following order:

0,12,1,8,15,2,3,4,13,5,11,6,7,9,10,14

The bytes at these locations are:

0x4d, 0x4d, 0x61, 0x61, 0x61, 0x79, 0x62, 0x65, 0x65, 0x20, 0x20, 0x42, 0x6C, 0x63, 0x6B, 0x73


Taking these bytes as ASCII representations of characters they become:


M, M, a, a, a, y, b, e, e, ' ', ' ', B, l, c, k, s


Where ' ' is a literal space. Rearranging the characters so that they are sequential gives:

Maybe Black Mesa

Running the program with this argument gives the expected success message, so we have the password to decrypt the zip file now.

The decrypted zip file contains a text file with the next part of the passphrase - "Tao_JE-Y7F6w".

Challenge 5 - part 1

You are given three files. The first is an encrypted zip file, encrypted.zip. The second is an encoded note, hidden-ink-message.txt.

The third file is a book written in a strange language, unknown-book.txt. You are told that it is impossible to decode, but seems that the language uses a western alphabet and that numbers seem in the normal order. Anyone with a basic knowledge of cryptography will notice the repeated string "Oqvesai" and realise that the algorithm used to encode the book is likely a substitution cipher.

We know that this is a book, so the repeated string, "Oqvesai", at the beginning is likely to be the word "Chapter". Therefore, o=c, q=h, v=a, etc. Using substitution cipher cracker I was able derive the substitution alphabet and decode the book, which was The Hound of the Baskervilles.


Once the book has been decoded we shift our attention to the encoded note. The note contains groupings of numbers in the form:

[9,208,3,1]

I guessed that the book would play a part in decoding the note and thought about how the numbers could relate to that. It didn't take long to realise what the numbers meant:

[chapter number, line number, word number, character number]

I attempted to decode the note using this method and my output looked a lot like English. However, it would take a very long time to decode the note manually so I wrote the following Perl script to decode it:


#!/usr/bin/perl

open F, "encoded.txt" or die $!;
my @encrypted_text = <F>;
close F;

my $encrypted_line;

foreach $encrypted_line (@encrypted_text) {
        if(@codes = ($encrypted_line =~ /\[(\d+,\d+,\d+,\d+)\]|(.)/g)) {
                my $char;
                foreach $code (@codes) {
                        if($code =~ m/\d+,\d+,\d+,\d+/) {
                                my @parts = split(/,/, $code);
                                #print "Opening chapter @parts[0]...\n";
                                open F, "@parts[0].txt" or die $!;
                                my(@lines) = <F>;
                                close F;
                                #print "Reading line @parts[1]...\n";
                                my $line_num = @parts[1] - 1;
                                my $line = @lines[$line_num];
                                #print "Reading word @parts[2]...\n";
                                my @words = split(/ /, $line);
                                my $word_num = @parts[2] - 1;
                                my $word = @words[$word_num];
                                #print "Reading letter @parts[3]...\n";
                                $word =~ tr/[\-"']//d;
                                my @letters = split(//, $word);
                                my $letter_num = @parts[3] - 1;
                                my $letter = @letters[$letter_num];
                                print "$letter";
                        } else {
                                print "$code";
                        }
                }
        }
        print "\n";
}

The book needs to be divided into chapter files called 1.txt, 2.txt, etc., all blank lines deleted, the chapter heading (not the chapter title removed), and the encoded note stored in encoded.txt for the script to work. The script isn't perfect, but is sufficient to decode the note and learn the password to decrypt the zip file.


Note that the site referenced to perform the substitution cipher converts everything to upper case. The password is case sensitive, so I had to try every combination of upper and lower case to find the correct password. Thankfully, the password contained all lower case character, so I got it first time.

The final password to decrypt the zip file is "sqcrfrtavsthzbtfghcpemkz".

Challenge 5 - part 2

The zip file contains two public RSA keys and an encrypted message. Somehow we need to derive the private key to decrypt the message from the two provided public keys.

RSA (at a very high level) works by taking two very large prime numbers, to produce the private key, and multiplying them together, to produce the public key. The strength of this lies in the fact that it is very hard to derive the two large prime numbers from their very large product. However, if two private keys share a prime number then it is trivial to derive the other primes that make up the private key and thus derive the private keys themselves. Research has found that the number of shared prime numbers to create public keys online is worryingly common, so it is likely that the two public keys share a prime number to allow us to derive their private counterparts.

I failed to keep a record of my exact steps to calculate the shared prime numbers and generate the private key to decrypt the message, but I did find the Sage Virtual Machine very useful in calculating the greatest common denominator (i.e. the shared prime number) between the two public keys. I also found this RSA-cracking puzzle incredibly useful in helping to understand the problem. There is also a service to generate a private key based on two prime numbers.

When the message is decrypted the final part of the passphrase is revealed to be "-6LcwSz_E3FB".

Epilogue

The final part of the challenge was to decrypt the file epilogue-crypt.txt. With all the parts of the passphrase this was trivially done with the following command line:

openssl enc -d -des-ede3-cfb8 -in epilogue-crypt.txt -out text.txt -a -k WNzr7BaH-y7_-Y2j_Q4EQdtJDe3qUNa_AU-FTao_JE-Y7F6w-6LcwSz_E3FB