bcrypt将是一种更好的方法，因为它被设计为（可编程）缓慢。

使用足够大的盐和合理的复杂性因子，bcrypt(salt + number, complexityFactor)应该会产生一个可行的哈希值，并且您可以避免“滚动自己的密码学”，这可能会变得很难卖。为了提高安全性，您只需加快速度complexityFactor。

攻击者现在不仅要生成每个 10 位电话号码的 bcrypt（这可能是可行的：毕竟只有 10 ^{10 个数字），而且要生成每个可能的加盐序列。}使用 10 个字符的 base64 salt（60 位熵），复杂性增加了 20 个数量级。

蛮力

假设您有 1,000 个联系人。普通手机的 CPU似乎比服务器核心阵列慢两个数量级。我认为有理由说它会比一个半专用的 GPU 实现慢三个bcrypt数量级，据说效率不高。

因此，我们将每个编码调整bcrypt 为 100 毫秒。这意味着我们需要 1 分 40 秒来生成我们的 1,000 个哈希值，这对于一千个联系人来说是合理的时间（进度条似乎是有序的）。如果用户只有 100 个联系人，他将在 10 秒内完成。

给定一个数字的盐，攻击者必须生成大约 10 ⁸个数字才能合理地覆盖手机号码空间（第一个数字，也可能是前两个，并不是真正的 10 或 100——我把它们算作 1） . 它将花费三个数量级，小于10 ⁸乘以 100 毫秒，即小于 10 ⁷秒。这减少到 10 ⁴秒，或大约两个半小时（如果 GPU 优化结果不起作用，则需要一整天）。

在不到四个月的时间里，全部 1,000 个联系人将被解密 - 使用一台优化的服务器。使用十台这样的服务器，攻击者将在两周内完成。

正如 Ángel 的回答和 Neil Smithline 的评论所指出的，问题在于密钥空间很小。

在实践中，用户 A 会生成一些东西（哈希块或其他什么）以某种方式提供给 B。用户 B 必须有一个类似的方法

matches = (boolean|NumberArray) function(SomethingFromA, NumberFromB)

（如果第二个参数是一组 N 个数字，则变化不大，因为 UserB 可以使用一个真实数字和 N-1 个已知是假的或不感兴趣的数字来构建一个集合。它可以将攻击时间延长 N 倍）。

该功能在时间 T 内工作……实际上，该功能必须在足够短的时间 T 内工作，以使在商业现实世界应用程序中的用户 B 满意。

因此，我们不能轻易回避的一个界限是，必须在普通智能手机上在可接受的时间内检查 M 个数字。另一个我们无法合理回避的界限是用户 B 可以向算法提供假数字（即不是真正联系人的人，甚至可能不存在）。

如果检查器在第三台服务器上，这两个界限也会被强制执行；这只确保较低的执行时间限制可以阻止某些情况，例如“解密所有UserA 的号码”，但不能保证其他情况，例如“验证谁拥有这个号码”，如drawbenn的回答）。

从这两个界限中可以得出这样一个事实，即使用智能手机（或强制执行最短执行时间的第三方服务器），循环遍历所有 10 ^{8 个}合理数字大约需要 10 ^{8 个}智能手机时间，或大约一千个月。

减少此时间的攻击策略是在多个验证者之间分配攻击，或者在不受限制且速度更快的服务器上运行它（这需要算法可用，但假设相反是通过默默无闻的安全性），它们看起来既可行又负担得起.

漏洞？

一种可能性是引入小概率的误报。即，上述 oracle 函数将偶尔（例如每万个联系人一次），并且确定性地根据 UserA 的输入，对 UserB 的数字之一返回true。

^{这意味着对 10 8}个号码的暴力攻击将产生 UserA 的联系人与 10 ^{4 个}其他号码混合。UserA 输入的确定性意味着对这 10 ^{4 个}找到的项目进行两次连续检查不会进一步削弱它们。除非用户 B 可以获取用户 A 输入的不同副本，这将产生一组不同的误报，并允许将真正的联系人过滤为两组的交集，否则这可能会降低暴力回答的吸引力。这是有代价的——诚实的 UserB 将不得不偶尔受到错误的打击。

我们真的赢不了

如果用户 B必须能够回答“用户 A 的联系人中有 X 号吗？”这个问题。在确定的合理时间内，时间消耗是线性的，因为系统无法阻止针对数字 X1 和 X2 发出两个这样的请求，请求 X2 的时间与请求 X1 相同。因此，解决两个数字将需要两倍的合理时间；通过归纳，求​​解 N 个数字将需要 N 倍的合理时间（不是，比如说，N ²）。

合法请求和攻击之间的区别在于，攻击将在大十到十万倍的空间上进行。由于是线性的，它将需要长达十万倍的时间……但它也可以在一台机器或一组机器上运行，速度要快一百到一千倍。

因此，我们的攻击者将始终能够在“仍然不是不合理”的时间内解密 UserA 的所有联系人。对此唯一认真的检查是在第三台受信任的机器上运行检查，该机器具有速率限制和检测可能攻击的手段。

为了阻止攻击者，我们需要一些不好的东西随着 N 的增加而增加，并且由于它不能运行时间（增加的不够多），我认为剩下的唯一手段是误报的概率。攻击者仍然会得到答案，但我们仍然可能成功地使暴力破解的答案变得不那么可用。

