5 ms·

The cryptography behind this is done very well so that Google does not ever see even your hashed password, or know if there was a breached password detected. Wh

by zaroth 7y ago

The cryptography behind this is done very well so that Google does not ever see even your hashed password, or know if there was a breached password detected. What Google does see is a hash-prefix of your username, to narrow down the encrypted data set of compromised credentials being returned to your Chrome instance. Here’s what happens. Your instance of Chrome hashes your username and password and encrypts that value with an ephemeral key which doesn’t leave Chrome, Kc Google gets the encrypted cred-hash and applies a second round of encryption with a key only known to Google, Kg. They return the doubly-encrypted cred-hash, and also return 256 candidates encrypted with just Kg for you to compare against, those 256 candidates are selected based on a clear-text 3 byte prefix that Chrome also sends them. When Chrome gets the results back, it decrypts the cred-hash using Kc which results in the cred-hash now being encrypted only with Kg; coincidentally this is the same exact key used to encrypt the candidates, allowing Chrome to do a simple byte-compare to see if there’s a match between your cred-hash and the encrypted breach candidates. The cool part is the encryption operation is basically communicative. You can add your layer of encryption first, send the value to Google, they add their encryption and you get the double-encrypted blob back, and then you remove your encryption to end up with a plaintext encrypted just with Google’s key, even though Google never saw the plaintext, and you never saw their key. This trick allows your browser, and only your browser, to compare your cred-hash against the breached cred-hashes while all the data you are comparing is actually encrypted with a secret key held by Google that never leaves Google’s server. The only information leak is the 3-byte hash prefix to identify the slice of the comparison set. This is definitely not nothing, but perhaps it is a reasonable trade-off.

flashman 7y ago
Is this an okay simplification? • I want to send my password (44) to Google but don't want them to know it's 44. So I multiply it by 37 (Kc) and send 1628. • I also tell Google that the password is between 40 and 50. (Equivalent to sending three characters of cleartext.) • Google multiplies 1628 by 78 (Kg) and sends me the result, 126984. • Google also sends me every number between 40 and 50, multiplied by 78. • I divide 126984 by Kc and get 3432. I see that 3432 is in the set of other numbers Google sent me (44x78). So I can infer that my password is in Google's set of breached passwords.
- Reelin 7y ago
  > I also tell Google that the password is between 40 and 50. (Equivalent to sending three characters of cleartext.) I believe the (first 3 bytes of the) hash of your username is used, as opposed to your plaintext password. I realize you were simplifying, but the difference between "plaintext password" and "hashed username" is rather essential in this case. IIUC, their breach data consists of pairs of values - a username hash and the matching username-password hash (all encrypted ofc). This way they aren't storing a bunch of breached plain text credentials on their servers. This allows for a range search based on your username hash prefix, while the encrypted packages you send and receive are username-password hashes. Edit: I believe I was incorrect - they only retain the _prefix_ of the username hash (as opposed to the entire thing). This has the benefit of effectively rendering the username unrecoverable - you'd be forced to attack the combined username-password hash. So it's not really a range based search, but instead a hash table. They just return the entire (24-bit addressed) bucket to you, which for 4 billion (!) sets of credentials amounts to ~240 on average.
dexterdog 7y ago
How does a 3 byte prefix reduce a 4B data set to 250 records? Those bytes would have to be 256 bits each.
- zaroth 7y ago
  4B records is 2^32 which is 2^24 * 2^8 which is 256 (2^8) records for every 3 bytes (2^24) prefix.
  - dexterdog 7y ago
    I guess I assumed the logic was that you take a sha256 of, say 32501257be4512a04a184fed989fd5e46cd4d30f6ef7c8d20d07d90f82e83aaf and say give me all entries from the 4B that begin with 325 (or end with aaf) which would take your 4B and divide it by 16 3 times giving you about 1M?
    - usmannk 7y ago
      It’s 2 hex chars per byte. You have to divide by 16 6 times. Or rather by 32 (2^8) 3 times. 0x0 - 0xF can be represented with 4 bits or half a byte.
