Cryptology ePrint Archive: Report 2014/047
Down the Rabbit Hole: Revisiting the Shrinking Method
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.
Category / Keywords: secret-key cryptography / impossible differentials, block cipher, shrinking, generalized feistel networks with internal permutations, TEA
Date: received 19 Jan 2014, last revised 25 Jan 2014
Contact author: vivien dubois at m4x org
Available format(s): PDF | BibTeX Citation
Note: Acknowledgement added.
Version: 20140125:133439 (All versions of this report)
Short URL: ia.cr/2014/047
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]