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

摘要：

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

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

所属期刊栏目：51

分类号：TP309(计算技术、计算机技术)

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

在线出版日期：2014-12-01（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：2513-2517