Understanding the Related-Key Security of Feistel Ciphers from a Provable Perspective
This work addresses the security of widely used encryption schemes for cryptographers and practitioners, providing foundational proofs that are incremental but crucial for understanding and designing secure ciphers.
The paper tackles the problem of proving related-key security for practical Feistel ciphers, establishing conditions on key-schedules that ensure security against XOR-induced attacks up to 2^{n/2} queries, with proofs for 4 rounds with non-linear schedules and 6 rounds with affine schedules.
We initiate the provable related-key security treatment for models of practical Feistel ciphers. In detail, we consider Feistel networks with four whitening keys $w_i(k)$ ($i=0,1,2,3$) and round-functions of the form $f(γ_i(k)\oplus X)$, where $k$ is the main-key, $w_i$ and $γ_i$ are efficient transformations, and $f$ is a 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 non-linear, we prove security for 4 rounds. When only 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 Feistel-2 scheme in the cryptanalytic community, a.k.a. 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.