Cryptanalysis by Using Differential-Linear Hull: An Extension to Differential-Linear Cryptanalysis

Abstract

In 2002, Biham et al. proposed an enhanced differential-linear cryptanalysis, where a differential characteristic with probability p (0＜p≤1) can be combined with a linear characteristic to form a differential-linear distinguisher. In this paper, we firstly introduce the concept of differential-linear hull and the method of cryptanalysis by using differential-linear hull, an extension to the enhanced differential-linear cryptanalysis, in which a differential characteristic can be combined with multiple linear characteristics to derive a differential-linear distinguisher. Furthermore, we introduce a technique about how to search for differential-linear hull based on a differential-linear characteristic for SPN and Feistel block ciphers. As a demonstration, this extension is applied to describe a differential-linear distinguisher for 4-round Serpent, and then the best known key recovery attack on 6-round Serpent is presented based on the differential-linear distinguisher. In fact, our work is a new attempt to propose the idea of differential-linear hull and introduce a new cryptanalytic method for block ciphers by using differential-linear hull. This new cryptanalytic method may be helpful to analyze a variety of block ciphers including SPN and Feistel schemes which could be adopted as the fundamental cryptographic components in the security solutions for future computer science.