Wouldn't this setup mean that I can hack into your system with almost any password? As there is no direct connection AND you fill up with dummy hashes - doesn't that effectively mean you drive up the chances of a hack? The more fake hashes, the higher the probability that any random password I brute force may result in a match against the set of hashes. And if that happens - boom, I am in. Or am I missing something?
A Better Way to Store Password Hashes?
21–30 of 59 posts
Re: A Better Way to Store Password Hashes?
#22Wouldn't this setup mean that I can hack into your system with almost any password? As there is no direct connection AND you fill up with dummy hashes - doesn't that effectively mean you drive up the chances of a hack? The more fake hashes, the higher the probability that any random password I brute force may result in a match against the set of hashes. And if that happens - boom, I am in. Or am I missing something?
Definitely not. The back-end takes a user's password and hashes it with that user's specific salt. Then the result must be in the table. Another user's password will not work.
What you are worried about is a result existing in the table, even with the wrong password. That can only happen if you have a hash collision. The article on collisions I cited (http://preshing.com/20110504/hash-collision-probabilities) says that even with 171 trillion hashes already IN the database, the likelihood of a collision is still only 1 in 10^18. And that's using SHA1 -- SHA-256 would be even better.
[Edit] Ooops, I forgot a zero. It's actually 1,710 trillion hashes in the database to make the risk of collision 1 in 10^18. OK, that's 1.71 quadrillion.
Re: A Better Way to Store Password Hashes?
#23Earlier quoted context omitted.
_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…
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 found that the average password has only 40.5 bits o…
[deleted]
Re: A Better Way to Store Password Hashes?
#24Earlier quoted context omitted.
_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…
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 found that the average password has only 40.5 bits o…
The point is that nothing will "save" a single user for whom there is a dedicated attacker. But you can make it uneconomical to attack the whole database. That's what bcrypt, scrypt et al do.
Re: A Better Way to Store Password Hashes?
#25Earlier quoted context omitted.
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?
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 str…
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.
Re: A Better Way to Store Password Hashes?
#26This won't make an appreciable difference if your entire db is captured by the attacker (ala LinkedIn). You are just asking them to buy a box (rent a virtual server) with more RAM because the equals operation just became memory intensive. A machine with 128GB of RAM will still give a near-constant result to "does my test hash equal the user's password?"
"Just add more fake hashes", you say. To get around the above, you have to use billions upon billions of fake hashes. The database abuse will eventually catch up to you.
This is trying to accomplish what bcrypt and scrypt do using tunable parameters, which is force the attacker to spend significantly more to break passwords than it costs you to test passwords (because they are doing it billions of times, you are doing it once). Personally, I trust the math more.
Re: A Better Way to Store Password Hashes?
#27Wouldn't this setup mean that I can hack into your system with almost any password? As there is no direct connection AND you fill up with dummy hashes - doesn't that effectively mean you drive up the chances of a hack? The more fake hashes, the higher the probability that any random password I brute force may result in a match against the set of hashes. And if that happens - boom, I am in. Or am I missing something?
Definitely not. The back-end takes a user's password and hashes it with that user's specific salt. Then the result must be in the table. Another user's password will not work. What you are worried about is a result existing in the table, even with the wrong password. That can only happen if you have a hash collision. The article on collisions I cited ( http://preshing.com/20110504/hash-collision-probabilities ) says…
Ah OK. So effectively the salt becomes the foreign key ;-)
Re: A Better Way to Store Password Hashes?
#28Wouldn't this setup mean that I can hack into your system with almost any password? As there is no direct connection AND you fill up with dummy hashes - doesn't that effectively mean you drive up the chances of a hack? The more fake hashes, the higher the probability that any random password I brute force may result in a match against the set of hashes. And if that happens - boom, I am in. Or am I missing something?
[deleted]
Re: A Better Way to Store Password Hashes?
#29This won't make an appreciable difference if your entire db is captured by the attacker (ala LinkedIn). You are just asking them to buy a box (rent a virtual server) with more RAM because the equals operation just became memory intensive. A machine with 128GB of RAM will still give a near-constant result to "does my test hash equal the user's password?" "Just add more fake hashes", you say. To get around the above, y…
This is absolutely only to be used with bcrypt or scrypt, not instead of.
Facebook has 100PB of data, but all the password salts and hashes for their 800m active users fits on a single USB stick. One maligned employee and that data can walk right out the door.
The theft of all your users' passwords should make one heck of a racket on its way out of your data center. A thief should need the equivalent of a 747 to fly them out of there.
With this technique, Facebook could fairly easily make their salts and hashes fill 1PB of drives. You're not sneaking out of the data center with that tucked in your sock!
Re: A Better Way to Store Password Hashes?
#30Earlier quoted context omitted.
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?
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 str…
[deleted]