java - 检查我的数学：bouncycastle 问题：赔率 2 个不相等的密码被认为相等

问题描述

这是BouncyCastle 的 OpenBSD BCrypt 实现的 v1.66 版本的“检查哈希是否相等”代码：

for (int i = 0; i != sLength; i++){
  isEqual &= (bcryptString.indexOf(i) == newBcryptString.indexOf(i));
}

wheresLength保证为 60（见第 268 行），bcryptString 是一个完整的 openbsd 风格的 bcrypt 字符串，例如$2y$10$.vGA1O9wmRjrwAVXD98HNOgsNpDczlqm3Jq7KnEd1rVAGv3Fykk1a.

错误是使用的方法：他们打算使用charAt.

此循环的目的是检查从 0 到 59 的每个位置，位置 in 的字符是否与位置ini的a字符相同。ib

但是，由于错误使用indexOf(int), 相反，这会检查带有 unicode in 的第一个字符的位置是否与带有 unicode ini的a第一个字符的位置匹配，并且 'not in string' 匹配 'not in string'ib。

示例："Hello".indexOf(101)返回1（java 是从 0 开始的，101 是的 unicode e，并且e是第二个字符）。"Hello".indexOf(0)返回-1（因为“Hello”中没有 unicode-0）。

我正在尝试进行数学计算以找出以下问题的答案：

如果您尝试使用任意选择的密码而不是实际密码来登录给定用户（假设您碰巧选择了确切密码的几率为零），那么该算法错误考虑的几率是多少任意选择的密码为“相等”？

openbsd 字符串的构建

据我所知，这是：$2y$10$.vGA1O9wmRjrwAVXD98HNOgsNpDczlqm3Jq7KnEd1rVAGv3Fykk1a

分解如下：

$2y$ - 常量 - 它是一个几乎意味着“bcrypt 字符串”的标记。
10- 每个服务器的常数 - 使用的轮数；几乎所有地方都是 10，并且对于任何给定用户的密码哈希值总是相同的。
$- 不变的，再次。
.vGA1O9wmRjrwAVXD98HNO（22 个字符）：16 字节的盐用 2 个零字节填充，然后是 base-64ed，然后去掉最后 2 个字符。这可以用来重建盐。
其余（31 个字符）：bcrypt(rounds, concat(salt+utf8encode(pass)))base64 编码的结果，并丢弃最后一个字符。
请注意，base64 impl 使用所有小写字母、所有大写字母、所有数字、点和斜杠。

关于赔率的基本认识

错误的算法将最终检查 unicode 范围 0 到 59（含）中所有字符的第一次出现的位置对于两个散列（“realhash”和“inhash”）是否相同。如果所有 60 个对于 realhash 和 inhash 都具有相同的“首次出现位置”，则该算法认为密码相等。

在 0 到 59 之间的所有 unicode 符号中，唯一可能出现在此字符串中的是0123456789$./.

但是，其中$012无关紧要：对于 any passhash.indexOf('$')，答案是 0。对于 any passhash.indexOf('1')，答案是 4。对于 0 和 2 也是如此。只剩下9 个字符可能导致算法说“inhash”不是等于“真实哈希”：3456789./。

为了弄清楚几率是多少，我们需要让这 9 个字符中的每一个都不会成为差异化因素。要弄清楚一个特定字符（假设“3”）无法区分的几率是多少，那么这只是1-ZZ 是“3”足以区分的几率。

Z = Q * (U*A + (1-U)*B)
Q = '3' 不在 realhash 的 salt 部分。（前 22 名）
U = '3' 在 inhash 的 pass 部分。（最后 31 个）
A = '3' 不在 realhash 的 pass 部分，或者它在，但它的第一次出现与 inhash 中第一次出现的 '3' 不在同一个位置。
B = '3' 在 realhash 的 pass 部分。
A = 1- (V*W); V = '3' 在 realhash 的 pass 部分，W = 假设 '3' 在 realhash 和 passhash 中，它的第一次出现在同一个地方。一旦 Z 被确定，我的任意密码导致该算法认为它是正确的，即使它不是正确的，然后定义为：“3”和其他 8 个字符中的任何一个都不足以区分. 因此：(1-Z)^9。

Z = Q * ( (U * (1 - (V * W))) + ((1-U) * (1-V)) )


Q = (63/64)^22   ~= 0.707184
U = 1-(63/64)^31 ~= 0.386269
V = 1-(63/64)^31 ~= 0.386269
W = 1/31         ~= 0.032258
(1 - (V * W))    ~= 0.987539
(1-U) * (1-V)    ~= 0.376666
Z                ~= 0.536131

Chance that the 3 fails to differentiate:
(1-Z)            ~= 0.463868

Chance that all of 3456789./ fail:
(1-Z)^9          ~= 0.00099438

因此，大约为 0.001：算法说 2 个密码相等但实际上不相等的概率约为千分之一。

我错过了什么重要的东西吗？

注意：BouncyCastle 的最新公开版本已修复此错误。CVE-2020-28052 跟踪问题）。

标签： javaalgorithmmathcryptographybouncycastle

解决方案

对于此类问题，蒙特卡洛模拟是一种有用的健全性检查。我从模拟中得到的结果是 0.0044，大约是问题中计算结果的 4 倍。这对我来说似乎很高，所以我做了一些调试来看看结果来自哪里。

事实证明，绝大多数错误匹配是由于一种非常简单的机制造成的：22 个字符的盐消除了一些感兴趣的字符，而剩余的感兴趣的字符不会出现在哈希的其余部分中.

