# Improved Conditional Differential Analysis on NLFSR-Based Block Cipher KATAN32 with MILP

Authors: Zhaohui Xing; Wenying Zhang; Guoyong Han
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

In this paper, a new method for constructing a Mixed Integer Linear Programming (MILP) model on conditional differential cryptanalysis of the nonlinear feedback shift register- (NLFSR-) based block ciphers is proposed, and an approach to detecting the bit with a strongly biased difference is provided. The model is successfully applied to the block cipher KATAN32 in the single-key scenario, resulting in practical key-recovery attacks covering more rounds than the previous. In particular, we present two distinguishers for 79 and 81 out of 254 rounds of KATAN32. Based on the 81-round distinguisher, we recover 11 equivalent key bits of 98-round KATAN32 and 13 equivalent key bits of 99-round KATAN32. The time complexity is less than231 encryptions of 98-round KATAN32 and less than 233 encryptions of 99-round KATAN32, respectively. Thus far, our results are the best known practical key-recovery attacks for the round-reduced variants of KATAN32 regarding the number of rounds and the time complexity. All the results are verified experimentally.


---

## Body

## 1. Introduction

Cryptographic techniques move into applications like access control, parking management, goods tracking, radio frequency identification tags, and integrated circuit (IC) printing [1]. At the same time, wireless sensor networks (WSNs) have been used for various critical industrial applications, such as heartbeat monitoring, temperature monitoring for precision agriculture, self-monitoring of autonomous vehicles, and power usage monitoring for smart grid [2, 3]. In these new cryptography environments, RFID technology applications and sensor networks have similar features such as weak computation ability, small storage space, and strict power constraints. However, the data processed in these applications are sensitive [4]. The ever-increasing demand for security and privacy in these very constrained environments requires new cryptographic primitives, like low cost, tiny, and efficient ciphers. Hence, traditional block ciphers such as AES are not suitable for these constrained environments. Many lightweight ciphers, including KATAN and KTANTAN family [5] and Piccolo [6], have been proposed to tackle this problem.The KATAN and KTANTAN block ciphers were proposed by Christophe DeCannière, Orr Dunkelman, and Miroslav Knezevic at CHES 2009 [5]. In order to reduce the energy consumed in data processing and improve the efficiency, KATAN uses nonlinear feedback shift registers (NLFSRs) as well as a linear key schedule [7]. Both KATAN and KTANTAN have three variants with 32-bit, 48-bit, and 64-bit block sizes, each requiring an 80-bit user key. In addition, KATAN and KTANTAN share the same data path specification, including round transformation and round constants. The only difference between KATAN and KTANTAN is the generation of subkeys. For KTANTAN, two bits of the 80-bit K=k79k78⋯k1k0 are selected each round. However, the key schedule of the KATAN32 cipher (and the other two variants KATAN48 and KATAN64) loads the 80-bit key into an LFSR (the least significant bit of the key is loaded to position 0 of the LFSR). For each round, positions 0 and 1 of the LFSR are generated as the round subkey k2i and k2i+1, and the LFSR is clocked twice. Because of the simple key schedule, KTANTAN was broken by Wei et al. [8], and while a more complex key schedule makes KATAN secure and stronger, the key schedule is also linear.


### 1.1. Related Work

KATAN family ciphers have been analyzed by extensive cryptanalysis. At ASIACRYPT 2010, Knellwolf et al. analyzed KATAN and KTANTAN [9] using conditional differential cryptanalysis [10] and recovered four equivalent key bits for 78 of 254 rounds of KATAN32 in the single-key scenario. They subsequently analyzed KATAN32 in the related-key scenario with an improved technique using automatic tools and then obtained key-recovery attacks for 120 of 254 rounds of KATAN32 [11]. Finding the nonuniformity of the difference distribution after 91 rounds, Albrecht and Leander proposed a 91-round distinguisher with the time complexity being 232 encryptions [12]. These results on KATAN32 are listed in Table 1.Table 1
Cryptanalytic results on KATAN32.
TypeScenarioRoundsTime complexityReferenceConditional differentialSingle key78222[9]Related key120231[11]Improved conditional differentialSingle key97230This paperSingle key98231This paperSingle key99233This paperDifferentialSingle key91232∗[12]Single key115278MIMT ASRSingle key119279.1[13]Match Box MITMSingle key153278.5[14]Dynamic CubeSingle key155278.3[15]Multidimensional MITMSingle key175279.3[16]Single key206279[17]∗A 91-round differential distinguisher.Other types of attacks formally published on this cipher are also listed in Table1, such as all subkeys recovery (ASR), which is a variant of the meet-in-the-middle (MITM) attack [13], Match Box MITM attack [14], Dynamic Cube attack [15], and Multidimensional MITM attack [16, 17]. As can be seen from the details in Table 1, each time complexity is too high to present a practical attack.As stated in [18], related-key attacks are arguable in a practical sense, because a related-key attack is under the assumption that the attacker had known and even controlled the relation between multiple unknown keys. Because of this assumption, the related-key attack is arguable from the aspect of practical security, though it is meaningful during the design and certification of a cipher. In particular, the key of an ultra-lightweight block cipher in low-end devices such as a passive RFID tag may not be changed during its life cycle. In a practical sense, the security of a lightweight cipher under the single-key scenario is the most important. As shown in [19], even though the result of an attack in the related-key scenario is better, it is still meaningful to explore an attack in the single-key scenario.Conditional differential cryptanalysis was first introduced by Biham and Ben-Aroya at Crypto 1993 in [10]. The idea is to control the propagation of differences by imposing conditions on the public variables of the cipher. In particular, we want to impose some conditions to filter plaintexts. Depending on whether these conditions involve secret variables or not, key-recovery or distinguishing attacks can be mounted. The key bit conditions lead to a key-recovery attack. The technique has been extended to higher order differential cryptanalysis. Later, it has been a very popular technique in hash functions cryptanalysis [20]. It allows increasing the probability of a differential characteristic satisfying some conditions; it also can be useful for block ciphers.In some attacks, attackers derive the conditions by hand, which is time consuming and error prone. This paper uses an automatic tool named Mixed Integer Linear Programming (MILP) to get minimum conditions and obtain new cryptanalytic results. MILP is a general mathematical tool for optimization that takes as inputs a linear objective function and a system of linear inequalities and finds solutions that optimize the objective function under the constraints of all inequalities. It was first applied by Mouha et al. in [21] and Wu et al. in [22] to count the active Sboxes of word-based block ciphers. It has been applied to search for differential characteristics and linear approximations [23, 24]. It has also been applied to search for integral distinguishers and division trails [25, 26] and impossible differentials [27, 28]. In particular, it has been applied to key-recovery attacks of keyed Keccak MAC, where attackers implemented conditional cube attacks on Keccak with the propagation of cube variables controlled under conditions in the first several rounds and attacked keyed Keccak [29–31].


### 1.2. Our Contributions

In this paper, we improve conditional differential attacks from two aspects. On the one hand, we propose a method of automatic conditional differential cryptanalysis using MILP. This method helps us minimize the number of conditions under which the differential characteristic can hold because the fewer the conditions, the higher the probability of the differential path. On the other hand, we propose a method to quickly calculate the bias of every bit quickly and detect the bit, which has a strongly biased difference. Finally, using the standard differential attack, we extend the conditional differential attack to more rounds. The details are described in the following paragraphs.We first propose a novel method using MILP to automatically search an initial difference and conditions for conditional differential cryptanalysis. In [9], Knellwolf et al. chose initial differences manually, and it is difficult to find the optimal choice, a crucial element in this attack. In this paper, we solve this problem by using MILP. We analyze how to identify conditions on internal state variables, and then, by modeling relations between differences in state bits and conditions, we construct a linear inequality system. The object function of this MILP problem is the minimum number of conditions in a certain number of rounds. Based on the method using MILP, we automatically obtain the initial difference and conditions.Second, we present an approach to detecting the bias in the difference of the update bit. In [9], Knellwolf et al. detected the bias experimentally by observing certain nonrandomness of a difference of the update bit. We find that the probability of a difference in the update bit is determined by the probabilities of differences in bits that generate the update bit. After the analysis, we present a formula for evaluating the probability of the difference in the update bit, helping us detect which bit has a strongly biased difference.Given the initial difference, the conditions, and the bit’s position with a bias, we can mount a key-recovery attack.We apply conditional differential cryptanalysis with these two improvements to analyze the security of KATAN32. It is shown that we can retrieve ten equivalent key bits for the variant of KATAN32 with 79 initialization rounds and four equivalent key bits with 81 initialization rounds.Using standard differential attacks, we extend the 81-round conditional differential key-recovery attacks to 97-round, 98-round, and 99-round with time complexity being230,231, and 233 encryptions, respectively. Extended key-recovery attacks can recover 10, 11, and 13 equivalent key bits, respectively. It is the best known practical cryptanalytic result on KATAN32 so far.All of our attacks succeed experimentally. All of our source codes and experiment results are available athttps://www.dropbox.com/sh/028s4f06f363b2h/AADItFkz-N1KaAMZR7nIPTawa?dl=0.


### 1.3. Organization

The paper is organized as follows. In Section2, some preliminaries are introduced. Section 3 describes the two improvements in conditional differential attacks. In Section 4, with these improvements, the attacks mounted on 79 and 81 of 254 rounds of KATAN32 are presented in detail. In Section 5, we extend the attacks to 97, 98, and 99 of 254 rounds of KATAN32 combined with standard differential attacks. Finally, we conclude the paper in Section 6.


## 1.1. Related Work

KATAN family ciphers have been analyzed by extensive cryptanalysis. At ASIACRYPT 2010, Knellwolf et al. analyzed KATAN and KTANTAN [9] using conditional differential cryptanalysis [10] and recovered four equivalent key bits for 78 of 254 rounds of KATAN32 in the single-key scenario. They subsequently analyzed KATAN32 in the related-key scenario with an improved technique using automatic tools and then obtained key-recovery attacks for 120 of 254 rounds of KATAN32 [11]. Finding the nonuniformity of the difference distribution after 91 rounds, Albrecht and Leander proposed a 91-round distinguisher with the time complexity being 232 encryptions [12]. These results on KATAN32 are listed in Table 1.Table 1
Cryptanalytic results on KATAN32.
TypeScenarioRoundsTime complexityReferenceConditional differentialSingle key78222[9]Related key120231[11]Improved conditional differentialSingle key97230This paperSingle key98231This paperSingle key99233This paperDifferentialSingle key91232∗[12]Single key115278MIMT ASRSingle key119279.1[13]Match Box MITMSingle key153278.5[14]Dynamic CubeSingle key155278.3[15]Multidimensional MITMSingle key175279.3[16]Single key206279[17]∗A 91-round differential distinguisher.Other types of attacks formally published on this cipher are also listed in Table1, such as all subkeys recovery (ASR), which is a variant of the meet-in-the-middle (MITM) attack [13], Match Box MITM attack [14], Dynamic Cube attack [15], and Multidimensional MITM attack [16, 17]. As can be seen from the details in Table 1, each time complexity is too high to present a practical attack.As stated in [18], related-key attacks are arguable in a practical sense, because a related-key attack is under the assumption that the attacker had known and even controlled the relation between multiple unknown keys. Because of this assumption, the related-key attack is arguable from the aspect of practical security, though it is meaningful during the design and certification of a cipher. In particular, the key of an ultra-lightweight block cipher in low-end devices such as a passive RFID tag may not be changed during its life cycle. In a practical sense, the security of a lightweight cipher under the single-key scenario is the most important. As shown in [19], even though the result of an attack in the related-key scenario is better, it is still meaningful to explore an attack in the single-key scenario.Conditional differential cryptanalysis was first introduced by Biham and Ben-Aroya at Crypto 1993 in [10]. The idea is to control the propagation of differences by imposing conditions on the public variables of the cipher. In particular, we want to impose some conditions to filter plaintexts. Depending on whether these conditions involve secret variables or not, key-recovery or distinguishing attacks can be mounted. The key bit conditions lead to a key-recovery attack. The technique has been extended to higher order differential cryptanalysis. Later, it has been a very popular technique in hash functions cryptanalysis [20]. It allows increasing the probability of a differential characteristic satisfying some conditions; it also can be useful for block ciphers.In some attacks, attackers derive the conditions by hand, which is time consuming and error prone. This paper uses an automatic tool named Mixed Integer Linear Programming (MILP) to get minimum conditions and obtain new cryptanalytic results. MILP is a general mathematical tool for optimization that takes as inputs a linear objective function and a system of linear inequalities and finds solutions that optimize the objective function under the constraints of all inequalities. It was first applied by Mouha et al. in [21] and Wu et al. in [22] to count the active Sboxes of word-based block ciphers. It has been applied to search for differential characteristics and linear approximations [23, 24]. It has also been applied to search for integral distinguishers and division trails [25, 26] and impossible differentials [27, 28]. In particular, it has been applied to key-recovery attacks of keyed Keccak MAC, where attackers implemented conditional cube attacks on Keccak with the propagation of cube variables controlled under conditions in the first several rounds and attacked keyed Keccak [29–31].


