Computer Science ›› 2016, Vol. 43 ›› Issue (8): 123-127, 147.doi: 10.11896/j.issn.1002-137X.2016.08.026

Previous Articles     Next Articles

New Algorithm for Automatic Deriving Sufficient Conditions of SHA-1

HU Yun-shan, SHEN Yi, ZENG Guang and HAN Wen-bao   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Deriving sufficient conditions is one of the important technologies in the differential mode attacking.In this paper,turning the problem of deriving sufficient conditions into structure of linear equations in F2,using the judgment theorem of linear equations to determine the correctness of the sufficient conditions derived by each step,a new algorithm for automatic deriving sufficient conditions of SHA-1 hash function was proposed.This algorithm is equally applicable to derive sufficient conditions in SHA-0 which has similar structure with SHA-1 after appropriate deformation.

Key words: Cryptology,Hash function,SHA-1,Sufficient conditions,Collision attacks

[1] Wang Xiao-yun,L Yi-qun,Yu Hong-bo.Finding collisions in the full SHA-1[M]∥Advance in Cryptology-CRYPTO 2005.Berlin Heidelberg:Springer-Verlag,2005:17-36
[2] McDonald C,Hawkes P,Pieprzyk J.Differential Path for SHA-1 with complexity O(252):Report 2009 ,259[R/OL].Cryptology ePrint Archive,
[3] Chen R.New Techniques for Cryptanalysis of CryptographicHash Functions[D].Technion:Technion-Israel Institute of Technology,2011
[4] Stevens M.Attacks on Hash Functions and Applications [D].Holland:Leiden University,2012
[5] Stevens M.New Collision Attacks on SHA-1 Based on Optimal Joint Local-Collision Analysis[M]∥Advance in Cryptology-CRYPTO 2005.Berlin Heidelberg:Springer-Verlag,2013:245-261
[6] Biham E,Chen R,Joux A.Cryptanalysis of SHA-0 and Reduced SHA-1[J].Journal of Cryptology ,2014,8(1):110-160
[7] Cannière C D,Rechberger C.Finding SHA-1 Characteristics:General Results and Applications [M]∥Advances in Cryptology-ASIACRYPT 2006.Berlin Heidelberg:Springer-Verlag,2006:1-20
[8] Cannière C D,Mendel F,Rechberger C.Collisions for 70-StepSHA-1:On the Full Cost of Collision Search [M]∥Selected A-reas in Cryptography.Berlin Heidelberg:Springer-Verlag,2007:56-73
[9] Grechnikov E A.Collisions for 72-step and 73-step SHA-1:Improvements in the Method of Characteristics: Report 2010,413 [R/OL].Cryptology ePrint Archive,
[10] Grechnikov E A,Adinetz A V.Collision for 75-step SHA-1:Intensive Parallelization with GPU: Report 2011,641 [R/OL].Cryptology ePrint Archive,
[11] Adinetz A V,Grechnikov E A.Building a collision for 75-round reduced SHA-1 Using GPU Clusters[M]∥Euro-Par 2012 Pa-rallel Processing.Berlin Heidelberg:Springer-Verlag,2012:933-944
[12] Sugita M,Kawazoe M,Perret L,et al.Algebraic Cryptanalysisof 58-Round SHA-1[M]∥Fast Software Encryption.Berlin Heidelberg:Springer-Verlag,2007:349-365
[13] Pramstaller N, Rechberger C, Rijimen V.Exploiting Coding Theory for Collision Attacks on SHA-1[M]∥Cryptography and Coding.Berlin Heidelberg:Springer-Verlag,2005:78-95
[14] Joux A,Peyrin T.Hash Functions and the (Amplified) Boome-rang Attack[M]∥Advances in Cryptology-CRYPTO 2007.Berlin Heidelberg:Springer-Verlag,2007:244-263

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .