2 ms·

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 th

by geofft 8y ago

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 someone took a shortcut and used your list.

throwawaymath 8y ago
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 through those 20 trillion in an online brute force attempt. Eventually you are only constrained by computational resources. If the passwords are cryptographically secured, it's fine if any one of them is published on the internet if you cannot associate it with any given user. If they're not cryptographically secured, this won't meaningfully reduce your already poor security anyway.
- geofft 8y ago
  But what is the harm in blocking all 20 trillion such passwords? Do you expect to have any false positives?
  - throwawaymath 8y ago
    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.
    - geofft 8y ago
      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.)
      - throwawaymath 8y ago
        I'm actually withdrawing my argument, as I mentioned in the sibling comment to this one. The HIBP API does introduce a lot of latency, but you can do this checking with Troy Hunt's entire password database locally. He provides it for free.
        geofft 8y ago
        You still haven't answered or conceded my question: is the online API too much latency? You only need to check it when changing a password or registering a new account, not when validating a password. The world has decided that making me go through a Google CAPTCHA when registering a new account - a process that takes me several seconds of active mental effort - is fine. If the check takes even 1 second of server time, is that noticeable?
    - darkpuma 8y ago
      Bloom filters! B-trees! There are MUCH smarter ways to implement this than grepping a list line by line. I mean seriously who the hell would do that... If your bio isn't complete BS then surely you understand that proposed implementation is BS.
      - throwawaymath 8y ago
        To clarify the context I was talking about, I mean online checking of a hashed user password against Troy Hunt's HIBP database of hashed passwords. The original context of this discussion was an API, not a local copy of the database. That being said I'm actually going to concede this argument, because on further investigation Troy Hunt provides the entire copy of his database freely for local lookups. Once you hash the user password to match the database hashes you can introduce the optimizations you mentioned, and in any case it shouldn't introduce intolerable latency to do that lookup locally.
- Dylan16807 8y ago
  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.
rmtech 8y ago
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.
- geofft 8y ago
  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.)
  - rmtech 8y ago
    Well there is one important factor about these 20 trillion passwords: are they associated with real user accounts? If not then it really doesn't matter that they got published. They're useless to hackers without knowing what email to type in. The attack model is that the attacker actually has to log into a website and you don't get 20 trillion attempts.
    - Dylan16807 8y ago
      Never underestimate the ingenuity of the user. They might search for a list of good passwords, find it, and pick one. > The attack model is that the attacker actually has to log into a website Not to find the password. If it was then nobody would get upset about plaintext password storage.

by geofft 8y ago

throwawaymath 8y ago

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 through those 20 trillion in an online brute force attempt. Eventually you are only constrained by computational resources. If the passwords are cryptographically secured, it's fine if any one of them is published on the internet if you cannot associate it with any given user. If they're not cryptographically secured, this won't meaningfully reduce your already poor security anyway.

geofft 8y ago
But what is the harm in blocking all 20 trillion such passwords? Do you expect to have any false positives?
- throwawaymath 8y ago
  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.
  - geofft 8y ago
    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.)
    - throwawaymath 8y ago
      I'm actually withdrawing my argument, as I mentioned in the sibling comment to this one. The HIBP API does introduce a lot of latency, but you can do this checking with Troy Hunt's entire password database locally. He provides it for free.
      - geofft 8y ago
        You still haven't answered or conceded my question: is the online API too much latency? You only need to check it when changing a password or registering a new account, not when validating a password. The world has decided that making me go through a Google CAPTCHA when registering a new account - a process that takes me several seconds of active mental effort - is fine. If the check takes even 1 second of server time, is that noticeable?
  - darkpuma 8y ago
    Bloom filters! B-trees! There are MUCH smarter ways to implement this than grepping a list line by line. I mean seriously who the hell would do that... If your bio isn't complete BS then surely you understand that proposed implementation is BS.
    - throwawaymath 8y ago
      To clarify the context I was talking about, I mean online checking of a hashed user password against Troy Hunt's HIBP database of hashed passwords. The original context of this discussion was an API, not a local copy of the database. That being said I'm actually going to concede this argument, because on further investigation Troy Hunt provides the entire copy of his database freely for local lookups. Once you hash the user password to match the database hashes you can introduce the optimizations you mentioned, and in any case it shouldn't introduce intolerable latency to do that lookup locally.
Dylan16807 8y ago
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.

rmtech 8y ago

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.

geofft 8y ago
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.)
- rmtech 8y ago
  Well there is one important factor about these 20 trillion passwords: are they associated with real user accounts? If not then it really doesn't matter that they got published. They're useless to hackers without knowing what email to type in. The attack model is that the attacker actually has to log into a website and you don't get 20 trillion attempts.
  - Dylan16807 8y ago
    Never underestimate the ingenuity of the user. They might search for a list of good passwords, find it, and pick one. > The attack model is that the attacker actually has to log into a website Not to find the password. If it was then nobody would get upset about plaintext password storage.