对联接杂凑函数的“特洛伊”消息攻击

doi:10.11959/j.issn.1000-436x.2016154

通信学报 ›› 2016, Vol. 37 ›› Issue (8): 45-50.doi: 10.11959/j.issn.1000-436x.2016154

对联接杂凑函数的“特洛伊”消息攻击

陈士伟^1,²,金晨辉¹

¹ 解放军信息工程大学三院，河南郑州 450002
² 信息保障技术重点实验室，北京 100072

出版日期:2016-08-25 发布日期:2016-09-01
基金资助:
国家自然科学基金资助项目

Trojan message attack on the concatenated hash functions

Shi-Wei CHEN^1,²,INChen-Hui J¹

¹ The Third College,PLA Information Engineering University,Zhengzhou 450002,China
² Science and Technology on Information Assurance Laboratory,Beijing 100072,China

Online:2016-08-25 Published:2016-09-01

摘要/Abstract

摘要：

“特洛伊”消息攻击是Andreeva等针对MD结构杂凑函数提出的一种攻击方法，首次将其应用于不同于MD结构的一类杂凑函数，即联接杂凑。结合联接杂凑的特点，综合利用Joux的多碰撞和深度为n?l的“钻石树”结构多碰撞，构造出了2n-bit联接杂凑函数的长度为n 2^k· 块的“特洛伊”消息，并据此首次提出了对其的固定前缀“特洛伊”消息攻击，其存储复杂性为2l+2^n?l+1+n·2^k+1块消息，时间复杂性为O(n·2^n+k+l·2^l)次压缩函数运算，远低于理想的时间复杂性O(n·2^2n+k)。

关键词: 杂凑函数, 联接杂凑, “特洛伊”消息攻击, 多碰撞, 复杂性

Abstract:

The Trojan message attack was proposed by Andreeva,et al.aiming at the hash functions with MD structure.First it was applied on the hash function beyond MD structure,that was,concatenated hash.Utilizing the property of the concatenated hash,and combining the Joux's multicollision and the “diamond” structure with the depth of n?l,a Trojan message of the length n 2^k· blocks for the 2n-bit concatenated hash was constructed,based on which a chosen-prefix Trojan message attack was first proposed.And the memory complexity of proposed attack is about 2l+2^n?l+1+n·2^k+1blocks and the time complexity is about O (n·2^n+k+l·2^l)computations of the compression function,much less than the ideal value O(n·2^2n+k).

Key words: hash functions, concatenated hash, Trojan message attack, multicollsion, complexity

陈士伟,金晨辉. 对联接杂凑函数的“特洛伊”消息攻击[J]. 通信学报, 2016, 37(8): 45-50.

Shi-Wei CHEN,INChen-Hui J. Trojan message attack on the concatenated hash functions[J]. Journal on Communications, 2016, 37(8): 45-50.

图/表 1

参考文献 8

[1]	MERKLE R . A certified digital signature[C]// Advances in Cryptology-CRYPTO 1989.LNCS 435,Heidelberg:Springer-Verlag. c1990:218-238.
[2]	DAMGARD I . A design principle for hash functions[C]// Advances in Cryptology-CRYPTO 1989.LNCS 435,Heidelberg:Springerr-Verlag. c1990:416-427.
[3]	JOUX A . Multicollisions in iterated hash functions application to cascaded constructions[C]// Advances in Cryptology–CRYPTO 2004.LNCS 3152,Heidelberg:Springer-Verlag. c2004:306-316.
[4]	KELSEY J , SCHNEIER B . Second preimages on n-bit hash functions for much less than 2nwork[C]// Advances in Cryptology- EUROCRYPT 2005.LNCS 3494,Heidelberg:Springer-Verlag. c2005:474-490.
[5]	KELSEY J , KOHNO T . Herding hash functions and the nostradamus attack[C]// Advances in Cryptology–EUROCRYPT 2006.LNCS 4004,Heidelberg:Springer-Verlag. c2006:183-200.
[6]	陈士伟，金晨辉 . 对强化MD结构杂凑函数的一个新的“牧群”攻击[J]. 电子与信息学报， 2010，32(8):1953-1955. CHEN S W , JIN C H . A new herding atlack on hash functions with strengthening Merke-Damgard(MD) construction[J]. Journal of Elec-tronics ＆ Information Technology, 2010,32(8):1953-1955.
[7]	ANDREEVA E , BOUILLAGUET C , DUNKELMAN O , et al. Herd-ing,second preimage and Trojan message attacks beyond Merkle-Damg?rd[C]// Selected Areas in Cryptography 2009.LNCS 5867,Heidelberg:Springer-Verlag. c2009:393-414.
[8]	KORTELAINEN T , KORTELAINEN J . Advances in Cryptology–ASIACRYPT 2013,Part II,LNCS 8270.Heidelberg:Springer-Verlag[C]// Advances in Cryptology–ASIACRYPT 2013,Part II,LNCS 8270.Heidelberg:Springer-Verlag. c2013:524-539.

对联接杂凑函数的“特洛伊”消息攻击

Trojan message attack on the concatenated hash functions

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 1

参考文献 8

相关文章 5

Metrics

推荐阅读 0

[1]	王高丽1,2，申延召1. 带消息填充的29步SM3算法原根和伪碰撞攻击[J]. 通信学报, 2014, 35(2): 6-45.
[2]	王高丽,申延召. 带消息填充的29步SM3算法原根和伪碰撞攻击[J]. 通信学报, 2014, 35(2): 40-45.
[3]	官尚元,伍卫国,董小社,钱德沛. 自动信任协商的形式化描述与验证研究[J]. 通信学报, 2011, 32(2): 86-99.
[4]	石福丽,朱一凡. 基于超网络理论的军事通信网络复杂性度量方法[J]. 通信学报, 2011, 32(12): 51-59.
[5]	汪一鸣,朱洪波. 一种较低复杂度的UWB信道自适应均衡技术[J]. 通信学报, 2005, 26(10): 13-18.