Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

I'm running a very time-consuming script which takes many hours to end. Watching top I see that it's only taking 5% of the CPU at best, usually around 3%.

Is there any way to force the script to use more CPU in order to end faster?

Edit:

Basically the script is bruteforcing 5 chars length passwords given a the salt and the hash.

Not at home right now, but something like:

charset = ['a','b',.........'z'];
for i in $charset do
   for j in $charset do
       for k in $charset do
           for l in $charset do
              for m in $charset do
                  pass = `openssl passwd -salt $1 $i$j$k$l$m`
                  if [ pass == $2 ]]; then
                     echo "Password: $i$j$k$l$m";
                     exit;
                  fi
               done
            done
        done
    done
 done
share|improve this question
1  
you should consider to provide your script so we can really tell you if it's possible or not, if your script rely a lot on disk IO then you could put the highest priority on it, it wouldn't be able to go faster than your hard drive. –  Kiwy Mar 12 at 9:26
1  
Dude, you need a different script - in fact, you need a different programming language. That said, your problem could be openssl and /dev/random. You could try moving your mouse a lot and smashing keys on the keyboard a lot. If your processing time jumps from 3 hours to 3 minutes you might want to look into pseudo randomness generators. Catting/copying files from nowhere to nowhere can help a lot too. –  mikeserv Mar 12 at 11:26
    
Spawning a new openssl process for each attempted password will have a noticeable impact on performance. You should consider rewriting your script to hash passwords without spawning thousands of processes or (preferably) switch to a more sophisticated tool like John the Ripper. –  n.st Mar 12 at 11:31
    
If I wanted to use it for real brute-forcing, I would use John or Hydra. But that script is part of my Master's programme, and I need to use that for "learning purposes". –  yzT Mar 12 at 11:41
1  
You may consider building your script around the -in option to openssl passwd. That way you reduce your total number of execve calls. I agree with the other, you're probably better off writing this in C. The openssl tool is mostly just a vehicle for the project maintainers to do a proof of concept on how you would implement the underlying libraries. –  Joel Davis Mar 12 at 13:46

5 Answers 5

up vote 6 down vote accepted

Improvement #1 - Loops

Your looping structure seems completely unnecessary if you use brace expansions instead, it can be condensed like so:

$ more pass.bash 
#!/bin/bash

for str in $(echo {a..z}{a..z}{a..z}); do
  pass=$(openssl passwd -salt $1 $str)
  if [[ "$pass" == "$2" ]]; then
    echo "Password: $str"
    exit;
  fi
done

# vim: set nolist ts=2 :

I'm showing 4 characters just to make it run faster, simply add additional {a..z} braces for additional characters for password length.

Example runs

4 characters
$ openssl passwd -salt ab hhhh
abBYJnOuV8dUA

$ time ./pass.bash ab abBYJnOuV8dUA
Password: hhhh

real    18m3.304s
user    6m58.204s
sys     9m34.468s

So it completed in 18 minutes.

5 characters
$ openssl passwd -salt ab ccccc
abZwsITAI6uwM

$ time ./pass.bash ab abZwsITAI6uwM
Password: ccccc

real    426m37.234s
user    16m34.444s
sys     398m20.399s

This took ~426 minutes. I actually Ctrl+C this, so it hadn't finished, but I didn't want to wait any more than this!

NOTE: Both these runs were on this CPU:

brand = "Intel(R) Core(TM) i5 CPU       M 560  @ 2.67GHz

Improvement #2 - Using nice?

The next logical step would be to nice the above runs so that they can consume more resources.

 $ nice -n -20 ./pass.bash ab hhhhh

But this will only get you so far. One of the "flaws" in your approach is the calling of openssl repeatedly. With {a..z}^5 you're calling openssl 26^5 = 11881376 times.

One major improvement would be to generate the patterns of {a..z}.... and save them to a file, and then pass this as a single item to openssl one time. Thankfully openssl has 2 key features that we can exploit to get what we want.

Improvement #3 - our call structure to openssl

The command line tool openssl provides the switches -stdin and -table which we can make use of here to have a single invoke of openssl irregardless of how many passwords we want to pass to it. This is single modification will remove all the overhead of having to invoke openssl, do work, and then exit it, instead we keep a single instance of it open indefinitely, feeding it as many passwords as we want.

The -table switch is also crucial since it tells openssl to include the original password along side the ciphers version, so we can make fairly quick work of looking for our match.

