在服务器不知道查询的是哪条记录的情况下，查询服务器是否存在一条记录

Query a server for the existence of a record without the server knowing exactly what record was being queried for

本文关键字：记录 查询 服务器 查询服务 是否 存在 一条 不知道 情况下      更新时间：2023-09-26

我一直在思考像pwnedlist.com和shouldichangemypassword.com这样的服务，以及它们的根本问题——信任。

也就是说用户必须相信这些服务不会获取提交的查询。

Pwnedlist.com提供了提交用户查询的SHA-512哈希的选项，这是向前迈进了一步，但如果查询确实存在于数据库中，则仍然会泄露信息。也就是说，恶意服务会知道给定的电子邮件地址是有效的(参见:为什么你永远不应该点击垃圾邮件中的退订链接)。

我想到的解决方案如下:

1)不是用户自己计算和提交哈希值，哈希值(在我的例子中我将使用更简单的md5)是通过客户端javascript计算的:

md5("user@example.com") = "b58996c504c5638798eb6b511e6f49af"
2)现在，不是将整个哈希作为查询传输到服务器，而是只传输前N位: 
GET http://remotesite.com?query=b58996

3)服务器用数据库中所有以相同N位开头的哈希值来响应:

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

4)客户端javascript比较服务器返回的哈希列表，并通知用户她的电子邮件地址是否存在于数据库中。由于服务器响应中存在"b58996c504c5638798eb6b511e6f49af"，因此该电子邮件存在于数据库中-通知用户!

现在，这个解决方案的明显问题是，用户必须信任客户端javascript只传输它说要传输的内容。然而，有足够知识的人能够验证查询没有泄露(通过观察发送到服务器的查询)。这不是一个完美的解决方案，但如果用户可以(理论上)验证网站的功能，它将增加信任水平。

SO认为这个解决方案怎么样?重要的是，有人知道任何现有的例子或讨论这种技术吗?

注意:pwnedlist.com和shouldichangemypassword.com显然都是由信誉良好的人/组织运营的，我没有理由不这么认为。这更像是一个思维练习

像pwnedlist.com这样的服务正在处理公共信息。根据定义，每个人都可以访问这些数据，所以试图保护它是一个没有意义的问题。攻击者会直接从海盗湾下载。

然而，使用像这样的哈希函数仍然很容易被破坏，因为它没有加盐并且缺乏键直。实际上，像sha-512这样的消息摘要函数并不是完成这项工作的合适工具。

你最好使用Bloom Filter。这允许您创建泄露数据的黑名单，而不可能获得纯文本。这是因为基于排列的暴力破解比真正的纯文本更容易发现冲突。查找和插入的复杂度为0(1)，而且表本身占用的空间要少得多，可能是使用传统sql数据库占用空间的万分之一，但是这个值是可变的，取决于您指定的错误率。

相关文章：