## 1.2. Our Contributions

In this paper, we improve conditional differential attacks from two aspects. On the one hand, we propose a method of automatic conditional differential cryptanalysis using MILP. This method helps us minimize the number of conditions under which the differential characteristic can hold because the fewer the conditions, the higher the probability of the differential path. On the other hand, we propose a method to quickly calculate the bias of every bit quickly and detect the bit, which has a strongly biased difference. Finally, using the standard differential attack, we extend the conditional differential attack to more rounds. The details are described in the following paragraphs.We first propose a novel method using MILP to automatically search an initial difference and conditions for conditional differential cryptanalysis. In [9], Knellwolf et al. chose initial differences manually, and it is difficult to find the optimal choice, a crucial element in this attack. In this paper, we solve this problem by using MILP. We analyze how to identify conditions on internal state variables, and then, by modeling relations between differences in state bits and conditions, we construct a linear inequality system. The object function of this MILP problem is the minimum number of conditions in a certain number of rounds. Based on the method using MILP, we automatically obtain the initial difference and conditions.Second, we present an approach to detecting the bias in the difference of the update bit. In [9], Knellwolf et al. detected the bias experimentally by observing certain nonrandomness of a difference of the update bit. We find that the probability of a difference in the update bit is determined by the probabilities of differences in bits that generate the update bit. After the analysis, we present a formula for evaluating the probability of the difference in the update bit, helping us detect which bit has a strongly biased difference.Given the initial difference, the conditions, and the bit’s position with a bias, we can mount a key-recovery attack.We apply conditional differential cryptanalysis with these two improvements to analyze the security of KATAN32. It is shown that we can retrieve ten equivalent key bits for the variant of KATAN32 with 79 initialization rounds and four equivalent key bits with 81 initialization rounds.Using standard differential attacks, we extend the 81-round conditional differential key-recovery attacks to 97-round, 98-round, and 99-round with time complexity being230,231, and 233 encryptions, respectively. Extended key-recovery attacks can recover 10, 11, and 13 equivalent key bits, respectively. It is the best known practical cryptanalytic result on KATAN32 so far.All of our attacks succeed experimentally. All of our source codes and experiment results are available athttps://www.dropbox.com/sh/028s4f06f363b2h/AADItFkz-N1KaAMZR7nIPTawa?dl=0.


## 1.3. Organization

The paper is organized as follows. In Section2, some preliminaries are introduced. Section 3 describes the two improvements in conditional differential attacks. In Section 4, with these improvements, the attacks mounted on 79 and 81 of 254 rounds of KATAN32 are presented in detail. In Section 5, we extend the attacks to 97, 98, and 99 of 254 rounds of KATAN32 combined with standard differential attacks. Finally, we conclude the paper in Section 6.


## 2. Preliminaries

We present our notations in Table2.Table 2
The notations used throughout the paper.
SymbolDefinitionF2The finite field of two elementsF2nThen-dimensional vector space over F2StThe state of the 13-bit NLFSR at roundtLtThe state of the 19-bit NLFSR at roundtst+iThei-th bit of the 13-bit NLFSR at round tlt+iThei-th bit of the 19-bit NLFSR at round tΔst+iThe difference inst+iΔlt+iThe difference inlt+iXA 32-bit plaintext blockxiThei-th bit of the plaintextKAn 80-bit keykiThei-th bit of the key


### 2.1. Description of KATAN

The block ciphers KATAN family are lightweight cryptographic primitives dedicated to hardware implementation. They share a very similar structure based on nonlinear feedback shift registers (NLFSR). KATAN and KTANTAN are composed of three block ciphers with 32-, 48-, and 64-bit block sizes, respectively, denoted by KATANn and KTANTANn for n=32,48,64. They all have 80-bit keys, and the only difference between KATAN and KTANTAN is the key schedule. The round key bits of KATAN are the linear combination of the initial key bits, and the key bits of KTANTAN are extracted directly from the initial 80 key bits according to the predefined rule. Here, we will briefly introduce KATAN32, which is analyzed in this paper.


#### 2.1.1. Key Schedule

The master keyK=k0,⋯,k79 is loaded into an 80-bit linear feedback register, and new round keys are generated by the linear feedback relation:
(1)ki+80=ki⊕ki+19⊕ki+30⊕ki+67,0≤i≤427.In the remainder of this paper, for anyi≥80, we call ki one equivalent key bit, which is the linear combination of the initial key bits.


#### 2.1.2. Round Function

In initialization, a 32-bit plaintext blockX=x31,⋯,x0 is loaded into two NLFSRs with lengths 13 and 19 bits, respectively. Denote states of the 13-bit NLFSR and the 19-bit NLFSR at round t as St=st,st+1,⋯,st+12 and Lt=lt,lt+1,⋯,lt+18.Whent=0, the plaintext is loaded as lt+i=x18−i for 0≤i≤18 and st+i=x31−i for 0≤i≤12.At roundt, for 0≤t≤253, two new bits st+13 and lt+19 are produced according to the following equations:
(2)st+13=lt⊕lt+11⊕lt+6lt+8⊕lt+10lt+15⊕k2t+1,(3)lt+19=st⊕st+5⊕st+4st+7⊕st+9at⊕k2t,where at is a round constant generated by the 8-bit LFSR using the recursive relation at=at−3⊕at−5⊕at−7⊕at−8t≥8 with the seed value a0,a1,a2,a3,a4,a5,a6,a7=1,1,1,1,1,1,1,0. After 254 rounds, the state is outputted as the ciphertext. The round function is depicted in Figure 1.Figure 1
The round function of KATAN32 cipher.


### 2.2. Conditional Differential Analysis

Knellwolf et al. applied conditional differential cryptanalysis to NLFSR-based cryptosystems at ASIACRYPT 2010 [9]. This technique is based on differential cryptanalysis used to analyze initialization mechanisms of stream ciphers in [32, 33]. After choosing an initial difference, it studies the propagation of the difference through NLFSR-based cryptosystems and identifies conditions on internal state bits to prevent difference propagation whenever possible. By taking the plaintext pairs conforming to these conditions as input, biases can be detected in differences of update bits at some rounds. Once a bias is detected, the key is considered to obey the expected conditions, and we obtain information for secret key bits. In some cases, there are single key bits or relations of key bits in the conditions; we call each of them one equivalent key bit, leading to a key-recovery attack.


## 2.1. Description of KATAN

The block ciphers KATAN family are lightweight cryptographic primitives dedicated to hardware implementation. They share a very similar structure based on nonlinear feedback shift registers (NLFSR). KATAN and KTANTAN are composed of three block ciphers with 32-, 48-, and 64-bit block sizes, respectively, denoted by KATANn and KTANTANn for n=32,48,64. They all have 80-bit keys, and the only difference between KATAN and KTANTAN is the key schedule. The round key bits of KATAN are the linear combination of the initial key bits, and the key bits of KTANTAN are extracted directly from the initial 80 key bits according to the predefined rule. Here, we will briefly introduce KATAN32, which is analyzed in this paper.


### 2.1.1. Key Schedule

The master keyK=k0,⋯,k79 is loaded into an 80-bit linear feedback register, and new round keys are generated by the linear feedback relation:
(1)ki+80=ki⊕ki+19⊕ki+30⊕ki+67,0≤i≤427.In the remainder of this paper, for anyi≥80, we call ki one equivalent key bit, which is the linear combination of the initial key bits.


### 2.1.2. Round Function

In initialization, a 32-bit plaintext blockX=x31,⋯,x0 is loaded into two NLFSRs with lengths 13 and 19 bits, respectively. Denote states of the 13-bit NLFSR and the 19-bit NLFSR at round t as St=st,st+1,⋯,st+12 and Lt=lt,lt+1,⋯,lt+18.Whent=0, the plaintext is loaded as lt+i=x18−i for 0≤i≤18 and st+i=x31−i for 0≤i≤12.At roundt, for 0≤t≤253, two new bits st+13 and lt+19 are produced according to the following equations:
(2)st+13=lt⊕lt+11⊕lt+6lt+8⊕lt+10lt+15⊕k2t+1,(3)lt+19=st⊕st+5⊕st+4st+7⊕st+9at⊕k2t,where at is a round constant generated by the 8-bit LFSR using the recursive relation at=at−3⊕at−5⊕at−7⊕at−8t≥8 with the seed value a0,a1,a2,a3,a4,a5,a6,a7=1,1,1,1,1,1,1,0. After 254 rounds, the state is outputted as the ciphertext. The round function is depicted in Figure 1.Figure 1
The round function of KATAN32 cipher.


## 2.1.1. Key Schedule

The master keyK=k0,⋯,k79 is loaded into an 80-bit linear feedback register, and new round keys are generated by the linear feedback relation:
(1)ki+80=ki⊕ki+19⊕ki+30⊕ki+67,0≤i≤427.In the remainder of this paper, for anyi≥80, we call ki one equivalent key bit, which is the linear combination of the initial key bits.


## 2.1.2. Round Function

In initialization, a 32-bit plaintext blockX=x31,⋯,x0 is loaded into two NLFSRs with lengths 13 and 19 bits, respectively. Denote states of the 13-bit NLFSR and the 19-bit NLFSR at round t as St=st,st+1,⋯,st+12 and Lt=lt,lt+1,⋯,lt+18.Whent=0, the plaintext is loaded as lt+i=x18−i for 0≤i≤18 and st+i=x31−i for 0≤i≤12.At roundt, for 0≤t≤253, two new bits st+13 and lt+19 are produced according to the following equations:
(2)st+13=lt⊕lt+11⊕lt+6lt+8⊕lt+10lt+15⊕k2t+1,(3)lt+19=st⊕st+5⊕st+4st+7⊕st+9at⊕k2t,where at is a round constant generated by the 8-bit LFSR using the recursive relation at=at−3⊕at−5⊕at−7⊕at−8t≥8 with the seed value a0,a1,a2,a3,a4,a5,a6,a7=1,1,1,1,1,1,1,0. After 254 rounds, the state is outputted as the ciphertext. The round function is depicted in Figure 1.Figure 1
The round function of KATAN32 cipher.


## 2.2. Conditional Differential Analysis

Knellwolf et al. applied conditional differential cryptanalysis to NLFSR-based cryptosystems at ASIACRYPT 2010 [9]. This technique is based on differential cryptanalysis used to analyze initialization mechanisms of stream ciphers in [32, 33]. After choosing an initial difference, it studies the propagation of the difference through NLFSR-based cryptosystems and identifies conditions on internal state bits to prevent difference propagation whenever possible. By taking the plaintext pairs conforming to these conditions as input, biases can be detected in differences of update bits at some rounds. Once a bias is detected, the key is considered to obey the expected conditions, and we obtain information for secret key bits. In some cases, there are single key bits or relations of key bits in the conditions; we call each of them one equivalent key bit, leading to a key-recovery attack.


## 3. Improved Conditional Differential Cryptanalysis

In [9], the authors traced differences through cryptosystems and prevented the propagation whenever possible by identifying conditions on internal state variables. They gave suggestions on manually choosing an initial difference rather than providing a specific method for acquiring it. They suggest that the difference propagation should be controllable for as many rounds as possible with fewer conditions. They also suggest there should not be too many conditions involving bits of K during initial rounds.While the initial difference is of crucial importance with respect to the number of rounds attacked, it is not easy to manually choose a suitable initial difference. In this paper, we propose a novel method using MILP to search for an initial difference, deriving as few conditions as possible and the differential characteristic that covers as many rounds as possible. We also present a method for evaluating the probability of the difference in the update bit, by which we can detect the bit with an obvious bias.Using these two improvements, we apply the improved conditional differential cryptanalysis to block cipher KATAN32. The framework of the analysis is divided into the following four steps.Search for an initial difference with MILP. With the method described in Section 3.1, one can formulate an MILP model of difference propagation, search for a differential characteristic with minimum conditions, and obtain the initial difference simultaneously.Choose conditions. We trace the propagation of the initial difference and identify conditions that prevent the propagation of differences until the number of key bits and plaintext bits involved in conditions becomes too great to mount an attack (exceed the enumeration capability).Calculate the bias. Given the initial difference and conditions chosen in the previous steps, the probability of the difference in each bit of the two NLFSRs can be easily derived when the conditions cease being applied. Taking this probability as the input of the method described in Section 3.2, we can calculate the probability of the difference in update bit at each subsequent round. According to these probabilities, we can locate the bit whose difference has an obvious bias, and the number of rounds is the largest.Mount the key-recovery attack. Since the conditions include some equivalent key bits, if plaintexts are selected with the conditions consisting of correct equivalent key bits, the difference in the located update bit will show the bias. The equivalent key bits involved in the conditions can be recovered. The attack is involved in Algorithm 1.Algorithm 1. The framework of the conditional differential attack.
Input: Equation (2) and Equation (3)Output: g: correct equivalent key bitsObtain an initial differenceΔX and a conditions set κ by MILP technique;κ← {conditions chosen from κ in the previous rounds to make sure that the number of key bits and plaintext bits involved in conditions should not exceed the enumeration capability};λ← {the probability of the difference of each bit at round r from which conditions just cease being applied. It is derived from ΔX and κ};P← {the probabilities of the differences of each subsequent update bit after round r calculated by λ using the method described in Section 3.2};t← the bit derived from P having the nonzero bias and at the highest possible number of rounds;forg∈{enumerate equivalent key bits involved in κ} docount1=0;count0=0;forx∈{enumerate plaintext bits involved in κ} doifx,g satisfy κthencalculateΔt from x and ΔX;ifΔt=1thencount1++;elsecount0++;endendendPΔt=1=count1/count1+count0;A←A∪g,∣PΔt=1−1/2∣;endsearching inA for the max ∣PΔt=1−1/2∣;returng in accordance with the max ∣PΔt=1−1/2∣.


