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

Collision and Second Preimage Attacks on the HTBC Hash Function

作　　者：马冰珂 李宝[1] 

机构地区：[1]中国科学院信息工程研究所,北京100195

出　　处：《计算机研究与发展》2014年第11期2513-2517,共5页Journal of Computer Research and Development

基　　金：国家"九七三"重点基础研究发展计划基金项目(2013CB338002);国家"八六三"高技术研究发展计划基金项目(2013AA014002);中国科学院战略性先导专项(XDA06010702);中国科学院信息工程研究所密码研究专项基金(Y3Z0027103)

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

关 键 词：杂凑函数 三重链接 HTBC 碰撞 第二原像 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]