Brute force password cracker

Question 1

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?

Question 2

Can you have a double quote in a string like that? It turns out that you cannot. You must escape any double quotes by prepending them with `, like \"`.

Question 3

Keep in mind that on Code Review, we require code to be working code. Questions that contain broken or otherwise not-working code will get closed and tend to take a hit to their popularity. For that reason, you should test your code before submitting it for review. That way both you and us benefit; you know your code is correct, and we can spend more time on the review, rather than debating whether the code is or is not broken.

Question 4

To learn about password cracking, get a copy of John the Ripper (JTR). JTR is a high-quality cracker with intelligent strategies: dictionary, brute force, and combinations. You can get source and binaries. Also plenty of JTR tutorials on Youtube. Not recommending you use this for anything illegal / immoral of course. They are notorious for CPU usage, so JavaScript is not your friend. Digging into the speedup methods used by JTR would far exceed the normal scope of an answer here, esp. given that it is not so much as a code review as an entirely new strategy.

Question 5

@GaryWalker Since your answer didn't say anything specific about either the algorithm or code in the question, I have converted it into a comment.

Question 6

Is JTR still blacklisted(9/11)? Where?

Question 7

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.

Question 8

But for 4 chars or less it should work perfectly fine, right?

Question 9

There are web workers in chrome.

Question 10

I can do multi-threading through web workers. What method would you suggest for multi-threading? I tried using two threads (one using even index values and one testing odd index values) and is took longer than just one thread!

Question 11

@Progo - I would not use a browser ;-) But, C would be the language of choice, and that's not a commonly supported language. Other answers have covered how you could improve it. I do recommend using more than just odd/even splits, but more along the lines of doing odd and even millions in each thread.

Question 12

3 million seconds is 5 weeks, not 2½ years

Question 13

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.

Question 14

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.

Question 15

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.

Question 16

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.

rolfl rolfl 98.1k17 gold badges219 silver badges419 bronze badges · Answer 1 · 2014-10-27 13:43:54Z

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.

But for 4 chars or less it should work perfectly fine, right?
I can do multi-threading through web workers. What method would you suggest for multi-threading? I tried using two threads (one using even index values and one testing odd index values) and is took longer than just one thread!
@Progo - I would not use a browser ;-) But, C would be the language of choice, and that's not a commonly supported language. Other answers have covered how you could improve it. I do recommend using more than just odd/even splits, but more along the lines of doing odd and even millions in each thread.

Pimgd Pimgd 22.5k5 gold badges68 silver badges144 bronze badges · Answer 2 · 2014-10-27 13:26:12Z

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.

Pharap Pharap 8025 silver badges16 bronze badges · Answer 3 · 2014-10-28 09:19:17Z

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.

Yann Yann 2,2361 gold badge17 silver badges36 bronze badges · Answer 4 · 2014-10-27 13:38:54Z

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.

Wouter van Vliet Wouter van Vliet 1211 bronze badge · Answer 5 · 2016-05-24 16:54:29Z

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.

Stack Exchange Network

Brute force password cracker

5 Answers 5

Expectation Setting

Alternate algorithm

Hot Network Questions

Brute force password cracker

5 Answers 5

Expectation Setting

Alternate algorithm

Related

Hot Network Questions