Improved Preimage Attack on 3-Pass HAVAL

doi:10.1007/s12204-011-1215-3

摘要/Abstract

摘要： HAVAL is a hash function proposed by
Zheng et al. in 1992, including 3-, 4- and 5-pass versions.
We improve pseudo-preimage and preimage attacks on 3-pass HAVAL at
the complexity of 2^ 172 and 2^ 209.6 , respectively, as
compared to the previous best known results: 2^ 192 and 2^ 225
by Sasaki et al. in 2008. We extend the skip interval for
partial-patching and apply the initial structure technique to find
the better message chunks, and combine the
indirect-partial-matching, partial-fixing and multi-neutral-word
partial-fixing techniques to improve the attacks based on the
meet-in-the-middle method. These are the best pseudo-preimage and
preimage attacks on 3-pass HAVAL.

关键词: , hash, meet-in-the-middle, preimage

Abstract: HAVAL is a hash function proposed by
Zheng et al. in 1992, including 3-, 4- and 5-pass versions.
We improve pseudo-preimage and preimage attacks on 3-pass HAVAL at
the complexity of 2^ 172 and 2^ 209.6 , respectively, as
compared to the previous best known results: 2^ 192 and 2^ 225
by Sasaki et al. in 2008. We extend the skip interval for
partial-patching and apply the initial structure technique to find
the better message chunks, and combine the
indirect-partial-matching, partial-fixing and multi-neutral-word
partial-fixing techniques to improve the attacks based on the
meet-in-the-middle method. These are the best pseudo-preimage and
preimage attacks on 3-pass HAVAL.

Key words: , hash, meet-in-the-middle, preimage

中图分类号:

TP309

ZHONG Jin-min (钟锦敏), LAI Xue-jia (来学嘉), DUAN Ming (段明) . Improved Preimage Attack on 3-Pass HAVAL[J]. 上海交通大学学报（英文版）, 2011, 16(6): 713-721.

ZHONG Jin-min (钟锦敏), LAI Xue-jia (来学嘉), DUAN Ming (段明) . Improved Preimage Attack on 3-Pass HAVAL[J]. Journal of shanghai Jiaotong University (Science), 2011, 16(6): 713-721.

参考文献

1 Wang X Y, Lai X J, Feng D G, et al. Cryptanalysis of the hash

functions MD4 and RIPEMD [C]// Advances in Cryptology,

EUROCRYPT 2005, LNCS 3494. Berlin: Springer-Verlag, 2005: 1-18.

    2 Wang X Y, Yu H B. How to break MD5 and other hash functions

[C]// Advances in Cryptology, EUROCRYPT 2005, LNCS

3494. Berlin: Springer-Verlag, 2005: 19-35.

    3 Wang X Y, Yu H B, Yin Y Q L. Efficient collision search

attacks on SHA-0 [C]// Advances in Cryptology, CRYPTO 2005,

LNCS 3621. Berlin: Springer-Verlag, 2005: 1-16.

    4 Wang X Y, Yin Y Q, Yu H B.   Finding collisions in the full

SHA-1 [C]// Advances in Cryptology, CRYPTO 2005, LNCS 3621.

Berlin: Springer-Verlag, 2005: 17-36.

    5 Zheng Y L, Pieprzyk J, Seberry J.   HAVAL---A one-way hashing

algorithm with variable length of output [C]// Advances in

Cryptology, ASIACRYPT 1992, LNCS 718. Berlin: Springer-Verlag,

1993: 83-104.

    6 Wang X Y, Feng D G, Yu X Y.   An attack on hash function

HAVAL-128 [J]. Science in China Series F: Information

Sciences, 2005, 48 (5): 545-556.

    7 Van ROMPAY B, Biryukov A, Preneel B,   et al. Cryptanalysis of

3-pass HAVAL [C]// Advances in Cryptology, ASIACRYPT 2003, LNCS

2894. Berlin: Springer-Verlag, 2003: 228-245.

    8 Yu H B, Wang X Y, Yun A, et al. Cryptanalysis of the full

