Review of Hash Runner Tasks

Intro

This year, Hashrunner had been taking place during three days before Positive Hack Days — from May, 16 19:00 (UTC+4, Moscow) till May, 19 19:00 (UTC+4, Moscow). Among other matters, we were trying to respect the interests of all geographically dispersed teams and cover 48 hours of two weekend days for every time zone. We received great positive feedback about including the whole weekend and thus we’ll try to keep it this way.

Congratulations to the winners!

1. InsidePro with 22.81% (write-up) won two R290x video cards plus souvenirs.
2. hashcat with 21.23% (write-up) won an R290x video card plus souvenirs.
3. john-users with 12.78% (write-up) won souvenirs.

Within three years of the contest, we had three unique winners: hashcat in 2012, john-users in 2013, and InsidePro in 2014. Every year, most submissions were received in the last 15 minutes and thus the winner was determined in the very nick of time. In 2012 and 2013, InsidePro was beaten into the second place by hashcat and john-users, respectively. This year, InsidePro finally became the first.

Hash Types and Pricing
Hash prices included weights assigned according to our own practical needs. It was our final decision, but we had considered two other ideas — with one hash giving one point and with prices calculated both from the plaintext entropy and the average cracking time (obtained on our standard hardware) for the certain hash type. The latter variant proved to be unsuitable for the competition, because only the slowest hashes would have mattered.

* coefficient for hashes in bonus packs

Contest Mechanics
First of all, we split the entire contest into separate tasks that reflected different systems and approaches, not only hash types. It was quite like Hash Runner 2013, but without tasks being tied to wordlists, the theme of which could be guessed from hints or restored plaintexts.

One of new features of Hash Runner 2014 was how contestants received their hashes. In previous years, it had been a plaintext file. This year, we had a special laboratory running real-life systems. To grab hashes, contestants followed the instructions and used exploits like in pentests. These tasks were completely described without any space left for guessing, except the hash cracking itself. You could see PCAP files, Lotus Domino installation, numerous web applications, SCADA project files, etc. It had no impact on scoring, but was just for pentest look & feel — and to be honest, became the hardest part for us to implement.

Furthermore, typical assessment doesn’t require all these unprivileged users; you need only the most privileged one. We added twenty-three admin hashes for each task that had the largest entropy of task plaintexts (twenty-three is just a number not anyhow related to the result of 966/42). If a participant managed to crack any admin hash, he/she was awarded with 250 bonus hashes not available in the original task. The bonus hashes types were: Raw-SHA-1, GOST, bcrypt, and Raw-MD5.

Accidents & Emergencies
As seen on the news:

Results uploading was buggy if the plaintext contained ":". Not that we hadn't expected this :) 

Some piece of information: due to some our mistakes made with hash dumping for the task #3 (md4 mt_rand), data from user.db.php and hashrunner_2014_hashes.zip did not match. The latter file was correct and hashes from it would have been accepted. The task became two times easier now. We couldn’t disclose the exact information, because one team had found it on their own. Other teams were invited to find and use this glitch to upload hashes for this task. 

Awful silent patches:

1. Cisco hashes had been generated twice by accident and thus were different because of the salt in algorithms.
2. We had wrong scores in the database for one of the bonus hashes (1 instead of 15). Fortunately, it was found during day one, when almost nobody had succeeded with these bonus hashes.
3. Some minor differences between the file with all hashes and the actual systems.

Wordlists and Mutations
Wordlists used came from real life experience with a pinch of broken fantasy:
random 6 and 8 chars, acronyms, Arabic mapped to Latin, Arabic forum (crawled), Arabic names, Canada towns, chemicals, Chinese names and surnames, Go game terms, Greek mythology, Hollywood stars, Italian cities, legendary creatures, Marvel characters, mental disorders, MMORPG sites, neurological disorders, tomato translations, web application banners and random samples from packetstorm wordlists and xato 10k wordlist.

Mutations used were those generally found during consulting mixed with uncommon cases:

• Leet everything, leet only specific alpha, leet random.
• Simple ones: <word><year>, <word><digit1><digit2><digit3>, <word><spec><year>, <word><date>, <word><date><month>.
• Permutations with case in <word> like <WoRD> and <wORD>. These mutations were mostly used in wordlists like mental disorders and legendary creatures.
• Ultra evil <word1><WORD2>, <word1><word2><word3>.
• Adding special symbols: <special1><word><special2>, <word><special1><special2<special3><special4>.
• Arabic mapped to Latin also should be considered as a mutation. A simple Arabic wordlist was mapped to the corresponding Latin keyboard chars. Like “password” in Russian (“пароль”) typed in English layout gives “gfhjkm”.

All these mixed up and mutated wordlists were randomly distributed among the tasks. The number of final plaintexts exceeded 40 thousands. Hopefully, we avoided attacks with themed patterns through using only small random parts of this set.

Review of Some Tasks

TIA Portal
The simplest task in the contest. SCADA engineering solution that had raw SHA-1 hashes with known plaintext length. That’s it. By modifying the provided script to extract the length as shown on picture, you got massive boost in cracking.

Lotus H-hash
Apart from two known hash types, lotus5 and dominosec (g-hash), newer hashes for versions >8 were generated. While the former two types were among the most popular for cracking, the latter one wasn’t touched at all. Good thing we haven’t seen them in wild life yet.