### 3.1. Modeling the Difference Propagation of the Round Function

By modeling the propagation of differences under the control of conditions, we obtain an initial difference and a conditional differential characteristic with the fewest conditions. The steps are as follows.(1) Finding All Modes of Difference Propagation under the Control of Conditions. For KATAN32, at each round, only two bits are generated by some bits from the previous round, so the differences in these two bits are caused only by these bits. Equations (2) and (3) show the relation between these bits.There are linear and nonlinear terms in Equations (2) and (3). If there are differences in nonlinear terms, the difference in the update bit can be canceled by imposing conditions even if there are differences in linear terms at the same time. If differences appear only in linear terms, there are no possible conditions that could be applied to cancel the differences; they only can be canceled by one another, or the difference appears in the update bit.For example, for Equation (2): st+13=lt⊕lt+11⊕lt+6lt+8⊕lt+10lt+15⊕k2t+1, if Δlt+6=1, with the other bits having no differences, we add the condition lt+8=0 to ensure that Δst+13=0. The number of conditions is 1, and the difference of the update bit is 0. If Δlt+11=1, with the other bits having no differences, no conditions could cancel the difference. The difference appears in the update bit and propagates to the next round. In this case, the number of conditions is 0 and the difference of the update bit is 1.This shows that we can apply conditions to prevent the propagation of differences when the difference state (we call the difference of the internal state the difference state) is at some particular value. At some other values, there are no conditions that can prevent the propagation of the differences.For each exact difference state, it can be confirmed whether conditions could be applied and whether there would be a difference in the update bit according to the previous strategy that is aimed at preventing the propagation of differences.With respect to Equation (2), st+13 is generated by six bits in the 19-bit NLFSR of round t so that the difference of st+13 depends on the values and the differences of these six bits. Let c (the flag of adding a condition) denote whether a condition is applied to cancel the difference of the update bit, and let us search all values of the vector Δlt,Δlt+11,Δlt+6,Δlt+8,Δlt+10,Δlt+15,Δst+13,c following the following strategies.IfΔst+13=0 according to Equation (2), c takes value 0.Example 1.
IfΔlt,Δlt+11,Δlt+6,Δlt+8,Δlt+10,Δlt+15=1,1,0,0,0,0, according to Equation (2), Δst+13=0. Since no conditions need to be added, Δlt,Δlt+11,Δlt+6,Δlt+8,Δlt+10,Δlt+15,Δst+13,c=1,1,0,0,0,0,0,0 is the vector we hunt.Assuming thatΔst+13 may be 1 or 0 according to Equation (2). If a condition could be applied to ensure that Δst+13=0, Δst+13 takes value 0 and c takes value 1.Example 2.
Suppose thatΔlt,Δlt+11,Δlt+6,Δlt+8,Δlt+10,Δlt+15=0,0,0,0,0,1, according to Equation (2), Δst+13 could be either 1 or 0. But if we impose the condition lt+10=0, Δst+13 must be 0, and c takes value 1, so 0,0,0,0,0,1,0,1 is the vector we hunt.If there must be a difference inst+13 and no conditions can cancel it, Δst+13 takes value 1 and c takes value 0.Example 3.
Suppose thatΔlt,Δlt+11,Δlt+6,Δlt+8,Δlt+10,Δlt+15=1,0,0,0,0,0, according to Equation (2), Δst+13=1, and it cannot be canceled by any conditions. Then, Δst+13 takes value 1 and c takes value 0. So we obtain 1,0,0,0,0,0,1,0.The difference stateΔlt,Δlt+11,Δlt+6,Δlt+8,Δlt+10,Δlt+15 can take on one of 26=64 values. We derive the exact values of c and Δst+13 from each value of the difference state in accordance with the above strategies. Then, with respect to Equation (2), we get all 64 values of the 8-dimensional vector (Δlt, Δlt+11, Δlt+6, Δlt+8, Δlt+10, Δlt+15, Δst+13, c), presented in Table 3.Table 3
64 vectorsΔlt,Δlt+11,Δlt+6,Δlt+8,Δlt+10,Δlt+15,Δst+13,c.
(0,0,0,0,0,0,0,0)(0,1,0,1,1,0,0,1)(1,0,1,1,0,0,0,1)(0,0,0,0,0,1,0,1)(0,1,0,1,1,1,0,1)(1,0,1,1,0,1,0,1)(0,0,0,0,1,0,0,1)(0,1,1,0,0,0,0,1)(1,0,1,1,1,0,0,1)(0,0,0,0,1,1,0,1)(0,1,1,0,0,1,0,1)(1,0,1,1,1,1,0,1)(0,0,0,1,0,0,0,1)(0,1,1,0,1,0,0,1)(1,1,0,0,0,0,0,0)(0,0,0,1,0,1,0,1)(0,1,1,0,1,1,0,1)(1,1,0,0,0,1,0,1)(0,0,0,1,1,0,0,1)(0,1,1,1,0,0,0,1)(1,1,0,0,1,0,0,1)(0,0,0,1,1,1,0,1)(0,1,1,1,0,1,0,1)(1,1,0,0,1,1,0,1)(0,0,1,0,0,0,0,1)(0,1,1,1,1,0,0,1)(1,1,0,1,0,0,0,1)(0,0,1,0,0,1,0,1)(0,1,1,1,1,1,0,1)(1,1,0,1,0,1,0,1)(0,0,1,0,1,0,0,1)(1,0,0,0,0,0,1,0)(1,1,0,1,1,0,0,1)(0,0,1,0,1,1,0,1)(1,0,0,0,0,1,0,1)(1,1,0,1,1,1,0,1)(0,0,1,1,0,0,0,1)(1,0,0,0,1,0,0,1)(1,1,1,0,0,0,0,1)(0,0,1,1,0,1,0,1)(1,0,0,0,1,1,0,1)(1,1,1,0,0,1,0,1)(0,0,1,1,1,0,0,1)(1,0,0,1,0,0,0,1)(1,1,1,0,1,0,0,1)(0,0,1,1,1,1,0,1)(1,0,0,1,0,1,0,1)(1,1,1,0,1,1,0,1)(0,1,0,0,0,0,1,0)(1,0,0,1,1,0,0,1)(1,1,1,1,0,0,0,1)(0,1,0,0,0,1,0,1)(1,0,0,1,1,1,0,1)(1,1,1,1,0,1,0,1)(0,1,0,0,1,0,0,1)(1,0,1,0,0,0,0,1)(1,1,1,1,1,0,0,1)(0,1,0,0,1,1,0,1)(1,0,1,0,0,1,0,1)(1,1,1,1,1,1,0,1)(0,1,0,1,0,0,0,1)(1,0,1,0,1,0,0,1)(0,1,0,1,0,1,0,1)(1,0,1,0,1,1,0,1)Meanwhile, with respect to Equation (3), we can also find all the difference state values (Δst, Δst+5, Δst+4, Δst+7, Δst+9, Δlt+19, c). It should be noted that in Equation (3) there is a constant at at each round. To simplify constraints of the MILP, we model two cases corresponding to the values of at.Whenat=1, Equation (3) contains five Boolean variables st, st+5, st+4, st+7, and st+9 so that the difference state (Δst, Δst+5, Δst+4, Δst+7, Δst+9) can take on one of 25=32 different values deriving the 32 values of the 7-dimensional vector Δst,Δst+5,Δst+4,Δst+7,Δst+9,Δlt+19,c shown in Table 4.Table 4
32 vectorsΔst,Δst+5,Δst+4,Δst+7,Δst+9,Δlt+19,c.
(0,0,0,0,0,0,0)(0,1,0,1,1,0,1)(1,0,1,1,0,0,1)(0,0,0,0,1,1,0)(0,1,1,0,0,0,1)(1,0,1,1,1,0,1)(0,0,0,1,0,0,1)(0,1,1,0,1,0,1)(1,1,0,0,0,0,0)(0,0,0,1,1,0,1)(0,1,1,1,0,0,1)(1,1,0,0,1,1,0)(0,0,1,0,0,0,1)(0,1,1,1,1,0,1)(1,1,0,1,0,0,1)(0,0,1,0,1,0,1)(1,0,0,0,0,1,0)(1,1,0,1,1,0,1)(0,0,1,1,0,0,1)(1,0,0,0,1,0,0)(1,1,1,0,0,0,1)(0,0,1,1,1,0,1)(1,0,0,1,0,0,1)(1,1,1,0,1,0,1)(0,1,0,0,0,1,0)(1,0,0,1,1,0,1)(1,1,1,1,0,0,1)(0,1,0,0,1,0,0)(1,0,1,0,0,0,1)(1,1,1,1,1,0,1)(0,1,0,1,0,0,1)(1,0,1,0,1,0,1)Whenat=0, Equation (3) contains four Boolean variables st, st+5, st+4, and st+7 so that the difference state (Δst, Δst+5, Δst+4, Δst+7) can take on one of 24=16 different values that lead to the 16 values of the 6-dimensional vector (Δst, Δst+5, Δst+4, Δst+7, Δlt+19, c) shown in Table 5.Table 5
16 vectorsΔst,Δst+5,Δst+4,Δst+7,Δlt+19,c.
(0,0,0,0,0,0)(0,1,1,0,0,1)(1,1,0,0,0,0)(0,0,0,1,0,1)(0,1,1,1,0,1)(1,1,0,1,0,1)(0,0,1,0,0,1)(1,0,0,0,1,0)(1,1,1,0,0,1)(0,0,1,1,0,1)(1,0,0,1,0,1)(1,1,1,1,0,1)(0,1,0,0,1,0)(1,0,1,0,0,1)(0,1,0,1,0,1)(1,0,1,1,0,1)(2) Modeling the Vector Sets Using Linear Inequalities. Via SageMath at http://www.sagemath.org, we obtain 19 linear inequalities that accurately describe the set of the 64 8-dimensional vectors in Table 3. This set of linear inequalities characterizes the difference propagation of Equation (2) under the control of conditions. Ten inequalities are remaining after a simple reduction. L1 shows the ten inequalities.
(4)L1=−Δst+13−c+1≥0,−Δlt+6+c≥0,−Δlt−Δlt+11−Δst+13+2≥0,−Δlt+8+c≥0,−Δlt+10+c≥0,−Δlt+15+c≥0,Δlt+Δlt+11−Δst+13≥0,−Δlt+Δlt+11+Δst+13+c≥0,Δlt−Δlt+11+Δst+13+c≥0,Δlt+6+Δlt+8+Δlt+10+Δlt+15−c≥0.Using the same method, we obtain two sets of linear inequalitiesL2 and L3 that accurately describe the 32 7-dimensional vectors given in Table 4 and the 16 6-dimensional vectors given in Table 5. The two sets are shown below:
(5)L2=−Δlt+19−c+1≥0,−Δst+7+c≥0,−Δst+4+c≥0,Δst+4+Δst+7−c≥0,Δst−Δst+5−Δst+9−Δlt+19+2≥0,−Δst+Δst+5−Δst+9−Δlt+19+2≥0,−Δst−Δst+5+Δst+9−Δlt+19+2≥0,Δst+Δst+5+Δst+9−Δlt+19≥0,−Δst−Δst+5−Δst+9+Δlt+19+c+2≥0,Δst+Δst+5−Δst+9+Δlt+19+c≥0,Δst−Δst+5+Δst+9+Δlt+19+c≥0,−Δst+Δst+5+Δst+9+Δlt+19+c≥0,L3=−Δlt+19−c+1≥0,−Δst+4+c≥0,−Δst+7+c≥0,Δst+4+Δst+7−c≥0,Δst−Δst+5+Δlt+19+c≥0,−Δst+Δst+5+Δlt+19+c≥0,Δst+Δst+5−Δlt+19≥0,−Δst−Δst+5−Δlt+19+2≥0.(3) Formulating the MILP Model to Determine an Initial Difference and Minimum Conditions. With these linear inequalities, we can obtain the relationships among the differences of bits that generate the update bit, the flag of adding a condition and the difference of the update bit in one round. We then expand the linear inequalities to n rounds, where n is a selected number, to obtain constraints of MILP. The objective function to be minimized is ∑i=0nci. The constraint of the initial difference is ∑i=031Δxi≥1. In our work, the MILP problem is solved by Cplex. With this solution, we can obtain both an initial difference and minimum conditions.There are too many plaintext bits and key bits in the conditions applied in the later rounds, so we prefer applying the conditions in earlier rounds rather than all of them. No more conditions have been applied since a particular round, which leads to uncontrollable difference propagation in subsequent rounds. After several rounds, the probability of the difference in the update bit would always be1/2. In Section 3.2, we propose a method to evaluate the update bit difference probability, which helps us find the bit whose difference probability deviates significantly from 1/2 and has the largest number of rounds.


