Collision and Second Preimage Attacks on the HTBC Hash Function
-
摘要: 使用安全的分组密码作为基本组件，并搭配合适的链接结构是一种常用的杂凑函数设计方法.当使用安全性较强的分组密码，如高级加密标准(Advanced Encryption Standard, AES)等作为基本组件时，这类杂凑函数的安全性很大程度上取决于链接结构的安全性.基于三重分组链接的杂凑函数(triple-block-chaining-based hash function, HTBC)，利用安全分组密码作为基本元件，采用一种特殊的三重链接结构，证明了HTBC杂凑算法的这种链接结构是不安全的.基于该链接结构的弱点，利用相关运算的特殊性质，直接构造出HTBC算法的碰撞，构造碰撞的时间复杂度为1.对于长度满足特定要求的消息，可以构造该消息的第二原像.当使用AES-256作为底层的分组密码时，攻击的最大时间复杂度为2\+{112}，低于穷举攻击所需要的时间复杂度2\+{128}；对于某些满足特定性质的弱消息，攻击的时间复杂度仅为1;如果消息的取值足够随机，攻击的平均时间复杂度为2\+{46.56}.Abstract: 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}.
-
Keywords:
- hash function /
- triple-block-chaining /
- HTBC /
- collision /
- second preimage
-
-
期刊类型引用(5)
1. 程宁，戴远泉. 基于核协方差矩阵的无监督数据聚类. 计算机应用与软件. 2023(05): 288-296 . 
百度学术
2. 刘旸，吴安波，李慧斌. LBSN中利用深度学习的POI推荐方法. 计算机工程与设计. 2022(10): 2926-2934 . 百度学术
3. 谢林基，赵铁柱，柳毅. 兴趣点推荐研究综述. 计算机应用与软件. 2022(12): 1-12+57 . 百度学术
4. 魏宁，袁方，刘宇. 面向本地和外地用户情感分析推荐模型. 河北大学学报(自然科学版). 2021(04): 419-425 . 百度学术
5. 李丹霞. 基于位置的社交网络潜在好友推荐系统研究. 计算机产品与流通. 2020(06): 98+105 . 百度学术
其他类型引用(13)
计量
- 文章访问数: 1447
- HTML全文浏览量: 0
- PDF下载量: 663
- 被引次数: 18
下载:
