6 ms·

It's a fair point that raw password count is available. But that value is an absolute number, without any in-API context of the total size of the corpus. This

by royce 9y ago

It's a fair point that raw password count is available. But that value is an absolute number, without any in-API context of the total size of the corpus. This makes expressing relative rarity only possible by hard-coding the total size of the corpus into a calculation. Put another way: the 20,000th position has a frequency value of "7889". But what does that mean? Where is that in the distribution of password frequency? It's impossible to tell, without manually constructed context that will change over time as the total number of passwords in his corpus expands. But more crucially, there is no way to tell relative rank ("is this password in the top 20k?") using the API that I can see. That would make using the top X much easier. But with the K-anonymity "feature", there's no way to do that that I can see.

jasonpeacock 9y ago
I don't follow - how is the relative rarity better than absolute frequency? What really matters is how common your password is - not how highly it's ranked in a compromised password list, which has no relevance to how common it may be. You want to filter on users choosing a password that's been re-used across all compromised more than N times. Filtering users on choosing a password that ranks N of M on a list of compromised passwords doesn't tell the user how bad that password is. In fact, once you get to the rail, the ranking is basically based on sort order and become irrelevant?
- royce 9y ago
  The ranking in Troy's list is based entirely on how common the words are. Here are the top 10, with their relative frequency: c4a8d09ca3762af61e59520943dc26494f8941b:123456 (20760336) f7c3bc1d808e04732adf679965ccc34ca7ae3441:123456789 (7016669) b1b3773a05c0ed0176787a4f1574ff0075f7521e:qwerty (3599486) 5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8:password (3303003) 3d4f2bf07dc1be38b20cd6e46949a1071f9d0e3d:111111 (2900049) 7c222fb2927d828af22f592134e8932480637c0d:12345678 (2680521) 6367c48dd193d56ea7b0baad25b19455e529f5ee:abc123 (2670319) e38ad214943daad1d64c102faec29de4afe9da3d:password1 (2310111) 20eabe5d64b0e216796e834f52d61fd0b70332fc:1234567 (2298084) 8cb2237d0679ca88db6464eac60da96345513964:12345 (2088998) So ... what is the "right" threshold for N? $ for topx in 1 100 1000 5000 10000 20000 50000 100000 200000 500000 1000000; do \ echo -n "$topx: "; head -n ${topx} pwned-passwords-2.0.txt | tail -1; done 1: 7C4A8D09CA3762AF61E59520943DC26494F8941B:20760336 100: 482FA19D5C487CB69ACDA19EEE861CC69D82CC94:272371 1000: 5B9FE558F673D63309BEB13BFA5DA6C30A3CA1BF:64912 5000: FE648FC459A6F6EF6CD347BEE3D494766239BBB5:19860 10000: 2682A3DBA7A1452EE7EE9980F195C6A768055DA6:11055 20000: 53490A3C8567342B57B6A4FF24908DF73182B357:6309 50000: 7517CD23A308BBCD05E5AD24AA6AD054237ED470:3153 100000: BA6D6A41B9548C523833627A8B0E5170558BE1EA:1752 200000: E50E6893264519636E90E95B6B1A85D0A691E0B1:931 500000: AF8DF653177BBB3FEE2DA68D314B94CB5281B4F3:381 1000000: BDD57A4CAA691A3441C1190C6F087B58B2EE3EF6:186 2000000: C824AF24AA8F2FD99AD6842DC0E4B49100D96161:93 10000000: 352DB7177AB7848DF1C102234401097FE40EB87D:22 The third field indicates how common the password is in the corpus (for example, the single most common password - "123456" - appears in the corpus 20,760,366 times). So ... based on this data ... what is a reasonable value for that count, such that if the value is exceeded, the user should be disallowed from using the password? How much real-world online or offline resistance is provided by disallowing, say, passwords used at least 186 times in the corpus (roughly a million passwords, though 5201 passwords are at the 186 mark)? (The answer should be self-evident; if it isn't, I can provide more background). Put another way ... if the corpus was only 1M in size, those right-hand values would be much smaller. How could you determine the threshold then? What I'm trying to illustrate here is that it's not the absolute value of that commonality number that matters; it's the relative rank. But that relative rank can't be determined via the API; you must analyze the entire corpus directly - and then discard the vast majority of it for blacklisting purposes. I totally get that the threshold might vary per implementation. But it varies much less once the hash is slow enough, and the authentication service is suitable rate-limited. In other words, any system that would get real benefit from a 1-million-word blacklist is one that needs to be improved elsewhere instead. But Troy didn't provide any guidance about that, or even how to judge for yourself what the threshold might be. He just provided an API to blacklist a corpus of passwords that is three orders of magnitude larger than a properly designed system would ever need. 1. https://blogs.dropbox.com/tech/2012/04/zxcvbn-realistic-password-strength-estimation/ https://blogs.dropbox.com/tech/2012/04/zxcvbn-realistic-pass...