### 3.2. Detecting the Bias of the Difference

In [9, 11], a bias was detected by experimentally observing certain nonrandomness, and we now present a method for automatically detecting the bias by programming. The method produces a formula for calculating the probability of the update bit difference, enabling us to find the bit whose probability of the difference has a bias from 1/2. The greater the bias, the higher probability of a successful attack.The properties below show that we can evaluate the probability of difference in the update bit, given all the probabilities of difference in the bits that generate the update bit. When conditions cease being applied, we get the probability of difference in each bit of two NLFSRs at that round. Using these probabilities, we can calculate the update bit difference probability in each subsequent round.Property 1.
Leta,b be two independent random Boolean variables, and then, the probability PΔa⊕b=1=PΔa=1+PΔb=1−2PΔa=1PΔb=1.With Property1, if the probabilities of the differences in a and b were known, we could evaluate the probability of the difference in a⊕b. It can be extended to the sum of four Boolean variables.Property 2.
Letx,y,z,w be independent random Boolean variables, and then, the probability
(6)PΔx⊕y⊕z⊕w=1=12−121−2PΔx=11−2PΔy=11−2PΔz=11−2PΔw=1.In the following, we consider the difference probability of two Boolean variables’ products. Property3 shows us how to evaluate the probability.Property 3.
Leta,b be the same as defined in Property 1, and then, the probability
(7)PΔa·b=1=PΔa=1+PΔb=1−PΔa=1PΔb=1·12.In Equations (2) and (3), there is no difference in the key and const, so k2t+1, k2t, and at do not influence the probability of the difference.Accordingly, we can derive the results as follows.From Equation (2), we can obtain the formula to calculate the probability of Δst+13=1:
(8)PΔst+13=1=PΔlt⊕lt+11⊕lt+6lt+8⊕lt+10lt+15=1=12−12·1−2PΔlt=11−2PΔlt+11=1=1−2PΔlt+6lt+8=11−2PΔlt+10lt+15=1,where
(9)PΔlt+6lt+8=1=PΔlt+6=1+PΔlt+8=1−PΔlt+6=1PΔlt+8=1·12,PΔlt+10lt+15=1=PΔlt+10=1+PΔlt+15=1−PΔlt+10=1PΔlt+15=1·12.From Equation (3), we can obtain the formula to calculate the probability of Δlt+19=1:
(10)PΔlt+19=1=PΔst⊕st+5⊕st+4st+7⊕st+9at=1=12−12·1−2PΔst=11−2PΔst+5=11−2PΔst+4st+7=11−2PΔst+9at=1,where
(11)PΔst+4st+7=1=PΔst+4=1+PΔst+7=1−PΔst+4=1PΔst+7=1·12,PΔst+9at=1=atPΔst+9=1.Using the two formulas, we can calculate the probabilities of the differences in the update bits in Algorithm2 at every subsequent round after the conditions stop being applied. After a certain round, the probability forever becomes 1/2. Before that, we can find the biased bit corresponding to the longest conditional differential characteristic.Algorithm 2. Calculating the probabilities of the differences in the update bits from roundt to round u.
Input: PΔst=1,PΔst+1=1,⋯PΔst+12=1: the set of probabilities of the difference for each bit of the 13-bit NLFSR at round t; PΔlt=1,PΔlt+1=1,⋯PΔlt+18=1: the set of probabilities of the difference for each bit of the 19-bit NLFSR at round t.Output: A: the set of the probabilities of the differences for update bits from round t to round u, there are two update bits at each round.S≔PΔst=1,PΔst+1=1,⋯PΔst+12=1;L≔PΔlt=1,PΔlt+2=1,⋯PΔst+18=1;A≔∅;fori∈t,t+1,⋯,udoPΔsi+13=1≔ the probability calculated from L according to formulas (8) and (9);PΔli+19=1≔ the probability calculated from S according to formulas (10) and (11);S≔PΔsi+1=1,PΔsi+2=1,⋯PΔsi+13=1;L≔PΔli+1=1,PΔli+2=1,⋯PΔli+19=1;A≔A∪PΔs¯i+13=1,PΔl¯i+19=1endreturnA.


## 3.1. Modeling the Difference Propagation of the Round Function

By modeling the propagation of differences under the control of conditions, we obtain an initial difference and a conditional differential characteristic with the fewest conditions. The steps are as follows.(1) Finding All Modes of Difference Propagation under the Control of Conditions. For KATAN32, at each round, only two bits are generated by some bits from the previous round, so the differences in these two bits are caused only by these bits. Equations (2) and (3) show the relation between these bits.There are linear and nonlinear terms in Equations (2) and (3). If there are differences in nonlinear terms, the difference in the update bit can be canceled by imposing conditions even if there are differences in linear terms at the same time. If differences appear only in linear terms, there are no possible conditions that could be applied to cancel the differences; they only can be canceled by one another, or the difference appears in the update bit.For example, for Equation (2): st+13=lt⊕lt+11⊕lt+6lt+8⊕lt+10lt+15⊕k2t+1, if Δlt+6=1, with the other bits having no differences, we add the condition lt+8=0 to ensure that Δst+13=0. The number of conditions is 1, and the difference of the update bit is 0. If Δlt+11=1, with the other bits having no differences, no conditions could cancel the difference. The difference appears in the update bit and propagates to the next round. In this case, the number of conditions is 0 and the difference of the update bit is 1.This shows that we can apply conditions to prevent the propagation of differences when the difference state (we call the difference of the internal state the difference state) is at some particular value. At some other values, there are no conditions that can prevent the propagation of the differences.For each exact difference state, it can be confirmed whether conditions could be applied and whether there would be a difference in the update bit according to the previous strategy that is aimed at preventing the propagation of differences.With respect to Equation (2), st+13 is generated by six bits in the 19-bit NLFSR of round t so that the difference of st+13 depends on the values and the differences of these six bits. Let c (the flag of adding a condition) denote whether a condition is applied to cancel the difference of the update bit, and let us search all values of the vector Δlt,Δlt+11,Δlt+6,Δlt+8,Δlt+10,Δlt+15,Δst+13,c following the following strategies.IfΔst+13=0 according to Equation (2), c takes value 0.Example 1.
IfΔlt,Δlt+11,Δlt+6,Δlt+8,Δlt+10,Δlt+15=1,1,0,0,0,0, according to Equation (2), Δst+13=0. Since no conditions need to be added, Δlt,Δlt+11,Δlt+6,Δlt+8,Δlt+10,Δlt+15,Δst+13,c=1,1,0,0,0,0,0,0 is the vector we hunt.Assuming thatΔst+13 may be 1 or 0 according to Equation (2). If a condition could be applied to ensure that Δst+13=0, Δst+13 takes value 0 and c takes value 1.Example 2.
Suppose thatΔlt,Δlt+11,Δlt+6,Δlt+8,Δlt+10,Δlt+15=0,0,0,0,0,1, according to Equation (2), Δst+13 could be either 1 or 0. But if we impose the condition lt+10=0, Δst+13 must be 0, and c takes value 1, so 0,0,0,0,0,1,0,1 is the vector we hunt.If there must be a difference inst+13 and no conditions can cancel it, Δst+13 takes value 1 and c takes value 0.Example 3.
Suppose thatΔlt,Δlt+11,Δlt+6,Δlt+8,Δlt+10,Δlt+15=1,0,0,0,0,0, according to Equation (2), Δst+13=1, and it cannot be canceled by any conditions. Then, Δst+13 takes value 1 and c takes value 0. So we obtain 1,0,0,0,0,0,1,0.The difference stateΔlt,Δlt+11,Δlt+6,Δlt+8,Δlt+10,Δlt+15 can take on one of 26=64 values. We derive the exact values of c and Δst+13 from each value of the difference state in accordance with the above strategies. Then, with respect to Equation (2), we get all 64 values of the 8-dimensional vector (Δlt, Δlt+11, Δlt+6, Δlt+8, Δlt+10, Δlt+15, Δst+13, c), presented in Table 3.Table 3
64 vectorsΔlt,Δlt+11,Δlt+6,Δlt+8,Δlt+10,Δlt+15,Δst+13,c.
(0,0,0,0,0,0,0,0)(0,1,0,1,1,0,0,1)(1,0,1,1,0,0,0,1)(0,0,0,0,0,1,0,1)(0,1,0,1,1,1,0,1)(1,0,1,1,0,1,0,1)(0,0,0,0,1,0,0,1)(0,1,1,0,0,0,0,1)(1,0,1,1,1,0,0,1)(0,0,0,0,1,1,0,1)(0,1,1,0,0,1,0,1)(1,0,1,1,1,1,0,1)(0,0,0,1,0,0,0,1)(0,1,1,0,1,0,0,1)(1,1,0,0,0,0,0,0)(0,0,0,1,0,1,0,1)(0,1,1,0,1,1,0,1)(1,1,0,0,0,1,0,1)(0,0,0,1,1,0,0,1)(0,1,1,1,0,0,0,1)(1,1,0,0,1,0,0,1)(0,0,0,1,1,1,0,1)(0,1,1,1,0,1,0,1)(1,1,0,0,1,1,0,1)(0,0,1,0,0,0,0,1)(0,1,1,1,1,0,0,1)(1,1,0,1,0,0,0,1)(0,0,1,0,0,1,0,1)(0,1,1,1,1,1,0,1)(1,1,0,1,0,1,0,1)(0,0,1,0,1,0,0,1)(1,0,0,0,0,0,1,0)(1,1,0,1,1,0,0,1)(0,0,1,0,1,1,0,1)(1,0,0,0,0,1,0,1)(1,1,0,1,1,1,0,1)(0,0,1,1,0,0,0,1)(1,0,0,0,1,0,0,1)(1,1,1,0,0,0,0,1)(0,0,1,1,0,1,0,1)(1,0,0,0,1,1,0,1)(1,1,1,0,0,1,0,1)(0,0,1,1,1,0,0,1)(1,0,0,1,0,0,0,1)(1,1,1,0,1,0,0,1)(0,0,1,1,1,1,0,1)(1,0,0,1,0,1,0,1)(1,1,1,0,1,1,0,1)(0,1,0,0,0,0,1,0)(1,0,0,1,1,0,0,1)(1,1,1,1,0,0,0,1)(0,1,0,0,0,1,0,1)(1,0,0,1,1,1,0,1)(1,1,1,1,0,1,0,1)(0,1,0,0,1,0,0,1)(1,0,1,0,0,0,0,1)(1,1,1,1,1,0,0,1)(0,1,0,0,1,1,0,1)(1,0,1,0,0,1,0,1)(1,1,1,1,1,1,0,1)(0,1,0,1,0,0,0,1)(1,0,1,0,1,0,0,1)(0,1,0,1,0,1,0,1)(1,0,1,0,1,1,0,1)Meanwhile, with respect to Equation (3), we can also find all the difference state values (Δst, Δst+5, Δst+4, Δst+7, Δst+9, Δlt+19, c). It should be noted that in Equation (3) there is a constant at at each round. To simplify constraints of the MILP, we model two cases corresponding to the values of at.Whenat=1, Equation (3) contains five Boolean variables st, st+5, st+4, st+7, and st+9 so that the difference state (Δst, Δst+5, Δst+4, Δst+7, Δst+9) can take on one of 25=32 different values deriving the 32 values of the 7-dimensional vector Δst,Δst+5,Δst+4,Δst+7,Δst+9,Δlt+19,c shown in Table 4.Table 4
32 vectorsΔst,Δst+5,Δst+4,Δst+7,Δst+9,Δlt+19,c.
(0,0,0,0,0,0,0)(0,1,0,1,1,0,1)(1,0,1,1,0,0,1)(0,0,0,0,1,1,0)(0,1,1,0,0,0,1)(1,0,1,1,1,0,1)(0,0,0,1,0,0,1)(0,1,1,0,1,0,1)(1,1,0,0,0,0,0)(0,0,0,1,1,0,1)(0,1,1,1,0,0,1)(1,1,0,0,1,1,0)(0,0,1,0,0,0,1)(0,1,1,1,1,0,1)(1,1,0,1,0,0,1)(0,0,1,0,1,0,1)(1,0,0,0,0,1,0)(1,1,0,1,1,0,1)(0,0,1,1,0,0,1)(1,0,0,0,1,0,0)(1,1,1,0,0,0,1)(0,0,1,1,1,0,1)(1,0,0,1,0,0,1)(1,1,1,0,1,0,1)(0,1,0,0,0,1,0)(1,0,0,1,1,0,1)(1,1,1,1,0,0,1)(0,1,0,0,1,0,0)(1,0,1,0,0,0,1)(1,1,1,1,1,0,1)(0,1,0,1,0,0,1)(1,0,1,0,1,0,1)Whenat=0, Equation (3) contains four Boolean variables st, st+5, st+4, and st+7 so that the difference state (Δst, Δst+5, Δst+4, Δst+7) can take on one of 24=16 different values that lead to the 16 values of the 6-dimensional vector (Δst, Δst+5, Δst+4, Δst+7, Δlt+19, c) shown in Table 5.Table 5
16 vectorsΔst,Δst+5,Δst+4,Δst+7,Δlt+19,c.
(0,0,0,0,0,0)(0,1,1,0,0,1)(1,1,0,0,0,0)(0,0,0,1,0,1)(0,1,1,1,0,1)(1,1,0,1,0,1)(0,0,1,0,0,1)(1,0,0,0,1,0)(1,1,1,0,0,1)(0,0,1,1,0,1)(1,0,0,1,0,1)(1,1,1,1,0,1)(0,1,0,0,1,0)(1,0,1,0,0,1)(0,1,0,1,0,1)(1,0,1,1,0,1)(2) Modeling the Vector Sets Using Linear Inequalities. Via SageMath at http://www.sagemath.org, we obtain 19 linear inequalities that accurately describe the set of the 64 8-dimensional vectors in Table 3. This set of linear inequalities characterizes the difference propagation of Equation (2) under the control of conditions. Ten inequalities are remaining after a simple reduction. L1 shows the ten inequalities.
(4)L1=−Δst+13−c+1≥0,−Δlt+6+c≥0,−Δlt−Δlt+11−Δst+13+2≥0,−Δlt+8+c≥0,−Δlt+10+c≥0,−Δlt+15+c≥0,Δlt+Δlt+11−Δst+13≥0,−Δlt+Δlt+11+Δst+13+c≥0,Δlt−Δlt+11+Δst+13+c≥0,Δlt+6+Δlt+8+Δlt+10+Δlt+15−c≥0.Using the same method, we obtain two sets of linear inequalitiesL2 and L3 that accurately describe the 32 7-dimensional vectors given in Table 4 and the 16 6-dimensional vectors given in Table 5. The two sets are shown below:
(5)L2=−Δlt+19−c+1≥0,−Δst+7+c≥0,−Δst+4+c≥0,Δst+4+Δst+7−c≥0,Δst−Δst+5−Δst+9−Δlt+19+2≥0,−Δst+Δst+5−Δst+9−Δlt+19+2≥0,−Δst−Δst+5+Δst+9−Δlt+19+2≥0,Δst+Δst+5+Δst+9−Δlt+19≥0,−Δst−Δst+5−Δst+9+Δlt+19+c+2≥0,Δst+Δst+5−Δst+9+Δlt+19+c≥0,Δst−Δst+5+Δst+9+Δlt+19+c≥0,−Δst+Δst+5+Δst+9+Δlt+19+c≥0,L3=−Δlt+19−c+1≥0,−Δst+4+c≥0,−Δst+7+c≥0,Δst+4+Δst+7−c≥0,Δst−Δst+5+Δlt+19+c≥0,−Δst+Δst+5+Δlt+19+c≥0,Δst+Δst+5−Δlt+19≥0,−Δst−Δst+5−Δlt+19+2≥0.(3) Formulating the MILP Model to Determine an Initial Difference and Minimum Conditions. With these linear inequalities, we can obtain the relationships among the differences of bits that generate the update bit, the flag of adding a condition and the difference of the update bit in one round. We then expand the linear inequalities to n rounds, where n is a selected number, to obtain constraints of MILP. The objective function to be minimized is ∑i=0nci. The constraint of the initial difference is ∑i=031Δxi≥1. In our work, the MILP problem is solved by Cplex. With this solution, we can obtain both an initial difference and minimum conditions.There are too many plaintext bits and key bits in the conditions applied in the later rounds, so we prefer applying the conditions in earlier rounds rather than all of them. No more conditions have been applied since a particular round, which leads to uncontrollable difference propagation in subsequent rounds. After several rounds, the probability of the difference in the update bit would always be1/2. In Section 3.2, we propose a method to evaluate the update bit difference probability, which helps us find the bit whose difference probability deviates significantly from 1/2 and has the largest number of rounds.