一种简单的实现（穷人的布隆过滤器）

为了回答 Mindwin 的评论，本地算法无法通过隐藏信息来工作 - 信息必须首先丢失，否则我们仍然会通过默默无闻来做安全。

一种方法是用户A（Alice）bcrypt为她（比如说）1000 个联系人发送盐，然后是 1000 个不完整的 bcrypt哈希值。如果哈希在第 i 个字节处被截断，则会出现伪随机冲突。在 UserB (Bob) 的少数联系人中，碰撞将非常罕见（除非 i 非常小）。在攻击者（夏娃）的整数空间中，碰撞将是显着的。

请注意，电话号码分布并不平坦，因此 Eve 可以通过删除未使用的编号序列来减少这些冲突。

如果每个联系人哈希有千分之一的碰撞概率，Bob 检查他的一千个联系人，完全没有碰撞的概率是 (1 - 1/1000) ¹⁰⁰⁰ - 那是 70%，不太好。如果碰撞概率为 1/10000，那么拥有 1000 个联系人的 Bob 将有 90% 的机会不会发生一次碰撞。仅在 100 个联系人中，Bob 的 no-coll 概率分别为 90% 和 99%。

Eve，验证 10 ⁸个数字，即使 p = 1/10000，无论如何都会得到一万次碰撞。

与发送一个冲突概率等于单独哈希乘积的单个哈希相比，发送两个或多个具有更高冲突概率的哈希对 Bob 或 Eve 并没有太大的改变。

例如，不要使用 p = 1/10000 的 1 轮，而是使用 p = 1/100 的两轮，因为 1/100*1/100 = 1/10000。

所以 Alice 发送了两组无序不完全哈希，种子不同，碰撞概率更高 1%；Bob 将测试他的 1000 个联系人，并为他的 100 个共同联系人获得正匹配；剩下的 900 个不应该匹配，但由于散列不完整，其中 1% 会匹配，这意味着 9 个虚假联系人，并且 Bob 在运行 1000 次测试后最终会得到 109 个可能的候选人。他现在必须用第二个哈希来测试这 109 个，这也有 1% 的概率。100 个真正的交叉点仍将匹配。在剩下的 9 个中，很可能没有一个会通过。一个联系人通过两个这样的回合的机会是 1% 的 1%，即万分之一，在 1000 个不匹配的联系人中甚至没有一个误报的机会是 (1-1/10000) ¹⁰⁰⁰，或 90.48%，与以前完全相同。

有了相同的数字，Eve 将在第一轮得到 100 万个误报，并且必须进行 100 万次额外的测试。其中 1% 将匹配第二轮，让 Eve 与 Alice 的 1000 个联系人混杂一万个误报。

Eve 必须运行 1.01 亿次测试而不是 100 次，Bob 必须运行 1109 次而不是 1000 次。按比例来说，双哈希方案对 Bob 的影响比 Eve 更大。最好使用复杂度更高的单个哈希。

回答“Alice 知道数字 N 吗？”这个问题的隐私问题。将保持未解决 - Bob 和 Eve 的回答时间相同。

您可能还没有考虑其他隐私问题。通过设计，您的应用程序可以轻松查看谁连接到某个目标。因此，攻击者在他们的手机上创建一个联系人（他们感兴趣的活动家/线人/恐怖分子/受害者），然后通过您的应用程序连接到许多其他用户，以创建目标联系人列表。例如，一个 DV 滥用者可以使用这个应用程序来列出仍然与他的前任有联系的人：即使是谷歌也很难做到这一点。

是的，它（有点）有缺陷。问题是空间太小，所以即使有多个轮次和盐，也比较容易暴力破解。

Open Whisper Systems 有一个机智的系统，他们提供了一个加密的布隆过滤器，可以使用盲签名在本地进行查询。他们在https://whispersystems.org/blog/contact-discovery/上解释了该过程（以及对私人信息检索问题的良​​好讨论）

遗憾的是，由于用户群庞大的实际问题，他们不得不在 TextSecure 上停止此功能。在您的情况下，当您在两个最终用户之间共享号码时，这应该是可行的，无论是使用他们相同的方法还是使用其他协议，例如 Moxie 提到的那些已发布的协议。

我们如何以加密安全的方式做到这一点并尊重用户的隐私（即不在他们之间或与服务器共享纯文本数字）？

tldr：你不能。

散列对于某些用途非常有用，但这可能不是其中之一。原因是攻击者会知道只有 100 亿种可能性（对于 10 位数的电话号码），这使得暴力破解任何发现的哈希变得太容易了。

相反，如果：

• 其中一部手机愿意信任另一部。一部手机与另一部共享其联系人列表，另一部进行比较。第二部电话不需要与第一部共享其列表。
• 您愿意使用受信任的中介，即服务器。从用户的角度来看，这是最好的方法，因为任何一方都不需要与另一方共享他们的联系人列表。双方都会与调解员分享他们的名单，调解员会报告比赛情况，并承诺不保存任何东西。与每个相关方的通信将使用标准的公共/私人加密密钥对，并且任何人的数据都不会受到威胁。当然，这假设您的用户在您承诺不保留他们的联系人列表时会信任您。但是，如果您可以让您的用户足够信任您来安装您的应用程序，那么您已经赢得了他们的信任。