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

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