20

I have been able to crack passwords, given their salts and their hashes, by using brute force.

In the first place, the length of passwords was 3 and the salt length 2:

e.g., hash: rrVo/xC.s5/hQ, salt: rr => password: thr (time: ~0m4.579s)

Now, for passwords of length 4 and salt length 2:

e.g., hash: ss1C5xfz6Nggg, salt: ss => password: four (time: ~7m19.531s)

As I have said, these passwords were obtained using a brute force algorithm. It is useful for short password lengths: as the numbers of characters for the password increase, the required time to break the password grows exponentially.

What I want to know is more efficient technique to reduce the search space.

Additional info:

  1. Passwords are created using: A-Z, a-z, 0-9, and symbols: $, #, +, @, =, /, &

  2. I have been using the openssl command to generate the hashes and compared them to the given hash 

    $ openssl passwd -crypt -salt rr thr

in a bash script.

Improve this question
2
  • 16
    Note that for all secure cryptographic algorithms, the main objective is in fact NOT having a method to reduce the search space. An algorithm that has such methods (like SHA1 or MD5 due to collisions) is considered broken (security reduction may vary), and sooner or later will be replaced by more secure ones. Commented Mar 6, 2017 at 11:26
  • 9
    @BgrWorker Nitpick: The known weaknesses in MD5 and SHA1 are purely collisions -- there are no known preimage attacks yet; there's no known way to calculate an input to generate a specific hash. Commented Mar 6, 2017 at 18:38

5 Answers 5

Reset to default
24

Without any more information, you can not reduce the search space. Since you don't have any prior information about the password, you can't rule out any possible password from the search space.

If your hash function (which you don't specify) has some vulnerabilities, you may be able to learn something about the password before starting the brute force attempt (starts with 'a', contains 'b' and so on...). Thus reducing the search space.

Something else that may answer your need for faster password cracking is Rainbow Tables which are a precomputation you perform given the salt, to be able to find the password faster later. Rainbow Tables are used as a lookup table for a given hash.

Say we have hash('four','ss') = ss1C5xfz6Nggg, and we know the salt ss. We will perform the following precomputation:

Precomputation Rainbow Table The actual Rainbow Table must be sorted according to the hash values, to enable fast lookup. This way, when given the hash of the password, ss1C5xfz6Nggg, we only need to lookup the hash in the Rainbow Table and our password is stored right next to it. Thus making the cracking process much faster (At the cost of precomputation time, of course).

Edit: Sjeord's comment is correct, so I must point out that:

Rainbow tables, despite their recent popularity as a subject of blog posts, have not aged gracefully. CUDA/OpenCL implementations of password crackers can leverage the massive amount of parallelism available in GPUs, peaking at billions of candidate passwords a second. You can literally test all lowercase, alphabetic passwords which are ≤7 characters in less than 2 seconds. And you can now rent the hardware which makes this possible to the tune of less than $3/hour. For about $300/hour, you could crack around 500,000,000,000 candidate passwords a second.

Source

Improve this answer
10
  • 23
    Some people argue that rainbow tables are no longer worth it because brute force cracking became so fast. For example, to store all four-letter words for all two-letter salts you would need 4 GB of disk space, which save you around 2 seconds of compute time. Commented Mar 6, 2017 at 8:04
  • 5
    @Sjoerd I'd think that rainbow tables would still be relevant for slow hashes like SCrypt/BCrypt/pbkdf2 even if they've been overcome by GPU speed for attacking fast hashes. Commented Mar 6, 2017 at 15:27
  • 8
    I don't agree with your definition of what a rainbow table is. Commented Mar 6, 2017 at 16:05
  • 9
    Rainbow tables are not just giant precomputed lookup tables of hash values. They are a specific space-saving optimization of the concept. This answer's portrayal of rainbow tables is wrong. Commented Mar 6, 2017 at 21:24
  • 3
    @user2357112 That is true. Rainbow tables use a lot less disk space than a naive table of hash and password pairs. However rainbow tables do use a little more CPU time than the naive table. In particular you cannot use a rainbow table to break any salt and password combination that wasn't computed while generating the table. Any properly salted hash will completely defeat the use of rainbow tables. If the salt is long enough and random enough, you are never going to find the password using a rainbow table. Commented Mar 6, 2017 at 23:39
19

There is no way to retrieve the password faster than brute force, but there is a lot you can change about your brute-force speed.

four (time: ~7m19.531s)

This is a long time to brute-force a password this short. You would get a big performance improvement by using hashcat with a decent graphics card. I could crack it in under two seconds with the following command:

/usr/src/cudaHashcat-2.01/cudaHashcat64.bin ss1C5xfz6Nggg -m 1500 -a 3
Improve this answer
1
  • 8
    "There is no way to retrieve the password faster than brute force": this is only true if the password is really random. Most passwords are chosen to be easy to remember and aren't that random, like "123456" or "password". So in most cases a dictionary attack will work. Sure, in a way this is still brute-forcing, but you are brute-forcing a list of very likely passwords. It's much faster than systematically attacking every possible password (which is the usual meaning of "brute force"). I'm sure you know it, but maybe you could state it more clearly. Commented Mar 6, 2017 at 16:44
9

The whole purpose of the salt+hash system is that there should be no way faster than a brute-force attack. As BgrWorker already pointed out, there are in fact weaknesses in older hash algorithms that reduce the search space (or more precisely: Allow the computation of collisions), but discovering one is considered a breakthrough that you will find in a journal more likely than in a stackoverflow answer. :-)

