对HTBC杂凑函数的碰撞和第二原像攻击

摘要

使用安全的分组密码作为基本组件,并搭配合适的链接结构是一种常用的杂凑函数设计方法.当使用安全性较强的分组密码,如高级加密标准(Advanced Encryption Standard,AES)等作为基本组件时,这类杂凑函数的安全性很大程度上取决于链接结构的安全性.基于三重分组链接的杂凑函数(triple-block-chaining-based hash function,HTBC),利用安全分组密码作为基本元件,采用一种特殊的三重链接结构,证明了HTBC杂凑算法的这种链接结构是不安全的.基于该链接结构的弱点,利用相关运算的特殊性质,直接构造出HTBC算法的碰撞,构造碰撞的时间复杂度为1.对于长度满足特定要求的消息,可以构造该消息的第二原像.当使用AES 256作为底层的分组密码时,攻击的最大时间复杂度为2112,低于穷举攻击所需要的时间复杂度2128;对于某些满足特定性质的弱消息,攻击的时间复杂度仅为1;如果消息的取值足够随机,攻击的平均时间复杂度为246.56.