Meet-in-the-Middle Preimage Attacks on Double-Branch Hash Functions: Application to RIPEMD and Others

摘要

We describe preimage attacks on several double-branch hash functions. We first present meet-in-the-middle preimage attacks on RIPEMD, whose output length is 128 bits and internal state size is 256 bits. With this internal state size, a straightforward application of the meet-in-the-middle attack will cost the complexity of at least 2~(128), which gives no advantage compared to the brute force attack. We show two attacks on RIPEMD. The first attack finds pseudo-preimages and preim-ages of the first 33 steps with complexities of 2~(121) and 2~(125.5), respectively. The second attack finds pseudo-preimages and preimages of the intermediate 35 steps with complexities of 2~96 and 2~(113), respectively. We next present meet-in-the-middle preimage attacks on full Extended MD4, reduced RIPEMD-256, and reduced RIPEMD-320. The best known attack for these is the brute force attack. We show how to find preimages more efficiently on these hash functions.