散列固定点/循环的风险有多大?

信息安全 哈希 理论 风险
2021-08-20 09:44:49

使用盐多次散列密码以增加每次蛮力迭代所需的时间是公认的智慧。同时(除非算法另有保证)以固定点循环结束的可能性很小但非零,因此(例如)

hash(hash(hash_so_far + salt) + salt) = hash(hash_so_far + salt)

或者

hash(hash(hash(hash_so_far + salt) + salt) + salt) = hash(hash_so_far + salt)

等等。

这样的身份或短*周期将是安全黑洞——更多的迭代并不意味着更难破解——而这样的周期很常见的算法将比无用更糟糕,导致几个明显的问题:

  • MD* 和 SHA-* 等常见算法的平均和中值循环长度是否已知?
  • 是否有有用的*算法可以保证最小的循环是整个输出空间?

* AFAICT,当输出空间用完时,任何有用的散列算法(有限输出,确定性)都会有至少一个“平凡”的循环。

1个回答

假设您有一个输出为n位的伪随机函数。具有给定盐的良好哈希函数应该表现得像 PRF。

对于重复应用,PRF 的一般、平均结构是有一个大“循环”:如果你反复哈希和重新哈希,你会在某个时候进入一个循环并获得一个你已经遇到过的值。循环的平均长度约为2 n/2在达到循环之前您必须执行的步骤数也将约为2 n/2几乎所有的初始值最终都会带你进入这个内在循环。可能有一些初始值不会导致你进入这个循环;甚至可能存在一些固定点(至少存在一个固定点的概率为 63.2%);但是这种潜在的麻烦点的数量平均不会超过2 n/2.

总而言之,如果n足够大,可以忽略2 -n/2的概率,那么一切都很好。特别是,如果n = 256(您使用的是 SHA-256),那么您就可以不用担心了。即使使用 MD5 ( n = 128 ),短周期也非常罕见,它们不会暗示任何实际的安全问题。

空间循环意味着您的哈希函数不是 PRF,而是一个排列 - 并且只有一个循环的排列。建立单向排列是可能的,但比单向函数要困难得多,因为单向函数似乎可以将一些按位运算和旋转组合在一起;对于排列,您需要数学(例如,以非质数为模取幂),这将意味着一些额外的麻烦(排列将平均是单向的,但可能有些值不会)。