Research On The Attack Methods Of The Hash Functions

The hash function is one of the hotpots in the cryptographic fields, which is mainly appliedon message authentication, digital signature and E-cash, etc. It mainly includes two parts, that is,domain extension and compression function. Aiming to the security of these two parts, we haveobtained the following results:（1） Construct a “diamond structure” multicollision with2^k（0<k <n/4-1.3）initial valuesand variant lengths, which is used to propose a new chosen target forced prefix preimage attack（that is, herding attack） on hash functions with strengthening Merkle-Damag rd （SMD）construction to find a preimage with2k+3blocks. Since the number of the chaining valuesavailable in the herding attack is increased, the computational complexity of herding attack isreduced to O(2^n-k/3+2^n/2+k+1), which is less than O（2ⁿ）;（2） Using one kind of multicollsion of Merkle-Damg rd （MD） construction proposed byKelsey and Schneier, we present a second preimage attack on MDP construction which is asimple variant of MD scheme with a permutation, of which the computational complexity isk′2^n/2+1+2^n-k+2^k less than2n; Using the “diamond structure” multicollision with2kinitialvalues and variant lengths, we propose a preimage attack on the MDP construction, of which thecomputational complexity isO (2^n-k/3+2^n/2+k+1)（0<k<n/2-1），less than O（2n）, where n is thelength of the hash value;（3） By constructing a simulator of the random double-length compression function, weprove that if the number of queries made by any distinguisher is much less than O（2n）, then the2n-bit double-length hash function is indifferentiable from the random function; Then byconsidering the relations between the two internal states and the truncated output function, wemake several changes to the simulator and then prove that if the number of queries made by anydistinguisher is much less thanO (2^n/20，then the double-pipe hash function with n-bit hash sizeproposed by Lucks is indifferentiable from a random oracle;（4） Propose a rebound attack on the9-round ECHO-512compression function. Byrestricting the truncated differences of byte-wise to be only four types, we outline all the possibletruncated differential paths through the non-linear layer and their probabilities. And thenfollowing the rules given in this paper, we obtain two new truncated differential paths for the4-round ECHO permutation and then by combining the two new4-round sparse truncateddifferential paths and extending the latter one round more, we construct a new sparse truncateddifferential path for the9-round ECHO-512compression function. Then we utilizemulti-technique to find a solution to the full truncated differential path and thereby present a rebound attack on it with the time complexity of O(2¹⁶⁴) andO (2⁹⁶)memory, which is used todistinguish the9-round ECHO-512compression function from an ideal compression function;Moreover, since the message authentication code （MAC） is the hash function with a key, wealso resarch on the security of the MAC based on a hash function. Our contribution is describedas follows:（5） Considering the probability of producing the dBB collsions as the distinguisher, wefirstly proposes an adaptive chosen message distinguishing attack on the MAC with envelopedmethod using MD5, of which the time complexity and data complexity are both296and tablesize is2⁸⁹ with a success rate0.87. Then we relax the adaptive chosen message distinguishingattack to a chosen message distinguishing attack, of which the data complexity is increased to2113, but the table size is reduced to2⁶⁶ with the same success rate.