Paper 2009/287

Generic Attacks on Alternating Unbalanced Feistel Schemes

Valerie Nachef

Abstract

\begin{abstract} Generic attacks against classical (balanced) Feistel schemes, unbalanced Feistel schemes with contracting functions and unbalanced Feistel schemes with expanding functions have been studied in \cite {P01}, \cite{Jut}, \cite{PNB06}, \cite{PNB07}. In this paper we study schemes where we use alternatively contracting random functions and expanding random functions. We name these schemes ``Alternating Unbalanced Feistel Schemes''. They allow constructing pseudo-random permutations from kn bits to kn bits where k3. At each round, we use either a random function from n bits to (k1)n bits or a random function from bits to bits. We describe the best generic attacks we have found. We present``known plaintext attacks'' (KPA) and ``non-adaptive chosen plaintext attacks'' (CPA-1). Let be the number of rounds. We show that if , there are CPA-1 with 2 messages and KPA with the number of messages about . For we have to distinguish even and odd. For even, we have in CPA-1 and in KPA. When is odd, we show that there exist CPA-1 for and KPA for with less than messages and computations. Beyond these values, we give KPA against generators of permutations. \end{abstract}

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
unbalanced Feistel permutationspseudorandom permutationsgeneric attacks
Contact author(s)
valerie nachef @ u-cergy fr
History
2009-06-16: received
Short URL
https://ia.cr/2009/287
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/287,
      author = {Valerie Nachef},
      title = {Generic Attacks on Alternating Unbalanced Feistel Schemes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/287},
      year = {2009},
      url = {https://eprint.iacr.org/2009/287}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.