On hash functions using checksums

We analyse the security of iterated hash functions that compute an input dependent checksum which is processed as part of the hash computation. We show that a large class of such schemes, including those using non-linear or even one-way checksum functions, is not secure against the second preimage attack of Kelsey and Schneier, the herding attack of Kelsey and Kohno and the multicollision attack of Joux. Our attacks also apply to a large class of cascaded hash functions. Our second preimage attacks on the cascaded hash functions improve the results of Joux presented at Crypto’04. We also apply our attacks to the MD2 and GOST hash functions. Our second preimage attacks on the MD2 and GOST hash functions improve the previous best known short-cut second preimage attacks on these hash functions by factors of at least 2²⁶ and 2⁵⁴, respectively. Our herding and multicollision attacks on the hash functions based on generic checksum functions (e.g., one-way) are a special case of the attacks on the cascaded iterated hash functions previously analysed by Dunkelman and Preneel and are not better than their attacks. On hash functions with easily invertible checksums, our multicollision and herding attacks (if the hash value is short as in MD2) are more efficient than those of Dunkelman and Preneel.     

Second order collision for the 42-step reduced DHA-256 hash function

At the Cryptographic Hash Workshop hosted by NIST in 2005, Lee et al. proposed the DHA-256 (Double Hash Algorithm-256) hash function. The design of DHA-256 builds upon the design of SHA-256, but introduces additional strengthening features such as optimizing the message expansion and step function against local collision attacks. Previously, DHA-256 was analyzed by J. Zhong and X. Lai, who presented a preimage attack on 35 steps of the compression function with complexity 2^239.6. In addition, the IAIK Krypto Group provided evidence that there exists a 9-step local collision for the DHA-256 compression function with probability higher than previously predicted. In this paper, we analyze DHA-256 in the context of higher order differential attacks. In particular, we provide a practical distinguisher for 42 out of 64 steps and give an example of a colliding quartet to validate our results.     

Improved preimage attacks on hash modes of 8-round AES-256

We observe the slow diffusion of the AES key schedule for 256-bit keys and find weakness which can be used in the preimage attack on its Davies-Meyer mode. Our preimage attack works for 8 rounds of AES-256 with the computational complexity of 2^124.9. It is comparable with Bogdanov et al.’s biclique-based preimage attack on AES-256, which is applicable up to full rounds but has the computational complexity more than 2^126.5. We also extend our result to the preimage attack on some well-known double-block-length hash modes assuming the underlying block cipher is 8-round AES-256, whose computational complexity is 2^252.9.     

An improved preimage attack against HAVAL-3

Hash functions play an important role in constructing cryptographic schemes that provide security services, such as confidentiality in an encryption scheme, authenticity in an authentication protocol and integrity in a digital signature scheme and so on. Such hash function is needed to process a challenge, a message, an identifier or a private key. In this paper, we propose an attack against HAVAL-3 hash function, which is used in open source Tripwire and is included in GNU Crypto. Under the meet-in-the-middle (MITM) preimage attack framework proposed by Aoki and Sasaki in 2008, the one-wayness of several (reduced-)hash functions had been broken recently. However, most of the attacks are of complexity close to brute-force search. Focusing on reducing the time complexity of such MITM attacks, we improve the preimage attacks against HAVAL-3 hash function to within lower time complexity and memory requirement, compared with the best known attack proposed by Sasaki and Aoki in ASIACRYPT 2008. Besides the 256-bit variant of HAVAL-3, similar improvements can be applied to some truncated variants as well. Interestingly, due to the low complexity of our attack, the preimage attack applies to the 192-bit variant of HAVAL-3 for the first time.     

Cryptographic hash standards: where do we go from here?

Successful attacks against the two most commonly used cryptographic hash functions, MD5 and SHA-1, have triggered a kind of feeding frenzy in the cryptographic community. Many researchers are now working on hash function attacks, and we can expect new results in this area for the next several years. This article discusses the SHA-1 attack and the US National Institute of Standards and Technology's (NIST's) plans for SHA-1 and hash functions in general.     

