We consider a situation where the adversary performs a second preimage attack and is able to influence slightly the preconditions under which the iterated hash function is used. In the first variant of the attack, the adversary is able to choose the initial value of the hash function after receiving the original message. In the second variant, the adversary is allowed to determine a prefix of the original message and has to create a second preimage with the same prefix. Both of these attacks use diamond structures and the expected number of compression function calls required to complete each of them successfully is in O({the square root of}n·2~(2n/3)) while on random oracle hash function it is in O(2~n). We also show that it is possible to decrease the before mentioned expected value to O(2 2n-1/3) if the length of the original message is 2~l and l is sufficiently large. Furthermore, we generalize these attacks to work against concatenated hash functions as well.
展开▼