## 3.2. Detecting the Bias of the Difference

In [9, 11], a bias was detected by experimentally observing certain nonrandomness, and we now present a method for automatically detecting the bias by programming. The method produces a formula for calculating the probability of the update bit difference, enabling us to find the bit whose probability of the difference has a bias from 1/2. The greater the bias, the higher probability of a successful attack.The properties below show that we can evaluate the probability of difference in the update bit, given all the probabilities of difference in the bits that generate the update bit. When conditions cease being applied, we get the probability of difference in each bit of two NLFSRs at that round. Using these probabilities, we can calculate the update bit difference probability in each subsequent round.Property 1.
Leta,b be two independent random Boolean variables, and then, the probability PΔa⊕b=1=PΔa=1+PΔb=1−2PΔa=1PΔb=1.With Property1, if the probabilities of the differences in a and b were known, we could evaluate the probability of the difference in a⊕b. It can be extended to the sum of four Boolean variables.Property 2.
Letx,y,z,w be independent random Boolean variables, and then, the probability
(6)PΔx⊕y⊕z⊕w=1=12−121−2PΔx=11−2PΔy=11−2PΔz=11−2PΔw=1.In the following, we consider the difference probability of two Boolean variables’ products. Property3 shows us how to evaluate the probability.Property 3.
Leta,b be the same as defined in Property 1, and then, the probability
(7)PΔa·b=1=PΔa=1+PΔb=1−PΔa=1PΔb=1·12.In Equations (2) and (3), there is no difference in the key and const, so k2t+1, k2t, and at do not influence the probability of the difference.Accordingly, we can derive the results as follows.From Equation (2), we can obtain the formula to calculate the probability of Δst+13=1:
(8)PΔst+13=1=PΔlt⊕lt+11⊕lt+6lt+8⊕lt+10lt+15=1=12−12·1−2PΔlt=11−2PΔlt+11=1=1−2PΔlt+6lt+8=11−2PΔlt+10lt+15=1,where
(9)PΔlt+6lt+8=1=PΔlt+6=1+PΔlt+8=1−PΔlt+6=1PΔlt+8=1·12,PΔlt+10lt+15=1=PΔlt+10=1+PΔlt+15=1−PΔlt+10=1PΔlt+15=1·12.From Equation (3), we can obtain the formula to calculate the probability of Δlt+19=1:
(10)PΔlt+19=1=PΔst⊕st+5⊕st+4st+7⊕st+9at=1=12−12·1−2PΔst=11−2PΔst+5=11−2PΔst+4st+7=11−2PΔst+9at=1,where
(11)PΔst+4st+7=1=PΔst+4=1+PΔst+7=1−PΔst+4=1PΔst+7=1·12,PΔst+9at=1=atPΔst+9=1.Using the two formulas, we can calculate the probabilities of the differences in the update bits in Algorithm2 at every subsequent round after the conditions stop being applied. After a certain round, the probability forever becomes 1/2. Before that, we can find the biased bit corresponding to the longest conditional differential characteristic.Algorithm 2. Calculating the probabilities of the differences in the update bits from roundt to round u.
Input: PΔst=1,PΔst+1=1,⋯PΔst+12=1: the set of probabilities of the difference for each bit of the 13-bit NLFSR at round t; PΔlt=1,PΔlt+1=1,⋯PΔlt+18=1: the set of probabilities of the difference for each bit of the 19-bit NLFSR at round t.Output: A: the set of the probabilities of the differences for update bits from round t to round u, there are two update bits at each round.S≔PΔst=1,PΔst+1=1,⋯PΔst+12=1;L≔PΔlt=1,PΔlt+2=1,⋯PΔst+18=1;A≔∅;fori∈t,t+1,⋯,udoPΔsi+13=1≔ the probability calculated from L according to formulas (8) and (9);PΔli+19=1≔ the probability calculated from S according to formulas (10) and (11);S≔PΔsi+1=1,PΔsi+2=1,⋯PΔsi+13=1;L≔PΔli+1=1,PΔli+2=1,⋯PΔli+19=1;A≔A∪PΔs¯i+13=1,PΔl¯i+19=1endreturnA.


## 4. Application to KATAN32

We have applied the MILP method to KATAN32 for different rounds to obtain different differential characteristics and minimum conditions. We choose two results with fewer conditions in the previous rounds.For 64-round KATAN32 (we have modeled 64-round KATAN32 together), the minimum number of conditions is 27. However, we cannot apply all these conditions since there are too many key bits and plaintext bits involved in them, resulting in attack failure. We only choose 11 conditions from the first 23 rounds to impose in this analysis. Since other conditions from round 24 have not been applied, difference propagation becomes out of control, with more and more probabilities of differences in update bits tending to be 1/2. We calculate the probabilities ofΔst+13=1 and Δlt+19=1 after round 23, and we find that finally the probability of Δst+13=1 would always be 1/2 starting from s79 and the probability of Δlt+19=1 would always be 1/2 starting from l82. Before l82, we detect an obvious bias in Δl79. l79 is generated at round 60 and is the rightmost bit of the 19-bit NLFSR at round 79. Utilizing the bias of Δl79, we can recover 10 equivalent key bits of the 79-round KATAN32.For 77-round KATAN32, the minimum number of conditions is 34. We only impose seven conditions from the first 16 rounds and recover four equivalent key bits of the 81-round KATAN32 with a bias inΔl81. l81 is generated at round 62 and is the rightmost bit of the 19-bit NLFSR at round 81.In this section, we present the details of our analysis and attacks on these two results.


### 4.1. Key-Recovery Attack on 79-Round KATAN32

