Prevent users registering with passwords from data breaches • Hacker News Board

Re: Prevent users registering with passwords from data breaches

#21

Post by geofft » Sat, Jan 19, 2019, 1:56 AM UTC

throwawaymath wrote: post #13

rmtech wrote: post #12

Earlier quoted context omitted.

If the password actually has a lot of entropy but it appears in a breach then that's some fairly strong evidence that the user is reusing it. Specifically if it appears n times in the HIBP database you should assign at least roughly 1/n probability that the user is reusing it. So if you assign disutility -V to letting a user have a known username + password combo and utility U to letting a user sign up with a known p…

> If the password actually has a lot of entropy but it appears in a breach then that's some fairly strong evidence that the user is reusing it. I'm not talking about scenarios where you can associate the password with a specific user.

You can in fact associate the password with a specific user - the fact that that exact password is being reused is, by itself, strong mathematical evidence that it's the same user or someone they told the password to, because it is basically mathematically impossible that anyone else could generate the same password by coincidence (unless they're both using a password generator that doesn't have good random seeds or is otherwise deterministic, in which case you should be banning the password anyway).

Re: Prevent users registering with passwords from data breaches

#22

Post by throwawaymath » Sat, Jan 19, 2019, 1:56 AM UTC

geofft wrote: post #16

throwawaymath wrote: post #15

Earlier quoted context omitted.

No, it's not the correct conclusion. Virtually no passwords are safe under an offline brute force attempt if they haven't been protected by a robust key derivation function and a randomized salt. If the password has been protected like that, you not only need to try all 20 trillion of those hypothetical passwords; you also need to try them with the correct salt. And this is aside from the fact that you won't even rip…

But what is the harm in blocking all 20 trillion such passwords? Do you expect to have any false positives?

The harm is the principle of it. You should not design a system that greps through e.g. every single breach dump for arbitrary passwords every single time someone tries to sign up for your service. That's maddeningly inefficient.

Re: Prevent users registering with passwords from data breaches

#23

Post by geofft » Sat, Jan 19, 2019, 1:58 AM UTC

throwawaymath wrote: post #19

simcop2387 wrote: post #9

Earlier quoted context omitted.

If it's published as a list of known passwords, yes. That's roughly 1.50463276905253e-21 percent of the potential passwords for that character space (assuming 64 possible characters). If it's know that those are passwords then they're much much easier to test against than the 1329227995784915872903807060280344576 possibilities.

First of all, in an online brute forcing scenario attackers will never get through the entire 20 trillion. Even if they knew for certain that the target victim's password satisfied the precise constraints of the passwords published in that list, they'd need around 2 years (with reasonable assumptions of millisecond latency) of constant, 24/7 attempts to run through them all. This is assuming there is no rate limiting…

No, you're not screwed either way, because there are trillions of trillions of trillions of possible 20-character passwords. So even if they can get one trillion attempts per second, it will still take an attacker trillions of trillions of seconds to brute-force all possible 20-character passwords, which is longer than the lifetime of the universe.

Re: Prevent users registering with passwords from data breaches

#24

Post by rmtech » Sat, Jan 19, 2019, 1:58 AM UTC

throwawaymath wrote: post #8

bijection wrote: post #6

Earlier quoted context omitted.

Any known password is no longer a particularly strong one.

That doesn't make sense. If I publish a list of 20 trillion alphanumeric passwords, each of which is 20 characters long, your thesis is that no one should ever use any of those passwords again?

> publish a list of 20 trillion alphanumeric passwords, each of which is 20 characters long, your thesis is that no one should ever use any of those passwords again?

No because they each still have a very low probability.

You have to be Bayesian about this: a list of one trillion passwords that have no further distinguishing information about each one of them cannot be assigned a probability of > 1/(1 trillion)

In a data breach, a given password appears next to a particular username or email, which means it has a very high probability of being the password for that account.

Re: Prevent users registering with passwords from data breaches

#25

Post by rmtech » Sat, Jan 19, 2019, 2:00 AM UTC

geofft wrote: post #11

throwawaymath wrote: post #8

Earlier quoted context omitted.

That doesn't make sense. If I publish a list of 20 trillion alphanumeric passwords, each of which is 20 characters long, your thesis is that no one should ever use any of those passwords again?

Yes, that is the correct conclusion. There are about 0.7 trillion trillion trillion alphanumeric passwords 20 characters long (62^20). Banning 20 trillion of them is a drop in the oceans, and nobody using a password generator is statistically likely to generate them within the expected lifetime of the universe, let alone of any given website. So, if you see one of those passwords, it is overwhelmingly likely that som…

Editing since I misunderstood you:

If you publish one trillion passwords from a large space then each one of them gets a probability boost (of approximately 1/1 trillion), though not enough to ban them, especially if they are not actually associated with accounts.

The danger with using a rare but breached password is that there is actually quite a high chance that it was breached from your account elsewhere.

Re: Prevent users registering with passwords from data breaches

#26

Post by geofft » Sat, Jan 19, 2019, 2:02 AM UTC

throwawaymath wrote: post #22

geofft wrote: post #16

Earlier quoted context omitted.

But what is the harm in blocking all 20 trillion such passwords? Do you expect to have any false positives?

