3 ms·

The problem is, even with the salted hash, it’s still too easy for an attacker to run dictionary attacks if they are able to retrieve a single user’s salt and h

The problem is, even with the salted hash, it’s still too easy for an attacker to run dictionary attacks if they are able to retrieve a single user’s salt and hash. When your attacker can do 1 billion SHA1 hashes/second with cheap hardware, even slowing it down 10,000 times and they’re still cracking a lot of your users’ passwords. False. If you use Colin Percival's scrypt to hash your passwords, then it's impossible for an attacker to crack them via brute force. See previous discussion: http://news.ycombinator.com/item?id=4076197 http://news.ycombinator.com/item?id=4076197

dfox 14y ago
It's certainly not impossible. scrypt provides reasonable defense against using cheap highly parallel approaches to brute force, but still can obviously be cracked by brute force. For passwords, current typical attacker does not care about cracking all of them, but cares about finding some (mostly weak) passwords that he can try with other services used by same user.
- michaelfairley 14y ago
  Ultimately, OP's strategy is just increasing the cost of brute forcing. Why not use the cost increasing features built into the hashing algorithms themselves?
  - zaroth 14y ago
    Current algorithms allow you to increase cost in terms of CPU and RAM only. I want to increase cost on as many axis as possible, in this case, by requiring you to steal 1TB of mostly meaningless data, and not just 100 odd bytes. [Edit] sillysaurus - It's a great image, but a little hard to parse since it doesn't actually show you the bits of entropy for each choice. If they did show a column for 40.5bits (average strength of a user's password) you would see the result is a lot closer to $150 for 'scrypt 64ms' than it is to the very sexy looking $4.8m. Of course the technique could work even better with scrypt behind it (find/replace 20 bytes with 32 bytes).
    - deleted 14y ago
      [deleted]
    - repsilat 14y ago
      It's worse than the average strength would suggest, too. You can't do an arithmetic average and get a meaningful figure because cracking difficulty doubles with every bit. Say passwords were distributed evenly at 35, 40.5 and 46 bits. You may have a lot of difficulty cracking the 46-bit passwords, but the 35-bit ones will be easy. Now, you can't tell which users have easy passwords, but it's easy enough to try the "top 10,000 passwords" (from previous dumps) on all of the hashes you get and see if any match. Without the scheme outlined in TFA many users' passwords can be compromised this way. At 64ms each you can run those top 10,000 passwords on each user in less than 11 minutes, and you're almost guaranteed to get some hits. With this new technique, though, you won't, because you'll be lucky to even pick a "real user" in the first place. EDIT: Of course, if your system is going to remain at all practical to use you can probably filter out the fake passwords with a simple join. You won't have user-data for all of your fake users, and you don't want the username space taken up by trillions of realistic-sounding dummy names preventing bona fide users from registering.
      - foxylad 14y ago
        You can't do a join because the hash table contains only hashes - nothing to relate them back to the user record. This idea uncouples the password from the username and salt, which seems a good idea. But assuming you have access to the database, the additional work required is an indexed lookup instead of a simple equality - not actually a huge deal. Having said that, when it comes to security I'll defer every time to someone with real chops in this area. Wake me up when Bruce Schneier comments on this.
    - deleted 14y ago
      [deleted]
- deleted 14y ago
  [deleted]
zaroth 14y ago
I am the author of the article. Thanks for pointing out scrypt, I have heard of it before. PBKDF2, bcrypt, scrypt... they all share one thing in common: They MUST be configured to run fast enough on your server so that your users can login even under high system load. Let's say you need to support being able to test 1,000 passwords per second on your server (to support your projected peak login traffic). In that case, relatively weak passwords can be cracked, and by relatively weak I mean 95th percentile entropy bits for less than $1,000 on EC2. This is why I'm trying to think differently about the problem. If we hide the hash in a haystack, the attacker will no longer be able to target an individual user, and theft of the entire hash database should be more easily detectable and preventable.
- michaelfairley 14y ago
  _Nobody_ is hashing thousands of passwords per second as part of a typical webapp load. Even if somebody was, they would need only ~50 cores for hashing. I'm sure anybody with that much traffic could easily shell out a few thousand bucks for the extra processors without blinking. Also, an 8 character password hashed with scrypt with a very low (64ms) cost takes on average $4.8 million to brute force[1]. 1: http://www.tarsnap.com/scrypt/scrypt.pdf http://www.tarsnap.com/scrypt/scrypt.pdf
  - zaroth 14y ago
    Thanks for citing your source! You rock. They are claiming 6.57 * 8 = 52.5 bits of entropy would cost $4.8m to crack a single password in a year. They also state 4.7 * 8 = 37.6 bits of entropy would cost $150 to crack a single password in a year. Their own citation of 'A large scale study of web password habbits' http://research.microsoft.com/pubs/74164/www2007.pdf http://research.microsoft.com/pubs/74164/www2007.pdf found that the average password has only 40.5 bits of entropy. I'm afraid even scrypt will not save you from 40 bit entropy passwords.
    - deleted 14y ago
      [deleted]

dfox 14y ago

It's certainly not impossible. scrypt provides reasonable defense against using cheap highly parallel approaches to brute force, but still can obviously be cracked by brute force. For passwords, current typical attacker does not care about cracking all of them, but cares about finding some (mostly weak) passwords that he can try with other services used by same user.

michaelfairley 14y ago
Ultimately, OP's strategy is just increasing the cost of brute forcing. Why not use the cost increasing features built into the hashing algorithms themselves?
- zaroth 14y ago
  Current algorithms allow you to increase cost in terms of CPU and RAM only. I want to increase cost on as many axis as possible, in this case, by requiring you to steal 1TB of mostly meaningless data, and not just 100 odd bytes. [Edit] sillysaurus - It's a great image, but a little hard to parse since it doesn't actually show you the bits of entropy for each choice. If they did show a column for 40.5bits (average strength of a user's password) you would see the result is a lot closer to $150 for 'scrypt 64ms' than it is to the very sexy looking $4.8m. Of course the technique could work even better with scrypt behind it (find/replace 20 bytes with 32 bytes).
  - deleted 14y ago
    [deleted]
  - repsilat 14y ago
    It's worse than the average strength would suggest, too. You can't do an arithmetic average and get a meaningful figure because cracking difficulty doubles with every bit. Say passwords were distributed evenly at 35, 40.5 and 46 bits. You may have a lot of difficulty cracking the 46-bit passwords, but the 35-bit ones will be easy. Now, you can't tell which users have easy passwords, but it's easy enough to try the "top 10,000 passwords" (from previous dumps) on all of the hashes you get and see if any match. Without the scheme outlined in TFA many users' passwords can be compromised this way. At 64ms each you can run those top 10,000 passwords on each user in less than 11 minutes, and you're almost guaranteed to get some hits. With this new technique, though, you won't, because you'll be lucky to even pick a "real user" in the first place. EDIT: Of course, if your system is going to remain at all practical to use you can probably filter out the fake passwords with a simple join. You won't have user-data for all of your fake users, and you don't want the username space taken up by trillions of realistic-sounding dummy names preventing bona fide users from registering.
    - foxylad 14y ago
      You can't do a join because the hash table contains only hashes - nothing to relate them back to the user record. This idea uncouples the password from the username and salt, which seems a good idea. But assuming you have access to the database, the additional work required is an indexed lookup instead of a simple equality - not actually a huge deal. Having said that, when it comes to security I'll defer every time to someone with real chops in this area. Wake me up when Bruce Schneier comments on this.
  - deleted 14y ago
    [deleted]
deleted 14y ago
[deleted]

zaroth 14y ago

I am the author of the article. Thanks for pointing out scrypt, I have heard of it before. PBKDF2, bcrypt, scrypt... they all share one thing in common: They MUST be configured to run fast enough on your server so that your users can login even under high system load. Let's say you need to support being able to test 1,000 passwords per second on your server (to support your projected peak login traffic). In that case, relatively weak passwords can be cracked, and by relatively weak I mean 95th percentile entropy bits for less than $1,000 on EC2. This is why I'm trying to think differently about the problem. If we hide the hash in a haystack, the attacker will no longer be able to target an individual user, and theft of the entire hash database should be more easily detectable and preventable.

michaelfairley 14y ago
_Nobody_ is hashing thousands of passwords per second as part of a typical webapp load. Even if somebody was, they would need only ~50 cores for hashing. I'm sure anybody with that much traffic could easily shell out a few thousand bucks for the extra processors without blinking. Also, an 8 character password hashed with scrypt with a very low (64ms) cost takes on average $4.8 million to brute force[1]. 1: http://www.tarsnap.com/scrypt/scrypt.pdf http://www.tarsnap.com/scrypt/scrypt.pdf
- zaroth 14y ago
  Thanks for citing your source! You rock. They are claiming 6.57 * 8 = 52.5 bits of entropy would cost $4.8m to crack a single password in a year. They also state 4.7 * 8 = 37.6 bits of entropy would cost $150 to crack a single password in a year. Their own citation of 'A large scale study of web password habbits' http://research.microsoft.com/pubs/74164/www2007.pdf http://research.microsoft.com/pubs/74164/www2007.pdf found that the average password has only 40.5 bits of entropy. I'm afraid even scrypt will not save you from 40 bit entropy passwords.
  - deleted 14y ago
    [deleted]