Here's an example using just 3 characters to show what we're changing:

$ openssl passwd -salt ab abc
abFZSxKKdq5s6

$ printf "%s\n" {a..z}{a..z}{a..z} | \
    openssl passwd -stdin -table -crypt -salt ab | grep -m1 abFZSxKKdq5s6
abc abFZSxKKdq5s6

So now we can really revamp our original pass.bash script like so:

$ cat pass2.bash 
#!/bin/bash

pass=$(printf "%s\n" {a..z}{a..z}{a..z}{a..z}{a..z} | \
  openssl passwd -stdin -table -crypt -salt $1 | grep -m1 $2)

if [[ "$pass" =~ "$2" ]]; then
  echo "Password: $pass"
fi

# vim: set nolist ts=2 :

Now when we run it:

$ time ./pass2.bash ab aboznNh9QV/Q2
Password: hhhhh aboznNh9QV/Q2

real    1m11.194s
user    1m13.515s
sys     0m7.786s

This is a massive improvement! This same search that was taking more than 426 minutes is now done in ~1 minute! If we search through to say "nnnnn" that's roughly in the middle of the {a..z}^5 character set space. {a..n} is 14 characters, and we're taking 5 of them.

$ echo "14^5" | bc 
537824

$ openssl passwd -salt ab nnnnn
abRRCp5N3WN32

$ time ./pass2.bash ab abRRCp5N3WN32
Password: nnnnn abRRCp5N3WN32

real    1m10.865s
user    1m12.842s
sys     0m8.530s

This search took ~1.1 minutes. NOTE: We can search the entire space of 5 character passwords in ~1 minute too.

$ time ./pass2.bash ab abBQdT5EcUvYA
Password: zzzzz abBQdT5EcUvYA

real    1m10.783s
user    1m13.556s
sys     0m8.251s

Conclusions

So with a restructuring we're running much faster. This approach scales much better too as we add a 6th, 7th, etc. character to the overall length of the password.

Be warned though that we're using a smallish character set, mainly only the lowercase alphabet characters. If you mix in all the number, both cases, and special characters you can typically get ~96 characters per position. This may not seem like a big deal but this increase your pool tremendously:

$ echo 26^5 | bc
11881376
$ echo 96^5 | bc
8153726976

Adding all those characters just increased by 2 orders of magnitude our search space. If we go up to roughly 10-12 characters of length to the password, it really puts a brute force hacking methodology out of reach.

Using proper a salt as well as additional NONCE's throughout the construction of a hashed password can add still more stumbling blocks.

What else?

You've mentioned using John (John the Ripper) or other cracking tools. Probably the state of the art currently would be HashCat.

Where John is a tighter version of the approach you're attempting to use, HashCat takes it to another level by enlisting the use of GPUs (up to 128) to really make your hacking attempts fly.

You can even make use of CloudCrack, which is a hosted version, and for a mere $17 US you can pay to have a password crack attempted.

References

share|improve this answer
    
The first example is taking exactly the same time as when bruteforcing. Maybe it has something to do that I'm running the script in a VM? Exactly it's taking 50s on 3 chars. The VM setup is 2 cores 3GHz and 2 GB RAM. –  yzT Mar 12 at 21:31
1  
the nice example also lasts 50s. The example of the table is the good one. –  yzT Mar 12 at 21:40
    
mmm, what does the =~ do? First time I see it. –  yzT Mar 12 at 22:10
    
I don't understand one thing. According to man bash, =~ compare two expressions, doesn't it? However, if we are just matching two strings, why == doesn't work? –  yzT Mar 13 at 9:40
    
Why the echo ... | while read where you could have done for i in ...? –  Stéphane Chazelas Mar 13 at 10:58

Your script isn't just sitting on its hands! It's probably waiting for a resource other than the CPU; perhaps it's manipulating lots of files and waiting for the disks, or sending lots of stuff over the network and waiting for that.

Look at the aggregate resource usage lines at the top of top and you'll see something like

%Cpu(s): 28.6 us, 28.6 sy,  0.0 ni, 42.9 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st

The us number is the amount of CPU actually being used by the logic of your script (or other things that it calls). sy and wa are CPU time spent in system calls and waiting for I/O. If these numbers are high while your script is running, and there's no other activity on the system, then something other than the CPU is your bottleneck.

share|improve this answer
    