The differential characteristic of 64-round KATAN32 has the initial difference of weight six at the positions0,11,21,26,30,31 of the plaintext block, ΔX=0xc4200801. We only apply 11 conditions in the first 23 rounds.At round 1, we haveΔs14=x9,Δl20=x23, and we impose conditions x9=0,x23=0. At round 3, we have Δs16=x5,Δl22=x24, and we impose conditions x5=0,x24=0. At round 6, we have Δl25=s13, and we impose the condition
(12)s13=x18⊕x7⊕x12x10⊕x8x3⊕k1=0.At round 8, we haveΔs21=l23, and we impose the condition
(13)l23=x27⊕x22⊕k8=0.At round 10, we haveΔs23=x2, and we impose the condition x2=0. At round 12, we have Δs25=l20, and we impose the condition
(14)l20=x30⊕x25⊕x21⊕k2=0.At round 14, we haveΔs27=l24, and we impose the condition
(15)l24=x26⊕x21⊕x22x19⊕x17⊕x6⊕k3⊕k10=0.At round 19, we haveΔs32=l34. If we try to impose the condition l34=0, it has too many variables, which would make the attack unavailable because of the significantly high computing complexity. So we skip this condition, and assume PΔs32=1=1/2. At round 21, we have Δs34=l27, and we impose the condition
(16)l27=x19x16⊕x10x8⊕x6x1⊕k5⊕k16=0.At round 23, we haveΔs36=l31, and we impose the condition
(17)l31=x19⊕x14⊕x3⊕x8x6⊕x4x31⊕x26⊕x22⊕k0⊕x15⊕x4⊕k7x12⊕x1⊕x6x4⊕k13⊕k9⊕k24=0.The difference propagation and the conditions applied are presented in Table6.Table 6
Differential characteristic and conditions forΔX=0xc4200801.
RoundDifference stateConditions01100010000100 0000000100000000001110001000010000000001000000000010x9=0,x23=0200010000100000000010000000000100300100001000000000100000000001000x5=0,x24=0401000010000000001000000000010000510000100000000010000000000100000600001000000000100000000001000000Condition (12)700010000000001000000000010000000800100000000000000000000100000000Condition (13)9010000000000000000000010000000001010000000000000000000010000000000x2=011000000000000000000001000000000011200000000000000000001000000000010Condition (14)13000000000000000000100000000001001400000000000000000100000000001000Condition (15)1500000000000000001000000000010000160000000000000001000000000010000017000000000000001000000000010000001800000000000001000000000010000000190000000000000000000000010000000020000000000000∗00000000010000000002100000000000∗00000000010000000000Condition (16)220000000000∗00000000010000000000023000000000∗0000000001000000000000Condition (17)2400000000∗00000000010000000000000The bold bits denote the update bits. The bold italic bits denote the bits that generate the update bits. The differential probability of the bit∗ is 1/2.After imposing these conditions, we obtain the probability of difference in each bit at round 24 as follows: (0,0,0,0,0,0,0,0, 1/2,0,0,0,0,0,0,0,0,0,1, 0, 0, 0, 0, 0, 0, 0, 0, 0,0,0,0,0).According to Algorithm2, we can compute the bias of the difference in the update bit for each round after round 24 and find that starting from l82 the probability of Δlt+19=1 would always be 1/2. Among the bits whose positions are very close to l82, l79 has the maximum biased difference, shown as follows:
(18)PΔl79=1∣alltheconditionssatisfied≈0.5−0.00001.We confirmed the strongly biased difference in bitl79 experimentally. Let us consider the conditions applied. There are ten equivalent key bits k0, k1, k2, k3⊕k10, k5, k7, k8, k9⊕k24, k13, k16 and 21 bits of plaintext x1, x3, x4, x6, x7, x8, x10, x12, x14, x15, x16, x17, x18, x19, x21, x22, x25, x26, x27, x30, x31 involved in the conditions. We choose 28 key in which bits k0,k1,k2,k3,k5,k7,k8,k9 are free, and the remaining bits are fixed. For each key, we enumerate 221 plaintexts of which the 21 bits involved in the conditions are free and other bits are zero. We then can use conditions (12)–(17) to filter the 221 plaintexts, and if the plaintext satisfied the conditions, we calculate Δl79 with the initial difference ΔX=0xc4200801 and count PΔl79=1 at last. The complexity of each experiment is less than 221+1=222 evaluations of the 60-round KATAN32 encryption because not every plaintext can pass the filtering. The experimental results verify the strongly biased difference in bit l79. All the results of these 256 experiments are that PΔl79=1 is lower than 0.5−0.00001.Furthermore, we can mount a key-recovery attack. Looking at conditions (12)–(17), we consider k0, k1, k2, k3⊕k10, k5, k7, k8, k9⊕k24, k13, k16, the 10 equivalent key bits, as ten variables. In a key-recovery attack, since the key is unknown to the attacker, we enumerate 210 guesses of these ten equivalent key bits. For each guess, similar to the verification, we use conditions (12)–(17) to filter 221 plaintexts of which the 21 bits involved in conditions (12)–(17) are free and other 11 bits are fixed to zero, then calculate Δl79 with initial difference ΔX=0xc4200801, and finally count PΔl79=1.When the guess is correct, plaintexts are filtered by the conditions corresponding to the correct guessed equivalent key bits, and then,PΔl79=1 shows the obvious bias. In the 1024 statistical results from guesses of 10 equivalent key bits, the maximum bias in the results corresponds to the ten equivalent key bits’ correct values. This allows us to recover k0, k1, k2, k3⊕k10, k5, k7, k8, k9⊕k24, k13, k16, with experimental complexity less than 210+21+1=232 evaluations of the 60-round KATAN32 encryption. We randomly choose four 80-bit keys and mount four key-recovery attack experiments and each time the ten equivalent key bits can be recovered correctly, as shown by the results listed in Table 7.Table 7
Four key-recovery attack experiments on 79-round KATAN32.
No.80-bit keyEquivalent key bits with the maximum biask0k1k2k3⊕k10k5k7k8k9⊕k24k13k1610x68b1644ead28b1644e8e011100100020xf8b164cead28b1644e8e111000110030x38116486a99ab3664d9e001100010040x2d11e4062b92bb2e4d9f0010110001


### 4.2. Key-Recovery Attack on 81-Round KATAN32

The initial difference of the differential characteristic of 77-round KATAN32 weights three at position 7, 18, and 28 of the plaintext block,ΔX=0x10040080.At round 1, we haveΔs14=x2 and then impose the condition x2=0 to prevent difference propagation.Similarly, at round3,5,7, we have Δs16=x9,Δs18=x5,Δs20=x1, so we require bits x9,x5,x1 to be zero.At round 12, we haveΔs25=l27, and we impose the condition
(19)l27=x23⊕x18⊕x7⊕x12x10⊕x8x3⊕x19x16⊕x10x8⊕k5⊕k16⊕k1=0.At round 14, we haveΔs27=l20 and we impose the condition
(20)l20=x30⊕x25⊕x26x23⊕x21⊕k2=0.At round 16, we haveΔs29=l24 and we impose the condition
(21)l24=x26⊕x21⊕x22x19⊕x17⊕x6⊕k3⊕k10=0.The differences in propagation and conditions applied are presented in Table8. After imposing these conditions, we obtain the probability of difference in each bit at round 17 as follows: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0.Table 8
Differential characteristic and conditions forΔX=0x10040080.
RoundDifference stateConditions00001000000000 1000000000010000000100100000000000000000000100000000x2=0201000000000000000000001000000000310000000000000000000010000000000x9=0400000000000000000000100000000001500000000000000000001000000000010x5=0600000000000000000010000000000100700000000000000000100000000001000x1=0800000000000000001000000000010000900000000000000010000000000100000100000000000000010000000000100000011000000000000010000000000100000001200000000000000000000000100000000Condition (19)1300000000000000000000001000000000140000000000000 0000000010000000000Condition (20)15000000000000000000001000000000001600000000000000000001000000000000Condition (21)1700000000000000000010000000000000The bold bits denote the update bits. The bold italic bits denote the bits that generate the update bits.We compute the bias of the update bit of each round from the 17th round and find that starting froml84 the probability of Δlt+19=1 would always be 1/2. Among the bits whose positions are very close to l84, l81 has the maximum biased difference, shown as follows:
(22)PΔl81=1∣alltheconditionssatisfied≈0.5+0.000226.We experimentally verified the strongly biased difference in bitl81. There are four equivalent key bits k5,k16⊕k1,k2,k3⊕k10 and 16 bits of plaintext x30, x26, x25, x23, x22, x21, x19, x18, x17, x16, x12, x10, x8, x7, x6, x3 in conditions (19)–(21). We choose 24 keys of which k1,k2,k3,k5 are free and the other bits are fixed. For each key, we enumerate 216 plaintexts of which the 16 bits involved in conditions are free and other bits are fixed to 0. We then use conditions (19)–(21) to filter the 216 plaintexts, and if a plaintext satisfies the conditions, we calculate Δl81 with the initial difference Δx=0x10040080 and calculatePΔl81=1. The complexity of each experiment is less than 216+1=217 evaluations of the 62-round KATAN32 encryption. In all the results of these 16 experiments PΔl81=1 is greater than 0.5+0.000226.We now will describe mounting the key-recovery attack. Looking at conditions (19)–(21), we consider k1⊕k16,k2,k3⊕k10,k5 these four equivalent key bits as four Boolean variables. There are 16 bits of plaintext involved in conditions (19)–(21). To enlarge the space of plaintexts after filtering, we choose other three bits of plaintext not included in any condition as free bits in addition to the 16 bits of plaintext involved in conditions (19)–(21). For each of the 24 guesses of these four variables, we use conditions (19)–(21) to filter the 219 plaintexts enumerated by the 19 bits we just choose with the remaining 13 bits fixed to 0. We then calculate Δl81 with initial difference Δx=0x10040080 and calculate PΔl81=1. In the 16 statistical results obtained from 16 guesses of four equivalent key bits, the maximum bias in the results corresponds to the correct value of the four equivalent key bits, allowing us to recover k1⊕k16,k2,k3⊕k10,k5. The complexity of the experiment is less than 24+19+1=224 evaluations of the 62-round KATAN32 encryption. We choose five 80-bit keys randomly and mount five key-recovery attack experiments, and each time the four equivalent key bits can be correctly recovered. The results of these five key-recovery attack experiments are listed in Table 9.Table 9
Five key-recovery attack experiments on 81-round KATAN32.
No.80-bit keyEquivalent key bits with the maximum biask1⊕k16k2k3⊕k10k510x68b1644ead28b1644e8e111020x48b1644ead28b1644e8e101030xcda964ceb98cb7644e8e101140xc9a1448cb886b7644f86101050x99a1448cb88680644f860000


## 4.1. Key-Recovery Attack on 79-Round KATAN32

The differential characteristic of 64-round KATAN32 has the initial difference of weight six at the positions0,11,21,26,30,31 of the plaintext block, ΔX=0xc4200801. We only apply 11 conditions in the first 23 rounds.At round 1, we haveΔs14=x9,Δl20=x23, and we impose conditions x9=0,x23=0. At round 3, we have Δs16=x5,Δl22=x24, and we impose conditions x5=0,x24=0. At round 6, we have Δl25=s13, and we impose the condition
(12)s13=x18⊕x7⊕x12x10⊕x8x3⊕k1=0.At round 8, we haveΔs21=l23, and we impose the condition
(13)l23=x27⊕x22⊕k8=0.At round 10, we haveΔs23=x2, and we impose the condition x2=0. At round 12, we have Δs25=l20, and we impose the condition
(14)l20=x30⊕x25⊕x21⊕k2=0.At round 14, we haveΔs27=l24, and we impose the condition
(15)l24=x26⊕x21⊕x22x19⊕x17⊕x6⊕k3⊕k10=0.At round 19, we haveΔs32=l34. If we try to impose the condition l34=0, it has too many variables, which would make the attack unavailable because of the significantly high computing complexity. So we skip this condition, and assume PΔs32=1=1/2. At round 21, we have Δs34=l27, and we impose the condition
(16)l27=x19x16⊕x10x8⊕x6x1⊕k5⊕k16=0.At round 23, we haveΔs36=l31, and we impose the condition
(17)l31=x19⊕x14⊕x3⊕x8x6⊕x4x31⊕x26⊕x22⊕k0⊕x15⊕x4⊕k7x12⊕x1⊕x6x4⊕k13⊕k9⊕k24=0.The difference propagation and the conditions applied are presented in Table6.Table 6
Differential characteristic and conditions forΔX=0xc4200801.
RoundDifference stateConditions01100010000100 0000000100000000001110001000010000000001000000000010x9=0,x23=0200010000100000000010000000000100300100001000000000100000000001000x5=0,x24=0401000010000000001000000000010000510000100000000010000000000100000600001000000000100000000001000000Condition (12)700010000000001000000000010000000800100000000000000000000100000000Condition (13)9010000000000000000000010000000001010000000000000000000010000000000x2=011000000000000000000001000000000011200000000000000000001000000000010Condition (14)13000000000000000000100000000001001400000000000000000100000000001000Condition (15)1500000000000000001000000000010000160000000000000001000000000010000017000000000000001000000000010000001800000000000001000000000010000000190000000000000000000000010000000020000000000000∗00000000010000000002100000000000∗00000000010000000000Condition (16)220000000000∗00000000010000000000023000000000∗0000000001000000000000Condition (17)2400000000∗00000000010000000000000The bold bits denote the update bits. The bold italic bits denote the bits that generate the update bits. The differential probability of the bit∗ is 1/2.After imposing these conditions, we obtain the probability of difference in each bit at round 24 as follows: (0,0,0,0,0,0,0,0, 1/2,0,0,0,0,0,0,0,0,0,1, 0, 0, 0, 0, 0, 0, 0, 0, 0,0,0,0,0).According to Algorithm2, we can compute the bias of the difference in the update bit for each round after round 24 and find that starting from l82 the probability of Δlt+19=1 would always be 1/2. Among the bits whose positions are very close to l82, l79 has the maximum biased difference, shown as follows:
(18)PΔl79=1∣alltheconditionssatisfied≈0.5−0.00001.We confirmed the strongly biased difference in bitl79 experimentally. Let us consider the conditions applied. There are ten equivalent key bits k0, k1, k2, k3⊕k10, k5, k7, k8, k9⊕k24, k13, k16 and 21 bits of plaintext x1, x3, x4, x6, x7, x8, x10, x12, x14, x15, x16, x17, x18, x19, x21, x22, x25, x26, x27, x30, x31 involved in the conditions. We choose 28 key in which bits k0,k1,k2,k3,k5,k7,k8,k9 are free, and the remaining bits are fixed. For each key, we enumerate 221 plaintexts of which the 21 bits involved in the conditions are free and other bits are zero. We then can use conditions (12)–(17) to filter the 221 plaintexts, and if the plaintext satisfied the conditions, we calculate Δl79 with the initial difference ΔX=0xc4200801 and count PΔl79=1 at last. The complexity of each experiment is less than 221+1=222 evaluations of the 60-round KATAN32 encryption because not every plaintext can pass the filtering. The experimental results verify the strongly biased difference in bit l79. All the results of these 256 experiments are that PΔl79=1 is lower than 0.5−0.00001.Furthermore, we can mount a key-recovery attack. Looking at conditions (12)–(17), we consider k0, k1, k2, k3⊕k10, k5, k7, k8, k9⊕k24, k13, k16, the 10 equivalent key bits, as ten variables. In a key-recovery attack, since the key is unknown to the attacker, we enumerate 210 guesses of these ten equivalent key bits. For each guess, similar to the verification, we use conditions (12)–(17) to filter 221 plaintexts of which the 21 bits involved in conditions (12)–(17) are free and other 11 bits are fixed to zero, then calculate Δl79 with initial difference ΔX=0xc4200801, and finally count PΔl79=1.When the guess is correct, plaintexts are filtered by the conditions corresponding to the correct guessed equivalent key bits, and then,PΔl79=1 shows the obvious bias. In the 1024 statistical results from guesses of 10 equivalent key bits, the maximum bias in the results corresponds to the ten equivalent key bits’ correct values. This allows us to recover k0, k1, k2, k3⊕k10, k5, k7, k8, k9⊕k24, k13, k16, with experimental complexity less than 210+21+1=232 evaluations of the 60-round KATAN32 encryption. We randomly choose four 80-bit keys and mount four key-recovery attack experiments and each time the ten equivalent key bits can be recovered correctly, as shown by the results listed in Table 7.Table 7
Four key-recovery attack experiments on 79-round KATAN32.
No.80-bit keyEquivalent key bits with the maximum biask0k1k2k3⊕k10k5k7k8k9⊕k24k13k1610x68b1644ead28b1644e8e011100100020xf8b164cead28b1644e8e111000110030x38116486a99ab3664d9e001100010040x2d11e4062b92bb2e4d9f0010110001


