How Quickly Can Password Schemes be Beaten?
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.
The Impact of Using a Random Salt
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.
The Safest Hashing Algorithms 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.