Towards Accurate Statistical Analysis of Security Margins: New Searching Strategies for Differential Attacks

Abstract

In todays world of the internet, billions of computer systems are connected to one another in a global network. The internet provides an unsecured channel in which hundreds of terabytes of data is being transmitted daily. Computer and software systems rely on encryption algorithms such as block ciphers to ensure that sensitive data remains confidential and secure. However, adversaries can leverage the statistical behavior of underlying ciphers to recover encryption keys. Accurate evaluation of the security margins of these encryption algorithms remains to be a big challenge. In this paper, we tackle this issue by introducing several searching strategies based on differential cryptanalysis. By clustering differential paths, the searching algorithm derives more accurate distinguishers as compared to examining individual paths, which in turn provides a more accurate estimation of cipher security margins. We verify the effectiveness of this technique on ciphers with the generalized Feistel and SPN structures, whereby the best distinguishers for each of the investigated ciphers were obtained by discovering clusters with thousands of paths. With the KATAN block cipher family as a test case, we also show how to apply the searching algorithm alongside other cryptanalysis techniques such as the boomerang attack and related-key model to obtain the best cryptanalytic results. This also depicts the flexibility of the proposed searching scheme, which can be tailored to improve upon other differential attack variants. In short, the proposed searching strategy realizes an automated security evaluation tool with higher accuracy compared to previous techniques. In addition, it is applicable to a wide range of encryption schemes which makes it a flexible tool for both academic research and industrial purposes.