## 4.2. Key-Recovery Attack on 81-Round KATAN32

The initial difference of the differential characteristic of 77-round KATAN32 weights three at position 7, 18, and 28 of the plaintext block,ΔX=0x10040080.At round 1, we haveΔs14=x2 and then impose the condition x2=0 to prevent difference propagation.Similarly, at round3,5,7, we have Δs16=x9,Δs18=x5,Δs20=x1, so we require bits x9,x5,x1 to be zero.At round 12, we haveΔs25=l27, and we impose the condition
(19)l27=x23⊕x18⊕x7⊕x12x10⊕x8x3⊕x19x16⊕x10x8⊕k5⊕k16⊕k1=0.At round 14, we haveΔs27=l20 and we impose the condition
(20)l20=x30⊕x25⊕x26x23⊕x21⊕k2=0.At round 16, we haveΔs29=l24 and we impose the condition
(21)l24=x26⊕x21⊕x22x19⊕x17⊕x6⊕k3⊕k10=0.The differences in propagation and conditions applied are presented in Table8. After imposing these conditions, we obtain the probability of difference in each bit at round 17 as follows: 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0.Table 8
Differential characteristic and conditions forΔX=0x10040080.
RoundDifference stateConditions00001000000000 1000000000010000000100100000000000000000000100000000x2=0201000000000000000000001000000000310000000000000000000010000000000x9=0400000000000000000000100000000001500000000000000000001000000000010x5=0600000000000000000010000000000100700000000000000000100000000001000x1=0800000000000000001000000000010000900000000000000010000000000100000100000000000000010000000000100000011000000000000010000000000100000001200000000000000000000000100000000Condition (19)1300000000000000000000001000000000140000000000000 0000000010000000000Condition (20)15000000000000000000001000000000001600000000000000000001000000000000Condition (21)1700000000000000000010000000000000The bold bits denote the update bits. The bold italic bits denote the bits that generate the update bits.We compute the bias of the update bit of each round from the 17th round and find that starting froml84 the probability of Δlt+19=1 would always be 1/2. Among the bits whose positions are very close to l84, l81 has the maximum biased difference, shown as follows:
(22)PΔl81=1∣alltheconditionssatisfied≈0.5+0.000226.We experimentally verified the strongly biased difference in bitl81. There are four equivalent key bits k5,k16⊕k1,k2,k3⊕k10 and 16 bits of plaintext x30, x26, x25, x23, x22, x21, x19, x18, x17, x16, x12, x10, x8, x7, x6, x3 in conditions (19)–(21). We choose 24 keys of which k1,k2,k3,k5 are free and the other bits are fixed. For each key, we enumerate 216 plaintexts of which the 16 bits involved in conditions are free and other bits are fixed to 0. We then use conditions (19)–(21) to filter the 216 plaintexts, and if a plaintext satisfies the conditions, we calculate Δl81 with the initial difference Δx=0x10040080 and calculatePΔl81=1. The complexity of each experiment is less than 216+1=217 evaluations of the 62-round KATAN32 encryption. In all the results of these 16 experiments PΔl81=1 is greater than 0.5+0.000226.We now will describe mounting the key-recovery attack. Looking at conditions (19)–(21), we consider k1⊕k16,k2,k3⊕k10,k5 these four equivalent key bits as four Boolean variables. There are 16 bits of plaintext involved in conditions (19)–(21). To enlarge the space of plaintexts after filtering, we choose other three bits of plaintext not included in any condition as free bits in addition to the 16 bits of plaintext involved in conditions (19)–(21). For each of the 24 guesses of these four variables, we use conditions (19)–(21) to filter the 219 plaintexts enumerated by the 19 bits we just choose with the remaining 13 bits fixed to 0. We then calculate Δl81 with initial difference Δx=0x10040080 and calculate PΔl81=1. In the 16 statistical results obtained from 16 guesses of four equivalent key bits, the maximum bias in the results corresponds to the correct value of the four equivalent key bits, allowing us to recover k1⊕k16,k2,k3⊕k10,k5. The complexity of the experiment is less than 24+19+1=224 evaluations of the 62-round KATAN32 encryption. We choose five 80-bit keys randomly and mount five key-recovery attack experiments, and each time the four equivalent key bits can be correctly recovered. The results of these five key-recovery attack experiments are listed in Table 9.Table 9
Five key-recovery attack experiments on 81-round KATAN32.
No.80-bit keyEquivalent key bits with the maximum biask1⊕k16k2k3⊕k10k510x68b1644ead28b1644e8e111020x48b1644ead28b1644e8e101030xcda964ceb98cb7644e8e101140xc9a1448cb886b7644f86101050x99a1448cb88680644f860000


## 5. Extension with the Standard Differential Attack

Combined with the standard differential attack, the conditional differential attack on 81-round KATAN32 can be extended to 97-round, 98-round, and 99-round key-recovery attacks.


### 5.1. Key-Recovery Attack on 97-Round KATAN32

Inspired by the technique representing the dependence of the intermediate state on the output by an algebraic representation in [34], we give the algebraic representation of the intermediate state using the ciphertext and round keys.Using Equations (2) and (3), we can get the expression of lt,st in decryption direction:
(23)lt=st+13⊕lt+11⊕lt+6lt+8⊕lt+10lt+15⊕k2t+1,(24)st=lt+19⊕st+5⊕st+4st+7⊕st+9at⊕k2t.Suppose the output bits of 97-round KATAN32 corresponding to plaintextX are S97=s97,s98,⋯,s110 and L97=l97,l98,⋯,l115, and the output bits of 97-round KATAN32 corresponding to plaintext X+ΔX are S′97=s′97,s′98,⋯,s′110 and L′97=l′97,l′98,⋯,l′115. For decryption direction, Δl81 can be expressed by round keys and the ciphertext of 97-round KATAN32 by using Equations (23) and (24) iteratively.
(25)Δl81=l113⊕s99⊕s98s101⊕s105⊕l103⊕l98l100⊕l102l107⊕s100⊕l98⊕s106⊕l104⊕l99l101⊕l103l108⊕k187s108⊕l106⊕l101l103⊕l105l110⊕k191⊕l97l102⊕k175s102⊕l100⊕s108⊕l106⊕l101l103⊕l105l110⊕k191l97⊕l99l104⊕k179⊕s104⊕l102⊕l97l99⊕l101l106⊕k183s109⊕l107⊕l102l104⊕l106l111⊕k193⊕l113′⊕s99′⊕s98′s101′⊕s105′⊕l103′⊕l98′l100′⊕l102′l107′⊕s100′⊕l98′⊕s106′⊕l104′⊕l99′l101′⊕l103′l108′⊕k187s108′⊕l106′⊕l101′l103′⊕l105′l110′⊕k191⊕l97′l102′⊕k175s102′⊕l100′⊕s108′⊕l106′⊕l101′l103′⊕l105′l110′⊕k191l97′⊕l99′l104′⊕k179⊕s104′⊕l102′⊕l97′l99′⊕l101′l106′⊕k183s109′⊕l107′⊕l102′l104′⊕l106′l111′⊕k193.According to this expression, one can calculateΔl81 by using the ciphertexts of 97-round KATAN32 and six equivalent key bits k175,k179,k183,k187,k191,k193. We extend the attack described in Section 4.2 to 97-round. Plaintexts being filtered by the conditions are encrypted to ciphertexts by 97-round KATAN32. Δl81 can be computed from ciphertexts of 97-round KATAN32 and the guess of these six equivalent key bits k175,k179,k183,k187,k191,k193. Given every guess of ten equivalent key bits (k1⊕k16,k2,k3⊕k10,k5,k175,k179,k183,k187,k191,k193), we can calculate and count Δl81 with respect to a set of filtered plaintexts. If the guess is right, PΔl81=1 shows an obvious bias. The computational cost of the experiment is less than 224+6 encryptions of 97-round KATAN32. We mount five key-recovery attack experiments with the same key as the experiments in Section 4.2, and each time the ten equivalent key bits can be correctly recovered.


### 5.2. Key-Recovery Attack on 98-Round KATAN32

Suppose the output bits of 98-round KATAN32 corresponding to plaintextX are S98=s98,s99,⋯,s111 and L98=l98,l99,⋯,l116, and the output bits corresponding to plaintext X+ΔX are S′98=s′98,s′99,⋯,s′111 and L′98=l′98,l′99,⋯,l′116. For decryption direction, Δl81 can be expressed using round keys and the ciphertext of 98-round KATAN32.
(26)Δl81=l113⊕s99⊕s98s101⊕s105⊕l103⊕l98l100⊕l102l107⊕s100⊕l98⊕s106⊕l104⊕l99l101⊕l103l108⊕k187s108⊕l106⊕l101l103⊕l105l110⊕k191⊕s110⊕l108⊕l103l105⊕l107l112⊕k195l102⊕k175s102⊕l100⊕s108⊕l106⊕l101l103⊕l105l110⊕k191s110⊕l108⊕l103l105⊕l107l112⊕k195⊕l99l104⊕k179⊕s104⊕l102⊕s110⊕l108⊕l103l105⊕l107l112⊕k195l99⊕l101l106⊕k183s109⊕l107⊕l102l104⊕l106l111⊕k193⊕l113′⊕s99′⊕s98′s101′⊕s105′⊕l103′⊕l98′l100′⊕l102′l107′⊕s100′⊕l98′⊕s106′⊕l104′⊕l99′l101′⊕l103′l108′⊕k187s108′⊕l106′⊕l101′l103′⊕l105′l110′⊕k191⊕s110′⊕l108′⊕l103′l105′⊕l107′l112′⊕k195l102′⊕k175s102′⊕l100′⊕s108′⊕l106′⊕l101′l103′⊕l105′l110′⊕k191s110′⊕l108′⊕l103′l105′⊕l107′l112′⊕k195⊕l99′l104′⊕k179⊕s104′⊕l102′⊕s110′⊕l108′⊕l103′l105′⊕l107′l112′⊕k195l99′⊕l101′l106′⊕k183s109′⊕l107′⊕l102′l104′⊕l106′l111′⊕k193.The expression contains seven equivalent key bitsk175, k179, k183, k187, k191, k193, k195, which makes the computational cost of the key-recovery attack be less than 224+7 times 98-round KATAN32 encryption. In this attack, 11 equivalent key bits k1⊕k16, k2, k3⊕k10, k5, k175, k179, k183, k187, k191, k193, k195 can be correctly recovered. Every experiment requires about 2.4 hours on a 2.5 GHz PC with our implementation.


### 5.3. Key-Recovery Attack on 99-Round KATAN32

