2014 | OriginalPaper | Chapter
New Second Preimage Attack Variants against the MD-Structure
Authors : Tuomas Kortelainen, Juha Kortelainen
Published in: Cryptology and Network Security
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
$\mathrm O(\sqrt{n} \cdot 2^{\frac{2n}{3}})$
while on random oracle hash function it is in
$\mathrm O(2^n)$
. We also show that it is possible to decrease the before mentioned expected value to
$\mathrm O(2^{\frac{2n-l}{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.