rspeer 9y ago
Why would a password that occurs in this list, but rarely, be safer? Attackers aren't going to skip the rare ones.
- royce 9y ago
  Because: 1) In an online attack, against a properly-configured service, even if password spraying is used, only the first few thousand passwords can be tried before rate-limiting, CAPTCHAs, etc. kick in. Would a user with a known leaked password at a different site be vulnerable to an online correlation attack? Yes. And that's why some big services supplement their approach by proactively searching for those leaks and forcing a password reset for those specific users. 2) In an offline attack, when the passwords are properly hashed with a modern slow hash, even an expensive GPU or FPGA cluster would take weeks to exhaust a 10,000 word dictionary against a large user corpus, and a significant amount of time even when a single user is targeted. Would users with '123456' get cracked pretty quickly? Yes. And that's why the top X are forbidden - to make offline attackers have to dig deeper into their wordlists (and thereby also their pocketbooks) to crack a password in a useful amount of time.
  - rspeer 9y ago
    I find it hard to believe that you could set a cutoff of passwords that have been leaked but that you could rely on an attacker not to try. These passwords are more useful guesses than anything a password cracker would make up out of components. XKCD considers a password that's one of 2^28 possibilities "easy" to guess, and provides a well-regarded strategy [1] for coming up with a password that's one of 2^44. Passwords in this list are one of 2^29. [1] https://xkcd.com/936/ https://xkcd.com/936/
    - royce 9y ago
      Random passphrases are indeed a good idea. XKCD #936 advocates for 4 words randomly selected from a 6000-word dictionary, which is 6000^4, or ~1.296 × 10^15, which isn't actually that strong if the service in question has chosen a weak password hashing algorithm. When using pure bruteforce or masks (not a dictionary or hybrid attack) against a large-ish corpus of passwords (say, a few million) a system with 6 GTX 1080s can realistically try 8.2 billion SHA1-hashed passwords per second, which would exhaust the entire XKCD 936 keyspace in about 45 hours. (If you bump it up to five words from a 20,000 word dictionary, you get ~3.2x10^21 possibilities, which is better.). And if you focus on a single hash, that SHA1 rate jumps to ~32 billion hashes per second, which would take less than 15 hours. At that speed, processing the entire Pwned Passwords list would almost take longer to read from disk and into memory than it would take to exhaust against a single password. Password cracking specialists would of course try raw wordlists first (And therefore "more useful", in a way) ... but we many other tools in their arsenal that generate far more than a half a billion candidate passwords. And at that rate, you can exhaust all 8-character passwords made up of printable ASCII - 95^8, ~6x10^15 - in a couple of days. Other techniques (mask, hybrid, rules) can achieve similar rates, and combinator attacks are slower but still pretty efficient. By contrast, attacking bcrypt cost 12 on the same system can only try ~660 hashes per second - against a single hash. At that rate, if you just tell the attacker "it's somewhere in the Pwned Passwords list", it would take about 210 hours to exhaust the raw list, and 36 years to exhaust all 6-character passwords made up of printable ASCII. In other words, if a service is storing passwords poorly, that service should be fixing that long before they should be trying to blacklist a half billion passwords. The purpose of blacklisting up front in the password-changing UI isn't to forbid a half-billion passwords. It's a way to reduce risk of online attack - and an opportunity to guide users towards better selection methods. There's a reason why Dropbox only blacklists the top 30K.