The harm is the principle of it. You should not design a system that greps through e.g. every single breach dump for arbitrary passwords every single time someone tries to sign up for your service. That's maddeningly inefficient.

Why is it inefficient? Is the HIBP API too slow? How slow is too slow?

My principle is that you should not let people sign up with breached passwords at all - don't make judgment calls about which breaches matter, and whether you think it's the same user or not, or the password is strong enough or not. Just ban the passwords. (Remember that no actual data breach contains 20 trillion passwords.)

Re: Prevent users registering with passwords from data breaches

#27

Post by throwawaymath » Sat, Jan 19, 2019, 2:02 AM UTC

geofft wrote: post #23

throwawaymath wrote: post #19

Earlier quoted context omitted.

First of all, in an online brute forcing scenario attackers will never get through the entire 20 trillion. Even if they knew for certain that the target victim's password satisfied the precise constraints of the passwords published in that list, they'd need around 2 years (with reasonable assumptions of millisecond latency) of constant, 24/7 attempts to run through them all. This is assuming there is no rate limiting…

No, you're not screwed either way, because there are trillions of trillions of trillions of possible 20-character passwords. So even if they can get one trillion attempts per second, it will still take an attacker trillions of trillions of seconds to brute-force all possible 20-character passwords, which is longer than the lifetime of the universe.

Now keep in mind that 1) it is possible to choose a strong password with fewer than 20 characters, and 2) most people will not choose a password that long.

Extrapolating further, this "policy" would disallow people from choosing passwords below a certain length, because it's theoretically plausible someone has published the set of all possible strings fewer than n characters long.

Re: Prevent users registering with passwords from data breaches

#28

Post by Dylan16807 » Sat, Jan 19, 2019, 2:03 AM UTC

throwawaymath wrote: post #15

geofft wrote: post #11

Earlier quoted context omitted.

Yes, that is the correct conclusion. There are about 0.7 trillion trillion trillion alphanumeric passwords 20 characters long (62^20). Banning 20 trillion of them is a drop in the oceans, and nobody using a password generator is statistically likely to generate them within the expected lifetime of the universe, let alone of any given website. So, if you see one of those passwords, it is overwhelmingly likely that som…

No, it's not the correct conclusion. Virtually no passwords are safe under an offline brute force attempt if they haven't been protected by a robust key derivation function and a randomized salt. If the password has been protected like that, you not only need to try all 20 trillion of those hypothetical passwords; you also need to try them with the correct salt. And this is aside from the fact that you won't even rip…

If you have a password manager you can and should create passwords that are completely safe against offline brute force. 20 characters works for that. Nothing has 2^119 computation power to break it.

Blocking a list of 20 trillion passwords is probably overkill if you have a slow hash. But with a fast hash it's the difference between "impossible" and "less than one GPU-week".

And if it's easy to block, you might as well do it. There's no upside to letting people use already-posted 20 character strings.

Re: Prevent users registering with passwords from data breaches

#29

Post by geofft » Sat, Jan 19, 2019, 2:04 AM UTC

rmtech wrote: post #25

geofft wrote: post #11

Earlier quoted context omitted.

Yes, that is the correct conclusion. There are about 0.7 trillion trillion trillion alphanumeric passwords 20 characters long (62^20). Banning 20 trillion of them is a drop in the oceans, and nobody using a password generator is statistically likely to generate them within the expected lifetime of the universe, let alone of any given website. So, if you see one of those passwords, it is overwhelmingly likely that som…

Editing since I misunderstood you: If you publish one trillion passwords from a large space then each one of them gets a probability boost (of approximately 1/1 trillion), though not enough to ban them, especially if they are not actually associated with accounts. The danger with using a rare but breached password is that there is actually quite a high chance that it was breached from your account elsewhere.

I think we're reading the question differently - I'm responding to the question of, what if you publish a tiny subset of the passwords, 20 trillion out of 0.7 trillion trillion trillion. That does change the probabilities.

I do agree that if the entire space of possible passwords is only 20 trillion, that doesn't change the probabilities. But there are over 20 trillion eight-character alphanumeric passwords. So, I would actually say you should ban them all, because you should insist your passwords are at least eight characters long. :-)

Edit: yes, agree, in practice the probability boost is not very much. I'm just saying you may as well ban them on the assumption that the HIBP API will do so at its current level of performance. (20 trillion is a ridiculous number, because it's much larger than any possible breach and yet much smaller than any meaningful password space, so any arguments about it are going to be inherently silly in some fashion. My current silly assumption is that the HIBP API is capable of ingesting 20 trillion breached passwords with no performance hit.)

Re: Prevent users registering with passwords from data breaches

#30

Post by dwighttk » Sat, Jan 19, 2019, 2:04 AM UTC

I need password fields to:

1)not silently fail when I try a 64 character (or 32 character) password

2)not fail and say my password is "too short" when it is 32 characters and you have an unrevealed maximum password length of fewer characters than that.

3)just all-around quit failing when my password is totally fine, it's a quasi-random string of letters, numbers, and symbols and I'll never type it...

oh yeah

4)don't disable pasting in the password field

4b)IF you do, freaking let me see what I've typed. I promise to not enter the password in a place someone can shoulder surf. Trust me that's WAY down on the threat list for my life.

Then, and only then, if you really want, keep me from registering with a breached password. But you had better tell me that is what is going on.