1

我试图就用 C 编写的游戏中的一段代码中的漏洞演示一个简单的概念证明。

假设我们要验证角色登录。登录由用户从图形菜单中选择n项目（我们现在假设）来处理。n=5这些物品都是中世纪的主题：

例如：

 _______________________________
|           |           |       |
| Bow       | Sword     | Staff |
|-----------|-----------|-------|
| Shield    | Potion    | Gold  |
|___________|___________|_______|

用户必须单击每个项目，然后为每个项目选择一个数字。

然后验证算法执行以下操作：

  1. 确定选择了哪些项目
  2. 将每个字符串删除为小写（即：Bow变为bow等）
  3. 为每个字符串计算一个简单的字符串哈希（即：`bow => b=2, o=15, w=23, sum = (2+15+23=40)
  4. 将哈希乘以用户为相应项目选择的值；这个新值称为key
  5. 将keys每个选定项目的总和; 这是最终的验证哈希
  6. 重要提示：验证器将接受此哈希以及它的非零倍数（即：如果最终哈希等于 1111，则 2222、3333、8888 等也是有效的）。

因此，例如，假设我选择：

Bow (1)
Sword (2)
Staff (10)
Shield (1)
Potion (6)

该算法将这些字符串中的每一个都删除为小写，计算它们的字符串哈希，将该哈希乘以为每个字符串选择的数字，然后将这些键相加。

例如：

Final_Validation_Hash = 1*HASH(Bow) + 2*HASH(Sword) + 10*HASH(Staff) + 1*HASH(Shield) + 6*HASH(Potion)

通过应用欧拉方法，我计划证明这些哈希不是唯一的，并想设计一个简单的应用程序来证明它。

就我而言，对于 5 个项目，我基本上会尝试计算：

(B)(y) = (A_1)(x_1) + (A_2)(x_2) + (A_3)(x_3) + (A_4)(x_4) + (A_5)(x_5)

在哪里：

B is arbitrary
A_j are the selected coefficients/values for each string/category
x_j are the hash values for each string/category
y is the final validation hash (eg: 1111 above)
B,y,A_j,x_j are all discrete-valued, positive, and non-zero (ie: natural numbers)

有人可以帮助我解决这个问题还是给我一个类似的例子（即：代码、计算出的方程式等）？我只需要解决最后一步（即：（B）（Y）= ...）。

最后，我编写了一个递归算法，该算法n深入层次，然后为所有剩余的可能组合处理递增、测试等。效率不是很高，但它确实有效。我可以根据要求提供（太大，无法在此处发布）。

4

5 回答 5

1

它可能是唯一的，也可能不是唯一的，具体取决于菜单上的项目x_j、系数A_j、验证散列y以及所选项目的数量n。

例如，如果您的验证哈希是 会发生什么1？然后一切都会验证。

另一方面，如果您有n项目总数，那么只有一个可能的哈希值是唯一的。

当然，这些都是极端的例子，但它们说明了这一点。这取决于你的参数。除了蛮力之外，没有一种简单的通用方法可以检测哈希是否唯一。

于 2012-06-12T16:21:18.500 回答
1

这很简单，因为该算法接受非零倍数。如果将所有输入乘以 2，则会发生冲突：

Bow (1)
Sword (2)
Staff (10)
Shield (1)
Potion (6)

y = (A_1)(x_1) + (A_2)(x_2) + (A_3)(x_3) + (A_4)(x_4) + (A_5)(x_5)

然后将它们乘以 2：

Bow (2)
Sword (4)
Staff (20)
Shield (2)
Potion (12)

2(A_1)(x_1) + 2(A_2)(x_2) + 2(A_3)(x_3) + 2(A_4)(x_4) + 2(A_5)(x_5)
= 2((A_1)(x_1) + (A_2)(x_2) + (A_3)(x_3) + (A_4)(x_4) + (A_5)(x_5))
= 2y
于 2012-06-12T16:22:05.537 回答
1

虽然这不是一个正式的证明，但我有一个想法。

让不同字符串的哈希为h_1, h_2, ...,h_n线性和为

y = h_1 + h_2 + ... + h_n

一旦我们有了y，我们总能找到h_1', h_2', ...,h_n'这样至少对于系列中的一对iand j h_i != h_j'。

所以我们可以有重复h的值来得到最终的总和。

再次，因为每个h值都是由一些整数（字符的代表值）的线性和产生的，因此h可以通过不同的线性和来获得一个特定的值，即不同的字符串。

乘数值可以调整。此外，即使乘数值是恒定的，即重复哈希生成器无法选择它，h也可以修改乘以乘数的值，以使相乘的键的总和保持不变。

因此，我们可以从许多字符串中生成一个哈希。

于 2012-06-12T16:23:00.247 回答
1

在我看来，大多数用户会为每个项目选择相当小的数字（毕竟“2”比“438483”更容易记住）。

鉴于这种限制，蛮力可能实际上是合理的。

简单地为 5 个符号生成所有可能的输入值加上一个在 1..99 范围内的数字，计算结果哈希，并计算（例如使用字典）产生给定哈希的不同组合的数量应该给出经验了解最可能输入值的哈希分布。

从那里我将查看实际生成了多少不同的哈希值（如果哈希是 Int32，则在 2^32 个可能的哈希值中），并查找以特定频率生成的哈希值（具有高在字典中计数）。

于 2012-06-12T16:18:36.187 回答
1

将除最后一个系数之外的所有系数都设置为 1，因此您会得到形式为 An*xn = r (mod y) 的东西，然后使用扩展的欧几里得算法找到解决方案，请参阅Wikipedia

于 2012-06-12T16:37:53.220 回答