Preimage Attacks on Full-ARIRANG: Analysis of DM-Mode with Middle Feed-Forward

摘要

In this paper, we present preimage attacks on hash function ARIRANG, which is one of the first round candidates in the SHA-3 com petition. Although ARIRANG was not chosen for the second round, the vulnerability as a hash function has not been discovered yet. ARIRANG has an unique design where the feed-forward operation is computed not only after the last step but also in a middle step. In fact, this design prevents previous preimage attacks from breaking full steps. In this pa per, we apply a framework of meet-in-the-middle preimage attacks to ARIRANG. Specifically, we propose a new initial-structure technique optimized for ARIRANG that overcomes the use of the feed-forward to the middle. This enables us to find preimages of full steps ARIRANG-256 and ARIRANG-512 with 2~(254) and 2~(505) compression function operations and 2~6 and 2~(16) amount of memory, respectively. These are the first results breaking the security of ARIRANG as a hash function.