设计良好的非加密Hash函数

http://ticki.github.io/blog/designing-a-good-non-cryptographic-hash-function/

函数设计的关键是,要对每个input block -> output block 映射关系进行打散(diffusions & bijection).diffusions通常可以通过使用小的bijective的组件(函数)进行组合,这些函数称为 sub-diffusions. 常见的下面这些,其中P(x) 表示对X中bits进行重排列。

  1. d(x) = P(x) ^ m (和固定值进行异或)
  2. d(x) = P(x) ^ x
  3. d(x) = (x << m) ^ x
  4. d(x) = (ax + c) MOD m. 其中gcd(x, m) = 1. 称为linear subdiffusions.
  5. d(x) = x ^ (x+c) 称为arithmetic subdiffusions.

在设计这些sub-diffusions的时候务必保证有一个函数是zero-senstive. 大致意思就是如果输入是0,那么输出必须是某个特定的值。我其实也没有太理解这个有什么特别的意义。

测量Hash函数冲突率,通常使用雪崩(avalanche)图进行观察。图的大致意思是,X轴是inputs bits, Y轴是output bits. 如果input中某个bits的发生改变的话,那么output上会有那些bits发生变化。将这些变化数量统计出来做成热力图,就可以大致判断这个Hash函数的冲突比例。

Sorry, your browser does not support SVG. Sorry, your browser does not support SVG.

Sorry, your browser does not support SVG. Sorry, your browser does not support SVG.

设计好了冲突率比较低的函数之后,接下来就是要提高这个hash函数的执行效率了,可以上SIMD或者是调整指令顺序来提高流水。这里有个项目可以来测试hash函数 https://github.com/aappleby/smhasher. 包括执行速度和冲突率。