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