An improved impossible differential cryptanalysis of Zodiac

In this paper, we introduce a new impossible differential cryptanalysis of Zodiac that is considerably more effective than the one in the previous work (Hong et al., 2002). Using two new 13-round impossible differential characteristics and the early abort technique, this 3R-Attack breaks 128-bit key full-round Zodiac with complexity less than 271.3 encryptions, which is practical. This result is approximately 248 times better than what mentioned in the earlier work. Our result reveals depth of Zodiac’s weakness against impossible differential cryptanalysis due to its poor diffusion layer. We also obtain a tighter upper bound for time complexity.