Suppose the output bits of 99-round KATAN32 corresponding to plaintextX are S99=s99,s100,⋯,s112 and L99=l99,l100,⋯,l117, and the output bits corresponding to plaintext X+ΔX are S′99=s′99,s′100,⋯,s′112 and L′99=l′99,l′100,⋯,l′117. For decryption direction, Δl81 can be expressed using round keys and the ciphertext of 99-round KATAN32.
(27)Δl81=l113⊕s99⊕l117⊕s103⊕s102s105⊕s107⊕k196s101⊕s105⊕l103⊕s111⊕l109⊕l104l106⊕l108l113⊕k197l100⊕l102l107⊕s100⊕s111⊕l109⊕l104l106⊕l108l113⊕k197⊕s106⊕l104⊕l99l101⊕l103l108⊕k187s108⊕l106⊕l101l103⊕l105l110⊕k191⊕s110⊕l108⊕l103l105⊕l107l112⊕k195l102⊕k175s102⊕l100⊕s108⊕l106⊕l101l103⊕l105l110⊕k191s110⊕l108⊕l103l105⊕l107l112⊕k195⊕l99l104⊕k179⊕s104⊕l102⊕s110⊕l108⊕l103l105⊕l107l112⊕k195l99⊕l101l106⊕k183s109⊕l107⊕l102l104⊕l106l111⊕k193⊕l113′⊕s99′⊕l117′⊕s103′⊕s102′s105′⊕s107′⊕k196s101′⊕s105′⊕l103′⊕s111′⊕l109′⊕l104′l106′⊕l108′l113′⊕k197l100′⊕l102′l107′⊕s100′⊕s111′⊕l109′⊕l104′l106′⊕l108′l113′⊕k197⊕s106′⊕l104′⊕l99′l101′⊕l103′l108′⊕k187s108′⊕l106′⊕l101′l103′⊕l105′l110′⊕k191⊕s110′⊕l108′⊕l103′l105′⊕l107′l112′⊕k195l102′⊕k175s102′⊕l100′⊕s108′⊕l106′⊕l101′l103′⊕l105′l110′⊕k191s110′⊕l108′⊕l103′l105′⊕l107′l112′⊕k195⊕l99′l104′⊕k179⊕s104′⊕l102′⊕s110′⊕l108′⊕l103′l105′⊕l107′l112′⊕k195l99′⊕l101′l106′⊕k183s109′⊕l107′⊕l102′l104′⊕l106′l111′⊕k193.There are nine equivalent key bitsk175, k179, k183, k187, k191, k193, k195, k196, k197. So the computational cost of the key-recovery attack is less than 224+9 times 99-round KATAN32 encryption. In this attack, 13 equivalent key bits k1⊕k16, k2, k3⊕k10, k5, k175, k179, k183, k187, k191, k193, k195, k196, k197 can be correctly recovered. Every experiment requires about 9.64 hours on a 2.5 GHz PC with our implementation.It is thus possible to extend the conditional differential attack on 81-round KATAN32 to 114-round with the computational cost of less than263 times 114-round KATAN32 encryption.


## 5.1. Key-Recovery Attack on 97-Round KATAN32

Inspired by the technique representing the dependence of the intermediate state on the output by an algebraic representation in [34], we give the algebraic representation of the intermediate state using the ciphertext and round keys.Using Equations (2) and (3), we can get the expression of lt,st in decryption direction:
(23)lt=st+13⊕lt+11⊕lt+6lt+8⊕lt+10lt+15⊕k2t+1,(24)st=lt+19⊕st+5⊕st+4st+7⊕st+9at⊕k2t.Suppose the output bits of 97-round KATAN32 corresponding to plaintextX are S97=s97,s98,⋯,s110 and L97=l97,l98,⋯,l115, and the output bits of 97-round KATAN32 corresponding to plaintext X+ΔX are S′97=s′97,s′98,⋯,s′110 and L′97=l′97,l′98,⋯,l′115. For decryption direction, Δl81 can be expressed by round keys and the ciphertext of 97-round KATAN32 by using Equations (23) and (24) iteratively.
(25)Δl81=l113⊕s99⊕s98s101⊕s105⊕l103⊕l98l100⊕l102l107⊕s100⊕l98⊕s106⊕l104⊕l99l101⊕l103l108⊕k187s108⊕l106⊕l101l103⊕l105l110⊕k191⊕l97l102⊕k175s102⊕l100⊕s108⊕l106⊕l101l103⊕l105l110⊕k191l97⊕l99l104⊕k179⊕s104⊕l102⊕l97l99⊕l101l106⊕k183s109⊕l107⊕l102l104⊕l106l111⊕k193⊕l113′⊕s99′⊕s98′s101′⊕s105′⊕l103′⊕l98′l100′⊕l102′l107′⊕s100′⊕l98′⊕s106′⊕l104′⊕l99′l101′⊕l103′l108′⊕k187s108′⊕l106′⊕l101′l103′⊕l105′l110′⊕k191⊕l97′l102′⊕k175s102′⊕l100′⊕s108′⊕l106′⊕l101′l103′⊕l105′l110′⊕k191l97′⊕l99′l104′⊕k179⊕s104′⊕l102′⊕l97′l99′⊕l101′l106′⊕k183s109′⊕l107′⊕l102′l104′⊕l106′l111′⊕k193.According to this expression, one can calculateΔl81 by using the ciphertexts of 97-round KATAN32 and six equivalent key bits k175,k179,k183,k187,k191,k193. We extend the attack described in Section 4.2 to 97-round. Plaintexts being filtered by the conditions are encrypted to ciphertexts by 97-round KATAN32. Δl81 can be computed from ciphertexts of 97-round KATAN32 and the guess of these six equivalent key bits k175,k179,k183,k187,k191,k193. Given every guess of ten equivalent key bits (k1⊕k16,k2,k3⊕k10,k5,k175,k179,k183,k187,k191,k193), we can calculate and count Δl81 with respect to a set of filtered plaintexts. If the guess is right, PΔl81=1 shows an obvious bias. The computational cost of the experiment is less than 224+6 encryptions of 97-round KATAN32. We mount five key-recovery attack experiments with the same key as the experiments in Section 4.2, and each time the ten equivalent key bits can be correctly recovered.


## 5.2. Key-Recovery Attack on 98-Round KATAN32

Suppose the output bits of 98-round KATAN32 corresponding to plaintextX are S98=s98,s99,⋯,s111 and L98=l98,l99,⋯,l116, and the output bits corresponding to plaintext X+ΔX are S′98=s′98,s′99,⋯,s′111 and L′98=l′98,l′99,⋯,l′116. For decryption direction, Δl81 can be expressed using round keys and the ciphertext of 98-round KATAN32.
(26)Δl81=l113⊕s99⊕s98s101⊕s105⊕l103⊕l98l100⊕l102l107⊕s100⊕l98⊕s106⊕l104⊕l99l101⊕l103l108⊕k187s108⊕l106⊕l101l103⊕l105l110⊕k191⊕s110⊕l108⊕l103l105⊕l107l112⊕k195l102⊕k175s102⊕l100⊕s108⊕l106⊕l101l103⊕l105l110⊕k191s110⊕l108⊕l103l105⊕l107l112⊕k195⊕l99l104⊕k179⊕s104⊕l102⊕s110⊕l108⊕l103l105⊕l107l112⊕k195l99⊕l101l106⊕k183s109⊕l107⊕l102l104⊕l106l111⊕k193⊕l113′⊕s99′⊕s98′s101′⊕s105′⊕l103′⊕l98′l100′⊕l102′l107′⊕s100′⊕l98′⊕s106′⊕l104′⊕l99′l101′⊕l103′l108′⊕k187s108′⊕l106′⊕l101′l103′⊕l105′l110′⊕k191⊕s110′⊕l108′⊕l103′l105′⊕l107′l112′⊕k195l102′⊕k175s102′⊕l100′⊕s108′⊕l106′⊕l101′l103′⊕l105′l110′⊕k191s110′⊕l108′⊕l103′l105′⊕l107′l112′⊕k195⊕l99′l104′⊕k179⊕s104′⊕l102′⊕s110′⊕l108′⊕l103′l105′⊕l107′l112′⊕k195l99′⊕l101′l106′⊕k183s109′⊕l107′⊕l102′l104′⊕l106′l111′⊕k193.The expression contains seven equivalent key bitsk175, k179, k183, k187, k191, k193, k195, which makes the computational cost of the key-recovery attack be less than 224+7 times 98-round KATAN32 encryption. In this attack, 11 equivalent key bits k1⊕k16, k2, k3⊕k10, k5, k175, k179, k183, k187, k191, k193, k195 can be correctly recovered. Every experiment requires about 2.4 hours on a 2.5 GHz PC with our implementation.


## 5.3. Key-Recovery Attack on 99-Round KATAN32

Suppose the output bits of 99-round KATAN32 corresponding to plaintextX are S99=s99,s100,⋯,s112 and L99=l99,l100,⋯,l117, and the output bits corresponding to plaintext X+ΔX are S′99=s′99,s′100,⋯,s′112 and L′99=l′99,l′100,⋯,l′117. For decryption direction, Δl81 can be expressed using round keys and the ciphertext of 99-round KATAN32.
(27)Δl81=l113⊕s99⊕l117⊕s103⊕s102s105⊕s107⊕k196s101⊕s105⊕l103⊕s111⊕l109⊕l104l106⊕l108l113⊕k197l100⊕l102l107⊕s100⊕s111⊕l109⊕l104l106⊕l108l113⊕k197⊕s106⊕l104⊕l99l101⊕l103l108⊕k187s108⊕l106⊕l101l103⊕l105l110⊕k191⊕s110⊕l108⊕l103l105⊕l107l112⊕k195l102⊕k175s102⊕l100⊕s108⊕l106⊕l101l103⊕l105l110⊕k191s110⊕l108⊕l103l105⊕l107l112⊕k195⊕l99l104⊕k179⊕s104⊕l102⊕s110⊕l108⊕l103l105⊕l107l112⊕k195l99⊕l101l106⊕k183s109⊕l107⊕l102l104⊕l106l111⊕k193⊕l113′⊕s99′⊕l117′⊕s103′⊕s102′s105′⊕s107′⊕k196s101′⊕s105′⊕l103′⊕s111′⊕l109′⊕l104′l106′⊕l108′l113′⊕k197l100′⊕l102′l107′⊕s100′⊕s111′⊕l109′⊕l104′l106′⊕l108′l113′⊕k197⊕s106′⊕l104′⊕l99′l101′⊕l103′l108′⊕k187s108′⊕l106′⊕l101′l103′⊕l105′l110′⊕k191⊕s110′⊕l108′⊕l103′l105′⊕l107′l112′⊕k195l102′⊕k175s102′⊕l100′⊕s108′⊕l106′⊕l101′l103′⊕l105′l110′⊕k191s110′⊕l108′⊕l103′l105′⊕l107′l112′⊕k195⊕l99′l104′⊕k179⊕s104′⊕l102′⊕s110′⊕l108′⊕l103′l105′⊕l107′l112′⊕k195l99′⊕l101′l106′⊕k183s109′⊕l107′⊕l102′l104′⊕l106′l111′⊕k193.There are nine equivalent key bitsk175, k179, k183, k187, k191, k193, k195, k196, k197. So the computational cost of the key-recovery attack is less than 224+9 times 99-round KATAN32 encryption. In this attack, 13 equivalent key bits k1⊕k16, k2, k3⊕k10, k5, k175, k179, k183, k187, k191, k193, k195, k196, k197 can be correctly recovered. Every experiment requires about 9.64 hours on a 2.5 GHz PC with our implementation.It is thus possible to extend the conditional differential attack on 81-round KATAN32 to 114-round with the computational cost of less than263 times 114-round KATAN32 encryption.


## 6. Conclusion

Conditional differential analysis towards the NLFSR is quite a recent research topic. We advance the research in this direction by using Mixed Integer Linear Programming on the NLFSR-based block cipher KATAN32, a newly typical and well-designed lightweight block cipher. It is the first time applying MILP in the automatically searching for conditional differential trails. Using MILP helps us efficiently obtain the initial difference and conditions of the conditional differential analysis. We propose a new method to quickly calculate the probability of the difference to detect the bit with a bias. We apply the improved conditional differential analysis to KATAN32 and obtain two results, recovering ten equivalent key bits of 79-round KATAN32 and four equivalent key bits of 81-round KATAN32, respectively.Combined with the standard differential attack, we extend the 81-round conditional key-recovery attack to 99-round with the time complexity being233 encryptions of 99-round KATAN32 and recover 13 equivalent key bits. Compared with the previously best practical distinguisher on KATAN32, our results are extended more than seven rounds with less computation time and memory. We believe both strategies to be general to NLFSR-based ciphers. Applying these two strategies on other NLFSR-based ciphers will be one topic of interest in our future works.



---

*Source: 8883557-2020-11-23.xml*