Understanding the Related-Key Security of Feistel Ciphers from a Provable Perspective

Abstract

We initiate the provable related-key security treatment for models of \emph{practical} Feistel ciphers. In detail, we consider Feistel networks with four whitening keys \(\wf_i(k)\) (\(i=0,1,2,3\)) and round-functions of the form \(f(\ga_i(k)\oplus X)\), where \(k\) is the main-key, \(\wf_i\) and \(\ga_i\) are efficient transformations, and \(f\) is a \emph{public} ideal function or permutation that the adversary is allowed to query. We investigate conditions on the key-schedules that are sufficient for security against XOR-induced related-key attacks up to \(2^{n/2}\) adversarial queries. When the key-schedules are \emph{non-linear}, we prove security for 4 rounds. When only \emph{affine} key-schedules are used, we prove security for 6 rounds. These also imply secure tweakable Feistel ciphers in the Random Oracle model. By shuffling the key-schedules, our model unifies both the DES-like structure (known as \emph{Feistel-2} scheme in the cryptanalytic community, a.k.a. \emph{key-alternating Feistel} due to Lampe and Seurin, FSE 2014) and the Lucifer-like model (previously analyzed by Guo and Lin, TCC 2015). This allows us to derive concrete implications on these two (more common) models, and helps understanding their differences---and further understanding the related-key security of Feistel ciphers.