破解 CityHash64、MurmurHash2/3、wyhash 等……

主要观点:

  • 哈希函数是很有用的数学对象,有多种用途,但也有其阴暗面,如可能被恶意利用。
  • 介绍了哈希函数安全的基础知识,包括预像抗性、第二预像抗性和碰撞抗性等性质。
  • 讨论了非加密哈希函数,它们速度快但安全性较低。
  • 讲解了逆操作的基本技巧,并利用该技巧攻击了CityHash64MurmurHash2MurmurHash3FarmHash64wyhash等哈希函数。
  • 结论是常见哈希函数较脆弱,应使用随机初始化的哈希表,通用哈希可防止某些攻击,且数据不受用户控制时可使用较快的不安全哈希。

关键信息:

  • 常见哈希函数如MD5SHA-1曾被认为安全,但现在已被攻破。
  • 非加密哈希函数在一些语言中的默认实现,如C++CityHash64Java的简单哈希算法等。
  • 攻击哈希函数的方法,如利用逆操作、特定的输入构造等。
  • 通用哈希函数的概念及相关应用,如polymur-hashPoly1305GCM

重要细节:

  • CityHash64的攻击通过计算模乘逆元等步骤,找到特定输入以得到目标哈希值。
  • MurmurHash2很弱,可通过特定方式创建碰撞字符串,即使随机化种子也会碰撞。
  • MurmurHash3的攻击类似,找到特定输入使哈希函数输出特定值,且可进行通用碰撞攻击。
  • FarmHash64结构与CityHash64相似,攻击方法类似。
  • wyhash在固定种子下易产生碰撞,通过特定技巧利用字符串开头准备“秘密”值。
阅读 94
0 条评论