The Full Cost of Cryptanalytic Attacks

An open question about the asymptotic cost of connecting many processors to a large memory using three dimensions for wiring is answered, and this result is used to find the full cost of several cryptanalytic attacks. In many cases this full cost is higher than the accepted complexity of a given algorithm based on the number of processor steps. The full costs of several cryptanalytic attacks are determined, including Shanks method for computing discrete logarithms in cyclic groups of prime order n, which requires n^1/2+o(1) processor steps, but, when all factors are taken into account, has full cost n^2/3+o(1). Other attacks analyzed are factoring with the number field sieve, generic attacks on block ciphers, attacks on double and triple encryption, and finding hash collisions. In many cases parallel collision search gives a significant asymptotic advantage over well-known generic attacks.     

Cryptanalysis of MD4

In 1990 Rivest introduced the hash function MD4. Two years later RIPEMD, a European proposal, was designed as a stronger mode of MD4. In 1995 the author found an attack against two of three rounds of RIPEMD. As we show in the present note, the methods developed to attack RIPEMD can be modified and supplemented such that it is possible to break the full MD4, while previously only partial attacks were known. An implementation of our attack allows us to find collisions for MD4 in a few seconds on a PC. An example of a collision is given demonstrating that our attack is of practical relevance. Received 23 October 1995 and revised 31 August 1997     

对缩减轮数DHA-256的原像与伪碰撞攻击

提出了对DHA-256散列函数37轮的原像攻击以及39轮的伪碰撞攻击。基于中间相遇攻击,利用Biclique方法可以改进之前对DHA-256的原像分析结果,将攻击轮数从原来的35轮提高到了37轮。通过上述方法还可以构造对DHA-256的39轮伪碰撞。最终,以2255.5的时间复杂度以及23的空间复杂度构造了对DHA-256的37轮原像,并以2127.5的时间复杂度以及常数2的空间复杂度构造了对DHA-256的39轮伪碰撞。这是目前对DHA-256最好的原像与碰撞攻击结果。     

带消息填充的 29 步 SM3 算法原根和伪碰撞攻击简

基于中间相遇攻击技术,提出了一种针对密码杂凑函数SM算法的原根攻击和伪碰撞攻击方法,给出了从第1步开始的带消息填充的29步SM3算法的原根攻击和伪碰撞攻击。结果表明：对于29步SM3算法的原根攻击的时间复杂度为2254;对于29步SM3伪碰撞攻击的时间复杂度为2125。说明从第1步开始的带消息填充的29步SM3算法不能抵抗原根攻击和伪碰撞攻击。     

Improved Practical Attacks on Round-Reduced Keccak

The Keccak hash function is the winner of NIST’s SHA-3 competition, and so far it showed remarkable resistance against practical collision finding attacks: After several years of cryptanalysis and a lot of effort, the largest number of Keccak rounds for which actual collisions were found was only 2. In this paper, we develop improved collision finding techniques which enable us to double this number. More precisely, we can now find within a few minutes on a single PC actual collisions in the standard Keccak-224 and Keccak-256, where the only modification is to reduce their number of rounds to 4. When we apply our techniques to 5-round Keccak, we can get in a few days near collisions, where the Hamming distance is 5 in the case of Keccak-224 and 10 in the case of Keccak-256. Our new attack combines differential and algebraic techniques, and uses the fact that each round of Keccak is only a quadratic mapping in order to efficiently find pairs of messages which follow a high probability differential characteristic. Since full Keccak has 24 rounds, our attack does not threaten the security of the hash function.     

Two-Key Triple Encryption

In this paper we consider multiple encryption schemes built from conventional cryptosystems such as DES. The existing schemes are either vulnerable to variants of meet-in-the-middle attacks, i.e., they do not provide security corresponding to the full key length used or there is no proof that the schemes are as secure as the underlying cipher. We propose a variant of two-key triple encryption with a new method of generating three keys from two. Our scheme is not vulnerable to the meet-in-the-middle attack and, under an appropriate assumption, we can show that our scheme is at least about as hard to break as the underlying block cipher. Received 22 June 1995 and revised 11 October 1996     

Improved preimage and pseudo-collision attacks on SM3 hash function

A preimage attack on 32-step SM3 hash function and a pseudo-collision attack on 33-step SM3 hash function respectively were shown.32-step preimage attack was based on the differential meet-in-the-middle and biclique technique,while the previously known best preimage attack on SM3 was only 30-step.The 33-step pseudo-collision attack was constructed by using the same techniques.The preimage attack on 32-step SM3 can be computed with a complexity of 2^254.5,and a memory of 2⁵.Furthermore,The pseudo-preimage and pseudo-collision attacks on 33-step SM3 by extending the differential characteristic of the 32-step preimage attack were present.The pseudo-collision attack on 33-step SM3 can be computed with a complexity of 2^126.7,and a memory of 2³.     

Cryptanalysis of MD2

This paper considers the hash function MD2 which was developed by Ron Rivest in 1989. Despite its age, MD2 has withstood cryptanalytic attacks until recently. This paper contains the state-of-the-art cryptanalytic results on MD2, in particular collision and preimage attacks on the full hash function, the latter having complexity 2⁷³, which should be compared to a brute-force attack of complexity 2¹²⁸.     

