Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Better Way to Store Password Hashes?

opine.me

Post reply on HN
Print view View original

11–20 of 59 posts

Re: A Better Way to Store Password Hashes?

#11

Post by dekz »

zaroth wrote: post #9
gibybo wrote: post #7

I am skeptical that this method adds any protection to a brute force attack relative to a standard implementation of PBKDF2 hashes stored with the users. With proper salts, we have no advantage cracking a password in a database of 10 users or 10 million users. LinkedIn didn't have any salts. The effectiveness of brute forcing a password is determined entirely by how many passwords they can test for a particular user…

It's a question of sizing up what resources the attacker has, versus what they will need to succeed in an attack. We want to make password cracking extremely difficult. It's a problem a big site should want to throw some money at. Today, we make it hard by requiring lots of CPU. Another commenter said 'scrypt' -- yes, we want to make it hard by requiring lots of RAM too. Here's another way to make it hard -- now you'…

> We want to make password cracking extremely difficult. It's a problem a big site should want to throw some money at.

Maybe we should start heading back in the other direction, like making our stacks secure and not expecting a data leak in the first place. Sure be prepared with your time/memory hard hash constructs, it's not a solution to writing insecure code in the first place.

Re: A Better Way to Store Password Hashes?

#12

Post by michaelfairley »

dfox wrote: post #5
sillysaurus wrote: post #2

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…

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.

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?

Re: A Better Way to Store Password Hashes?

#13

Post by Jarred »

This sounds interesting. But, in implementing this, what's the purpose of storing password hashes in your own database? Wouldn't it be safer (and maybe even faster) for a centralized service to handle checking the existence of password hashes and storing them?

Compromising this central database would be meaningless because it would only store password hashes. If an intruder accessed it, they'd just have billions of long strings of random characters -- they wouldn't know where it came from/who uses it.

I think the biggest downside would be that the larger number of password hashes, the more likely duplicates exist. The answer to that, I think, is more randomness. But, I don't know how soon/if that would be a problem.

Another potential downside is performance. Would making a request to this other server make logging in slower? I think the answer to this question depends on the implementation, but there's a guranteed latency of another server to contact before logging in/registering. Beyond that, I think, would be getting too much into the implementation details.

Note -- I know very little about cryptography, but I'd love to learn more.

Re: A Better Way to Store Password Hashes?

#14

Post by zaroth »

michaelfairley wrote: post #8
zaroth wrote: post #6

Earlier quoted context omitted.

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…

_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 of entropy. I'm afraid even scrypt will not save you from 40 bit entropy passwords.

Re: A Better Way to Store Password Hashes?

#15

Post by [deleted] »

michaelfairley wrote: post #8
zaroth wrote: post #6

Earlier quoted context omitted.

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…

_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…

[deleted]

Re: A Better Way to Store Password Hashes?

#16

Post by px1999 »

gibybo wrote: post #10
zaroth wrote: post #9

Earlier quoted context omitted.

It's a question of sizing up what resources the attacker has, versus what they will need to succeed in an attack. We want to make password cracking extremely difficult. It's a problem a big site should want to throw some money at. Today, we make it hard by requiring lots of CPU. Another commenter said 'scrypt' -- yes, we want to make it hard by requiring lots of RAM too. Here's another way to make it hard -- now you'…

Ok, requiring the attacker to download several terabytes could be an interesting advantage. Could we also achieve that by inserting billions of fake users in a traditional [user, salt, hash] setup?

You could, but I don't really see any difference between this and just slapping many tb of unrelated data in the database - the smart attacker will realise that a bunch of accounts are fake and just join to a table that holds only data for real users before extracting the info.

That's part of the elegance (well, it's something other than elegant because it uses a whole mass of data) of the original solution - all of the data could be significant in checking a single password so none can be discarded.

Re: A Better Way to Store Password Hashes?

#17

Post by zaroth »

michaelfairley wrote: post #12
dfox wrote: post #5

Earlier quoted context omitted.

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.

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 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).

Re: A Better Way to Store Password Hashes?

#18

Post by [deleted] »

dfox wrote: post #5
sillysaurus wrote: post #2

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…

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.

[deleted]

Re: A Better Way to Store Password Hashes?

#19

Post by [deleted] »

zaroth wrote: post #17
michaelfairley wrote: post #12

Earlier 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]

Re: A Better Way to Store Password Hashes?

#20

Post by zaroth »

px1999 wrote: post #16
gibybo wrote: post #10

Earlier quoted context omitted.

Ok, requiring the attacker to download several terabytes could be an interesting advantage. Could we also achieve that by inserting billions of fake users in a traditional [user, salt, hash] setup?

You could, but I don't really see any difference between this and just slapping many tb of unrelated data in the database - the smart attacker will realise that a bunch of accounts are fake and just join to a table that holds only data for real users before extracting the info. That's part of the elegance (well, it's something other than elegant because it uses a whole mass of data) of the original solution - all of…

As the OP, I'd say it's as elegant as securing your bike by locking a cinder block to it! ;-)
Post reply on HN