Brute force password cracker

Question

I wrote this script for a proof of concept JavaScript password cracker:

var charset = " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~";
function crack(value){
    function toRadix(N,radix) {
        var HexN = "", 
            Q = Math.floor(Math.abs(N)), 
            R,
            strv = charset,
            radix = strv.length;
        while (true) {
            R = Q % radix;
            HexN = strv.charAt(R) + HexN;
            Q = (Q - R) / radix; 
            if (Q == 0) 
                break;
        };
        return ((N < 0) ? "-" + HexN : HexN);
    };
    var start = (new Date()) * 1,
        cracked = false,
        index = 0;
    while(!cracked){
        if(toRadix(index) == value)
            cracked = true;
        else
            index++;
    };
    alert(((new Date()) * 1) - start);
};

This script works fine, but it is slow.

What would be the best way to speed up this algorithm?

Answer 1

Expectation Setting

Your algorithm is an incrementing index, which you then convert in to the radix of your charset.

Your charset is what, 95 characters?

So, there are the following possible permutations for passwords:

1 char -> 95
2 char -> 9025
3 char -> 857375
4 char -> 81450625
5 char -> 7737809375
6 char -> 735091890625
7 char -> 69833729609375
8 char -> 6634204312890625

OK, so, let's assume the person chooses an 8 char password you need to crack, and that it starts about half-way through your alphabet with a 'K'.

That means you will have to calculate about... 3,000,000,000,000,000 passwords before you get to the right one....

Now, let's assume your browser is super fast (like in the scale of a super-computer), and can compute 1 billion passwords each second....

It will need 3,000,000 seconds to get to the right one.... which is.... about 5 weeks (not 2.5 years as originally stated).

Now, your browser, if it is on an amazing PC, will be 1000 times slower.... so, the right way to crack this password this millennium, is to actually wait about 20 years, and then crack it then when computers are a few hundred times faster ;-)

Note, I would not expect even the fastest PC to be able to get to 5char passwords using a single-threaded execution model, in the most optimal way, to check more than 1,000,000 passwords a second, which makes 5 char passwords more than 2 minutes away....

This is one of the joys about brute-force tactics, by the way, is that, in general, the fastest way to crack a brute-force password of reasonable length, is to do nothing.... and wait for technology to get faster... and then start later, and finish sooner.

Alternate algorithm

Using recursion would be a natural way to solve the general problem of checking all solutions, but it has the problem that it checks all solutions in the wrong order (typically it solves the longest passwords first.... which would be counter-intuitive to check a bunch of 8-char passwords before you check all 7 char passwords.

So, you are left with just making the current system faster... and, that's a somewhat fruitless problem, because even halving the time would not be meaningful in most cases.

This leads on to multi-threading, which is the fastest way to accelerate the problem, but I am not sure this is available on your browser.

Answer 2

I see a minor speed-up already.

while (true) {
    R = Q % radix;
    HexN = strv.charAt(R) + HexN;
    Q = (Q - R) / radix; 
    if (Q == 0) 
        break;
};

When you have a while(true){blah blah if(condition) break;}, you really have this:

do {
   blah blah
} while (!condition);

And that's what I'd suggest to you too.

do {
    R = Q % radix;
    HexN = strv.charAt(R) + HexN;
    Q = (Q - R) / radix; 
} while (Q != 0);

You can apply the same idea here:

    var start = (new Date()) * 1,
        cracked = false,
        index = 0;
    while(!cracked){
        if(toRadix(index) == value)
            cracked = true;
        else
            index++;
    };

to

    var start = (new Date()) * 1,
        cracked = false,
        index = -1;
    do {
        index++;
    } while(toRadix(index) != value);

And remove the whole cracked variable.

    var start = (new Date()) * 1,
        index = -1;
    do {
        index++;
    } while(toRadix(index) != value);

---

For the bigger performance gains it might be better to look for algorithmic optimization, rather than optimization of the implementation.

Answer 3

Unfortunately most of my points are about redundancy rather than cool speed tips, but removing clutter generally helps improve speed anyway (not massively, but enough). If you want to skip straight to the 'cool' tip, it's the Finally paragraph(s).

Firstly: your toRadix function is defined as taking two arguments, N and radix, which I believe is a mistake (I might be wrong, I don't usually use Javascript).

Secondly: Math.abs and Math.floor appear to be redundant since the index you're passing starts at 0 and adds 1 each time, meaning the value is never negative and always an integer. (That should speed things up and remove some clutter)

Thirdly: strv appears to just be an alias for charset and as you never appear to modify strv you could just be operating charset directly.

Fourth: Do what @pimgd said about using do loops rather than while loops. In normal languages it wouldn't make a massive difference, but Javascript is a scripting language without a proper optimiser so it helps to use the proper constructs.

Finally: This is the potential cool speed up tip. Instead of keep appending to HexN every turn of the loop, save the values you would be appending to an array and then concatenate them at the end. This is better in two ways: it saves memory and it reduces the amount of processing that must be done.

Every time the loop runs the line HexN = strv.charAt(R) + HexN; you are actually creating a new string (the result of the + operation) and destroying an old one (HexN). This is happening many times per second, which means a large amount of string allocation and destruction is taking place. By just adding strv.charAt(R) (or better yet, charset.charAt(R) as mentioned earlier) to an array and then doing the concatenation at the end, you are only doing the string creation and destruction once per call to toRadix. Aside from the obvious not having to do so many memory accesses, certain browsers actually specifically optimise string concatenation as mentioned here.

Answer 4

Following from @Pimgd's suggestion about algorithmic optimizations, if you're finding an algorithm is too slow, finding a better one is usually the way to increasing the speed the most.

Dictionary attacks are much faster than iterating, although they require much more space for the speed that you gain. If you're looking to take into account the fact that passwords should be hashed, a rainbow table attack is something else to look into.

Answer 5

Do I get it right that the intention of your code is to brute force guess the contents of a known string value? As noted by @Pharap your approach seems quite complicated and a simpler version would indeed be faster.

I took the liberty of writing an alternative, which was able to match an input value of 4096 characters in just over a second.

var charset = " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~";
function crack(knownPassword) {

    var start = (new Date()).getTime(),
        guess = '',
        c;

    while(guess !== knownPassword) {
        for(var i = 0; i < charset.length; i++) {
            c = charset.charAt(i);
            if (c === knownPassword.charAt(guess.length)) {
                guess += c;
                console.log(guess);
                break;
            }
        }

    }

    console.log('mycrack', ((new Date()) * 1) - start, 'ms');
};

It's still not very useful though, as it requires one to know the string you're about to guess.