验证成本低但计算哈希算法成本高

信息安全 哈希 垃圾邮件
2021-08-17 19:39:13

我正在寻找一种有点像 bcrypt 的散列算法,除了我希望验证非常便宜。

作为一项反垃圾邮件措施,我想要求我的客户在提交信息之前花费半秒的计算时间。我想将他们的信息分配给散列,然后在我这边快速检查信息是否正确散列。使用 bcrypt 之类的东西来保护自己免受 DoS 攻击是不可行的。

由于它是一种反垃圾邮件措施,我并不追求完美,散列算法可能很弱。

这种算法有名字吗?我能用什么?

1个回答

它被称为“工作量证明”算法。基本思想是在创建哈希后强制调用者做一些额外的工作。您可以使用任何散列算法。这是一种简单的形式:

  1. 客户端计算数据的哈希值。(比如说,它是 160 位。)

  2. 客户端创建一个包含散列和其余数据全为零的块。(假设块是 512 位。)

  3. 客户端计算这个块的哈希值。

  4. 如果这个最终哈希值低于目标值,则客户端提交它刚刚哈希过的整个块并完成。

  5. 客户端将块中除散列之外的数据递增,并跳转到第 3 步。

当服务器获得区块时,它会计算区块的哈希值。如果哈希值低于目标值,则服务器接受该块并从块的开头读取哈希值。如果哈希值高于目标值,服务器将拒绝它。

因此,如果目标是 0fffffff.. 客户端通常必须执行第 3 步(散列操作)16 次,然后才能获得低于目标的最终散列。(在十六进制中,给定的哈希值以 0 开头的可能性为 16 分之一。)如果这太简单了,请将目标设置为 00fff ... 并且客户端通常必须执行 256 个块哈希。

平均而言,您可以强制客户端执行任意数量的哈希。客户端需要执行的实际哈希数遵循泊松分布。缺点是客户总是有可能不走运并且必须做大量的工作。

如果您需要阻止客户端“重用”工作,您可以让客户端要求您提供序列号。然后该块包含哈希,然后是序列号,然后是随机数(客户端增加的部分)。然后,您可以验证序列号,这样客户端就不能重用它之前所做的块,也不能预先计算块。

如果您不喜欢这样,您也可以选择两个随机素数并发送这些素数的乘积。强制客户考虑该数字。每个因子接受一个哈希值。当然,您可以根据需要控制客户需要做的工作量来使素数变大或变小。