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

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

Collision and Second Preimage Attacks on the HTBC Hash Function

A common way to build hash functions is combining a secure block cipher with an appropriate chaining structure. When the block cipher used has strong security properties such as AES, the security of this kind of hash functions mainly depends on the security of the certain chaining structure. HTBC is a hash function design which uses a special triple-block-chaining structure to be combined with a secure block cipher. The triple-block-chaining structure used by the HTBC hash function is not secure. Based on the serious flaws of the chaining structure, using particular properties of related operations, the collisions of the HTBC hash function can be directly constructed, and the time complexity to find a single collision is only 1. For the messages with certain length, a second preimage can be constructed as well. When AES-256 is used as the block cipher, the maximum time complexity to launch a second preimage attack is 2+{112}, which is lower than the brute force attack bound 2+{128}. For the particular weak messages, the overall time needed to find a second preimage is only 1. If the message is randomly chosen, the average time complexity to launch a successful second preimage attack is 2+{46.56}.