Paper 2009/627

A Unified Method for Finding Impossible Differentials of Block Cipher Structures

Yiyuan Luo, Zhongming Wu, Xuejia Lai, and Guang Gong

Abstract

In this paper, we propose a systematic method for finding impossible differentials for block cipher structures, better than the $\mathcal{U}$-method introduced by Kim \textit{et al}~\cite{Kim03}. It is referred as a unified impossible differential finding method (UID-method). We apply the UID-method to some popular block ciphers such as {\sf Gen-Skipjack}, {\sf Gen-CAST256}, {\sf Gen-MARS}, {\sf Gen-RC6}, {\sf Four-Cell}, {\sf SMS4} and give the detailed impossible differentials. By the UID-method, we find a 16-round impossible differential on {\sf Gen-Skipjack} and a 19-round impossible differential on {\sf Gen-CAST256}. Thus we disprove the \textsl{Conjecture 2} proposed in \textsl{Asiacrypt'00}~\cite{Sung00} and the theorem in \textsl{FSE'09} rump session presentation~\cite{Pudovkina09}. On {\sf Gen-MARS} and {\sf SMS4}, the impossible differentials find by the UID-method are much longer than that found by the $\mathcal{U}$-method. On the {\sf Four-Cell} block cipher, our result is the same as the best result previously obtained by case-by-case treatment.