Dustin set the third challenge Tuesday just gone. This was the last in the series, which i can honestly say, i’ve really enjoyed working on.

I was asked how I solved Challenge 2, i did it largely the same way as the example given when the winner was announced, with some variation of the script. So there didn’t seem much point.

This challenge I decided i would document how I did it.

Challenge 3:

So what do we know?

• An encrypted “mount passphrase” inside 128-bits of random data, symmetrically encrypted using a wrapping passphrase and the standard eCryptfs salt
• The MD5 hash as a shadow of the wrapping passphrase
• The “challenge_3.txt“, which is the underlying data ecrypted using eCryptfs – basically the encrypted form of data that would otherwise be in your ~/Private directory.

Clearly the mount passphrase is the strongest link, as shown in challenge 2. As Dustin pointed out cracking 4 digits for the wrapping passphrase will take an estimated 40 days (based on 4.3 attempts a second), using multiple threads, on many servers with lots of cores will significantly decrease this – however, it’s still a long time for this challenge.

We also know the md5 hash of the wrapping passphrase, there has been recent publicity about md5 being insecure for passwords – however, there are various other aspects. This will be our vector for attack.

The MD5 Hash is quicker to brute force than the unwrapping of the passphrase, as documented in the solution challenge 2.

So how do we do it? The initial obvious method is to brute force, every range within the known constraints. These are, that the passphrase is 4 character alpha numeric string (a-z A-Z 0-9).

So, lets look at this script based on Dustin’s previous challenge:

#!/bin/bash
# crackmd5.sh
 
MD5HASH="74b87337454200d4d33f80c4663dc5e5"
 
CHARS="a b c d e f g h i \
j k l m n o p q r s t u v \
w x y z A B C D E F G H I \
J K L M N O P Q R S T U V \
W X Y Z 0 1 2 3 4 5 6 7 8 9"
for i in $CHARS; do
     for j in $CHARS; do
        for k in $CHARS; do
           for l in $CHARS; do
                  md5=$( echo -n "$i$j$k$l" | md5sum |  awk '{print $1}' )
                   if [ $md5 = $MD5HASH ]; then
                         echo "Cracked: $i$j$k$l"
                          exit 0
                   fi
done  ;    done  ;   done  ;   done

This will find the result by brute force, it’s SLOW. mainly because it’s a single process on one server, using one core.

The next method to attack this would be using MD5 rainbow tables, now not many people have these – but if you do *GREAT*. They are basically a table, making cracking of MD5’s really fast and efficient. To have all combinations “laying” around could easily consume a few terrabytes. So this isn’t really practical.

The next method is to ask your friend, that knows everything and will know the answer. For the benefit of this exercise we will call this friend “Google”. So inserting the md5 hash from the shadow file into Google, we get the answer.

Okay, so we have effectively recovered the wrapping passphrase, and so we can now unlock it. I’ll miss that step out as Dustin covered that in the solution for Challenge 2.

The plain text challenge_2.txt contained (amongst other things):

Start with the sha512sum of the following seed:
$ echo “Daemon” | sha512sum
Write the computed sum to the first line of a new file.
sha512sum that new file.
Write the resulting sum to the second line of the new file.
sha512sum that new file.
Write the resulting sum to the third line of the new file.
…
Continue doing this until you have exactly 1,000,000 lines in the file.

Hmm.. this sounds tricky. Let’s try doing this as described.. the /logical/ way. Generate the sha512sum of “Daemon” and output that to a file, then append the sha512sum generated of that file to the bottom of the file, repeat until file has 1000000 lines.

#!/bin/bash
# sha512brute.sh
echo "Daemon" | sha512sum |  awk '{print $1}'   > test.log
for ((i=2;i<=1000000;i+=1)); do
sha512sum test.log |  awk '{print $1}' >>  test.log
done

The above will work, but running on one server could easily take 70 hours – as the whole sha512sum is being calculated from scratch, even though only the last line of the text file is being changed. If only you could cache the calculation round so far, and append to the end. Well you can!

I hadn’t used Perl in anger recently, and decided to use it to solve this aspect. So i knocked up a script to do just this. Surprisingly,it was pretty trival in perl. With this new number, find out “Who own’s this number?”.

#!/usr/bin/perl
# Run as:
# ./genSHA512.pl > sha512sums.txt
 
use Digest::SHA; # qw( sha512 sha512_hex );
 
$keyword = "Daemon";
$sha = Digest::SHA->new(512);
 
$sha->add($keyword,"\n");
$digest = $sha->hexdigest;
print $digest . "\n" ;
 
for ($i = 2; $count <= 1000000; $i++) {
        $sha->add($digest,"\n");
        $digest = $sha->clone->hexdigest;
        print $digest . "\n" ;
}

This will generate the 1000000 line sha512sum file in around 15-20 seconds on an average!

Now lets extract the lines asked in the next phase of the challenge, convert them from hex to decimal, and subtract the difference.

#!/bin/sh
# ./sha512_process.sh
#
# Use the txt generated from genSHA512.pl
SHA512SUMS=sha512sums.txt
 
LastHex=$(tail -n1 $SHA512SUMS | sed -e 's/^.*\(......\)$/\1/'  )
LastDec=$( printf "%d\n" "0x"$LastHex )
echo  "Last 6 digits of the 1,000,000th line: " $LastHex " (Decmimal: ${LastDec})"
 
FirstHex=$( sed '961325q;d' $SHA512SUMS | sed 's/\([0-9]\{6\}\).*/\1/g' )
FirstDec=$( printf "%d\n" "0x"$FirstHex )
 
echo "First six digits of line 961,325: " $FirstHex " (Decmimal: ${FirstDec})"
 
diff=$(( $LastDec - $FirstDec ))
echo "      Difference = " $diff
echo "            Who's number is this?"
echo "                  * HINT: http://letmegooglethatforyou.com/?q=$diff&l=1  *"

So lets run them!

daviey@katana:~$ time ./genSHA512.pl > sha512sums.txt

real 0m15.567s
user 0m15.090s
sys 0m0.480s

daviey@katana:~$ ./sha512_process.sh

Last 6 digits of the 1,000,000th line: da7080 (Decmimal: 14315648)
First six digits of line 961,325: 561093 (Decmimal: 5640339)
Difference = 8675309
Who’s number is this?
* HINT: http://letmegooglethatforyou.com/?q=8675309&l=1 *

As we can see, this is very efficient (probably could be more so without saving to disk, but it’s certainly enough!), solving this part of the challenge in under 20 seconds!

So, what can we learn from this? If you plan to do something like this, don’t jump in too quickly, spend a good amount of time thinking through a good solution! Using a thought out solution, this challenge could be cracked in under 5 minutes!

I would like to say a big thank you to Dustin for setting this challenge, it is my understanding that he spent a great deal of time setting these tasks! I do hope he sets some more, and more people take part.

January 23rd, 2009 | All, Blogroll, hantslug, lugradio, ubuntu, ubuntu-uk | 1 comment

Lenovo X61
Just came across an old screen-shot I took some time ago, showing how much longer the battery will last for. I should mention that i have never managed to squeeze that long out of it!

January 22nd, 2009 | All, Blogroll, hantslug, lugradio, ubuntu, ubuntu-uk | 1 comment