Paper 2016/1162

Meet-in-the-Middle Attacks on Classes of Contracting and Expanding Feistel Constructions

Jian Guo, Jérémy Jean, Ivica Nikolic, and Yu Sasaki

Abstract

We show generic attacks on unbalanced Feistel ciphers based on the meet-in-the-middle technique. We analyze two general classes of unbalanced Feistel structures, namely contracting Feistels and expanding Feistels. In both of the cases, we consider the practical scenario where the round functions are keyless and known to the adversary. In the case of contracting Feistels with 4 branches, we show attacks on 16 rounds when the key length k (in bits) is as large as the block length n (in bits), and up to 24 rounds when k = 2n. In the case of expanding Feistels, we consider two scenarios: one, where different nonlinear functions without particular structures are used in the round function, and a more practical one, where a single nonlinear is used but different linear functions are introduced in the state update. In the former case, we propose generic attacks on 13 rounds when k = n, and up to 21 rounds when k = 2n. In the latter case, 16 rounds can be attacked for k = n, and 24 rounds for k = 2n.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in FSE 2017
Keywords
Unbalanced FeistelGeneric AttackKey RecoveryMITM
Contact author(s)
ntu guo @ gmail com
Jeremy Jean @ ssi gouv fr
inikolic @ ntu edu sg
History
2016-12-28: received
Short URL
https://ia.cr/2016/1162
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1162,
      author = {Jian Guo and Jérémy Jean and Ivica Nikolic and Yu Sasaki},
      title = {Meet-in-the-Middle Attacks on Classes of Contracting and Expanding Feistel Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1162},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1162}},
      url = {https://eprint.iacr.org/2016/1162}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.