Collision Attack on the Full Extended MD4 and Pseudo-Preimage Attack on RIPEMD

The cryptographic hash functions Extended MD4 and RIPEMD are double-branch hash functions,which consist of two parallel branches.Extended MD4 was proposed by Rivest in 1990,and RIPEMD was devised in the framework of the RIPE project(RACE Integrity Primitives Evaluation,1988～1992).On the basis of differential analysis and meet-in-themiddle attack principle,this paper proposes a collision attack on the full Extended MD4 and a pseudo-preimage attack on the full RIPEMD respectively.The collision attack on Extended MD4 holds with a complexity of 237,and a collision instance is presented.The pseudo-preimage attack on RIPEMD holds with a complexity of 2 125.4,which optimizes the complexity order for brute-force attack.The results in this study will also be beneficial to the analysis of other double-branch hash functions such as RIPEMD-160.     

Evaluate the security margins of SHA-512, SHA-256 and DHA-256 against the boomerang attack评估飞去来器方法对 SHA-512, SHA-256 和 DHA-256 三种哈希函数的攻击效率

For an n-bit random permutation, there are three types of boomerang distinguishers, denoted as Type I, II and III, with generic complexities 2ⁿ, 2^n/3 and 2^n/2 respectively. In this paper, we try to evaluate the security margins of three hash functions namely SHA-512, SHA-256 and DHA-256 against the boomerang attack. Firstly, we give a boomerang attack on 48-step SHA-512 with a practical complexity of 2⁵¹. The correctness of this attack is verified by providing a Type III boomerang quartet. Then, we extend the existing differential characteristics of the three hash functions to more rounds. We deduce the sufficient conditions and give thorough evaluations to the security margins as follows: Type I boomerang method can attack 54-step SHA-512, 51-step SHA-256 and 46-step DHA-256 with complexities 2⁴⁸⁰, 2²¹⁸ and 2²³⁶ respectively. Type II boomerang method can attack 51-step SHA-512, 49-step SHA-256 and 43-step DHA-256 with complexities 2^158.50, 2^72.91 and 2^74.50 respectively. Type III boomerang method can attack 52-step SHA-512, 50-step SHA-256 and 44-step DHA-256 with complexities 2^223.80, 2^123.63 and 2^99.85 respectively.     

On security arguments of the second round SHA-3 candidates

In 2007, the US National Institute for Standards and Technology (NIST) announced a call for the design of a new cryptographic hash algorithm in response to vulnerabilities like differential attacks identified in existing hash functions, such as MD5 and SHA-1. NIST received many submissions, 51 of which got accepted to the first round. 14 candidates were left in the second round, out of which five candidates have been recently chosen for the final round. An important criterion in the selection process is the SHA-3 hash function security. We identify two important classes of security arguments for the new designs: (1) the possible reductions of the hash function security to the security of its underlying building blocks and (2) arguments against differential attack on building blocks. In this paper, we compare the state of the art provable security reductions for the second round candidates and review arguments and bounds against classes of differential attacks. We discuss all the SHA-3 candidates at a high functional level, analyze, and summarize the security reduction results and bounds against differential attacks. Additionally, we generalize the well-known proof of collision resistance preservation, such that all SHA-3 candidates with a suffix-free padding are covered.     

密码杂凑函数及其安全性分析

文章提出了针对密码杂凑函数及其安全性进行研究的重要意义,列举了单向杂凑函数、MD5、SHA-1等技术原理进行了技术分析,并从攻击手段入手,分析了密码杂凑函数的安全性,提出对SHA-1与MD-5的＂破解＂应客观看待的观点。     

Improved Collision Attack on Hash Function MD5

