我一直在考虑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比较服务器返回的哈希列表,并通知用户她的电子邮件地址是否存在于DB中.
    由于服务器响应中存在“b58996c504c5638798eb6b511e6f49af”,因此电子邮件存在于数据库中 – 通知用户！

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

SO如何看待这个解决方案？重要的是,有没有人知道任何现有的例子或对这种技术的讨论？

注意：pwnedlist.com和shouldichangemypassword.com显然都是由信誉良好的人/组织运营,我没有理由不相信.这更像是一次思考练习.

解决方法:

像pwnedlist.com这样的服务正在处理公共信息.根据定义,每个人都可以访问这些数据,因此尝试保护它是一个没有实际意义的问题.攻击者只需从The Pirate Bay下载它.

但是,使用像这样的哈希函数仍然很容易打破,因为它没有保证,缺乏关键的直线.在所有现实中,像sha-512这样的消息摘要功能并不适合这项工作.

使用Bloom Filter可以获得更好的效果.这使您可以创建泄露数据的黑名单,而无需获取纯文本.这是因为基于排列的蛮力可能发现碰撞而不是真正的纯文本.查找和插入一个很酷的O(1)复杂性,并且它自己占用的表空间要少得多,可能是使用传统sql数据库的空间的1 / 10,000,但是这个值是可变的,具体取决于你指定的错误率.