Is it a mistake to use a password that has previously been used (by anyone ever)?

Question

A few months ago, kutschkem answered a question about HIBP with this:

Let's say every person on earth has used ~1000 passwords so far. That makes approximately 10 trillion passwords, which is ~2⁴³ if I am not mistaken. Choosing any existing password at random is thus about as good as a truly random 8-9 character case-sensitive character password. Not very good. See this answer.

That basically means that, in theory, not only should one not reuse a password, one should not reuse a password that has been used by anyone ever. Passwords that have been used before are basically one big dictionary attack waiting to happen.

I was reminded again by the discussion between Mike Ounsworth and Conor Mancone in the comments on this answer about blacklisting the top N passwords versus the entire HIBP database.

Is kutschkem's math right? Does this make the conclusion right?

Answer 1

The math may be right. One could refine and complicate it as much as desired, but it doesn't really add to the point. So I'll leave it be.

Also, in practice it is easier—and might be faster—to check for any random character password with a fixed length than to check unique passwords from a list. A password list with 2⁴³ passwords with an average password length of 8 characters would be about 64 TB in size, if my calculation is correct. This would have to be stored somewhere in close proximity to the processor to be read with the same speed as the processor calculates the hashes.

The conclusion however, is not right: The important question is not if a password has ever been used, but if the password has ever been included in a breach.

If the breached passwords were thereafter publicly disclosed, they are now available on the internet. The passwords are now not just any passwords that have been used, but a very small subset of them. And to make things worse, this subset is used in wordlists by a lot of people around the world to check if they have been reused. So the chance that someone checks a hash against this password is a lot higher than the chance of him or her checking a hash against an unknown password, even if it has been used somewhere.

So I would not use a password that is included in the HIBP database, simply for the reason that those passwords have a higher chance to be included in wordlists.

Answer 2

