Cryptanalysis of a Generalized Unbalanced Feistel Network Structure

This paper reevaluates the security of GF-NLFSR, a new kind of generalized unbalanced Feistel network structure that was proposed at ACISP 2009. We show that GF-NLFSR itself reveals a very slow diffusion rate, which could lead to several distinguishing attacks. For GF-NLFSR containing

n

sub-blocks, we find an

n

2

-round integral distinguisher by algebraic methods and further use this integral to construct an (

n

2

 + 

n

 − 2)-round impossible differential distinguisher. Compared with the original (3

n

 − 1)-round integral and (2

n

 − 1)-round impossible differential, ours are significantly better.

Another contribution of this paper is to introduce a kind of non-surjective attack by analyzing a variant structure of GF-NLFSR, whose provable security against differential and linear cryptanalysis can also be provided. The advantage of the proposed non-surjective attack is that traditional non-surjective attack is only applicable to Feistel ciphers with non-surjective (non-uniform) round functions, while ours could be applied to block ciphers with bijective ones. Moreover, its data complexity is

$\mathcal{O}(l)$

with

l

the block length.