7 ms·

do not skip the section on "Cloudflare, Privacy and k-Anonymity" ... it is a great summary of an elegant privacy solution. And check out Cloudflare's detail po

do not skip the section on "Cloudflare, Privacy and k-Anonymity" ... it is a great summary of an elegant privacy solution. And check out Cloudflare's detail post too: https://blog.cloudflare.com/validating-leaked-passwords-with-k-anonymity/ https://blog.cloudflare.com/validating-leaked-passwords-with...

jkaptur 9y ago
I'm a bit confused - why not distribute a serialized Bloom filter representing these passwords? That would seem to enable a compact representation (low Azure bill) and client-side querying (maximally preserving privacy).
- fhenneke 9y ago
  A Bloom filter with >500M items, even when allowing for a comparatively high rate of false positives such as 1 in 100, is still in the hundreds of MBs, which would not be that much more accessible than the actual dump files.
  - KMag 9y ago
    The compressed archive here is over 8 GB. An uncompressed 2 GB Bloom filter with 24 hash functions and half a billion entries has a false positive rate of less than 1 in 14 million. 75% space savings, with no decompression necessary for use, and a 1 in 14 million false positive rate is nothing to sneeze at.
    - rrobukef 9y ago
      But no count of how often the hash is used. Counting bloom filters are till a bit harder to implement.
      - KMag 9y ago
        Counting bloom filters are only marginally more difficult to implement. To increment a key, find the minimum value stored in all of the slots for the key, and then increment all of the stored values for that key that are equal to the minimum value. To read, return the minimum value for all of the values stored in slots for the key. For these purposes, however, you probably instead want to store just separate Bloom filters for counts above different thresholds, since the common use case would be accept/reject decisions based upon a single threshold.
- Ajedi32 9y ago
  There are half a billion passwords in the list. A bloom filter with even a 1 in 10 false positive rate would still be 286.59 MB.
  - richdougherty 9y ago
    You could do a Bloom filter on each bucket, each of which has about 500 items. This would reduce the size of the response from about 16k to < 1k. But it would be a lot harder to use since all clients would have to use the Bloom filter code correctly.
- w8rbt 9y ago
  I agree. Just need to set some bits and test them. This is too big really for a tree or a hash table.
Lxr 9y ago
Can you clarify what problem this solves?
- ChrisSD 9y ago
  As stated in the post, it's a simple solution to help with anonymity. "The password has been hashed client side and just the first 5 characters passed to the API As mentioned earlier, there are 475 hashes beginning with "21BD1", but only 1 which matches the remainder of the hash for "P@ssw0rd" and that record indicates that the password has previously been seen 47,205 times."
  - Lxr 9y ago
    Forgive my ignorance but why is submitting a hash a problem? Because Troy knows which passwords have been checked? Why should I care about that? I get that it’s like submitting your password in the clear if it’s in the DB, but in that case surely you have bigger problems.
    - pfg 9y ago
      One way that sites can use this service is to check whether a password has been leaked when users sign up. By handing over the SHA-1 hash of the password you're effectively trusting this service (and anyone who might have compromised it) with all your user's clear text passwords. Connecting the right password with the right user can be trivial in some circumstances, say because a site has a publicly visible sign-up date on profiles, or even if it just hands out sequential IDs to users.
  - febed 9y ago
    But Troy could still very easily guess the complete hash. It's the one with the 47,205 hits.
    - kingvash 9y ago
      Yes but Troy doesn't learn the hashes of uncompromised passwords
