Colliding Keys for SC2000-256

In this work we present analysis for the block cipher SC2000, which is in the Japanese CRYPTREC portfolio for standardization. In spite of its very complex and non-linear key-schedule we have found a property of the full SC2000-256 (with 256-bit keys) which allows the attacker to find many pairs of keys which generate identical sets of subkeys. Such colliding keys result in identical encryptions. We designed an algorithm that efficiently produces colliding key pairs in 2^39 time, which takes a few hours on a PC. We show that there are around 2^68 colliding pairs, and the whole set can be enumerated in 2^58 time. This result shows that SC2000-256 cannot model an ideal cipher. Furthermore we explain how practical collisions can be produced for both Davies-Meyer and Hiroses hash function constructions instantiated with SC2000-256 .