23

If you use a quick hashing algorithm like MD5 or SHA-1 to hash passwords and you don't use any salt at all, how quickly could one expect a hacker to find my password out?

If I use a truly random salt for each user, on what order of magnitude will this affect the length of time to crack my password?

I have heard that hashing algorithms like md5 or sha-1 can be computed very quickly and at great scale, so you should not use them for password schemes today. But I know that there are lots of systems out there that use them, and I am curious to understand just how quickly these systems can be beaten, or if it is more of a theoretical problem that won't truly exist until a decade from now. I know the user chosen password matters a lot here, and if you can work that into your response, that would be great.

As a bonus, which hashing algorithms are safest to use?

Michael Berkhart
  • 273
  • 1
  • 3
  • 6

4 Answers4

32

Assume you have no rainbow table (or other precomputed list of hashes), and would actually need to do a brute-force or dictionary attack.

This program IGHASHGPU v0.90 asserts to be able to do about 1300 millions of SHA-1 hashes (i.e. more than 2^30) in each second on a single ATI HD5870 GPU.

Assume a password of 40 bits of entropy, this needs 2^10 seconds, which is about 17 minutes.

A password of 44 bits of entropy (like the one in the famous XKCD comic) takes 68 minutes (worst case, average case is half of this).

Running on multiple GPUs in parallel speeds this up proportionally.

So, brute-forcing with fast hashes is a real danger, not a theoretical one. And many passwords have a much lower entropy, making brute-forcing even faster.

If I use a truly random salt for each user, on what order of magnitude will this affect the length of time to crack my password?

The salt itself is assumed to be known to the attacker, and it by itself doesn't much increase the cracking time for a single password (it might increase it a bit, because the hashed data becomes one block longer, but that at most doubles the work).

The real benefit of a (independent random) salt is that an attacker can't use the same work to attack the passwords of multiple users at the same time. When the attacker wants just any user's password (or "as many as possible"), and you have some millions of users, not having a salt would could down the attack time proportionally, even if all users would have strong passwords. And certainly not all will have.

As a bonus, which hashing algorithms are safest to use?

The current standard is to use a slow hashing algorithm. PBKDF2, bcrypt or scrypt all take both a password and a salt as input and a configurable work factor - set this work factor as high as your users just accept on login time with your server's hardware.

  • PBKDF2 is simply an iterated fast hash (i.e. still efficiently parallelizable). (It is a scheme which can be used with different base algorithms. Use whatever algorithm you are using anyways in your system.)
  • Bcrypt needs some (4KB) working memory, and thus is less efficiently implementable on a GPU with less than 4KB of per-processor cache.
  • Scrypt uses a (configurable) large amount of memory additionally to processing time, which makes it extremely costly to parallelize on GPUs or custom hardware, while "normal" computers usually have enough RAM available.

All these functions have a salt input, and you should use it.

Community
  • 1
Paŭlo Ebermann
  • 2,477
  • 20
  • 20
  • with the bcrypt, does the attacker need to know the exact work factor you used to originally compute the password to be able to brute force it? – Michael Berkhart Nov 02 '11 at 19:48
  • 4
    The work factor is not considered to be secret. It is normally fixed for a system (i.e. your whole password database), and for bcrypt it is even usually stored together with salt and hash. – Paŭlo Ebermann Nov 02 '11 at 19:55
  • 8
    One cute side effect of storing the work factor is that you can actually increase the work factor over time, making new passwords stronger as computers get faster. – Peter Recore Nov 03 '11 at 01:57
  • 2
    It is important to point out that Paŭlo Ebermann quotes how long it would take to crack a password with 40 bits or 44 bits of entropy -- but most passwords have nowhere near this much entropy. Most passwords have much less entropy, and thus will be cracked even more rapidly. – D.W. Nov 03 '11 at 05:17
  • 2
    Also worth pointing out is the difference between salted and unsalted passwords, as asked in the question. Unsalted passwords mean that an attacker only needs to enumerate through each password guess *once* to reveal passwords in the entire database. With proper salting, the attacker must enumerate each guess *for every user* (or alternatively, in the specific case in the example, he/she would have to target your password specifically). – Stephen Touset Apr 03 '13 at 18:02
  • @StephenTouset Good point, I added some text relating this to the answer. Seems I missed this part of the question. – Paŭlo Ebermann Apr 03 '13 at 18:30
7

If you don't use salts, the hacker can simply type them into Google and likely find it. MD5 encrypt your password, then Google the result, and you'll see what I mean.

If you've chosen a sufficiently complex password, then it probably won't be on Google, but it will still be in pre-computed tables called "rainbow tables" (the full tables would take too much space, so the "rainbow" technique is used to compress them).

If no tables are being used, then it doesn't matter if the password is salted or not. Of course, tables are always used, so yes, you should salt the passwords.

A desktop machine, with a gaming card (which can also be used to accelerate password cracking), and calculate a billion hashes/second. How fast this cracks your password depends. It can calculate all combinations for short passwords within a few minutes. But the, the problem is exponential, so that it cannot calculate all possible combinations for long passwords, even if you used a billion computers over a billion years.

Instead, what hacker do is a "mutated dictionary" crack. They start with a list of well-known words. It's called a "dictionary", but such lists contain a lot of words that you wouldn't find in a real dictionary, like "ncc1701", the designation for the Star Trek Enterprise. For each word, it does a number of mutations, such as capitalizing some letters, changing some letters to numbers, like "p4ssw0rd", or appending characters, like "password1234". How fast this works depends upon the skill of the hacker choosing just the right dictionary and just the right mutations. This can also change depending upon the hacker's knowledge of you. For example, if you are Hispanic, the hacker will add Spanish words and names to the dictionary.

You can expect that if your password database is stolen, the hacker will be able to crack about half of the salted passwords with a couple day's worth of work.

Robert David Graham
  • 3,893
  • 1
  • 15
  • 14
  • 1
    in the last sentence, do you mean to say "the hacker will be able to crack about half of the UNsalted passwords..."? – Tom Harrison Jr Jun 08 '12 at 14:14
  • 1
    hey that is cool, did not know that MD5 hashes of common passwords can be simply googled for the plaintext – marcwho Apr 04 '13 at 13:42
6

This slide describes how much of a hardware investment is needed to crack a password in 1 year:

It compares various KDFs including MD5, PBKDF2, bcrypt, scrypt with a varying number of rounds.

enter image description here

makerofthings7
  • 50,488
  • 54
  • 253
  • 542
5

Well if you're just using MD5 or SHA-1 with no salt, just download a rainbow table and have it cracked in no time.

A subject on rainbow tables can be found here and how they leverage a bit better efficiency than just brute forcing one password in the case of a fixed salt.

how long does it take to actually generate rainbow tables?

On top of the first two, which applies to any hash without salt or with a fixed salt, MD5 has a lot of security vulnerabilities (reducing the time to crack the password).

http://en.wikipedia.org/wiki/MD5

Community
  • 1
StrangeWill
  • 1,593
  • 8
  • 13