Improved preimage attack on one-block MD4

MD4 is a hash function designed by Rivest in 1990. The design philosophy of many important hash functions, such as MD5, SHA-1 and SHA-2, originated from that of MD4. We propose an improved preimage attack on one-block MD4 with the time complexity 2⁹⁵ MD4 compression function operations, as compared to the 2^{107 1} complexity of the previous attack by Aoki et al. (SAC 2008). The attack is based on previous methods, but introduces new techniques. We also use the same techniques to improve the pseudo-preimage and preimage attacks on Extended MD4 with 2^25.2 and 2^12.6 improvement factor, as compared to previous attacks by Sasaki et al. (ACISP 2009).     

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.     

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.     

MIBS-64算法的三子集中间相遇攻击

MIBS算法于2009年在CANS会议上提出,是一个32轮Feistel结构、64比特分组长度以及包含64比特、80比特两种主密钥长度的轻量级分组密码.针对该算法密钥编排中第1轮到第11轮子密钥之间存在部分重复和等价关系,本文首次完成了MIBS-64的11轮三子集中间相遇攻击,数据复杂度为2^[47],存储复杂度为2^[47]64-bit,时间复杂度为2^[62.25]次11轮加密.与目前已有的对MIBS-64算法的中间相遇攻击相比,将攻击轮数由10轮扩展至11轮,刷新了该算法在中间相遇攻击下的安全性评估结果.     

An attack on hash function HAVAL-128

Hash function is directly applied to data integrity, and is the security guarantee for many cryptosystems and protocols such as signature, group signature, message authentication code, e-cash, bit commitment, coin-flipping, e-voting, etc. According to the structure of the existing hash functions, they can be mainly divided into two kinds: one is based on the cipher blocks, the other is directly constructed. We name the second the dedicated hash function.According to the different message proce…     

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.     

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

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

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.     

Known-key distinguishers on type-1 Feistel scheme and near-collision attacks on its hashing modes

We present some known-key distinguishers for a type-1 Feistel scheme with a permutation as the round function. To be more specific, the 29-round known-key truncated differential distinguishers are given for the 256-bit type-1 Feistel scheme with an SP (substitution-permutation) round function by using the rebound attack, where the S -boxes have perfect differential and linear properties and the linear diffusion layer has a maximum branch number. For two 128-bit versions, the distinguishers can be applied on 25-round structures. Based on these distinguishers, we construct near-collision attacks on these schemes with MMO (Matyas-Meyer-Oseas) and MP (Miyaguchi-Preneel) hashing modes, and propose the 26-round and 22-round near-collision attacks for two 256-bit schemes and two 128-bit schemes, respectively. We apply the near-collision attack on MAME and obtain a 26-round near-collision attack. Using the algebraic degree and some integral properties, we prove the correctness of the 31-round known-key integral distinguisher proposed by Sasaki et al. We show that if the round function is a permutation, the integral distinguisher is suitable for a type-1 Feistel scheme of any size.     

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.     

HSP: A solution against heap sprays

Heap sprays are a new buffer overflow attack (BOA) form that can significantly increase the successful chance of a BOA even though the attacked process is protected by a lot of state-of-the-art anti-BOA mechanisms, such as ASLR, non-executable stack/DEP, signature-based IDSes, and type-safe languages. In this paper, we propose a glibc-and-ASLR-based solution to heap sprays—Heap Spray Protector (HSP). HSP controls the number and location of int 80 instructions in a process and hides the whereabouts of the only legal int 80 instruction; hence, HSP makes it difficult for attackers to issue a system call, let alone a heap spray attack. Moreover HSP can help ASLR defend against memory information leaking attacks. Furthermore, because HSP only modifies the glibc library and the kernel, it does not need to modify any source code or executable file. Finally, HSP allows attackers to execute as much code as possible before an attack can really create some damage; therefore, it enables the attacked hosts to collect more information about attackers which may be useful to block future attacks. Experimental results show HSP implemented on a Linux platform can effectively defend a system against heap sprays with less than 4.56% performance overhead.     

Cryptanalysis of Reduced-Round DASH

In ACISP 2008,the hash family DASH has been proposed by Billet et al.,which considers the design of Rijndael and RC6.DASH family has two variants that support 256-bit and 512-bit output length respectively.This paper presents the first third-party cryptanalysis of DASH-256 with a focus on the underlying block cipher A256.In particular,we study the distinguisher using differential and boomerang attack.As a result,we build a distinguishing attack for the compression function of DASH-256 with 8-round A256 using the differential cryptanalysis.Finally,we obtain a boomerang distinguisher of 9-round A256.     

