Brute force attacks from A to Z – part II (last)

Passwords are a regrettable nuisance. Perhaps even one of the most dreaded inconveniences of computer security. This last part will contain some very basic examples that will demonstrate brute force attacks on passwords. The beauty of a brute force attack is its simplicity by nature: test all combinations. Of course there are some clever tricks to speed up the search or, to be more accurate; increase the likelihood of finding the password.

Before I go any further I would like to make one thing very clear: I don’t want to give attackers a blueprint on how to stage a brute force attack. As a consequence this article will be limited to basics only. But do note that there are some very compelling reasons to further investigate on how to effectively perform brute force attacks. On the other hand: I’m pretty confident that true attackers won’t use anything from these pages, as there are plenty tools available that work a lot better than trying to do this yourself. So what you’ll find here is simply my personal search into the programming-logic behind brute force attacks.

This interest started somewhere in 2004 when I tried to write an anagram-solver, which soon became a password brute force tool. You can find that original still here. I rewrote that in C for better performance. As it turns out, anagrams and password brute forcing do not differ that much. With anagrams you shouldn’t reuse characters and therefor have less combinations to test.

When figuring out on how to find a password I originally started out with nested for loops, one for each character of the password as shown in the Perl-snippet below. This doesn’t work well when you try to find a password of arbitrary length. You would need to adjust the program for each different password length, or have a recursive algorithm. The problem with recursion – although I find them often quite beautiful to read – is that it is general heavy on system resources.

foreach $a (@allchars) {
  foreach $b (@allchars) {
    foreach $c (@allchars) {
      foreach (@allchars) {
        print ++$tot . ": " . $a . $b . $c . $_ . "\n";
      }
    }
  }
}

The following is a “linear” search, which simply starts at attempt number 0 and ends at (number of characters)^(length of password). More about that later. The difficult part was to calculate the index ($e) of the string containing all possible characters to form the password. Picking an index from a string is not so very different from picking a word from a dictionary as you’ll see further on.

$nrofchars = length($allchars);
$I = $passwdlength - 1;
$K = $nrofchars ** $passwdlength;
for($j=0; $j<$K; ++$j) {
    print("$j : ");
    for($f=$I; $f>=0; --$f) {
        $e = int($j/($nrofchars**$f)) % $nrofchars;
        $c = substr($allchars, $e, 1);
        print("$c");
    }
    print("\n");
}

When looking for every combination in a dictionary, you would very likely start with something like the Perl code below. The while(<>) allows input from STDIN, so you can use something like ‘cat /usr/share/dict/words | ./this-script.pl’.

#!/usr/bin/env perl
use warnings;
use strict;

my(@DICT);

while(<>) {
  chomp();
  $DICT[++$#DICT] = $_;
}

my($a,$b,$c);
my($tot) = 0;
foreach $a (@DICT) {
  foreach $b (@DICT) {
    foreach $c (@DICT) {
      foreach (@DICT) {
        print ++$tot . ": " . $a . $b . $c . $_ . "\n";
      }
    }
  }
}

Now let’s put a and b together! The code below still is clumsy, but you can see where this is going.

#!/usr/bin/env perl
use warnings;
use strict;

my(@abc) = ();
my($z,$y) = 0;
my($a,$b,$c) = '';
my($test) = "";
my($pwlen) = 3;

while(<>) {
       chomp();
       $abc[++$#abc] = $_;
}

my($t) = ($#abc)+1;
my($i) = $t**$pwlen;

for ($z=0; $z<$i; ++$z) {
       $test = "";
       for ($y=($pwlen-1); $y>=0; --$y) {
               $c = ($z/($t**$y))%$t;
               $a = $abc[$c];
               $test .= $a;
       }
       print $test . "\n";
}

Epilogue

First of all and as mentioned earlier, this article will stick to basics only as this blog will remain “mostly harmless”. It would not take a lot of effort to fix the clumsy code and get rid of the $pwlen = 3 and to add something like Net::HTTP or LWP::UserAgent, which would allow the script to be used “in real life” to do some HTTP brute forcing. You could also add MD5 or SHA hashing of the resulting strings which could be used to build a database.

Second: Searching over the entire set of combinations is best cut up into blocks across multiple machines instead of starting at 0 and ending at somewhere near infinity. Additionally you would need to write a Command and Control script that handles multiple machines, but… that will not be addressed here. There are quite some more enhancements to this, like common replaced characters, such as i with 1 or o with 0 etc. When looking back at the code: Linear searching is perhaps suboptimal for the purpose of brute forcing, and some minor adjustments there are likely to improve results.

Last: So how do you prevent an attacker from stealing your password? I’d recommend the following:

1. Use a long password, or a passphrase if possible. No matter if they contain true words or random characters. Here, size does count! Longer is better.
2. Change your password/phrase with some frequency over a secure channel. This is perhaps even the most difficult.

These two simple measures will make it next to impossible for an attacker to launch a successful brute force attack. Having said that; A determined attacker will probably not depend on a brute force attack to figure out your password.

PS. If you feel like doing some benchmarks with the last piece of code from this article on the raw computing power of your computer, type:

time cat /usr/share/dict/words | ./bf.pl >/dev/null 2>&1
This entry was posted in IT Security and tagged . Bookmark the permalink.