这是bouncycastle 1.66版openbsd bcrypt实现的“检查哈希是否相等”代码：
for (int i = 0; i != sLength; i++){
isEqual &= (bcryptString.indexOf(i) == newBcryptString.indexOf(i));
}哪里 sLength 保证为60（参见第268行），bcryptstring是一个完整的openbsd样式的bcrypt字符串，例如 $2y$10$.vGA1O9wmRjrwAVXD98HNOgsNpDczlqm3Jq7KnEd1rVAGv3Fykk1a .
错误是所用的方法：他们本打算使用 charAt .
此循环的目的是检查从0到59的每个位置的字符 i 在 a 在位置上是同一个字符 i 在 b .
但是，由于错误使用 indexOf(int) ，而是检查第一个字符的位置是否为unicode i 在 a 用unicode匹配第一个字符的位置 i 在 b ，与“not in string”匹配。
例子： "Hello".indexOf(101) 退货 1 （java是基于0的，101是 e ，和 e 是第二个字符）。 "Hello".indexOf(0) 退货 -1 （因为“hello”中没有unicode-0）。
我试着做数学来找出以下问题的答案：
如果您尝试使用任意选择的密码而不是实际密码来登录给定用户（假设您选择确切密码的几率为零），那么此算法错误地将任意选择的密码视为“相等”的几率是多少？
openbsd字符串的构造
据我所知，这是： $2y$10$.vGA1O9wmRjrwAVXD98HNOgsNpDczlqm3Jq7KnEd1rVAGv3Fykk1a 分解如下： $2y$ -常量-它是一个表示“bcrypt string”的标记，差不多。 10 -每个服务器的常量-使用的轮数；几乎所有地方都是10，对于任何给定用户的passhash值都是相同的。 $ -又是一样的。 .vGA1O9wmRjrwAVXD98HNO （22个字符）：用2个零字节填充16字节，然后用base-64ed，然后去掉最后2个字符。这可以用来重建盐。
其余（31个字符）：结果 bcrypt(rounds, concat(salt+utf8encode(pass))) ，base64编码，并抛出最后一个字符。
请注意，base64 impl使用所有小写字母、所有大写字母、所有数字、点和斜杠。
关于几率的基本认识
错误的算法将检查unicode范围0到59（包括0到59）中所有字符第一次出现的位置是否与两个哈希相同（“realhash”和“inhash”）。如果所有60个realhash和inhash的“第一次出现的位置”相同，则算法认为密码相等。
在所有介于0和59之间的unicode符号中，唯一可能出现在这个字符串中的是 0123456789$./ .
然而，其中 $012 不相关：对于任何 passhash.indexOf('$') ，答案是0。对于任何 passhash.indexOf('1') ，答案是4。0和2也是如此。只剩下9个字符，可能导致算法说“inhash”不等于“realhash”： 3456789./ .
要想弄清楚几率是多少，我们需要这9个字符中的每一个都不能成为区分的因素。要找出一个特定的字符（比如说“3”）无法区分的几率有多大，那就是 1-Z z是“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-（vw）；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:1/1000的概率，算法说2个密码是相等的，而他们不是。
我遗漏了什么重要的东西吗？
注意：bouncycastle的最新公开版本已经修复了这个bug。cve-2020-28052跟踪问题）。
1条答案
按热度按时间bfrts1fy1#
对于这样的问题，蒙特卡罗模拟是一个有用的健全性检查。模拟得到的结果是0.0044，比问题的计算结果高出4倍左右。这对我来说似乎很高，所以我做了一些调试，看看结果是从哪里来的。
事实证明，绝大多数错误匹配都是由于一种非常简单的机制：22个字符的salt消除了一些感兴趣的字符，而剩余的感兴趣字符不会出现在散列的其余部分。
如问题所述，有9个有趣的字符：
3456789./如果其中任何一种出现在盐中，那么indexOf()因为那个角色会匹配，而那个角色已经不再有兴趣了。montecarlo显示，平均而言，salt中出现了9个字符中的2.6个，并且被排除在考虑范围之外。这是有道理的，因为salt最多包含22个base-64字符，所以大约有三分之一。下面是蒙特卡罗模拟的一个示例：第一列是被salt删除的感兴趣的字符数。第二列是100万次尝试中发生的次数。例如，在100万次尝试中有3次，salt消除了所有9个感兴趣的字符，这就保证了错误匹配。
在100万次尝试中的139次中，盐消除了9个感兴趣的字符中的8个。剩下的字符要么需要在两个哈希字符串中匹配，要么需要在两个哈希字符串中都不存在。缺席的可能性很小
(63/64) ^ 62 = 0.377.所以我们可以像这样扩充结果表（这些是蒙特卡罗结果）：
从第二行到最后一行可以解释为：盐在100万次尝试中，有139次消除了8个感兴趣的字符。在这139个字符中，有53个（或38.6%）是匹配的，因为剩余的一个感兴趣的字符没有出现在任何一个哈希字符串的最后31个字符中。
以下是完整的结果：
最后一列是哈希字符串的最后31个字符中一个或多个感兴趣的字符与索引匹配的次数。
问题的数学分析
分析问题有两个步骤：
计算salt（22个字符）消除感兴趣字符（koi1）的几率。
计算散列尾部的字符（最后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列（salt中有0到22个字符）和10行（剩下9到0个koi）。决策树中的最后一列（如下所示）给出了盐被检查后剩余锦鲤数量的几率（百万分之一）。
第二步的决策树要复杂一些。在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锦鲤开始的决策树如下所示：
与salt决策树相比，最大的区别是增加了故障行。任何列的匹配都可能失败。一旦发生故障，该故障将前进到决策树中的最后一列。例如
55*9第1栏中的失败按以下顺序进行：55*9 * 64*64在第2列中（因为不管第二个位置出现哪两个字符，结果仍然是失败的）。对于给定的哈希值，假哈希值与真哈希值匹配的概率k（成功率）是1 - failures为了这个k.因此，对于
k，我们可以把几率增加一倍k（从步骤1）的成功率k. 下表显示了结果。第一列是
k，盐后剩余的锦鲤数。第二栏是锦鲤数量的几率。
第三列是由于以下原因而发生的匹配数