Paper 2009/346

Security Analysis of the GF-NLFSR Structure and Four-Cell Block Cipher

Wenling Wu, Lei Zhang, Liting Zhang, and Wentao Zhang

Abstract

The overall structure is one of the most important properties of block ciphers. At present, the most common structures include Feistel structure, SP structure, MISTY structure, L-M structure and Generalized Feistel structure. In \cite{29}, Choy et al. proposed a new structure called GF-NLFSR (Generalized Feistel-NonLinear Feedback Shift Register), and designed a new block cipher called Four-Cell which is based on the 4-cell GF-NLFSR. In this paper, we first study properties of the $n$-cell GF-NLFSR structure, and prove that for an $n$-cell GF-NLFSR, there exists an $(n^2+n-2)$ rounds impossible differential. Then we present an impossible differential attack on the full 25-round Four-Cell using this kind of 18-round impossible differential distinguisher together with differential cryptanalysis technique. The data complexity of our attack is $2^{111.5}$ and the time complexity is less than $2^{123.5}$ encryptions. In addition, we expect the attack to be more efficient when the relations between different round subkeys can be exploited by taking the key schedule algorithm into consideration.