Paper 2014/047

Down the Rabbit Hole: Revisiting the Shrinking Method

Vivien Dubois

Abstract

The paper is about methodology to detect and demonstrate impossible differentials in a block cipher. We were inspired by the shrinking technique proposed by Biham et al. in 1999 which recovered properties of scalable block cipher structures from numerical search on scaled down variants. Attempt to bind all concepts and techniques of impossible differentials together reveals a view of the search for impossible differentials that can benefit from the computational power of a computer. We demonstrate on generalized Feistel networks with internal permutations an additional clustering layer on top of shrinking which let us merge numerical data into relevant human-readable information to be used in an actual proof. After that, we show how initial analysis of scaled down TEA-like schemes leaks the relevant part of the design and the length and ends of the impossible differentials. We use that initial profiling to numerically discover 4 15-round impossible differentials (beating the current 13-round) and thousands of shorter ones.

Note: Acknowledgement added.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
impossible differentialsblock ciphershrinkingTEA
Contact author(s)
vivien dubois @ m4x org
History
2014-01-25: revised
2014-01-20: received
See all versions
Short URL
https://ia.cr/2014/047
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/047,
      author = {Vivien Dubois},
      title = {Down the Rabbit Hole: Revisiting the Shrinking Method},
      howpublished = {Cryptology ePrint Archive, Paper 2014/047},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/047}},
      url = {https://eprint.iacr.org/2014/047}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.