HAVAL with 4 and 5 passes [C]// Fast Software Encryption 2006,

LNCS 4047. Berlin: Springer-Verlag, 2006: 89-110.

    9 Suzuki K, Kurosawa K.   How to find many collisions of 3-pass

haval [C]// Second International Workshop on Security, IWSEC

2007, LNCS 4752. Berlin: Springer-Verlag, 2007: 428-443.

    10 Yu H B, Wang X Y.   Multi-collision attack on the compression

functions of MD4 and 3-pass HAVAL [C]// Information Security

and Cryptology, ICISC 2007, LNCS 4817. Berlin: Springer-Verlag,

2007: 206-226.

    11 Lee E, Chang D, Kim J,   et al. Second preimage attack on 3-pass

HAVAL and partial key-recovery attacks on HMAC/NMAC-3-pass HAVAL

[C]// Fast Software Encryption 2008, LNCS 5086. Berlin:

Springer-Verlag, 2008: 189-206.

    12 Yu H B, Wang G L, Zhang G Y, et al. The second preimage attack

on MD4 [C]// Cryptology and Network Security (CANS) 2005, LNCS

3810. Berlin: Springer-Verlag, 2005: 1-12.

    13 Wang G L, Wang S H.   Second preimage attack on 5-pass HAVAL and

partial key-recovery attack on HMAC/NMAC-5-pass HAVAL [C]//

Progress in Cryptology, AFRICACRYPT 2009, LNCS 5580. Berlin:

Springer-Verlag, 2009: 1-13.

    14 Aoki K, Guo J, Matusiewicz K, et al. Preimages for

step-reduced SHA-2 [C]// Advances in Cryptology, ASIACRYPT

2009, LNCS 5912. Berlin: Springer-Verlag, 2009: 578-597.

    15 Sasaki Y, Aoki K.   Finding preimages in full MD5 faster than

exhaustive search [C]// Advances in Cryptology, EUROCRYPT 2009,

LNCS 5479. Berlin: Springer-Verlag, 2009: 134-152.

    16 Leurent G.   MD4 is not one-way [C]// Fast Software

Encryption 2008, LNCS 5086. Berlin: Springer-Verlag, 2008: 412-428.

    17 Sasaki Y.   Meet-in-the-middle attacks using output truncation

in 3-pass HAVAL [C]// Information Security (ISC) 2009, LNCS

5735. Berlin: Springer-Verlag, 2009: 79-94.

    18 Aumasson J P, Meier W, Mendel F.   Preimage attacks on 3-pass

HAVAL and step-reduced MD5 [C]// Selected Areas in Cryptography

2008, LNCS 5381. Berlin: Springer-Verlag, 2009: 120-135.

    19 Sasaki Y, Aoki K.   Preimage attacks on 3, 4, and 5-pass HAVAL

[C]// Advances in Cryptology, ASIACRYPT    2008,

LNCS 5350. Berlin: Springer-Verlag, 2008: 253-271.

    20 Isobe T, Shibutani K.   Preimage attacks on reduced tiger and

SHA-2 [C]// Fast Software Encryption 2009, LNCS 5665. Berlin:

Springer-Verlag, 2009: 139-155.

    21 Aoki K, Sasaki Y.   Meet-in-the-middle preimage attacks against

reduced SHA-0 and SHA-1 [C]// Advances in Cryptology, CRYPTO

2009, LNCS 5677. Berlin: Springer-Verlag, 2009: 70-89.

    22 Guo J, Ling S, Rechberger C,   et al. Advanced

meet-in-the-middle preimage attacks: First results on full tiger,

and improved results on MD4 and   SHA-2   [C]// Advances in

Cryptology, ASIACRYPT 2010, LNCS 6477. Berlin: Springer-Verlag,

2010: 56-75.

    23 Zhong J M, Lai X J.   Improved preimage attack on one-block md4

[EB/OL]. (2011-07-01). http://eprint.iacr.org/2010/583.pdf.

    24 Aoki K, Sasaki Y.   Preimage attacks on one-block MD4, 63-step

MD5 and more [C]// Selected Areas in Cryptography 2008, LNCS

