On the (In)Equivalence of Impossible Differential and Zero-Correlation Distinguishers for Feistel- and Skipjack-Type Ciphers

Celine Blondeau, Andrey Bogdanov, Meiqin Wang

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

For many word-oriented block ciphers, impossible differential (ID) and zero-correlation linear (ZC) cryptanalyses are among the most powerful attacks. Whereas ID cryptanalysis makes use of differentials which never occur, the ZC cryptanalysis relies on linear approximations with correlations equal to zero. While the key recovery parts of ID and ZC attacks may differ and are often specific to the target cipher, the underlying distinguishing properties frequently cover the same number of rounds. However, in some cases, the discrepancy between the best known IDs and ZC approximations is rather significant.At EUROCRYPT'13, a link between these two distinguishers has been presented. However, though being independent of the underling structure of the cipher, it is usually not useful for most known ID or ZC distinguishers. So despite the relevance of those attacks, the question of their equivalence or inequivalence has not been formally addressed so far in a constructive practical way.In this paper, we aim to bridge this gap in the understanding of the links between the ID and ZC properties. We tackle this problem at the example of two wide classes of ciphers, namely, Feistel- and Skipjack-type ciphers. As our major contribution, for those ciphers, we derive conditions for impossible differentials and zero-correlation approximations to cover the same number of rounds. Using the conditions, we prove an equivalence between ID and ZC distinguishers for type-I and type-II Feistel-type ciphers, for Rule-A and Rule-B Skipjack-type ciphers, as well as for TWINE and LBlock. Moreover, we show this equivalence for the Extended Generalised Feistel construction presented at SAC'13. We also use our theoretical results to argue for an inequivalence between ID and ZC distinguishers for a range of Skipjack-type ciphers.
Original languageEnglish
Title of host publicationApplied Cryptography and Network Security
PublisherSpringer
Publication date2014
Pages271-288
ISBN (Print)978-3-319-07535-8
ISBN (Electronic)978-3-319-07536-5
DOIs
Publication statusPublished - 2014
Event12th International Conference on Applied Cryptography and Network Security (ACNS) - Lausanne, Switzerland
Duration: 10 Jun 201413 Jun 2014
Conference number: 12
http://acns2014.epfl.ch/

Conference

Conference12th International Conference on Applied Cryptography and Network Security (ACNS)
Number12
Country/TerritorySwitzerland
CityLausanne
Period10/06/201413/06/2014
Internet address
SeriesLecture Notes in Computer Science
Volume8479
ISSN0302-9743

Keywords

  • Impossible differential
  • Zero-correlation
  • Feistel-type ciphers
  • Skipjack-type ciphers

Fingerprint

Dive into the research topics of 'On the (In)Equivalence of Impossible Differential and Zero-Correlation Distinguishers for Feistel- and Skipjack-Type Ciphers'. Together they form a unique fingerprint.

Cite this