There are some common tricks you can use:

Rainbow Tables were already mentioned and - depending on the salt size - even for realistic hash and password lengths they provide a possible approach to the top 100 or so passwords.

Using dictionary attacks and crackers instead of dumb brute force. The password aaaaaaaa is much less likely than the password "password" or "12345678", so testing them first is smart.

Finally, in many real-world scenarios, the password policy of a site or company actually reduces your search-space, sometimes dramatically. If password not only can, but have to contain, say, at least one number and one special character, your search space on 8 characters just dropped from 10^15 to 10^13.

Improve this answer
4
  • Actually aaaaaaaa (as well as zzzzzzzz) is still quite more likely than e.g. tcpohqdr, so it will appear in a good password list, too. Commented Mar 6, 2017 at 21:57
  • Yes, but it is at top 807, while "password" is #1 and "12345678" is #3. (source: passwordrandom.com). The point was to test passwords in order of likelihood. Commented Mar 8, 2017 at 6:25
  • Could you explain the last paragraph? It sounds really wrong, and I'm unsure whether I'm misunderstanding what you're saying. Commented Sep 9, 2018 at 0:31
  • If you want to brute-force passwords, you will not try them in the order "a", "b", "c" ... "aaa", "aab", "aac" ... that would be stupid. You will take a list of common passwords and try that first. Then you will iterate through variations, then through patterns and pronouncable phrases, etc. Commented Sep 9, 2018 at 4:45
4

I believe your problem is that you're using openssl in a bash script. This means every new password attempt needs to spawn yet another process. For brute-forcing, consider using an efficient compiled programming language such as C. I'm sure you will find your efficiency increases by more than one order of magnitude.

Of course, this means you will have to rewrite your entire brute-forcing application.

Improve this answer
2

What you are seeking is in direct opposition to the fundamental goals of password hashing algorithms in general. You should not be surprised that what you seek is difficult -- people have spent thousands of hours making it difficult for you.

People have mentioned Rainbow Tables, and other password hashing approaches, which would be a logical extension of what you are doing. The other alternative is to take advantage of the fact that people typically don't choose perfectly random passwords. Software like John the Ripper are designed to exploit this, using common password generation schemes to guess more likely passwords first. This means you only have to resort to a brute force search if the password was well chosen.

Improve this answer

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.