Cryptology ePrint Archive: Report 2016/689

New Automatic Search Tool for Impossible Differentials and Zero-Correlation Linear Approximations

Tingting Cui and Keting Jia and Kai Fu and Shiyao Chen and Meiqin Wang

Abstract: Impossible differential cryptanalysis and zero-correlation linear cryptanalysis are two of the most useful cryptanalysis methods in the field of symmetric ciphers. Until now, there are several automatic search tools for impossible differentials such as $\mathcal{U}$-method and UID-method, which are all independent of the non-linear S-boxes. Since the differential and linear properties can also contribute to the search of impossible differentials and zero-correlation linear approximations respectively, it is meaningful to study the search with considering the properties of non-linear components. In this paper, we propose an automatic search tool for impossible differentials and zero-correlation linear approximations in both ARX ciphers and ciphers with S-box, which is the first widely applicable one that considers the influence of non-linear operations, especially in ARX ciphers. What's more, this tool can be used to prove whether there are impossible differentials (zero-correlation linear approximations) in certain rounds of a target cipher, particularly for certain subset of input and output differences (masks) patterns. As applications, we use this automatic tool on HIGHT and LBlock ciphers. Consequently, we find total 4 impossible differentials and 4 zero-correlation linear approximations for 17-round HIGHT which are the longest ones until now, and find six 16-round related-key impossible differentials for LBlock, which are the best ones up to now.

Category / Keywords: Automatic search tool, (related-key) impossible differential, zero-correlation linear approximation, HIGHT, LBlock

Date: received 11 Jul 2016, last revised 29 Nov 2016

Contact author: mqwang at sdu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20161129:085313 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]