Mike Ounsworth here (author of the thread you're referencing)

This is a great excuse to do some back-of-the-envelope math! The factor to think about here is that when you're getting to numbers like 2⁴³, you have to start factoring in the number of hard drives, CPUs, and electricity required to store and use that data.

To make math easy, let's say each of those 2⁴³ password is stored as a SHA-1 hash (as is the case with the HIBP database). Each SHA-1 value is 160 bits, or 20 bytes. 2⁴³ * 20 bytes = 176 terabytes. Larger than my laptop, but chump change for a cloud service.

Going the other direction, imagine you have a database of all 2⁴³ plaintext passwords. You get your hands on the hash of an admin's password and you want to brute-force it against your database. Let's take the simplest and most insecure case; it's an unsalted SHA-256 hash. This is the problem that bitcoin mining rigs were built for baby! Let's take this bitcoin miner as a rough benchmark: $3,000 USD, 50TH/s (tera-hash per second), and consumes 1975 W.

According to my hasty math, one of those units would take 2^43 / (50,000,000,000,000 / s) = 0.2s to try all passwords, assuming that a database can feed 176 TB of data to it that quickly.

In reality, passwords are (well, should be) stored with salted PBKDF2 or Argon2. This changes the game considerably as these hash functions are intended to prevent this kind of attack. These hash functions can be tuned as slow as you want at the time that you store the password as a hash. Say you tune it to be ~ 0.1 s per hash. Now suddenly you're looking at numbers like "thousands of centuries", and "power consumption of the planet".

---

TL;DR: this is a great question to ask!

The answer is that if you're going to choose a password that you can remember and might collide with someone else on the internet, then your choice of password is less important than the site you're giving it to storing it securely.

IMHO, in choosing a password, you're not trying to prevent a dedicated enough attacker from ever cracking it; instead you're trying to make it hard enough that they'll go after a softer target. "I don't need to outrun a bear, I just need to outrun my friend".

If course, if you use a password manager with a completely random 32-char password, then you're getting into the cryptographic strength realm of "age of the universe", and "power output of a large star". So do that!

Answer 3

I see some logical errors with that statement - first of all, how would you ever know it?
If Joe Schmoe used a specific password in 2007 - 2009 for his Windows PC, and it was never hacked, and the machine is trashed and burned, there would be no record of it anywhere.
Therefore, unless a password was hacked or published in any other way, you cannot know, and so cannot avoid reusing it.

Aside from that, of the estimated 2^43 passwords ever used, probably 2^42.9 are duplicates, and the list fits on one hard disk.

Answer 4

A mixed-case alphanumeric password for lengths between 1 and 9 (inclusive) has a key space of 13,759,005,997,841,642, which is between 2⁵³ and 2⁵⁴.

The math is a decent ballpark guess, but not a reasonable back-of-the-napkin guess.

However, just because the math is wrong does not mean that conclusion is invalid.

Humans are bad at passwords. We memorize them, reuse them, and generate them from easy to remember words.

So, a naive brute force of passwords will generate a lot of possibilities that people have never memorized, have never reused, and aren't similar to words in a human language.

Using a dictionary of previously leaked passwords is probably the fastest way to guess passwords, because you know that someone, somewhere has used that password before. Humans being human, it's more probable that this password will be used again than it's probable that any random value matches a password.

Because of this, my firm opinion is that it's a mistake to use a password that wasn't randomly generated, but I'll agree with the sentiment that it's a mistake to use a password that anyone has used before regardless of how it was generated.

Answer 5

Is kutschkem's math right?

What kutschkem seems to be saying is:

1. If about 7⋅10⁹ people chose 1000 passwords each, there would be about 2⁴³ passwords in use.

   This seems like a reasonable approximation: log₂(1000⋅7⋅10⁹) ≈ 42.7; round it up to 43. (I am not assessing the empirical question of how many passwords people have chosen—only verifying the multiplication!)

2. There are about 2⁴³ 8-character passwords.

   This is a slightly low estimate: If we count only US-ASCII alphabetic passwords, with case distinctions (‘truly random 8-9 character case-sensitive character password’), there are 2⋅26 possible characters, and log₂[(2⋅26)⁹] ≈ 45.6; round it down to 43.

But if everyone chose 8-character alphabetic passwords uniformly at random like this, it is essentially guaranteed that they'd collide at some point!

Suppose we choose passwords uniformly at random from a space of k possibilities. If there are n passwords in the world the probability of a collision by the birthday paradox is at most n²/k. When k and n are the same, that bound doesn't mean anything, but the probability is extremely close to 1.

But suppose all picked our 1000 passwords each independently and uniformly at random from 2¹²⁸ possibilities—say, 10-word diceware phrases with a 7776-word list, or 20-character graphic US-ASCII strings. Then n = 2⁴³ and k = 2¹²⁸, so the probability of a collision between any two of the passwords the seven billion people have chosen is at most n²/k = (2⁴³)²/2¹²⁸ = 2⁸⁶⁻¹²⁸ = 1/2⁴²—less than one in a trillion.

I recommend that if you want password security you should let a computer pick a password for you uniformly at random from over 2¹²⁸ possibilities. (For services that use unsalted password hashes, maybe double the length to mitigate multi-target attacks.)

Does this make the conclusion right?

The conclusion—one should not reuse a password that has been used by anyone ever—seems to take as a premise that my goal as the user is to prevent anyone form guessing the password. Maybe I as a user don't care if someone can guess my password and it's more important that I can just remember it. One might make throwaway accounts all the time—see, e.g., BugMeNot—to subvert advertising-driven mass surveillance that relies on tracking users by login for higher-value advertisements.

Answer 6

I think it would depend on how passwords are handled on the targeted system.

For a system that uses best practice salting and hashing, password lists are only useful in a brute-force attack. An attacker would have to compile a hash lookup for each account, using its specific salt. That's effectively a brute-force attack on the password file (or table); with cryptographically secure hashing, it's infeasible on a large password space (hashing each password takes a non-trivial amount of time). An attacker might prioritize known passwords ahead of all other possibilities, but that's still a large space.

For a system that uses less than best practice, it would depend on the specific security flaws as to how a list of known used passwords might accelerate an attack.

Since you can't be certain what measures are in place on any given system, it might be prudent to avoid likely known passwords, but you aren't necessarily giving a hacker an open door by using an obscure password that happens to have been used by someone else at some time.

Answer 7

I don't think any math is needed other than set theory. The purpose of a password is to act as a method of authenticating, you are who you say you are because you know the secret. This "secret" ideally should be random to prevent brute force attacks. That is, attacks on the platform the credentials are for. Brute forcing is a last resort as it isn't efficient, you're literally blindly trying every permutation possible for that "secret." Here you have three sets:

1. The set of all possible permutations.
2. The subset of #1, the set of all possible permutations used by everyone, ever, known or not.
3. The subset of #2, the set of all possible permutations that are known (breaches).

Number 3 is only useful to use as a way to trim the attack because it's permutation count is lower than #2 and certainly lower than #1. Logically, one can assume that #2 isn't feasible just by the fact that no one has a collection of every password used ever. However, the important point I think is that #2 wouldn't be that useful on it's own. The idea is to trim down your attack to increase it's efficiency. Unless the target is a high valued target, #2 is likely already too large to be useful for trimming the attack. A dictionary attack, using actual dictionary terms or just common password variants, is useful largely because the permutation space is that much smaller than exhaustive brute force. #2 increases that space to the point of being impractical for the attacker just as much as the user.

Ironically, I'd argue that if #2 actually were released by some magic, avoiding any permutation in that list may make your more susceptible, as you're decreasing the potential permutation space an attacker would need to cover, for the same password length.

An attacker, if #2 was available, would very likely still try and only use it as a tool to make a better brute force attack by creating a dictionary from the highest frequency passwords from that set.

With that said, it is worth noting that the entirety of HIBP database still represents a relatively small subset of all permutations. Thus, it is still efficient to use the entirety of it as a dictionary attack. An attacker may still trim to the highest frequency if they're wanting more efficiency, but it wouldn't be a requirement, unlike #2.

Answer 8

There are no realistic conditions under which it is beneficial to reduce the set from which passwords are selected. Intentionally eliminating some passwords from consideration just shrinks an attacker's search space.