Paper 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.