mzh/blog

NABHash介绍及原理

项目地址

github.com/mengzhuo/nabhash

什么是NABHash?

NABHash 是一种 超级快的 基于AES的非密码学安全哈希算法(Hash Algorithm)

有以下特点:

性能对比图

NABHash性能对比图

可以看到,在65536字节时,NABHash的速度是xxhash、murmur3这些常见快速哈希算法的10倍左右。

为啥可以这么快?

因为“简约”。

一般哈希算法是使用加法、异或、移位完成的(Shift Add XOR) 而哈希算法为了满足雪崩性和分布性,会多计算几轮,导致就算使用SIMD技术,也无可避免性能下降。

这就是NABHash优化的地方,NABHash对于一个16字节数据块,在Intel平台上仅仅使用了1个指令:

AESENC

即AES加密。而选择AES的主要原因是,现在主流的CPU都支持了AES硬件加速(ARM、PPC),而SHA系列虽然有硬件支持,但指令复杂,往往一个数据块还需要多个指令才能完成计算。

主要流程可见下图: NABHash流程图

相当于用数据不停地加密初始向量值(0x5A827999 0x6ED9EBA1),最终得到一个哈希值。

可能有些小朋友就会问了,为啥初始向量是这个值,是随机生成的么?不,这是sha1的初始key值。

最后,为啥叫NABHash

因为这是Non-Crypto-Safe AES Based Hash,简写NABHash,基于AES的非密码学安全哈希算法。