skykooler 9y ago
Why does 0000 have the largest number of hashes? Does SHA-1 not distribute hash values evenly?
- jobigoud 9y ago
  It's indeed weird that "00000" would be the hash prefix with the highest number of entries. I think it must be a hidden variable. Like some sources put an all-zeroed-out hash in the database for testing or in case of a registration error or for deleted users, and these show up here.
  - cmurphycode 9y ago
    Great thought, but it doesn't seem to be the case - as the number of unique suffixes is the large number here -- in fact, none of the values in the range are simply all zeroes. https://api.pwnedpasswords.com/range/00000 https://api.pwnedpasswords.com/range/00000 I wonder if the hidden variable is something to do with how the passwords are leaked. First, let's suppose that a very commonly used broken password hash is plain SHA-1 (I think that's a valid assumption-- unfortunately!). Then, let's figure that amongst the many data dumps / extracts done by hackers, some of them are only able to extract part of the database, or save part of the database, or whatever....and they are fetched / saved / uploaded in lexical order? Can't think of anything else. EDIT: Ooops. The other thing is, that these actually are sha-1 hashes of real plaintext passwords. So it's definitely not a test-row in that sense.
- derefr 9y ago
  Maybe crypto people who have brute-forced up some typeable passwords that hash to low numbers on the first SHA-1 pass, for a fun-and-games equivalent to a Proof of Work? (It'd only show up in actual DB dumps for backends that use "SHA-1 with no salting" for password hashing, which might also serve as a useful canary value.)
  - cmurphycode 9y ago
    Great idea! I ran a quick hashcat against the range00000 list on my laptop. In 1 minute I cracked 79 of them, and not too many of them look very odd - that is, they look sorta like normal cracked passwords. I'm asking my friend to run a more thorough crack on his dedicated GPU, especially for hash value 000DD7F2A1C68A35673713783CA390C9E93:630 which does stick out to me!
markdown 9y ago
A warning about Cloudflare: You cannot access their support in any way without logging in. Trying to contact them via their contact/sales page won't work. They won't respond. This means that if you lose your phone (2FA) and can't log in, you're royally screwed and will have to go to your registrar to recover access to your domains/DNS.
- always_good 9y ago
  All of that is a good thing in my book. I've been the victim of the "customer service backdoor" on Amazon multiple times. It's ridiculous that someone can just about credentialize as you without even having to log in. They made off with whatever sensitive data the customer service rep had in front of them just from chatting to someone on that anonymous support chat widget. Meanwhile, all you have to do is backup your 2FA secrets. Why not make it a part of your regular computer backup routine?
- mulmen 9y ago
  If support can bypass 2FA why even have it?
  - markdown 9y ago
    What a silly question. One can prove who they are with documents, but nobody can prove who they are with 2FA. It goes like this: If you can prove who you are, you get access to your account. That's what this is all about. The more offline, human touch we go, the greater the security.
    - aianus 9y ago
      It's way more likely that a hacker can convince a customer support rep that he's me than that hacker can steal my 2FA codes. This isn't a hypothetical, this happens all the time including to people I know personally: https://www.forbes.com/sites/laurashin/2016/12/20/hackers-have-stolen-millions-of-dollars-in-bitcoin-using-only-phone-numbers/ https://www.forbes.com/sites/laurashin/2016/12/20/hackers-ha...
mino 9y ago
Just added an extra line to the bash wrapper to print how many time the given password appears in the dump: https://gist.github.com/mino98/8aa240fa55a8182198fba58fb810b366 https://gist.github.com/mino98/8aa240fa55a8182198fba58fb810b...
- Ixio 9y ago
  If you prefer a one-liner like me, the following line works for me: VARPWD=P@ssw0rd; HASH=`echo -n $VARPWD | sha1sum`; curl --silent https://api.pwnedpasswords.com/range/`cut https://api.pwnedpasswords.com/range/`cut -b 1-5 <(echo $HASH)` --stderr - | grep -i `cut -b 6- <(echo $HASH) | cut -d ' ' -f 1` If it doesn't return anything than your password isn't in the list. You should probably start your line with a space so that it isn't recorded in your bash_history. If someone else can make it better or shorter, be my guest.
oh_sigh 9y ago
Does anyone else not get results when searching for 'asdf' and 'hunter2', and 'lauragpe'(which appears in the article) not return results using the shell script provided? edit: Ok, so my `openssl sha1` (version 1.0.x) outputs '(stdin) <hash>', whereas the script expects just <hash>. add ' | cut -f2 -d" "' after the 'openssl sha1' call to fix this if you have the same problem.
- frumiousirc 9y ago
  Here's how I tested: echo -n 'hunter2' | sha1sum f3bbbd66a63d4bf1747940578ec3d0103530e21d - https://api.pwnedpasswords.com/range/f3bbb https://api.pwnedpasswords.com/range/f3bbb C-f d66a6 finds D66A63D4BF1747940578EC3D0103530E21D:16092

jkaptur 9y ago

I'm a bit confused - why not distribute a serialized Bloom filter representing these passwords? That would seem to enable a compact representation (low Azure bill) and client-side querying (maximally preserving privacy).

fhenneke 9y ago
A Bloom filter with >500M items, even when allowing for a comparatively high rate of false positives such as 1 in 100, is still in the hundreds of MBs, which would not be that much more accessible than the actual dump files.
- KMag 9y ago
  The compressed archive here is over 8 GB. An uncompressed 2 GB Bloom filter with 24 hash functions and half a billion entries has a false positive rate of less than 1 in 14 million. 75% space savings, with no decompression necessary for use, and a 1 in 14 million false positive rate is nothing to sneeze at.
  - rrobukef 9y ago
    But no count of how often the hash is used. Counting bloom filters are till a bit harder to implement.
    - KMag 9y ago
      Counting bloom filters are only marginally more difficult to implement. To increment a key, find the minimum value stored in all of the slots for the key, and then increment all of the stored values for that key that are equal to the minimum value. To read, return the minimum value for all of the values stored in slots for the key. For these purposes, however, you probably instead want to store just separate Bloom filters for counts above different thresholds, since the common use case would be accept/reject decisions based upon a single threshold.
Ajedi32 9y ago
There are half a billion passwords in the list. A bloom filter with even a 1 in 10 false positive rate would still be 286.59 MB.
- richdougherty 9y ago
  You could do a Bloom filter on each bucket, each of which has about 500 items. This would reduce the size of the response from about 16k to < 1k. But it would be a lot harder to use since all clients would have to use the Bloom filter code correctly.
w8rbt 9y ago
I agree. Just need to set some bits and test them. This is too big really for a tree or a hash table.

Lxr 9y ago

Can you clarify what problem this solves?

ChrisSD 9y ago
As stated in the post, it's a simple solution to help with anonymity. "The password has been hashed client side and just the first 5 characters passed to the API As mentioned earlier, there are 475 hashes beginning with "21BD1", but only 1 which matches the remainder of the hash for "P@ssw0rd" and that record indicates that the password has previously been seen 47,205 times."
- Lxr 9y ago
  Forgive my ignorance but why is submitting a hash a problem? Because Troy knows which passwords have been checked? Why should I care about that? I get that it’s like submitting your password in the clear if it’s in the DB, but in that case surely you have bigger problems.
  - pfg 9y ago
    One way that sites can use this service is to check whether a password has been leaked when users sign up. By handing over the SHA-1 hash of the password you're effectively trusting this service (and anyone who might have compromised it) with all your user's clear text passwords. Connecting the right password with the right user can be trivial in some circumstances, say because a site has a publicly visible sign-up date on profiles, or even if it just hands out sequential IDs to users.
- febed 9y ago
  But Troy could still very easily guess the complete hash. It's the one with the 47,205 hits.
  - kingvash 9y ago
    Yes but Troy doesn't learn the hashes of uncompromised passwords

skykooler 9y ago

Why does 0000 have the largest number of hashes? Does SHA-1 not distribute hash values evenly?

jobigoud 9y ago
It's indeed weird that "00000" would be the hash prefix with the highest number of entries. I think it must be a hidden variable. Like some sources put an all-zeroed-out hash in the database for testing or in case of a registration error or for deleted users, and these show up here.
- cmurphycode 9y ago
  Great thought, but it doesn't seem to be the case - as the number of unique suffixes is the large number here -- in fact, none of the values in the range are simply all zeroes. https://api.pwnedpasswords.com/range/00000 https://api.pwnedpasswords.com/range/00000 I wonder if the hidden variable is something to do with how the passwords are leaked. First, let's suppose that a very commonly used broken password hash is plain SHA-1 (I think that's a valid assumption-- unfortunately!). Then, let's figure that amongst the many data dumps / extracts done by hackers, some of them are only able to extract part of the database, or save part of the database, or whatever....and they are fetched / saved / uploaded in lexical order? Can't think of anything else. EDIT: Ooops. The other thing is, that these actually are sha-1 hashes of real plaintext passwords. So it's definitely not a test-row in that sense.
derefr 9y ago
Maybe crypto people who have brute-forced up some typeable passwords that hash to low numbers on the first SHA-1 pass, for a fun-and-games equivalent to a Proof of Work? (It'd only show up in actual DB dumps for backends that use "SHA-1 with no salting" for password hashing, which might also serve as a useful canary value.)
- cmurphycode 9y ago
  Great idea! I ran a quick hashcat against the range00000 list on my laptop. In 1 minute I cracked 79 of them, and not too many of them look very odd - that is, they look sorta like normal cracked passwords. I'm asking my friend to run a more thorough crack on his dedicated GPU, especially for hash value 000DD7F2A1C68A35673713783CA390C9E93:630 which does stick out to me!

markdown 9y ago

A warning about Cloudflare: You cannot access their support in any way without logging in. Trying to contact them via their contact/sales page won't work. They won't respond. This means that if you lose your phone (2FA) and can't log in, you're royally screwed and will have to go to your registrar to recover access to your domains/DNS.

always_good 9y ago
All of that is a good thing in my book. I've been the victim of the "customer service backdoor" on Amazon multiple times. It's ridiculous that someone can just about credentialize as you without even having to log in. They made off with whatever sensitive data the customer service rep had in front of them just from chatting to someone on that anonymous support chat widget. Meanwhile, all you have to do is backup your 2FA secrets. Why not make it a part of your regular computer backup routine?
mulmen 9y ago
If support can bypass 2FA why even have it?
- markdown 9y ago
  What a silly question. One can prove who they are with documents, but nobody can prove who they are with 2FA. It goes like this: If you can prove who you are, you get access to your account. That's what this is all about. The more offline, human touch we go, the greater the security.
  - aianus 9y ago
    It's way more likely that a hacker can convince a customer support rep that he's me than that hacker can steal my 2FA codes. This isn't a hypothetical, this happens all the time including to people I know personally: https://www.forbes.com/sites/laurashin/2016/12/20/hackers-have-stolen-millions-of-dollars-in-bitcoin-using-only-phone-numbers/ https://www.forbes.com/sites/laurashin/2016/12/20/hackers-ha...

mino 9y ago

Just added an extra line to the bash wrapper to print how many time the given password appears in the dump: https://gist.github.com/mino98/8aa240fa55a8182198fba58fb810b366 https://gist.github.com/mino98/8aa240fa55a8182198fba58fb810b...

Ixio 9y ago
If you prefer a one-liner like me, the following line works for me: VARPWD=P@ssw0rd; HASH=`echo -n $VARPWD | sha1sum`; curl --silent https://api.pwnedpasswords.com/range/`cut https://api.pwnedpasswords.com/range/`cut -b 1-5 <(echo $HASH)` --stderr - | grep -i `cut -b 6- <(echo $HASH) | cut -d ' ' -f 1` If it doesn't return anything than your password isn't in the list. You should probably start your line with a space so that it isn't recorded in your bash_history. If someone else can make it better or shorter, be my guest.

oh_sigh 9y ago

Does anyone else not get results when searching for 'asdf' and 'hunter2', and 'lauragpe'(which appears in the article) not return results using the shell script provided? edit: Ok, so my `openssl sha1` (version 1.0.x) outputs '(stdin) <hash>', whereas the script expects just <hash>. add ' | cut -f2 -d" "' after the 'openssl sha1' call to fix this if you have the same problem.

frumiousirc 9y ago
Here's how I tested: echo -n 'hunter2' | sha1sum f3bbbd66a63d4bf1747940578ec3d0103530e21d - https://api.pwnedpasswords.com/range/f3bbb https://api.pwnedpasswords.com/range/f3bbb C-f d66a6 finds D66A63D4BF1747940578EC3D0103530E21D:16092