Paper 2016/136

Automatic Expectation and Variance Computing for Attacks on Feistel Schemes

Emmanuel Volte, Valérie Nachef, and Nicolas Marrière

Abstract

There are many kinds of attacks that can be mounted on block ciphers: differential attacks, impossible differential attacks, truncated differential attacks, boomerang attacks. We consider generic differential attacks used as distinguishers for various types of Feistel ciphers: they allow to distinguish a random permutation from a permutation generated by the cipher. These attacks are based on differences between the expectations of random variables defined by relations on the inputs and outputs of the ciphers. Sometimes, one has to use the value of the variance as well. In this paper, we will provide a tool that computes the exact values of these expectations and variances. We first explain thoroughly how these computations can be carried out by counting the number of solutions of a linear systems with equalities and non-equalities. Then we provide the first applications of this tool. For example, it enabled to discover a new geometry in 4-point attacks. It gave an explanation to some phenomena that can appear in simulations when the inputs and outputs have a small number of bits.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Generic attacks on Feistel type schemespseudo-random permutationsdifferential cryptanalysis
Contact author(s)
valerie nachef @ u-cergy fr
History
2016-02-16: received
Short URL
https://ia.cr/2016/136
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/136,
      author = {Emmanuel Volte and Valérie Nachef and Nicolas Marrière},
      title = {Automatic Expectation and Variance Computing for Attacks on Feistel Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2016/136},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/136}},
      url = {https://eprint.iacr.org/2016/136}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.