Hacker News Reader

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.

> 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.

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-exchan...

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.

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.

What is stopping me doing a MITM on that, especially when it's digital - couldn't I copy the locked package that Alice sent, forward the original to Bob, and then when Bob sends his locked copy, I use my copy and attach my OWN lock to it, and send that instead to Alice, who then removes her lock from it, leaving only a package that is locked with my lock?

Sure, you need a way to verify that the package has been locked by who you thought you were sending it to.

Your attack would work by removing Bob completely, you just play his part in the protocol.

This is true for any protocol though. If you don't know who you're talking to then you could be talking to anyone.

In practice most protocols get around this by either pre-sharing a private key, or using a public/private key pair with a challenge round to establish identities.

It's pretty close to the service provided by Pwned Passwords [0], but automated.

https://haveibeenpwned.com/Passwords

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)

I'd like to add that (IIUC) this scheme doesn't require Google to retain plaintext credentials or even password hashes. (They still might of course, but they don't have to.) If implemented as described in the linked paper, it only requires storing the hash of the combined username-password (in encrypted form). It's difficult to imagine a less useful form from the perspective of an adversary.

Regarding costs, the one-time hash performed on intake is indeed computationally expensive. However, for queries the only cryptographic operation required is a single elliptic curve computation (using secp224r1) on the hashed record sent by the client. Computationally, that should be in the same ballpark as establishing a single TLS connection.

The primary expense (detailed in the paper) is bandwidth, on account of sending out an entire hash bucket with each response. The analysis in the paper assumes a 2 byte prefix, but they're using 3 bytes here to reduce bandwidth at the expense of privacy; for every query made, they have to send back ~250 values instead of just one.

I don't agree with 1.

This "But Google's Password Checkup doesn't just use public sources" is infering that Google's db is bigger and better. You don't know and this is example of magic lotion marketing.

"Our magic lotion for hair grow is muuuuch better, as it have secret formula".

Actually I suspect that Troy's db as for now is better/bigger.

See my other comment. Commercial outfits sell this data on a daily volume basis. Remember it has been (though admittedly not for over a year) literally my job to process the piles of new stolen password data or rather write and oversee programs which did that processing.

Didn't you ever wonder when you see viable SQL injections and other attacks announced so frequently why Troy's data set is so small? Troy is taking the ethical high ground by not buying data. So his data is the tip of the iceberg.

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

4B records is 2^32 which is 2^24 * 2^8 which is 256 (2^8) records for every 3 bytes (2^24) prefix.

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?

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.