In this paper, we present a fast attack algorithm to find two-block collision of hash function MD5. The algorithm is based on the two-block collision differential path of MD5 that was presented by Wang et al. in the Conference EUROCRYPT 2005. We found that the derived conditions for the desired collision differential path were not sufficient to guarantee the path to hold and that some conditions could be modified to enlarge the collision set. By using technique of small range searching and omitting the computing steps to check the characteristics in the attack algorithm, we can speed up the attack of MD5 efficiently. Compared with the Advanced Message Modification technique presented by Wang et al., the small range searching technique can correct 4 more conditions for the first iteration differential and 3 more conditions for the second iteration differential, thus improving the probability and the complexity to find collisions. The whole attack on the MD5 can be accomplished within 5 hours using a PC with Pentium4 1.70GHz CPU.     

Impossible Differential Attacks on 13-Round CLEFIA-128

CLEFIA,a new 128-bit block cipher proposed by Sony Corporation,is increasingly attracting cryptanalysts’ attention.In this paper,we present two new impossible differential attacks on 13 rounds of CLEFIA-128.The proposed attacks utilize a variety of previously known techniques,in particular the hash table technique and redundancy in the key schedule of this block cipher.The first attack does not consider the whitening layers of CLEFIA,requires 2 109.5 chosen plaintexts,and has a running time equivalent to about 2 112.9 encryptions.The second attack preserves the whitening layers,requires 2 117.8 chosen plaintexts,and has a total time complexity equivalent to about 2 121.2 encryptions.     

对104步杂凑函数HAVAL的原根攻击

针对杂凑函数HAVAL的第1圈中圈函数的性质和消息字的顺序,结合使用穷举搜索等方法,给出对前104步HAVAL压缩函数的原根攻击。其计算复杂度是2224次杂凑运算,需要存储238个字节,而穷举攻击的计算复杂度是2256次杂凑运算。分析结果对杂凑函数HAVAL安全性的评估有重要的参考价值。     

有意义的MD4碰撞攻击(英文)

2005年的欧密会,Wang等提出了一种构造MD4碰撞的有效方法,该方法不仅对寻找随机碰撞有效,还可以用于构造有意义的碰撞。以Wang的技术为基础,进一步分析和探讨了对构造纯文本文件有意义的MD4碰撞,给出了一种构造纯文本文件的有意义MD4碰撞的方法,概率为2-33.77。在1996年的FSE会议上,Dobbertin的"Crypt analysis of MD4"给出了一个有意义的碰撞,而其在开头包含了16个随机字符。这里给出了一个基于Latin-1字符集的有意义的碰撞。     

Cryptanalysis of GOST R hash function

GOST R 34.11-2012 is the new Russian hash function standard. This paper presents some cryptanalytic results on GOST R. Using the rebound attack technique, we achieve collision attacks on the reduced round compression function. Result on up to 9.5 rounds is proposed, the time complexity is 2¹⁷⁶ and the memory requirement is 2¹²⁸ bytes. Based on the 9.5-round collision result, a limited birthday distinguisher is presented. More over, a k-collision on 512-bit version of GOST R is constructed which shows the weakness of the structure used in GOST R.     

A New Hash Competition

Since the discovery of collision attacks against several well-known cryptographic hash functions in 2004, a rush of new cryptanalytic results cast doubt on the current hash function standards. The relatively new NIST SHA-2 standards aren't yet immediately threatened, but their long-term viability is now in question. The US National Institute of Standards and Technology (NIST) has therefore begun an international competition to select a new SHA-3 standard. This article outlines the competition, its rules, the requirements for the hash function candidates, and the process that NIST will use to select the final winning SHA-3 standard.     

代数系统求解4轮Keccak-256原像攻击的完善

Keccak哈希函数是第三代安全哈希函数,具有可证明的安全性与良好的实现性能.讨论基于代数系统求解的4轮Keccak-256原像攻击,对已有的4轮原像攻击方法进行了完善,有效降低了理论复杂度.目前,4轮Keccak-256原像攻击的理论复杂度最低为2239,通过充分利用二次比特的因式之间的关系,在自由度相同的情况下,线...     

关于比特币中BWH攻击的一个注记

