Cryptology ePrint Archive: Report 2010/434

Low-weight Pseudo Collision Attack on Shabal and Preimage Attack on Reduced Shabal-512

Takanori Isobe and Taizo Shirai

Abstract: This paper studies two types of attacks on the hash function Shabal. The first attack is a low-weight pseudo collision attack on Shabal. Since a pseudo collision attack is trivial for Shabal, we focus on a low-weight pseudo collision attack. It means that only low-weight difference in a chaining value is considered. By analyzing the difference propagation in the underlying permutation, we can construct a low-weight (45-bits) pseudo collision attack on the full compression function with complexity of 2^84. The second attack is a preimage attack on variants of Shabal-512. We utilize a guess-and-determine technique, which is originally developed for a cryptanalysis of stream ciphers, and customize the technique for a preimage attack on Shabal-512. As a result, for the weakened variant of Shabal-512 using security parameters (p; r) = (2; 12), a preimage can be found with complexity of 2^497 and memory of 2^400. Moreover, for the Shabal-512 using security parameters (p; r) = (1:5; 8), a preimage can be found with complexity of 2^497 and memory of 2^272. To the best of our knowledge, these are best preimage attacks on Shabal variants and the second result is a first preimage attack on Shabal-512 with reduced security parameters.

Category / Keywords: foundations / Shabal, low-weight pseudo collision attack, preimage attack, guess-and-determine technique, SHA-3 competition

Date: received 6 Aug 2010

Contact author: Takanori Isobe at jp sony com，Taizo Shirai@jp sony com

Available format(s): PDF | BibTeX Citation

Version: 20100813:143241 (All versions of this report)

Short URL: ia.cr/2010/434

Discussion forum: Show discussion | Start new discussion