Cogito 7y ago
This scheme sounds (unsurprisingly) similar to a well known crypto scenario. Here is a page that describes it[0]. Copying from there: You and I need to communicate via the National Postal Service. What you want to communicate is secret, so you don't want a postal worker or some random schmoe who finds your mail in the mailbox or a package on your stoop to be able to open it up and read what's inside, and you know from experience that any time you send something in the mail without securing it, it either gets read or (if it's not just text) stolen. We must live in a country with a really corrupt postal service, I guess -- kind of like the Internet. We each have access to an arbitrary number of indestructible boxes, and an arbitrary number of indestructable key locks. Each box can have as many locks on it as you like. Unfortunately, each lock has only one key, and only the person who possesses the lock has the key. We can send things to each other in locked boxes, but of course the recipient doesn't have the key to the lock because the sender has it. Sending the key unsecured will get it stolen or, worse, copied. We also have no way to meet each other in person to exchange keys securely (and if we did, we could just skip the postal service altogether, anyway). How can we arrange, with these resources, to communicate securely with each other? [0] https://www.techrepublic.com/blog/it-security/the-key-exchange-puzzle-test-your-cryptographic-skills/ https://www.techrepublic.com/blog/it-security/the-key-exchan...
- zaroth 7y ago
  It’s actually fundamentally different, because instead of trying to agree on a key we can use to securely communicate cleartext over a hostile network, this is a scenario where neither side wants to know anything about what the other side knows, except in the very special case where we both have the same exact value, in which case only one side should discover that.
  - Cogito 7y ago
    The solution to the scenario is (spoiler alert) to attach multiple locks. Alice attaches her lock. Alice sends the locked package to Bob. Bob attaches his lock. Bob sends the twice locked package to Alice. Alice removes her lock. Alice sends the package, locked with only Bob's lock, to Bob. Bob removes his lock and opens the package. ---- The scheme you discussed is really similar to this, but I guess with one key difference; in the scheme you describe the locks themselves contain information and are hidden by a second lock. I don't think there is a good extension to the solution I posted above, but it's as if when Bob attaches his lock it is hidden until Alice removes her lock, and at that point Alice only cares about what Bob's lock looks like.
ehsankia 7y ago
It's pretty close to the service provided by Pwned Passwords [0], but automated. https://haveibeenpwned.com/Passwords https://haveibeenpwned.com/Passwords
- tialaramex 7y ago
  No really, or at least for anyone at all tech savvy -- and the reasons why are important. The key trick to what Google are doing is that Google never ends up knowing anything about what their users passwords are AND their users never end up knowing which passwords Google has discovered YET between them they arrange that the user knows if any of their passwords are known to Google. Magic! With Pwned Passwords users can learn any arbitrary subset of the Pwned Passwords full password hashes they please for just one API call per prefix - with Password Checkup you have to start by guessing a username plus password combination, then do a bunch of fairly expensive operations, and you only get back a boolean. It's essentially never worth it for bad guys who are guessing. This has two advantages, and doubtless both are attractive to Google although one advantage is better PR than the other 1. Bad Guys can't sieve the Google system for valuable data. For Pwned Passwords this isn't a big concern because Troy is using readily available password lists. Spending say $5M to get the raw passwords Troy used as input back by processing Troy's data makes no sense, just download a Torrent of it. But Google's Password Checkup doesn't just use public sources. Spending $5M (again just an example figure) to steal data from Google that may not be available to your criminal gang otherwise might be worth it for a big enough score. And it'd be bad PR for Google if a customer gets attacked by such crooks using data which those crooks couldn't have obtained at all without Google. Troy can always say "This data already existed, I didn't make the problem worse" but Google's non-public data can't make that claim. 2. Good guys can't either. Google has a valuable service here, locked into Google's infrastructure. They can choose to give it away, but they could also (as they have with some other products) later decide they'd prefer to monetize it. Either way, nobody else can duplicate it even though millions of people are using it, thanks to cryptography. The costs are pretty enormous too. Pwned Passwords is mostly just a CDN, and clients are trivial. The upfront maths to make it work was hard, but that's a one-time thing. But Password Check incurs a considerable ongoing cost for Google to do hard maths AND each client needs lots of RAM (this is a memory hard problem on purpose, to exhaust bad guys who might try to exploit it)

by zaroth 7y ago

flashman 7y ago

Is this an okay simplification? • I want to send my password (44) to Google but don't want them to know it's 44. So I multiply it by 37 (Kc) and send 1628. • I also tell Google that the password is between 40 and 50. (Equivalent to sending three characters of cleartext.) • Google multiplies 1628 by 78 (Kg) and sends me the result, 126984. • Google also sends me every number between 40 and 50, multiplied by 78. • I divide 126984 by Kc and get 3432. I see that 3432 is in the set of other numbers Google sent me (44x78). So I can infer that my password is in Google's set of breached passwords.

Reelin 7y ago
> I also tell Google that the password is between 40 and 50. (Equivalent to sending three characters of cleartext.) I believe the (first 3 bytes of the) hash of your username is used, as opposed to your plaintext password. I realize you were simplifying, but the difference between "plaintext password" and "hashed username" is rather essential in this case. IIUC, their breach data consists of pairs of values - a username hash and the matching username-password hash (all encrypted ofc). This way they aren't storing a bunch of breached plain text credentials on their servers. This allows for a range search based on your username hash prefix, while the encrypted packages you send and receive are username-password hashes. Edit: I believe I was incorrect - they only retain the _prefix_ of the username hash (as opposed to the entire thing). This has the benefit of effectively rendering the username unrecoverable - you'd be forced to attack the combined username-password hash. So it's not really a range based search, but instead a hash table. They just return the entire (24-bit addressed) bucket to you, which for 4 billion (!) sets of credentials amounts to ~240 on average.

dexterdog 7y ago

How does a 3 byte prefix reduce a 4B data set to 250 records? Those bytes would have to be 256 bits each.

zaroth 7y ago
4B records is 2^32 which is 2^24 * 2^8 which is 256 (2^8) records for every 3 bytes (2^24) prefix.
- dexterdog 7y ago
  I guess I assumed the logic was that you take a sha256 of, say 32501257be4512a04a184fed989fd5e46cd4d30f6ef7c8d20d07d90f82e83aaf and say give me all entries from the 4B that begin with 325 (or end with aaf) which would take your 4B and divide it by 16 3 times giving you about 1M?
  - usmannk 7y ago
    It’s 2 hex chars per byte. You have to divide by 16 6 times. Or rather by 32 (2^8) 3 times. 0x0 - 0xF can be represented with 4 bits or half a byte.

Cogito 7y ago

This scheme sounds (unsurprisingly) similar to a well known crypto scenario. Here is a page that describes it[0]. Copying from there: You and I need to communicate via the National Postal Service. What you want to communicate is secret, so you don't want a postal worker or some random schmoe who finds your mail in the mailbox or a package on your stoop to be able to open it up and read what's inside, and you know from experience that any time you send something in the mail without securing it, it either gets read or (if it's not just text) stolen. We must live in a country with a really corrupt postal service, I guess -- kind of like the Internet. We each have access to an arbitrary number of indestructible boxes, and an arbitrary number of indestructable key locks. Each box can have as many locks on it as you like. Unfortunately, each lock has only one key, and only the person who possesses the lock has the key. We can send things to each other in locked boxes, but of course the recipient doesn't have the key to the lock because the sender has it. Sending the key unsecured will get it stolen or, worse, copied. We also have no way to meet each other in person to exchange keys securely (and if we did, we could just skip the postal service altogether, anyway). How can we arrange, with these resources, to communicate securely with each other? [0] https://www.techrepublic.com/blog/it-security/the-key-exchange-puzzle-test-your-cryptographic-skills/ https://www.techrepublic.com/blog/it-security/the-key-exchan...

zaroth 7y ago
It’s actually fundamentally different, because instead of trying to agree on a key we can use to securely communicate cleartext over a hostile network, this is a scenario where neither side wants to know anything about what the other side knows, except in the very special case where we both have the same exact value, in which case only one side should discover that.
- Cogito 7y ago
  The solution to the scenario is (spoiler alert) to attach multiple locks. Alice attaches her lock. Alice sends the locked package to Bob. Bob attaches his lock. Bob sends the twice locked package to Alice. Alice removes her lock. Alice sends the package, locked with only Bob's lock, to Bob. Bob removes his lock and opens the package. ---- The scheme you discussed is really similar to this, but I guess with one key difference; in the scheme you describe the locks themselves contain information and are hidden by a second lock. I don't think there is a good extension to the solution I posted above, but it's as if when Bob attaches his lock it is hidden until Alice removes her lock, and at that point Alice only cares about what Bob's lock looks like.

ehsankia 7y ago

It's pretty close to the service provided by Pwned Passwords [0], but automated. https://haveibeenpwned.com/Passwords https://haveibeenpwned.com/Passwords

tialaramex 7y ago
No really, or at least for anyone at all tech savvy -- and the reasons why are important. The key trick to what Google are doing is that Google never ends up knowing anything about what their users passwords are AND their users never end up knowing which passwords Google has discovered YET between them they arrange that the user knows if any of their passwords are known to Google. Magic! With Pwned Passwords users can learn any arbitrary subset of the Pwned Passwords full password hashes they please for just one API call per prefix - with Password Checkup you have to start by guessing a username plus password combination, then do a bunch of fairly expensive operations, and you only get back a boolean. It's essentially never worth it for bad guys who are guessing. This has two advantages, and doubtless both are attractive to Google although one advantage is better PR than the other 1. Bad Guys can't sieve the Google system for valuable data. For Pwned Passwords this isn't a big concern because Troy is using readily available password lists. Spending say $5M to get the raw passwords Troy used as input back by processing Troy's data makes no sense, just download a Torrent of it. But Google's Password Checkup doesn't just use public sources. Spending $5M (again just an example figure) to steal data from Google that may not be available to your criminal gang otherwise might be worth it for a big enough score. And it'd be bad PR for Google if a customer gets attacked by such crooks using data which those crooks couldn't have obtained at all without Google. Troy can always say "This data already existed, I didn't make the problem worse" but Google's non-public data can't make that claim. 2. Good guys can't either. Google has a valuable service here, locked into Google's infrastructure. They can choose to give it away, but they could also (as they have with some other products) later decide they'd prefer to monetize it. Either way, nobody else can duplicate it even though millions of people are using it, thanks to cryptography. The costs are pretty enormous too. Pwned Passwords is mostly just a CDN, and clients are trivial. The upfront maths to make it work was hard, but that's a one-time thing. But Password Check incurs a considerable ongoing cost for Google to do hard maths AND each client needs lots of RAM (this is a memory hard problem on purpose, to exhaust bad guys who might try to exploit it)