by royce 9y ago

jasonpeacock 9y ago

I don't follow - how is the relative rarity better than absolute frequency? What really matters is how common your password is - not how highly it's ranked in a compromised password list, which has no relevance to how common it may be. You want to filter on users choosing a password that's been re-used across all compromised more than N times. Filtering users on choosing a password that ranks N of M on a list of compromised passwords doesn't tell the user how bad that password is. In fact, once you get to the rail, the ranking is basically based on sort order and become irrelevant?

royce 9y ago
The ranking in Troy's list is based entirely on how common the words are. Here are the top 10, with their relative frequency: c4a8d09ca3762af61e59520943dc26494f8941b:123456 (20760336) f7c3bc1d808e04732adf679965ccc34ca7ae3441:123456789 (7016669) b1b3773a05c0ed0176787a4f1574ff0075f7521e:qwerty (3599486) 5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8:password (3303003) 3d4f2bf07dc1be38b20cd6e46949a1071f9d0e3d:111111 (2900049) 7c222fb2927d828af22f592134e8932480637c0d:12345678 (2680521) 6367c48dd193d56ea7b0baad25b19455e529f5ee:abc123 (2670319) e38ad214943daad1d64c102faec29de4afe9da3d:password1 (2310111) 20eabe5d64b0e216796e834f52d61fd0b70332fc:1234567 (2298084) 8cb2237d0679ca88db6464eac60da96345513964:12345 (2088998) So ... what is the "right" threshold for N? $ for topx in 1 100 1000 5000 10000 20000 50000 100000 200000 500000 1000000; do \ echo -n "$topx: "; head -n ${topx} pwned-passwords-2.0.txt | tail -1; done 1: 7C4A8D09CA3762AF61E59520943DC26494F8941B:20760336 100: 482FA19D5C487CB69ACDA19EEE861CC69D82CC94:272371 1000: 5B9FE558F673D63309BEB13BFA5DA6C30A3CA1BF:64912 5000: FE648FC459A6F6EF6CD347BEE3D494766239BBB5:19860 10000: 2682A3DBA7A1452EE7EE9980F195C6A768055DA6:11055 20000: 53490A3C8567342B57B6A4FF24908DF73182B357:6309 50000: 7517CD23A308BBCD05E5AD24AA6AD054237ED470:3153 100000: BA6D6A41B9548C523833627A8B0E5170558BE1EA:1752 200000: E50E6893264519636E90E95B6B1A85D0A691E0B1:931 500000: AF8DF653177BBB3FEE2DA68D314B94CB5281B4F3:381 1000000: BDD57A4CAA691A3441C1190C6F087B58B2EE3EF6:186 2000000: C824AF24AA8F2FD99AD6842DC0E4B49100D96161:93 10000000: 352DB7177AB7848DF1C102234401097FE40EB87D:22 The third field indicates how common the password is in the corpus (for example, the single most common password - "123456" - appears in the corpus 20,760,366 times). So ... based on this data ... what is a reasonable value for that count, such that if the value is exceeded, the user should be disallowed from using the password? How much real-world online or offline resistance is provided by disallowing, say, passwords used at least 186 times in the corpus (roughly a million passwords, though 5201 passwords are at the 186 mark)? (The answer should be self-evident; if it isn't, I can provide more background). Put another way ... if the corpus was only 1M in size, those right-hand values would be much smaller. How could you determine the threshold then? What I'm trying to illustrate here is that it's not the absolute value of that commonality number that matters; it's the relative rank. But that relative rank can't be determined via the API; you must analyze the entire corpus directly - and then discard the vast majority of it for blacklisting purposes. I totally get that the threshold might vary per implementation. But it varies much less once the hash is slow enough, and the authentication service is suitable rate-limited. In other words, any system that would get real benefit from a 1-million-word blacklist is one that needs to be improved elsewhere instead. But Troy didn't provide any guidance about that, or even how to judge for yourself what the threshold might be. He just provided an API to blacklist a corpus of passwords that is three orders of magnitude larger than a properly designed system would ever need. 1. https://blogs.dropbox.com/tech/2012/04/zxcvbn-realistic-password-strength-estimation/ https://blogs.dropbox.com/tech/2012/04/zxcvbn-realistic-pass...

