4 ms·

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

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.

4 ms·

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

by flashman 7y ago

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.