Known-Key Attacks on Generalized Feistel Schemes with SP Round Function

HyungChul KANG  Deukjo HONG  Dukjae MOON  Daesung KWON  Jaechul SUNG  Seokhie HONG  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E95-A   No.9   pp.1550-1560
Publication Date: 2012/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E95.A.1550
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Cryptography and Information Security
Keyword: 
generalized Feistel schemes,  rebound attack,  known-key distinguisher,  collision attack,  hashing mode,  

Full Text: PDF(1.7MB)>>
Buy this Article




Summary: 
We present attacks on the generalized Feistel schemes, where each round function consists of a subkey XOR, S-boxes, and then a linear transformation (i.e. a Substitution-Permutation (SP) round function). Our techniques are based on rebound attacks. We assume that the S-boxes have a good differential property and the linear transformation has an optimal branch number. Under this assumption, we firstly describe known-key distinguishers on the type-1, -2, and -3 generalized Feistel schemes up to 21, 13 and 8 rounds, respectively. Then, we use the distinguishers to make several attacks on hash functions where Merkle-Damgård domain extender is used and the compression function is constructed with Matyas-Meyer-Oseas or Miyaguchi-Preneel hash modes from generalized Feistel schemes. Collision attacks are made for 11 rounds of type-1 Feistel scheme. Near collision attacks are made for 13 rounds of type-1 Feistel scheme and 9 rounds of type-2 Feistel scheme. Half collision attacks are made for 15 rounds of type-1 Feistel scheme, 9 rounds of type-2 Feistel scheme, and 5 rounds of type-3 Feistel scheme.