5381. Berlin: Springer-Verlag, 2009: 103-119.

    25 Lai X J, Massey J L.   Hash functions based on block ciphers

[C]// Advances in Cryptology, EUROCRYPT 1992, LNCS 658.

Berlin: Springer-Verlag, 1993: 55-70.

[1]	王聚团, 戚晓宁, 黄志明. 水下生产管汇测试技术及其改进研究[J]. 海洋工程装备与技术, 2022, 9(2): 43-49.
[2]	袁振钦, 邹科, 孙亚峰, 刘刚, 屈衍, 李居跃. 基于时域分析法的动态电缆疲劳分析[J]. 海洋工程装备与技术, 2022, 9(2): 50-55.
[3]	王娟, 杨明旺, 郑茂尧, 刘凌云, 赵立君. 高强钢在大型半潜式平台组块建造中的应用[J]. 海洋工程装备与技术, 2022, 9(1): 27-31.
[4]	陈欣, 赵晓磊, 王立坤, 肖德明, 张腾月. 深水大型吸力锚建造技术研究[J]. 海洋工程装备与技术, 2022, 9(1): 32-36.
[5]	尹彦坤, 易涤非. 半潜式生产平台船体结构关键节点工程临界评估[J]. 海洋工程装备与技术, 2022, 9(1): 52-57.
[6]	MA Qunsheng (马群圣), CEN Xingxing (岑星星), YUAN Junyi (袁骏毅), HOU Xumin (侯旭敏). Word Embedding Bootstrapped Deep Active Learning Method to Information Extraction on Chinese Electronic Medical Record[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(4): 494-502.
[7]	ZHANG Shengfa (张胜发), TANG Na (唐纳), SHEN Guofeng (沈国峰), WANG Han (王悍), QIAO Shan (乔杉). Universal Software Architecture of Magnetic Resonance-Guided Focused Ultrasound Surgery System and Experimental Study[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(4): 471-481.
[8]	安庆升, 孙立东, 武秋生. 碳纤维增强复合材料发射筒设计研究[J]. 空天防御, 2021, 4(2): 13-.
[9]	KONG Xiangqiang (孔祥强), MENG Xiangxi (孟祥熙), LI Jianbo (李见波), SHANG Yanping (尚燕平), CUI Fulin (崔福林) . Comparative Study on Two-Stage Absorption Refrigeration Systems with Different Working Pairs[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(2): 155-162.
[10]	ZHUANG Weimin (庄蔚敏), WANG Pengyue (王鹏跃), AO Wenhong (熬文宏), CHEN Gang (陈刚) . Experiment and Simulation of Impact Response of Woven CFRP Laminates with Different Stacking Angles[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(2): 218-230.
[11]	ZHOU Xuhui (周旭辉), ZHANG Wenguang (张文光), XIE Jie (谢颉). Effects of Micro-Milling and Laser Engraving on Processing Quality and Implantation Mechanics of PEG-Dexamethasone Coated Neural Probe[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(1): 1-9.
[12]	HUANG Ningning (黄宁宁), MA Yixin (马艺馨), ZHANG Mingzhu (张明珠), GE Hao (葛浩), WU Huawei (吴华伟). Finite Element Modeling of Human Thorax Based on MRI Images for EIT Image Reconstruction[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(1): 33-39.
[13]	WANG Xianjin, GAO Xu, YU Kuigang . Fixture Locating Modelling and Optimization Research of Aluminum Alloy Sidewall in a High-Speed Train Body[J]. J Shanghai Jiaotong Univ Sci, 2020, 25(6): 706-713.
[14]	QIAO Xing, MA Dan, YAO Xuliang, FENG Baolin. Stability and Numerical Analysis of a Standby System[J]. J Shanghai Jiaotong Univ Sci, 2020, 25(6): 769-778.
[15]	WU Jin, MIN Yu, YANG Xiaodie, MA Simin . Micro-Expression Recognition Algorithm Based on Information Entropy Feature[J]. Journal of Shanghai Jiao Tong University(Science), 2020, 25(5): 589-599.