New impossible differential attacks on reduced-round Crypton

Crypton is a 128-bit block cipher which was submitted to the Advanced Encryption Standard competition. In this paper, we present two new impossible differential attacks to reduced-round Crypton. Using two new observations on the diffusion layer of Crypton, exploiting a 4-round impossible differential, and appropriately choosing three additional rounds, we mount the first impossible differential attack on 7-round Crypton. The proposed attacks require 2¹²¹ chosen plaintexts each. The first attack requires 2^125.2 encryptions. We then utilize more pre-computation and memory to reduce the time complexity to 2^116.2 encryptions in the second attack.     

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

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

A new one-bit diFFerence collision attack on HAVAL-128

In this paper,we give a new fast attack on HAVAL-128.Our attack includes many present methods of constructing hash collisions.Moreover,we present a neighborhood modification.We propose a new difference path different from the previous ones.The conclusion is that,when the output of each step satisfies our condition,the message m can collide with m’= m + Δm,where Δm =(0,0,0,0,231,0,...,0).There is only one bit difference between m and m’.Two pairs of collision examples for HAVAL-128 are given.In order to improve the probability of collision,we use four tricks of message modification.The attack’s running time is less than 225.83 2-pass HAVAL computations,which is the best result for one-bit collision of HAVAL so far.     

A SAT-based preimage analysis of reduced Keccak hash functions

In this paper, we present a preimage attack on reduced versions of Keccak hash functions. We use our recently developed toolkit CryptLogVer for generating the conjunctive normal form, CNF, which is passed to the SAT solver PrecoSAT. We found preimages for some reduced versions of the function and showed that full Keccak function has a comfortable security margin against this kind of attack.     

Efficient parallelizable hashing using small non-compressing primitives

A well-established method of constructing hash functions is to base them on non-compressing primitives, such as one-way functions or permutations. In this work, we present \(S^r\), an \(rn\)-to-\(n\)-bit compression function (for \(r\ge 1\)) making \(2r-1\) calls to \(n\)-to-\(n\)-bit primitives (random functions or permutations). \(S^r\) compresses its inputs at a rate (the amount of message blocks per primitive call) up to almost 1/2, and it outperforms all existing schemes with respect to rate and/or the size of underlying primitives. For instance, instantiated with the \(1600\)-bit permutation of NIST’s SHA-3 hash function standard, it offers about \(800\)-bit security at a rate of almost 1/2, while SHA-3-512 itself achieves only \(512\)-bit security at a rate of about \(1/3\). We prove that \(S^r\) achieves asymptotically optimal collision security against semi-adaptive adversaries up to almost \(2^{n/2}\) queries and that it can be made preimage secure up to \(2^n\) queries using a simple tweak.     

MD-4原象攻击的分析与改进

首先分析了Leurent提出的MD-4原象攻击方法,该方法利用MD-4布尔函数的吸收性质,迭代函数的可逆性以及消息扩展方式的特殊性,首先形成伪原象攻击,之后利用基于树的方法将伪原象转变为原象攻击。采用随机图的方法,对其后一部分进行了改进,提高了攻击效率,将复杂度从2102降低到298。     

Cryptanalysis of the application secure alternative to SNMP (APSSNMP)

The APSSNMP network management protocol was proposed as a secure alternative to the Simple Network Management Protocol (SNMP) used in the TCP/IP suite. The designers claimed that it resists meet-in-the-middle (MITM) attacks. In this paper, we present an advanced MITM attack on the APSSNMP and hence show that it fails to achieve its design objective of providing better security against MITM attacks. Since the APSSNMP has been presented in several journals, and IEEE and IASTED conferences, our result is important to highlight to network implementers and users of distributed systems that the APSSNMP is not secure for practical deployment.     

一种基于零知识证明的互联网密钥交换协议

IKE协议由于交换过程及密钥交换过程复杂,容易受到多种攻击。在分析其弱点的基础上,利用零知识证明的基本思想,提出了一种新的协议。该协议在减小系统消耗代价的同时,能够有效抵抗MITM（Man-In-The-Middle）,暴力破解攻击等。方案适用于对数据的安全性要求较高的用户。