如问题中所述，有 9 个感兴趣的字符：3456789./

如果其中任何一个出现在盐中，则该indexOf()字符的将匹配，并且该字符不再感兴趣。Monte Carlo 显示，平均而言，9 个字符中有 2.6 个出现在 salt 中，并且被排除在考虑之外。这是有道理的，因为 salt 最多包含 22 个 base-64 字符，大约是三分之一。这是蒙特卡洛模拟的示例运行：

 0     35645 
 1    156228 
 2    283916 
 3    281018 
 4    166381 
 5     61024 
 6     13791 
 7      1850 
 8       139 
 9         3

第一列是被盐消除的感兴趣字符的数量。第二列是 100 万次尝试中发生的次数。例如，在一百万次尝试中，盐消除了所有 9 个感兴趣的字符，从而保证了错误匹配。

在百万次尝试中的 139 次中，盐消除了 9 个感兴趣字符中的 8 个。剩下的字符要么需要在两个哈希字符串中匹配，要么需要在两个哈希字符串中都不存在。它缺席的几率是(63/64) ^ 62 = 0.377。

所以我们可以像这样扩充结果表（这些是蒙特卡洛结果）：

 0     35645    
 1    156228    
 2    283916    
 3    281018    
 4    166381    
 5     61024    
 6     13791    
 7      1850    
 8       139        53   0.386053
 9         3         3   1.000000

倒数第二行可以解释如下：在 100 万次尝试中，盐在 139 次中消除了 8 个感兴趣的字符。在 139 个中，53 个（或 38.6%）导致匹配，因为单个剩余的感兴趣字符没有出现在任一哈希字符串的最后 31 个字符中。

以下是完整结果：

 0     35645         2   0.000070   0
 1    156228        39   0.000250   5
 2    283916       214   0.000757  25
 3    281018       628   0.002237  64
 4    166381      1056   0.006349  83
 5     61024      1114   0.018260  68
 6     13791       702   0.050936  32
 7      1850       265   0.143467   7
 8       139        53   0.386053   0
 9         3         3   1.000000   0

false matches due to elimination and absence:   4076
false matches due to elimination, and matching:  284
total false matches:                            4360 out of 1 million

最后一列是哈希字符串最后 31 个字符中一个或多个感兴趣字符匹配索引的次数。

问题的数学分析

分析问题有两个步骤：

计算盐（22 个字符）消除感兴趣字符（锦鲤¹）的几率。
计算哈希尾部的字符（最后 31 个字符）匹配（第一次出现）或不出现的几率。

^{(1)：我使用“koi”作为缩写，因为拼写检查器认为它是一条鱼，不会理会它。}

第一步的决策树如下所示：

列标题是到目前为止看到的 salt 中的字符数。列脚是该列的除数。行标签是剩下的锦鲤数量。

树的第 0 列：
- 1/1是看到 0 个字符后剩下 9 个锦鲤的概率。
树的第 1 列：
- 55/64是盐的第一个字符不是锦鲤的概率。
- 9/64是盐的第一个字符是锦鲤的概率，剩下 8 个锦鲤。
树的第 2 列：
- 55*55/4096是前两个字符都不是锦鲤的概率。
- 55*9/4096是一个非锦鲤后跟一条锦鲤的概率，剩下 8 条锦鲤。
- 9*56/4096是第一个字符是锦鲤（留下 8）后跟非锦鲤的概率。
- 9*8/4096是前两个字符都是锦鲤的概率，剩下 7 个锦鲤。

完整的决策树有 23 列（盐中 0 到 22 个字符）和 10 行（剩余 9 到 0 条锦鲤）。决策树中的最后一列（如下所示）给出了检查盐后剩余锦鲤数量的几率（百万分之一）。

第二步的决策树稍微复杂一些。在 31 个字符位置中的每一个位置，都需要考虑两个字符，即真实散列中的字符和假散列中的字符。每个都是独立随机选择的，因此64*64=409631 个字符位置中的每一个都有可能。有四种可能的结果：

两个角色都不是锦鲤。剩余锦鲤数量的概率(64-k)/64 * (64-k)/64在哪里。k剩余锦鲤数量不变。
真实哈希中的字符不是锦鲤，但假哈希中的字符是锦鲤。概率为(64-k)/64 * k/64，结果为失败。
真实散列中的字符是锦鲤，而假散列中的字符不是完全相同的字符。概率为k/64 * 63/64，结果为失败。
真实散列中的字符是锦鲤，而假散列中的字符匹配。概率为k/64 * 1/64，锦鲤的数量减一。

以 9 条 koi 开头的决策树如下所示：

与盐决策树相比最大的不同是添加了失败行。匹配可能在任何列失败。一旦发生故障，该故障将延续到决策树中的最后一列。例如，第55*91 列中的失败与第55*9 * 64*642 列中的失败一样（因为无论哪个两个字符出现在第二个位置，结果仍然是失败）。假哈希与给定的真实哈希匹配的概率k（“成功”率）1 - failures就是k.

因此，对于的每个值k，我们可以将其k（从步骤 1 开始）的几率乘以的成功率k。下表显示了结果。

第一列是k，盐后剩余的锦鲤数量。
第二列是该数量锦鲤的几率。
第三列是因为没有 koi 出现在任一散列的尾部而发生的匹配数。
第四列是当一条或多条锦鲤在尾部成功匹配时发生的匹配次数。

所有值都超过一百万。