Are salted SHA-256/512 hashes still safe if the hashes and their salts are exposed?

  • Scenario: a database of hashed and and salted passwords, including salts for each password, is stolen by a malicious user. Passwords are 6-10 chars long and chosen by non-technical users.

    Can this malicious user crack these passwords?

    My understanding is that MD5 and SHA-1 are not safe anymore as GPU assisted password recovery tools can calculate billions of these hashes per second per GPU.

    What about SHA-256 or SHA-512? Are they safe currently? What about in a few years?

    Lifetimes of cryptographic hash functions is very interesting. A variation I've heard of is to always use *two* hashing algorithms. That way you can always deprecate one as soon as it's insecure, and you get a time window to migrate all data instances.

    @l0b0 depending on the use case, that can be detrimental to the overall security of the cryptosystem. E.g. using a weak hash as input to a strong hash, will still leave the strong hash with very low entropy (if this matter for your situation).

  • erickson

    erickson Correct answer

    10 years ago

    The question doesn't state how many rounds of hashing are performed. And the whole answer hinges on that point.

    All hash functions are unsafe if you use only one iteration. The hash function, whether it is SHA-1, or one of the SHA-2 family, should be repeated thousands of times. I would consider 10,000 iterations the minimum, and 100,000 iterations is not unreasonable, given the low cost of powerful hardware.

    Short passwords are also unsafe. 8 characters should be the minimum, even for low value targets (because users reuse the same password for multiple applications).

    With a $150 graphics card, you can perform 680 million SHA-1 hash computations per second. If you use only one round of hashing, all 6-character passwords can be tested in a little over 15 minutes (that's assuming all 94 printable ASCII characters are used). Each additional character multiplies the time by 94, so 7 characters requires one day, 8 characters requires 103 days on this setup. Remember, this scenario is a 14-year-old using his GPU, not an organized criminal with real money.

    Now consider the effect of performing multiple iterations. If 1,000 iterations of hashing are performed, the 6-character password space takes almost 12 days instead of 15 minutes. A 7-character space takes 3 years. If 20,000 iterations are used, those numbers go up to 8 months and 60 years, respectively. At this point, even short passwords cannot be exhaustively searched; the attacker has to fall back to a dictionary of "most likely" passwords.

    It's worth to note that a lot of passwords can be covered with much smaller amount of characters. http://www.r-bloggers.com/character-occurrence-in-passwords/

    But here is my main mistake, I didn't understand that these algorithms are meant to be iterated hundreds of times.

    @Seppo --- **thousands** of times, not hundreds. Even the original PKCS #5 recommend at least 1000 iterations. You should be thinking about tens of thousands. The good thing is, you should be able to update existing password hashes without forcing users to pick new passwords. Obviously if bad guys already have the poorly hashed passwords, it's too late (think about backups, etc.). But if they don't yet, it's not too late to fix things.

    You can also use bcrypt or similar tools which take some type of work factor to slow down the hashing process for you. http://codahale.com/how-to-safely-store-a-password/

    The iteration count of PBKDF2 is the work factor for a hashing solution. Bcrypt is really not so exotic. They both achieve slowness with a tunable key derivation routine. One key difference is that bcrypt actually uses the derived key to encrypt a well-known plain text, and store the resulting cipher text, while most hashing solutions just store the derived key directly. However, I think both approaches are robust.

    Succinctly, the generic cryptographic hash algorithms are designed to be fast. Protecting a password requires a slow cryptographic hash algorithm. A fast cryptographic hash algorithm, iterated 2^16 times, becomes a slow cryptographic hash algorithm. Then add in other requirements such as salts, etc.

    "Each additional charcter multiplies the time by 94, [...] 7 characters requires one day, 8 characters requires 7 years" - shouldn't 8 characters require 94 days?

    Also, regarding bcrypt: Isn't the point that bcrypt is equally slow on a GPU (or at least has a much smaller speedup)? We can expect attackers to have GPUs, but most servers don't, so anything that reduces the attacker's advantage seems like a good idea.

    @nick: yes - @erickson is wrong about 8 characters: 94^8 / 680 10^6 / 3600 / 24 => 103 days. As for GPUs and bcrypt, from what I've seen there may not be much published work on optimizing bcrypt for them, but no reason to think it would be very hard.

    After getting another confirmation, I fixed it for 8 characters.

    @nealmcb I believe Thomas Pornin has stated that bcrypt was designed to make GPU and hardware bruteforcing slow. Something about mutating some data to force them to hit have to keep hitting main memory?

    The work performed by bcrypt in key deriving a key is the same as PBKDF2, so hardware should affect both equally. You may be thinking of scrypt, which is designed to defeat memory optimization.

    @erickson: no, there really is a difference. PBKDF2 with SHA-256 is all 32-bit arithmetic operations; bcrypt is pseudorandom accesses (read and writes) in a 4 kB buffer. This makes bcrypt much harder to optimize on a GPU. Scrypt just builds further on that concept, extending the memory buffer to _megabytes_ (because while bcrypt is hostile to GPU, modern FPGA has small embedded RAM blocks which work just fine for that -- but FPGA suffer on scrypt implementations).

    @ThomasPornin I didn't realize that, thanks. I will have to take a closer look at `bcrypt`.

    Sad truth is scrypt & bcrypt do not offer much in terms of practical improvements vs brute force: a round takes more time, but you can in practice do less of them, because you are limited in terms of how long you can take to check a hash. GPU/FPGA/ASIC have been getting a lot better at scrypt, and have a fair margin for improvement before being limited by Moore's Law. CPUs are getting much better at SHA-256, while GPUs/FPGA/ASIC are now limited by Moore's Law for SHA-256. The medium/long term outlook is in favor of SHA-256.

    That's the first time I've seen that information, looks interesting! Got anything to read up on a more detailed explanation?

    QUESTION: So this answer assumes that the attacker *knows* the number of hashing rounds that were used right? So, if you can hide your code, is using a low but obscure number, like say 628 hashing rounds instead of a flat number like 1000 or 10000, a secure alternative?

    @csstudent1418 No, that would not add security. First, it's a form of security through obscurity. You should design your system so that it's secure when the algorithms are exposed and only the keys are secret. But more importantly in this case, the attacker can check with each iteration up to some maximum they choose. So if you pick 628, they'll crack the password on their way to 10000.

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM