[geogriffin]

> ... do not make it explicitly clear that the final solution sends a hash-prefixed password

I'm not sure if you're actually talking about something else, but the paper says: "Post-canonicalization, the server calculates a computationally expensive hash of both the canonical username and credential password... This 2-byte prefix—while leaking some bits of password material—provides the client with k-anonymity over the universe of all username and password pairs."

IOW, the 3-byte hash prefix sent is of the username and password concatenated. (Note that Google seems to have added another byte to the prefix versus the paper).

[Reelin]

To add to this, hashed username-password material is leaked only by the first variant described in the paper. The second variant described only leaks hashed username material. They reportedly used the first variant during testing but have now switched to the second variant.

They indeed appear to have increased the prefix from 2 to 3 bytes. This makes logistical sense though - with 4 billion items, a 2 byte address yields ~61k items per bucket (and thus sent to the client per request) while a 3 byte address yields only ~240 on average.