Cryptology ePrint Archive: Report 2009/360

Cryptanalysis of a Generalized Unbalanced Feistel Network Structure

Ruilin Li and Bing Sun and Chao Li and Longjiang Qu

Abstract: 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 $(3n-1)$-round integral and $(2n-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.

Category / Keywords: secret-key cryptography / block ciphers, generalized unbalanced Feistel network, integral attack, impossible differential attack, non-surjective attack

Publication Info: ACISP 2010

Date: received 20 Jul 2009, last revised 19 Jun 2012

Contact author: securitylrl at gmail com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20120620:025558 (All versions of this report)

Short URL: ia.cr/2009/360

Discussion forum: Show discussion | Start new discussion