Cryptology ePrint Archive: Report 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.

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)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]