RIPEMD with two-round compress function is not collision-free

In 1990 Rivest introduced the cryptographic hash function MD4. The compress function of MD4 has three rounds. After partial attacks against MD4 were found, the stronger mode RIPEMD was designed as a European proposal in 1992 (RACE project). Its compress function consists of two parallel lines of modified versions of MD4-compress. RIPEMD is currently being considered to become an international standard (ISO/IEC Draft 10118-3). However, in this paper an attack against RIPEMD is described, which leads to comparable results with the previously known attacks against MD4: The reduced versions of RIPEMD, where the first or the last round of the compress function is omitted, are not collision-free. Moreover, it turns out that the methods developed in this note can be applied to find collisions for the full MD4.     

Security Analysis of Randomize-Hash-then-Sign Digital Signatures

At CRYPTO 2006, Halevi and Krawczyk proposed two randomized hash function modes and analyzed the security of digital signature algorithms based on these constructions. They showed that the security of signature schemes based on the two randomized hash function modes relies on properties similar to the second preimage resistance rather than on the collision resistance property of the hash functions. One of the randomized hash function modes was named the RMX hash function mode and was recommended for practical purposes. The National Institute of Standards and Technology (NIST), USA standardized a variant of the RMX hash function mode and published this standard in the Special Publication (SP) 800-106. In this article, we first discuss a generic online birthday existential forgery attack of Dang and Perlner on the RMX-hash-then-sign schemes. We show that a variant of this attack can be applied to forge the other randomize-hash-then-sign schemes. We point out practical limitations of the generic forgery attack on the RMX-hash-then-sign schemes. We then show that these limitations can be overcome for the RMX-hash-then-sign schemes if it is easy to find fixed points for the underlying compression functions, such as for the Davies-Meyer construction used in the popular hash functions such as MD5 designed by Rivest and the SHA family of hash functions designed by the National Security Agency (NSA), USA and published by NIST in the Federal Information Processing Standards (FIPS). We show an online birthday forgery attack on this class of signatures by using a variant of Dean’s method of finding fixed point expandable messages for hash functions based on the Davies-Meyer construction. This forgery attack is also applicable to signature schemes based on the variant of RMX standardized by NIST in SP 800-106. We discuss some important applications of our attacks and discuss their applicability on signature schemes based on hash functions with ‘built-in’ randomization. Finally, we compare our attacks on randomize-hash-then-sign schemes with the generic forgery attacks on the standard hash-based message authentication code (HMAC).     

Immunizing public key cryptosystems against chosen ciphertextattacks

Three methods for strengthening public key cryptosystems in such a way that they become secure against adaptively chosen ciphertext attacks are presented. In an adaptively chosen ciphertext attack, an attacker can query the deciphering algorithm with any ciphertext except for the exact object ciphertext to be cryptanalyzed. The first strengthening method is based on the use of one-way hash functions, the second on the use of universal hash functions, and the third on the use of digital signature schemes. Each method is illustrated by an example of a public key cryptosystem based on the intractability of computing discrete logarithms in finite fields. Security of the three example cryptosystems is formally proved. Two other issues, namely, applications of the methods to public key cryptosystems based on other intractable problems and enhancement of information authentication capability to the cryptosystems, are also discussed     

椭圆曲线加密结合散列函数的移动网络匿名安全认证方案

为了防止私人数据泄露并完善已有的移动网络匿名漫游认证方案,提出了一种利用椭圆曲线加密结合散列函数的移动网络匿名安全认证方案。该方案利用椭圆曲线加密,结合散列函数,以随机数代替公开密钥加密和时间戳。首先,使用外地代理（FA）的漫游服务之前,计算单向散列函数,移动用户（MU）使用本地代理（HA）注册。然后,建立认证和会话的密钥,采用椭圆曲线加密,若HA一直待在同一FA中,则MU可以用FA更新会话密钥。最后,MU通过公共信道,利用HA修改密码。性能和安全性分析表明,相比其他几种类似方案,提出的方案明显提高了效率和安全性。其中,虚拟计算时间只有2.000 85 s,显著降低了计算开销。     

Quantum collision search algorithm against New FORK-256

In order to improve the attack efficiency of the New FORK-256 function,an algorithm based on Grover＇s quantum search algorithm and birthday attack is proposed.In this algorithm,finding a collision for arbitrary hash function only needs O（2m/3） expected evaluations,where m is the size of hash space value.It is proved that the algorithm can obviously improve the attack efficiency for only needing O（274.7） expected evaluations,and this is more efficient than any known classical algorithm,and the consumed space of the algorithm equals the evaluation.     

Homomorphic signature schemes for single-source and multi-source network coding

To solve the problems of pollution attacks of single-source and multi-source network coding,two homomorphic signature schemes for network coding were proposed.In homomorphic signature for single-source network,the message hash value was signed on the elliptic curve,then the message,hash value and the signature of hash value were output,and the receiving node could verify the signature,the elliptic curve signature based on homomorphism could resist intra/inter-generation pollution attacks.Homomorphic signature from pairings for multi-source network coding could resist pollution attacks,and the introduction of timestamp made it be capable to resist replay attacks.In the random oracle model,it proves that two schemes are all secure under the selective attacks.Analysis shows that two schemes can effectively improve the verification efficiency.     