valid point. changing niceness would be my first step though in case some other task is using resources. then it's moving the bottleneck around. –  hbdgaf Mar 12 at 9:19
    
%Cpu(s): 31.7 us, 21.3 sy, 0.0 ni, 47.0 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st –  yzT Mar 12 at 17:02

Your script is probably using more than 3% as explained by Flup but you are also wasting a lot of time spawning a copy of openssl every time you want to create a password (which is probably the main reason for the missing cpu time). If you have a multicore/threaded machine you will also not be able to stress more than a single thread of execution with your script so you will be using 1/max_number_of_threads of possible CPU time.

You will be better off implementing the code in something other than a shell script, that can natively do the encryption for you. Your openssl command is incomplete so my suggestions are a bit vague, but generally perl, python and ruby will have modules that implement the standard stuff (like scrypt and bcrypt)

Other ways you can generate the crypt passwd

$ openssl passwd -salt ab abcde
abHBZlaDwNzc2

$ gem install unix-crypt
$ ruby -e 'require "unix_crypt"; print UnixCrypt::DES.build("abcde","ab");'
abHBZlaDwNzc2

$ perl -e 'print crypt("abcde","ab");'
abHBZlaDwNzc2

Just don't use them in the innermost loop! Implement the loops in the perl or whatever you run the crypt function in.

As Stephane mentioned, you could build a list of passwords and pipe it into openssl as well

echo -e "abcde\nabcde" | openssl passwd -salt ab -stdin 

Then test the output for the correct password.

I'll leave the implementation down to you =)

share|improve this answer
    
I need to use shell script. It's not for "production", it's for knowledge purposes. maybe a -crypt is missing on the command, but anything else. And -crypt is the default I think. –  yzT Mar 12 at 11:43
1  
Oh.. you're running openssl passwd then. Running the openssl binary charset^5 times is always going to take a while. If you want it to complete quicker, you'll need to do it differently. –  mtm Mar 12 at 12:15
    
yea, indeed passwd was missing :D. That's what my teacher want me to do, modify the script so it is quicker, and I thought about increasing the resources usage. What other solutions do I have? I've tried to use a dictionary with every possible combination, but it lasts the same as when bruteforcing. –  yzT Mar 12 at 12:54
    
@yzT, one invocation of openssl can process as many passwords as you want if you use -stdin (and newline is not part of your charset). –  Stéphane Chazelas Mar 12 at 13:00
    
If you have a multicore/threaded machine you could run multiple copies as well. –  mtm Mar 12 at 13:01

renice is the utility to change niceness and increase or decrease priority, but you need root to make something more aggressive.

Start block-paste:

Terminal

If you're at a terminal you can use renice

renice [-n] priority [[-p] pid ...] [[-g] pgrp ...] [[-u] user ...]

A simple example would be

renice 8 31043
31043: old priority 5, new priority 8

You can also pass it hard flags, but it follows that order

renice -p 31043 -n 5
31043: old priority 8, new priority 5

Priorities work on a scale of -20 to 20 - The lower the number, the higher its priority on the system.

End block-paste.

share|improve this answer

In addition to the various implementation optimizations in @slm's answer, there is a huge algorithmic optimization to make. (There may also be some cryptanalytic attacks, I'm not sure how strong the UNIX crypt algorithm is, but that is probably beyond the scope of a shell script)

The problem you're trying to solve was probably described as "brute force a password". In order to do that, you generated all possibilities in alphabetical order, and tested them, exiting at the first match. If you model a password as "random string of 5 characters", then this is actually optimal.

A few people will use an actually random password. A few, not most. Even for things where they really ought to. Especially for things they don't consider important. We've had this confirmed recently and repeatedly by numerous leaked password databases.

The password you're looking for could be dbKbuW. But it's many, many times more likely to be qwerty, abc123, or 123456. We know from the leaked databases that the top thousand or so most common passwords will crack most accounts.

So the real speed up is to generate your guesses in a better order. At minimum, sort your letter-lists by frequency in English (or, better yet, in passwords). You should be trying e a lot earlier than z. Run through a list of 1000 or so common passwords first, before even starting your brute-force iteration across the search space (wastes a little time if it doesn't work, but depending on your users it'll work well over half the time).

If you look at how actual password cracking tools work, they run through a few lists of common passwords, then through a dictionary, then through variations (e.g., "change e to 3"), then through various password generating strategies, and only if none of that works, then finally start iterating through the search space.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.