比特币是当前信息安全应用研究领域的热点问题之一.在比特币所采用的PoW共识协议中,挖矿具有重要作用.在现实生活中,矿工为获得更多的奖励,往往聚集成矿池,以达到在挖矿中获取更高算力进而获取更多区块奖励的目的.针对比特币矿池,Meni Rosenfeld首次提出了一种称为BWH攻击的攻击方式,Loi Luu等人进一步从理论上证明了相对于诚实挖矿,攻击者通过实施BWH攻击可以获得更高的收益.在本文中,我们分析了BWH攻击的理论基础,发现Loi Luu等人关于BWH攻击的理论分析中存在的一个错误,即Loi Luu等人忽略了整体算力改变对系统产生区块所需时间的影响,从而导致其所对比的关于攻击者实施BWH攻击所获得的收益与不实施攻击所获得的收益,实际上是在不同时间长度下的收益对比.显然这种对比缺乏合理性.在相同时间长度下,我们进一步讨论了攻击者实施BWH攻击与不实施攻击所获得的收益对比,得到了与Loi Luu等人完全相反的结论,即相对诚实挖矿来说,攻击者实施BWH攻击反而获得了相对较少的收益.因此攻击者缺乏实施BWH攻击的动机,除非其纯粹出于破坏矿池的目的而采用BWH攻击.     

The parazoa family: generalizing the sponge hash functions

Sponge functions were introduced by Bertoni et?al. as an alternative to the classical Merkle-Damg?rd design. Many hash function submissions to the SHA-3 competition launched by NIST in 2007, such as CubeHash, Fugue, Hamsi, JH, Keccak and Luffa, derive from the original sponge design, and security guarantees from some of these constructions are typically based on indifferentiability results. Although indifferentiability proofs for these designs often bear significant similarities, these have so far been obtained independently for each construction. In this work, we introduce the parazoa family of hash functions as a generalization of “sponge-like” functions. Similarly to the sponge design, the parazoa family consists of compression and extraction phases. The parazoa hash functions, however, extend the sponge construction by enabling the use of a wider class of compression and extraction functions that need to satisfy certain properties. More importantly, we prove that the parazoa functions satisfy the indifferentiability notion of Maurer et?al. under the assumption that the underlying permutation is ideal. Not surprisingly, our indifferentiability result confirms the bound on the original sponge function, but it also carries over to a wider spectrum of hash functions and eliminates the need for a separate indifferentiability analysis.     

AN EARLY SUCCESS STORY

Abstract

In 2006, Shieh et al. proposed an efficient remote mutual authentication and key agreement scheme which uses smart cards and requires only hash function operations. In this paper, we show that Shieh et al.'s scheme is vulnerable to guessing attacks, forgery attacks and key compromise attacks. To eliminate these weaknesses, an improvement of Shieh et al.'s scheme with increased security is proposed. The security and efficiency of the improved scheme raises the attractiveness for implementation.     

New related-key rectangle attacks on reduced AES-192 and AES-256

In this paper, we examine the security of reduced AES-192 and AES-256 against related-key rectangle attacks by exploiting the weakness in the AES key schedule. We find the following two new attacks: 9-round reduced AES-192 with 4 related keys, and 10-round reduced AES-256 with 4 related keys. Our results show that related-key rectangle attack with 4 related keys on 9-round reduced AES-192 requires a data complexity of about 2¹⁰¹ chosen plaintexts and a time complexity of about 2^174.8 encryptions, and moreover, related-key rectangle attack with 4 related keys on 10-round reduced AES-256 requires a data complexity of about 2^97.5 chosen plaintexts and a time complexity of about 2²⁵⁴ encryptions. These attacks are the first known attacks on 9-round reduced AES-192 and 10-round reduced AES-256 with only 4 related keys. Furthermore, we give an improvement of the 10-round reduced AES-192 attack presented at FSE2007, which reduces both the data complexity and the time complexity. Supported by the National Natural Science Foundation of China (Grant No. 60673072), and the National Basic Research Program of China (Grant No. 2007CB311201)