Arabic forum
This forum was all about the targeted attack. One can't simply bruteforce an iterated MD5 hash if he/she doesn't know anything about the plaintext. Yes, there were “simple” hashes consisting of less than five English letters, but they were created with mapping from the Arabic keyboard to the English one. Most (if not all) dictionaries become useless if they are used against national alphabets. The only way is to create one yourself, for example, by parsing dictionaries or targeted sites. Thus, a forum is a great place to start. It contains vast amount of words that people actually use, and crawling such resource can give essential information about possible plaintexts. But sometimes crawling is not enough, you should also think about common things used in uncommon ways. There are at least four types of Unicode symbols only for encoding numbers, and one of our mutation masks was just appending two Unicode Arabic numbers to the plaintext. Actually, there were three mutations used:

1. Prefixing with three non-Unicode Arabic numbers.
2. Suffixing with two Unicode Arabic numbers.
3. Keyboard mapping to Latin letters.

mtrand()
The idea of this task was all about bad “random” numbers, which are used by not-so-experienced developers. Let us imagine that we have a forum/blog/any other website. All we want is a secure mean to create tokens that we will use to reset user passwords. One can use a linear congruential generator, but this task was about the Mersenne twister pseudorandom generator, which is really nice on paper with period of 219937 and seed of 32 bits. The seed is a problem for security — if we know the seed, we can reproduce the full stream of pseudorandom numbers. But this issue is implicitly mitigated by the common implementation: once the generator is seeded, its state will start to produce pseudorandom numbers different from those created by another seed. Now an attacker should implement the full Mersenne twister algorithm and bruteforce not only the seed (which is relatively small), but also the place of the target pseudo random number in the generated stream.

This approach should be enough for both h-type and l-type hashes, but we created two types on purpose. A developer can shoot himself in the leg not only by using a cryptographically unsecure random number generator, but also by using the generated stream badly. When you use integers or float type in your programming language, you should remember about the maximum precision for each type and the text representation of numbers. Here is an example. It should seem that if the product of three numbers 123456789 * 123456789 * 123456789 gives 1881676371789154860897069 in general decimal arithmetic, then you will get ~79 bits of entropy with its character representation. However, if your programming language uses floating numbers to handle such big numbers, then the result will be somewhat like 1.8816763717892E+24, which has only ~45 bits of entropy and can be easily bruteforced for any fast algorithm.

This task was haunted by bad luck. First of all, hashes in the web database were hashed only with one iteration of MD4, and the original code of generating h-hashes was a bit different from the code on the web.

Generate light plaintexts

function generate_password($length)
{
    $result = 1;
    for($i=0; $i<$length; ++$i) $result *= mt_rand();
    return $result;
}

for ($i=0; $i<$argv[1]; ++$i)
{
    if (($i % 32) == 0){
        mt_srand(get_real_rand());
        $skip = get_real_rand() & 0xFFFF + 8192; // Fix for easy attack
        for ($j=0; $j<$skip; ++$j)
            mt_rand();
    }
    echo generate_password(3)."\n";
    $skip = get_real_rand() & 0xFF; // Fix for easy attack
    for ($j=0; $j<$skip; ++$j)
        mt_rand();
}

Generate hard plaintexts

function generate_password($length)
{
    $result = 1;
    for($i=0; $i<$length; ++$i) $result .= mt_rand();
    return $result;
}

for ($i=0; $i<$argv[1]; ++$i)
{
    if (($i % 32) == 0){
        mt_srand(get_real_rand());
        $skip = get_real_rand() & 0xFFFF + 128; // Fix for easy attack
        for ($j=0; $j<$skip; ++$j)
            mt_rand();
    }
    echo generate_password(3)."\n";
    $skip = get_real_rand() & 0xFF; // Fix for easy attack
    for ($j=0; $j<$skip; ++$j)
        mt_rand();
}
As you can see, there is concatenation with a non-empty string containing number 1, so the numbers generated this way were actually unbrutable, even if someone would have managed to recreate MT rand generation or use the Solar Designer's code (http://www.openwall.com/php_mt_seed/).

Tomato
Ντομάτα, домат, Парадајз, Помідор, томат, улаанлооль, Լոլիկ, პომიდორი, टमाटर, टोमॅटो, हिण्डीरः, ਟਮਾਟਰ, ಟೊಮೇಟೊ, தக்காளி, තක්කාලි, 番茄, 蕃茄, …
No comments.

Wonderful
We received many questions about this task and methods we suggest to solve it. Actually, we don't know. This task (and mt_rand with Arabic) was developed to draw attention to some weaknesses of the current bruteforce utilities. During our work, we managed to find different old/unpopular applications. Many of them use just plain MD5, but some can use very weird schemes like SHA1(base64(MD5(base64(SFA1())))). SHA1 is widely used, base64 is cheap, but there is no obvious way to handle such hash. The idea to create a self-servicing module for such task is not feasible, but the idea to get a tool combining different bruteforce modules in arbitrary manner could be good. And don't forget to optimize HMAC with 1 MB file, as it will be just hashed to a small constant value :)

Statistics
Some nice graphics based on submissions during the contest. Hope you will find them interesting, and we are sorry if we disclose more information about the top-3 teams’ strategy than they wish to.

Graph by points

 Graph by the number of hashes

 Cumulative progress of all teams by the percentage of bruted hashes

Cumulative progress of all teams by the percentage of bruted hashes of different types

Part 1

Part 2 (pay attention to the maximum value here)

Progress of InsidePro by hash type

  Progress of hashcat by hash type

 Progress of john-users by hash type

Epilogue
It all started with beer in a Hamburg cafe during 30C3 and not everything came up as expected ;)

Full size