改进的减轮MIBS-80密码的中间相遇攻击

MIBS密码算法是一个Feistel结构的轻量级分组密码,广泛适用于资源严格受限的环境。该文利用多重集和有效的差分枚举方法,构造了8轮MIBS中间相遇区分器,并在新区分器的基础上,实现了12轮和13轮MIBS-80密码的中间相遇攻击。攻击过程利用差分传递的性质筛选明文对,利用MIBS-80密钥扩展算法中主密钥和轮密钥的关系减少密钥的猜测量,攻击12轮MIBS-80的时间复杂度为253.2,攻击13轮MIBS-80的时间复杂度为262。与已有中间相遇攻击的结果相比,该文对MIBS-80中间相遇攻击的轮数提高了2轮。     

Hash key-based video encryption scheme for H.264/AVC

An improved H.264/AVC comprehensive video encryption scheme is proposed. In the proposed scheme, the intra-prediction mode, motion vector difference, and quantization coefficients are encrypted. A novel hierarchical key generation method is likewise proposed, in which the encryption keys are generated based on the cryptographic hash function. Generated frame keys are consistent with the corresponding frame serial numbers, which can ensure frame synchronization in the decrypting process when frame loss occurs. This function provides the property that our scheme is secure against some special attacks for video, such as the frame regrouping attack and frame erasure attack. Our method not only avoids the distribution of encryption keys, but also increases the security. Experimental results show that the proposed scheme is efficient in computing, the encryption process does not affect the compression ratio greatly, and the encryption/decryption process hardly affects the video quality.     

对Zodiac算法的中间相遇攻击

Zodiac算法是由一批韩国专家设计的一个分组密码算法。该文首次研究了Zodiac算法抵抗中间相遇攻击的能力。找到了Zodiac算法新的9轮区分器和10轮区分器,基于这两个区分器分别对15轮和完整16轮Zodiac算法进行了中间相遇攻击。结果表明完整16轮Zodiac-128/192/256是不抗中间相遇攻击的。     

Ad hoc网络中基于环Zn上椭圆曲线和RSA的密钥管理

探讨了ad hoc网络密钥管理问题,首次利用环Zn上椭圆曲线所构成的陷门离散对数的同态性质,结合Shamir秘密分享方案,提出了一种新的适用于ad hoc网络的密钥管理方案.在该方案中,新加入的成员向组内成员提供环Zn上的椭圆曲线加密体制,并保密相应的陷门.利用该加密体制的同态性,参与密钥分发的成员将关于新成员的子密钥加密后依次相加,新成员得到最后的和,然后解密;为防止攻击者来自于组内成员,在每次子密钥加密中都加入了混合因子.新方案具有很好的安全性,破解该方案的难度不低于破解RSA.     

An efficient two‐party authentication key exchange protocol for mobile environment

The primary goal of this research is to ensure secure communications by client‐server architectures in mobile environment. Although various two‐party authentication key exchange protocols are proposed and claimed to be resistant to a variety of attacks, studies have shown that various loopholes exist in these protocols. What's more, many two‐party authentication key exchange protocols use timestamp to prevent the replay attack and transmit the user's identity in plaintext form. Obviously, these methods will lead to the clock synchronization problem and user's anonymity problem. Fortunately, the three‐way challenged‐response handshake technique and masking user's original identity with a secret hash value used in our study address these problems well. Of course, the proposed protocol based on elliptic curve cryptography supports flawless mutual authentication of participants, agreement of session key, impersonation attack resistance, replay attack resistance, and prefect forward secrecy, as well. The analyses in the aspects of efficiency and security show that the proposed protocol is a better choice for mobile users.     

New Second-Preimage Attacks on Hash Functions

In this work, we present several new generic second-preimage attacks on hash functions. Our first attack is based on the herding attack and applies to various Merkle–Damgård-based iterative hash functions. Compared to the previously known long-message second-preimage attacks, our attack offers more flexibility in choosing the second-preimage message at the cost of a small computational overhead. More concretely, our attack allows the adversary to replace only a few blocks in the original target message to obtain the second preimage. As a result, our new attack is applicable to constructions previously believed to be immune to such second-preimage attacks. Among others, these include the dithered hash proposal of Rivest, Shoup’s UOWHF, and the ROX constructions. In addition, we also suggest several time-memory-data tradeoff attack variants, allowing for a faster online phase, and even finding second preimages for shorter messages. We further extend our attack to sequences stronger than the ones suggested in Rivest’s proposal. To this end we introduce the kite generator as a new tool to attack any dithering sequence over a small alphabet. Additionally, we analyse the second-preimage security of the basic tree hash construction. Here we also propose several second-preimage attacks and their time-memory-data tradeoff variants. Finally, we show how both our new and the previous second-preimage attacks can be applied even more efficiently when multiple short messages, rather than a single long target message, are available.