检查我的数学：bouncycastle 问题：Odds 2 不相等的密码被认为是相等的
Check my math: The bouncycastle issue: Odds 2 non-equal passwords considered equal
这是BouncyCastle's v1.66 release of their OpenBSD BCrypt implementation的'check if hashes are equal'代码：
for (int i = 0; i != sLength; i++){
isEqual &= (bcryptString.indexOf(i) == newBcryptString.indexOf(i));
}
其中 sLength 保证为 60（见第 268 行），bcryptString 是一个完整的 openbsd 风格的 bcrypt 字符串，例如 y$.vGA1O9wmRjrwAVXD98HNOgsNpDczlqm3Jq7KnEd1rVAGv3Fykk1a.
错误是使用的方法：他们打算使用 charAt.
此循环的目的是检查从 0 到 59 的每个位置，a 中位置 i 处的字符是否与 i 中位置相同的字符b.
但是，由于 indexOf(int) 的错误使用，相反，这会检查 具有 unicode i 的第一个字符的位置是否与 a 中的位置匹配b 中具有 unicode i 的第一个字符，'not in string' 匹配 'not in string'.
示例："Hello".indexOf(101) returns 1（java是从0开始，101是e的unicode，e是第二个字符）。 "Hello".indexOf(0) returns -1（因为“你好”里面没有unicode-0）
我正在尝试计算以找出以下问题的答案：
如果您尝试使用任意选择的密码而不是实际密码来登录给定用户（假设您碰巧选择准确密码的几率为零），几率是多少该算法错误地将任意选择的密码视为 'equal'?
openbsd字符串的构造
据我所知，这个：y$.vGA1O9wmRjrwAVXD98HNOgsNpDczlqm3Jq7KnEd1rVAGv3Fykk1a
细分如下：
y$ - 常量 - 这是一个表示 'bcrypt string' 的标记。10 - 每个服务器常量 - 使用的回合数；几乎所有地方都是 10，并且对于任何给定用户的 passhash 始终具有相同的值。$ - 再次保持不变。.vGA1O9wmRjrwAVXD98HNO（22 个字符）：用 2 个零字节填充的 16 字节盐，然后进行 base-64 运算，然后去掉最后 2 个字符。这可以用来重建盐。- 其余（31个字符）：
bcrypt(rounds, concat(salt+utf8encode(pass)))的结果，base64编码，扔掉最后一个字符。
- 请注意，base64 实现使用所有小写字母、所有大写字母、所有数字、点和斜杠。
赔率的基本认识
错误的算法最终会检查 unicode 范围 0 到 59（含）中所有字符第一次出现的位置对于两个哈希值（“realhash”和“inhash”）是否相同。 realhash 和 inhash 如果所有 60 个都具有相同的 'pos of first occurrence'，则算法认为密码相等。
在 0 到 59 之间的所有 unicode 符号中，唯一可能出现在这个字符串中的是 0123456789$./.
然而，其中 2 是无关紧要的：对于任何 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- (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 的最新 public 版本已修复此错误。 CVE-2020-28052 跟踪问题）。
对于这样的问题，Monte Carlo simulation 是一种有用的完整性检查。我仿真得到的结果是0.0044，比题中的计算结果高了大约4倍。这对我来说似乎很高，所以我进行了一些调试以查看该结果的来源。
事实证明，绝大多数错误匹配是由于一种非常简单的机制：22 个字符的盐消除了一些 characters-of-interest，而剩余的 characters-of-interest 没有出现在哈希的其余部分。
如题中所述，有9个characters-of-interest：3456789./
如果其中任何一个出现在 salt 中，那么该字符的 indexOf() 将匹配，并且该字符不再有意义。 Monte Carlo 显示 9 个字符中平均有 2.6 个字符出现在盐中，并被排除在考虑范围之外。这是有道理的，因为 salt 最多包含 22 个 base-64 字符，大约三分之一。这是 Monte Carlo 模拟的示例 运行：
0 35645
1 156228
2 283916
3 281018
4 166381
5 61024
6 13791
7 1850
8 139
9 3
第一列是被盐消除的characters-of-interest个数。第二列是 100 万次尝试中出现的次数。例如，在一百万次尝试中有 3 次，salt 消除了所有 9 characters-of-interest，这就保证了错误匹配。
在一百万次尝试中有 139 次，盐消除了 9 次中的 8 次 characters-of-interest。剩下的字符要么需要在两个散列字符串中匹配，要么需要在两个散列字符串中都不存在。它缺席的几率是 (63/64) ^ 62 = 0.377.
所以我们可以像这样增加 table 结果（这些是 Monte Carlo 结果）：
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 characters-of-interest。在 139 个中，有 53 个（或 38.6%）匹配，因为剩余的单个 character-of-interest 没有出现在任一哈希字符串的最后 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 个字符）消除感兴趣字符 (koi1) 的几率。
- 计算散列尾部的字符（最后 31 个字符）匹配（第一次出现）或不匹配的几率。
(1): 我使用“koi”作为缩写，因为拼写检查器认为它是一条鱼，不会管它。
第一步的决策树如下所示：
第headers列是目前看到的salt中的字符数。列脚注是该列的除数。行标签是剩余锦鲤的数量。
树的第 0 列：
1/1是看到0个字符后还有9条锦鲤的概率。
树的第 1 列：
55/64是salt第一个字符不是锦鲤的概率9/64是盐第一个字符是锦鲤的概率，剩下8条锦鲤。
树的第 2 列：
55*55/4096是前两个字符都不是锦鲤的概率。55*9/4096是一条non-koi后一条锦鲤的概率，还剩8条锦鲤。9*56/4096 是第一个字符是锦鲤（剩下 8 个）后跟 non-koi.9*8/4096是前两个字符都是锦鲤的概率，剩下7条锦鲤。
完整的决策树有 23 列（salt 中的 0 到 22 个字符）和十行（剩余 9 到 0 条锦鲤）。决策树中的最后一列（如下所示）给出了检查盐分后剩余锦鲤数量的几率（一百万分之一）。
9 35647
8 156071
7 283872
6 281006
5 166489
4 61078
3 13837
2 1861
1 134
0 4
第二步的决策树有点复杂。在 31 个字符位置的每一个位置，都需要考虑两个字符，即真实散列中的字符和假散列中的字符。每个都是独立随机选择的，因此 31 个字符位置中的每一个都有 64*64=4096 种可能性。有四种可能的结果：
- 两个角色都不是锦鲤。概率
(64-k)/64 * (64-k)/64 其中k 是剩余锦鲤的数量。剩余锦鲤数量不变
- 真哈希中的字符不是锦鲤，而假哈希中的字符是锦鲤。概率是
(64-k)/64 * k/64，结果是失败
- 真散列中的字符是锦鲤，假散列中的字符不是完全相同的字符。概率是
k/64 * 63/64，结果是失败
- 真实hash中的字符是锦鲤，chara假哈希匹配中的 ter。概率为
k/64 * 1/64，锦鲤数量减少一条
9条锦鲤开头的决策树是这样的：
与salt决策树相比最大的区别是增加了失败行。匹配可能在任何列失败。一旦发生故障，该故障将继续到决策树中的最后一列。例如，第 1 列中的 55*9 失败将继续作为第 2 列中的 55*9 * 64*64 （因为无论第二个位置出现哪两个字符，结果仍然是失败）。对于给定的 k（“成功”率），假哈希与真实哈希相匹配的概率是 1 - failures k。
因此，对于 k 的每个值，我们可以将 k（来自步骤 1）的几率乘以 k 的成功率。下面的table显示了结果。
- 第一列是
k，盐后剩余的锦鲤数量。
- 第二列是锦鲤数量的几率。
- 第三列是由于 none 条锦鲤出现在任一散列的尾部而出现的匹配数。
- 第四列是一条或多条锦鲤在尾部配对成功时出现的配对次数。
所有数值都是一百万。
9 35647 3 1
8 156071 40 6
7 283872 216 27
6 281006 628 63
5 166489 1074 85
4 61078 1117 67
3 13837 705 30
2 1861 260 7
1 134 51 1
0 4 4 0
Matches with no koi present in the tail of either hash: 4098
Matches where 1 or more koi match in the tail: 287
Total matches per million: 4385
这是BouncyCastle's v1.66 release of their OpenBSD BCrypt implementation的'check if hashes are equal'代码：
for (int i = 0; i != sLength; i++){
isEqual &= (bcryptString.indexOf(i) == newBcryptString.indexOf(i));
}
其中 sLength 保证为 60（见第 268 行），bcryptString 是一个完整的 openbsd 风格的 bcrypt 字符串，例如 y$.vGA1O9wmRjrwAVXD98HNOgsNpDczlqm3Jq7KnEd1rVAGv3Fykk1a.
错误是使用的方法：他们打算使用 charAt.
此循环的目的是检查从 0 到 59 的每个位置，a 中位置 i 处的字符是否与 i 中位置相同的字符b.
但是，由于 indexOf(int) 的错误使用，相反，这会检查 具有 unicode i 的第一个字符的位置是否与 a 中的位置匹配b 中具有 unicode i 的第一个字符，'not in string' 匹配 'not in string'.
示例："Hello".indexOf(101) returns 1（java是从0开始，101是e的unicode，e是第二个字符）。 "Hello".indexOf(0) returns -1（因为“你好”里面没有unicode-0）
我正在尝试计算以找出以下问题的答案：
如果您尝试使用任意选择的密码而不是实际密码来登录给定用户（假设您碰巧选择准确密码的几率为零），几率是多少该算法错误地将任意选择的密码视为 'equal'?
openbsd字符串的构造
据我所知，这个：y$.vGA1O9wmRjrwAVXD98HNOgsNpDczlqm3Jq7KnEd1rVAGv3Fykk1a
细分如下：
y$- 常量 - 这是一个表示 'bcrypt string' 的标记。10- 每个服务器常量 - 使用的回合数；几乎所有地方都是 10，并且对于任何给定用户的 passhash 始终具有相同的值。$- 再次保持不变。.vGA1O9wmRjrwAVXD98HNO（22 个字符）：用 2 个零字节填充的 16 字节盐，然后进行 base-64 运算，然后去掉最后 2 个字符。这可以用来重建盐。- 其余（31个字符）：
bcrypt(rounds, concat(salt+utf8encode(pass)))的结果，base64编码，扔掉最后一个字符。 - 请注意，base64 实现使用所有小写字母、所有大写字母、所有数字、点和斜杠。
赔率的基本认识
错误的算法最终会检查 unicode 范围 0 到 59（含）中所有字符第一次出现的位置对于两个哈希值（“realhash”和“inhash”）是否相同。 realhash 和 inhash 如果所有 60 个都具有相同的 'pos of first occurrence'，则算法认为密码相等。
在 0 到 59 之间的所有 unicode 符号中，唯一可能出现在这个字符串中的是 0123456789$./.
然而，其中 2 是无关紧要的：对于任何 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- (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 的最新 public 版本已修复此错误。 CVE-2020-28052 跟踪问题）。
对于这样的问题，Monte Carlo simulation 是一种有用的完整性检查。我仿真得到的结果是0.0044，比题中的计算结果高了大约4倍。这对我来说似乎很高，所以我进行了一些调试以查看该结果的来源。
事实证明，绝大多数错误匹配是由于一种非常简单的机制：22 个字符的盐消除了一些 characters-of-interest，而剩余的 characters-of-interest 没有出现在哈希的其余部分。
如题中所述，有9个characters-of-interest：3456789./
如果其中任何一个出现在 salt 中，那么该字符的 indexOf() 将匹配，并且该字符不再有意义。 Monte Carlo 显示 9 个字符中平均有 2.6 个字符出现在盐中，并被排除在考虑范围之外。这是有道理的，因为 salt 最多包含 22 个 base-64 字符，大约三分之一。这是 Monte Carlo 模拟的示例 运行：
0 35645
1 156228
2 283916
3 281018
4 166381
5 61024
6 13791
7 1850
8 139
9 3
第一列是被盐消除的characters-of-interest个数。第二列是 100 万次尝试中出现的次数。例如，在一百万次尝试中有 3 次，salt 消除了所有 9 characters-of-interest，这就保证了错误匹配。
在一百万次尝试中有 139 次，盐消除了 9 次中的 8 次 characters-of-interest。剩下的字符要么需要在两个散列字符串中匹配，要么需要在两个散列字符串中都不存在。它缺席的几率是 (63/64) ^ 62 = 0.377.
所以我们可以像这样增加 table 结果（这些是 Monte Carlo 结果）：
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 characters-of-interest。在 139 个中，有 53 个（或 38.6%）匹配，因为剩余的单个 character-of-interest 没有出现在任一哈希字符串的最后 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 个字符）消除感兴趣字符 (koi1) 的几率。
- 计算散列尾部的字符（最后 31 个字符）匹配（第一次出现）或不匹配的几率。
(1): 我使用“koi”作为缩写，因为拼写检查器认为它是一条鱼，不会管它。
第一步的决策树如下所示：
第headers列是目前看到的salt中的字符数。列脚注是该列的除数。行标签是剩余锦鲤的数量。
树的第 0 列：
1/1是看到0个字符后还有9条锦鲤的概率。
树的第 1 列：
55/64是salt第一个字符不是锦鲤的概率9/64是盐第一个字符是锦鲤的概率，剩下8条锦鲤。
树的第 2 列：
55*55/4096是前两个字符都不是锦鲤的概率。55*9/4096是一条non-koi后一条锦鲤的概率，还剩8条锦鲤。9*56/4096是第一个字符是锦鲤（剩下 8 个）后跟 non-koi. 的概率
9*8/4096是前两个字符都是锦鲤的概率，剩下7条锦鲤。
完整的决策树有 23 列（salt 中的 0 到 22 个字符）和十行（剩余 9 到 0 条锦鲤）。决策树中的最后一列（如下所示）给出了检查盐分后剩余锦鲤数量的几率（一百万分之一）。
9 35647
8 156071
7 283872
6 281006
5 166489
4 61078
3 13837
2 1861
1 134
0 4
第二步的决策树有点复杂。在 31 个字符位置的每一个位置，都需要考虑两个字符，即真实散列中的字符和假散列中的字符。每个都是独立随机选择的，因此 31 个字符位置中的每一个都有 64*64=4096 种可能性。有四种可能的结果：
- 两个角色都不是锦鲤。概率
(64-k)/64 * (64-k)/64其中k是剩余锦鲤的数量。剩余锦鲤数量不变 - 真哈希中的字符不是锦鲤，而假哈希中的字符是锦鲤。概率是
(64-k)/64 * k/64，结果是失败 - 真散列中的字符是锦鲤，假散列中的字符不是完全相同的字符。概率是
k/64 * 63/64，结果是失败 - 真实hash中的字符是锦鲤，chara假哈希匹配中的 ter。概率为
k/64 * 1/64，锦鲤数量减少一条
9条锦鲤开头的决策树是这样的：
与salt决策树相比最大的区别是增加了失败行。匹配可能在任何列失败。一旦发生故障，该故障将继续到决策树中的最后一列。例如，第 1 列中的 55*9 失败将继续作为第 2 列中的 55*9 * 64*64 （因为无论第二个位置出现哪两个字符，结果仍然是失败）。对于给定的 k（“成功”率），假哈希与真实哈希相匹配的概率是 1 - failures k。
因此，对于 k 的每个值，我们可以将 k（来自步骤 1）的几率乘以 k 的成功率。下面的table显示了结果。
- 第一列是
k，盐后剩余的锦鲤数量。 - 第二列是锦鲤数量的几率。
- 第三列是由于 none 条锦鲤出现在任一散列的尾部而出现的匹配数。
- 第四列是一条或多条锦鲤在尾部配对成功时出现的配对次数。
所有数值都是一百万。
9 35647 3 1
8 156071 40 6
7 283872 216 27
6 281006 628 63
5 166489 1074 85
4 61078 1117 67
3 13837 705 30
2 1861 260 7
1 134 51 1
0 4 4 0
Matches with no koi present in the tail of either hash: 4098
Matches where 1 or more koi match in the tail: 287
Total matches per million: 4385