Request a server for a record to exist without a server, knowing exactly which record was requested for

Question

I was thinking about services like pwnedlist.com and shouldichangemypassword.com and the main problem with them is trust.

That is, the user must believe that these services are not going to collect sent requests.

Pwnedlist.com offers the ability to send a SHA-512 hash request to a user request, which is a step forward, but still loses information if the request exists in the database. That is, the malicious service will know that this email address was valid (see also: why you should not click on unsubscribe links in a spam email).

The solution I came up with is as follows:

1) Instead of having the user compute and send the hash itself, the hash (I use the much simpler md5 in my example) is computed using javascript on the client side:

md5(" [e-mail] ") = "b58996c504c5638798eb6b511e6f49af" 

2) Now instead of transmitting the entire hash as a request to the server, only the first N bits are transmitted:

 GET http://remotesite.com?query=b58996 

3) The server responds to all hashes that exist in the database that begin with the same N bits:

 { "b58996afe904bc7a211598ff2a9200fe", "b58996c504c5638798eb6b511e6f49af", "b58996443fab32c087632f8992af1ecc", ...etc... } 

4) Javascript on the client side compares the list of hashes returned by the server and informs the user about whether his email address exists in the database. Since "b58996c504c5638798eb6b511e6f49af" is present in the server response, there is an email address in the database - tell the user!

Now the obvious problem with this solution is that the user must trust client-side javascript in order to transmit only what he says he is going to transfer. Well-informed people, however, will be able to verify that the request is not leaking (by observing requests sent to the server). This is not an ideal solution, but it would add a level of trust if the user could (theoretically) verify that the site is functioning as it says.

What is thinking about this decision? It is important to note that anyone knows any existing examples or discussion of this technique?

NOTE. Both pwnedlist.com and mustichangemypassword.com are apparently managed by reputable people / organizations, and I have no reason to believe otherwise. It is rather an exercise of thought.

Answer 1

Services like pwnedlist.com work with publicly available information. By definition, everyone has access to this data, so trying to provide this is a moot point. An attacker will simply download it from The Pirate Bay .

However, using a hash function like this is still easy to break because it is unsalted and does not have key straightening. In all reality, a message digest function, such as sha-512, is not a suitable tool for the job.

You are much better off with Bloom Filter . This allows you to create a blacklist of leaked data without the possibility of obtaining simple text. This is because brute force based on permutations can find a collision than a real plain text. Searching and pasting class complexity O (1), and the table itself takes up much less space, maybe 1/100 000 of the space that the traditional sql database will use, but this value is variable depending on the frequency you specify mistakes