rspeer 9y ago

Why would a password that occurs in this list, but rarely, be safer? Attackers aren't going to skip the rare ones.

royce 9y ago
Because: 1) In an online attack, against a properly-configured service, even if password spraying is used, only the first few thousand passwords can be tried before rate-limiting, CAPTCHAs, etc. kick in. Would a user with a known leaked password at a different site be vulnerable to an online correlation attack? Yes. And that's why some big services supplement their approach by proactively searching for those leaks and forcing a password reset for those specific users. 2) In an offline attack, when the passwords are properly hashed with a modern slow hash, even an expensive GPU or FPGA cluster would take weeks to exhaust a 10,000 word dictionary against a large user corpus, and a significant amount of time even when a single user is targeted. Would users with '123456' get cracked pretty quickly? Yes. And that's why the top X are forbidden - to make offline attackers have to dig deeper into their wordlists (and thereby also their pocketbooks) to crack a password in a useful amount of time.
- rspeer 9y ago
  I find it hard to believe that you could set a cutoff of passwords that have been leaked but that you could rely on an attacker not to try. These passwords are more useful guesses than anything a password cracker would make up out of components. XKCD considers a password that's one of 2^28 possibilities "easy" to guess, and provides a well-regarded strategy [1] for coming up with a password that's one of 2^44. Passwords in this list are one of 2^29. [1] https://xkcd.com/936/ https://xkcd.com/936/
  - royce 9y ago
    Random passphrases are indeed a good idea. XKCD #936 advocates for 4 words randomly selected from a 6000-word dictionary, which is 6000^4, or ~1.296 × 10^15, which isn't actually that strong if the service in question has chosen a weak password hashing algorithm. When using pure bruteforce or masks (not a dictionary or hybrid attack) against a large-ish corpus of passwords (say, a few million) a system with 6 GTX 1080s can realistically try 8.2 billion SHA1-hashed passwords per second, which would exhaust the entire XKCD 936 keyspace in about 45 hours. (If you bump it up to five words from a 20,000 word dictionary, you get ~3.2x10^21 possibilities, which is better.). And if you focus on a single hash, that SHA1 rate jumps to ~32 billion hashes per second, which would take less than 15 hours. At that speed, processing the entire Pwned Passwords list would almost take longer to read from disk and into memory than it would take to exhaust against a single password. Password cracking specialists would of course try raw wordlists first (And therefore "more useful", in a way) ... but we many other tools in their arsenal that generate far more than a half a billion candidate passwords. And at that rate, you can exhaust all 8-character passwords made up of printable ASCII - 95^8, ~6x10^15 - in a couple of days. Other techniques (mask, hybrid, rules) can achieve similar rates, and combinator attacks are slower but still pretty efficient. By contrast, attacking bcrypt cost 12 on the same system can only try ~660 hashes per second - against a single hash. At that rate, if you just tell the attacker "it's somewhere in the Pwned Passwords list", it would take about 210 hours to exhaust the raw list, and 36 years to exhaust all 6-character passwords made up of printable ASCII. In other words, if a service is storing passwords poorly, that service should be fixing that long before they should be trying to blacklist a half billion passwords. The purpose of blacklisting up front in the password-changing UI isn't to forbid a half-billion passwords. It's a way to reduce risk of online attack - and an opportunity to guide users towards better selection methods. There's a reason why Dropbox only blacklists the top 30K.