对强化MD结构杂凑函数的一个新的“牧群”攻击
陈士伟 金晨辉
信息工程大学电子技术学院 郑州 450004
A New Herding Attack on Hash Functions with Strengthening Merkle-Damagard (MD) Construction
Chen Shi-wei Jin Chen-hui
Institute of Electronic Technology, University of Information Engineering, Zhengzhou 450004, China
摘要 该文构造了具有2k 个起始点的变长“钻石树”结构的多碰撞,并据此提出了对强化MD结构杂凑函数的一个新的选择目标强制前缀且原像长度为2k +3块的原像攻击(即“牧群”攻击)。由于增大了攻击过程中可利用的中间链接值的数量,故当k≥n/ 4-1.05时,新的牧群攻击可将该攻击的计算复杂性由现有结果O (2n -2(k +1) +2n /2+k +5/2 )降至O (2n -k /3+2n /2+k +2 )。
关键词 :
密码学 ,
杂凑函数 ,
强化MD结构 ,
原像攻击 ,
牧群攻击 ,
多碰撞
Abstract :This paper constructs a “diamond structure” multicollision with 2k initial values and variant lengths, which is used to propose a new chosen target forced prefix preimage attack (herding attack) on hash functions with Strengthening Merkle-Damagard (SMD) construction to find a preimage with 2k +3 blocks. Since the number of the chaining values available in herding attack is increased, the computational complexity of herding attack is reduced to O (2n -k /3+2n /2+k +2 ) from O (2n -2(k +1) +2n /2+k +5/2 ) for k≥n/ 4-1.05.
Key words :
Cryptography
Hash functions
SMD construction
Preimage attack
Herding attack
Multicollision
收稿日期: 2009-10-09
基金资助: 河南省杰出青年科学基金(0312001800)资助课题
通讯作者:
陈士伟
E-mail: chenshiwei1012@sohu.com
[1]
路秀华,温巧燕,王励成, 杜蛟. 无陷门格基签密方案 [J]. 电子与信息学报, 2016, 38(9): 2287-2293.
[2]
杨小东,李亚楠,高国娟,王彩芬,鲁小勇. 标准模型下的服务器辅助验证代理重签名方案 [J]. 电子与信息学报, 2016, 38(5): 1151-1157.
[3]
毛可飞,陈杰,刘建伟. 层次身份基认证密钥协商方案的安全性分析和改进 [J]. 电子与信息学报, 2016, 38(10): 2619-2626.
[4]
杨孝鹏,马文平,张成丽. 一种新型基于环上带误差学习问题的认证密钥交换方案 [J]. 电子与信息学报, 2015, 37(8): 1984-1988.
[5]
潘森杉,胡予濮,王保仓. 齐次F5算法的简单终止性证明 [J]. 电子与信息学报, 2015, 37(8): 1989-1993.
[6]
严迎建,杨昌盛,李伟,张立朝. ZUC序列密码算法的选择IV相关性能量分析攻击 [J]. 电子与信息学报, 2015, 37(8): 1971-1977.
[7]
张玉磊,李臣意,王彩芬,张永洁. 无证书聚合签名方案的安全性分析和改进 [J]. 电子与信息学报, 2015, 37(8): 1994-1999.
[8]
潘森杉, 胡予濮, 王保仓. 基于标签的矩阵型Gröbner基算法研究 [J]. 电子与信息学报, 2015, 37(4): 881-886.
[9]
郭瑞, 金晨辉. 低轮FOX64算法的零相关-积分分析 [J]. 电子与信息学报, 2015, 37(2): 417-422.
[10]
张彦华, 胡予濮, 江明明, 来齐齐. 格上可撤销的基于身份的适应性安全的加密方案 [J]. 电子与信息学报, 2015, 37(2): 423-428.
[11]
张习勇, 祁应红,高光普,李玉娟. 一种计算旋转对称布尔函数的汉明重量和非线性度的新方法 [J]. 电子与信息学报, 2015, 37(11): 2691-2696.
[12]
杨明, 金晨辉, 张国双. 截断差分概率的上界估计与应用 [J]. 电子与信息学报, 2014, 36(9): 2124-2130.
[13]
沈璇, 李瑞林, 李超, 赵光耀. SHACAL-2算法中非线性函数的差分特性及其应用 [J]. 电子与信息学报, 2014, 36(7): 1661-1666.
[14]
付向群, 鲍皖苏, 史建红, 李发达. 基于多离散对数问题的公钥密码 [J]. 电子与信息学报, 2014, 36(6): 1423-1427.
[15]
李瑞芳, 柯品惠. 一类新的周期为2pq 的二元广义分圆序列的线性复杂度 [J]. 电子与信息学报, 2014, 36(3): 650-654.