# Differential Fault Attack on KASUMI Cipher Used in GSM Telephony

Authors: Zongyue Wang; Xiaoyang Dong; Keting Jia; Jingyuan Zhao
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

The confidentiality of GSM cellular telephony depends on the security of A5 family of cryptosystems. As an algorithm in this family survived from cryptanalysis, A5/3 is based on the block cipher KASUMI. This paper describes a novel differential fault attack on KAUSMI with a 64-bit key. Taking advantage of some mathematical observations on the FL, FO functions, and key schedule, only one 16-bit word fault is required to recover all information of the 64-bit key. The time complexity is only 232 encryptions. We have practically simulated the attack on a PC which takes only a few minutes to recover all the key bits. The simulation also experimentally verifies the correctness and complexity.


---

## Body

## 1. Introduction

These years witness the rapid development of computer and network communication. The requirement of privacy and authentication in open access environment promote the developments of cryptography as well. Various cryptosystems have been proposed as well as some new studies [1, 2]. Fast encryption method can be used in real-time communications [3, 4]. GSM (Global System for Mobile Communications) is a widely used real-time communication system which is also the stander for mobile telephony. The confidentiality of GSM depends on the security of A5 family of cryptosystems. The first two members of this family, A5/1 and A5/2, are stream ciphers which were designed 20 years ago in an opaque process and were kept secret until they were reverse engineered in 1999 [5]. Since then, many cryptanalytic results on these two ciphers have been proposed. It becomes clear that A5/2 provides almost no security and A5/1 is too weak to prevent adversary from eavesdropping on GSM conversations [6, 7]. Even emulating a mobile phone to make calls and send text messages is possible [8, 9].In response to these attacks, GSM association has vowed to switch to the much more secure A5/3 cipher since 2010. A5/3 is a cryptosystem based on block cipher KASUMI [10], which has eight Feistel rounds with a 64-bit block size. KASUMI accepts 128-bit key in the specification, but the key length needs to be reduced in some cases. In practice, A5/3 cryptosystem supports a 64~128-bit session key. We denote KASUMI with 64-bit key by KASUMI-64 and A5/3 with 64-bit session key by A5/3-64, respectively.Lots of attacks on variants of KASUMI have been proposed in the past years with a variety of techniques [11–14]. Among them, Jia et al. give a result on KASUMI-64 with only 1152 chosen plaintexts and a time complexity of 262.75 encryptions. Dunkelman et al. also show that they could derive the complete 128-bit key with data complexity of 226, 232 encryptions, and 230 bytes of memory under the related key setting [12].Differential attack was proposed by Biham and Shamir to analyze DES [15]. This powerful method has been successfully applied to evaluate cryptosystems and ciphers in subsequent works [16–18]. Combined with side channel attack and engineering, differential fault analysis (DFA) is a well-known threat to cryptographic devices. Utilizing differential information between correct and faulty ciphertexts, DFA recovers key efficiently. Fault is injected by giving external impact on a device with voltage variation, glitch, laser, and so forth. Since the first DFA on DES proposed by Biham and Shamir [19], this technique has been successfully applied to many other block ciphers, for example, AES [20–23], CLEFIA [24, 25], SM4 [26], and ARIA [27].In 2011, Jeong et al. proposed the first fault injection attack on A5/3-64 [28]. Their attack is based on the fault assumption in [29], which assumes that the implementation of a symmetric cipher in the PIC assembly language has the following format:movlw  08 hmovwf  RoudCounterRoundLabelCall  RoundFunctiondecfz  RoundCountergoto  RoundLabelThe RAM variable (RoundCounter) is set to the round number. The adversary may decrease the number of rounds by injecting faults to RoundCounter. With about 245.44 KASUMI encryptions and one fault on average, the author recovers a 64-bit session key. However, in many cases, this attack may fail. As a simple example, it is possible to implement block ciphers so that each round is called independently:Call RoundFunctionCall RoundFunctionCall RoundFunction…In this paper, a novel DFA on KASUMI with a 64-bit key is proposed. The method is also applicable to A5/3-64. Based on some mathematical observations on the FL, FO functions, and the key schedule, we show that only one 16-bit word fault is enough to perform an efficient key recovery with 232 encryptions. We highlight that the attack is practical. The attacking procedure is simulated on a PC where the correct key is recovered in a few minutes. The simulation experimentally verifies the correctness and complexity. Compared with the attack proposed by Kitae Jeong, our method is more flexible and has lower time complexity.The remainder of the paper is organized as follows. Section2 gives a brief description of KASUMI. Section 3 shows some important observations useful to our DFA method. The detailed attack procedure is described in Section 4. In Section 5, we show some simulation results. Finally, we conclude this paper in Section 6.


## 2. Description of KASUMI

As depicted in Figure1, KASUMI is a Feistel structure with 8 rounds. It works on a 64-bit block and uses a 128-bit key. Each round is made up of an FL function and an FO function. The order of the two functions depends on the round number: in odd numbered rounds the FL function precedes the FO function, whereas in even numbered rounds the FO function precedes the FL function.Figure 1
The structure and building blocks of block cipher KASUMI.FL is a simple key-dependent Boolean function, which acceptsXL as well as round key KL as input and output YL (Figure 1(d)). XL, KL, and YL are all 32-bit words which can be divided into two halves. We denote the most significant half by subscript l and the other by subscript r. Subscript i is used to denote the ith round. Then the inputs of the FL function of the ith round are XLi=XLi,l∥XLi,r, KLi=(KLi,1,KLi,2) and the output is YLi=YLi,l∥YLi,r (“∥” is the concatenating operation). FL is defined as follows:
(1)YLi,r=((XLi,l∧KLi,1)⋘1)⊕XLi,r,YLi,l=((YLi,r∨KLi,2)⋘1)⊕XLi,l,
where the “∧” and “∨” denote bitwise AND and OR, respectively. “x⋘i” implies that x rotates left by i bits.As shown in Figure1(b), the FO function is a three-round Feistel structure which consists of three FI functions and key adding stages. A 96-bit round key enters FO function in each round (48 subkey bits KI used in FI and 48 subkey bits KO in the key adding stage). The FI function is another four-round Feistel structure that uses two nonlinear S-boxes S7 and S9 (where S7 is a 7-bit to 7-bit permutation and S9 is a 9-bit to 9-bit permutation). We define half of FI function as FI¯, which is a 16-bit to 16-bit permutation. The structure of FI and FI¯ is illustrated in Figure 1(c).The key schedule of KASUMI is very simple. More precisely, a 128-bit key is divided into 16-bit words:(k1,k2,…,k8). Round keys are linearly derived from these eight key words (see Table 1). Since the key length needs to be reduced in some cases, the key words should be cyclically repeated to fill 128 bits. The eight key words of KASUMI-64, in particular, are listed as follows: (k1,k2,k3,k4,k1,k2,k3,k4).Table 1
The key schedule of KASUMI.
Round
K
L
i
,
1
K
L
i
,
2
K
O
i
,
1
K
O
i
,
2
K
O
i
,
3
K
I
i
,
1
K
I
i
,
2
K
I
i
,
3
1
k
1
⋘
1
k
3
′
k
2
⋘
5
k
6
⋘
8
k
7
⋘
13
k
5
′
k
4
′
k
8
′
2
k
2
⋘
1
k
4
′
k
3
⋘
5
k
7
⋘
8
k
8
⋘
13
k
6
′
k
5
′
k
1
′
3
k
3
⋘
1
k
5
′
k
4
⋘
5
k
8
⋘
8
k
1
⋘
13
k
7
′
k
6
′
k
2
′
4
k
4
⋘
1
k
6
′
k
5
⋘
5
k
1
⋘
8
k
2
⋘
13
k
8
′
k
7
′
k
3
′
5
k
5
⋘
1
k
7
′
k
6
⋘
5
k
2
⋘
8
k
3
⋘
13
k
1
′
k
8
′
k
4
′
6
k
6
⋘
1
k
8
′
k
7
⋘
5
k
3
⋘
8
k
4
⋘
13
k
2
′
k
1
′
k
5
′
7
k
7
⋘
1
k
1
′
k
8
⋘
5
k
4
⋘
8
k
5
⋘
13
k
3
′
k
2
′
k
6
′
8
k
8
⋘
1
k
2
′
k
1
⋘
5
k
5
⋘
8
k
6
⋘
13
k
4
′
k
3
′
k
7
′
x
⋘
i: x rotates left by i bits.
k
i
′
=
k
i
⊕
c
i, where cis are fixed constants.


## 3. Some Observations of KASUMI

In this section, several observations of KASUMI are given, which are bases of our DFA.Observation 1 (see [30]).
LetX,X′ be l-bit values, and ΔX=X⊕X′. Then there are two difference properties of ADD and OR operations, such that
(2)(X∧K)⊕(X′∧K)=ΔX∧K,(X∨K)⊕(X′∨K)=ΔX⊕(ΔX∧K).Observation 2.
Given the output differenceΔY=ΔYl∥ΔYr and the key value KL=(KL1,KL2) of FL function, the corresponding input difference can be calculated by
(3)ΔXl=((ΔXr⊕(ΔXr∧KL2)⋘1))⊕ΔYl,ΔXr=((ΔXl∧KL1)⋘1)⊕ΔYr.This observation is deduced from Observation1 and the definition of the FL function easily.Observation 3.
For both S7 and S9, lets(·) be the S-box and consider the following equation:
(4)s(x)⊕s(x⊕α)=β,
where α and β are randomly given input and output difference correspondingly. On average, there is a solution x.Actually, for both S7 and S9, the number of solution of (4) could only be 0 and 2. The probabilities of each case are both 1/2. This property could be verified by traversing every value x under any possible α and β. So on average, for a randomly given pair of α and β, only one solution is found. In practice, we build a look-up table indexed by α and β to help us solve this kind of equation.Observation 4.
Given an input differenceΔx and an output difference Δy of FI¯, one could deduce the possible input and output values. On average, there is one input value matching the difference.FI
¯ is made up of an S7 and an S9. From Δx and Δy, we calculate the input and output difference of both S7 and S9. Thus, this observation is derived from Observation 3 normally.Observation 5.
Given an input differenceΔx and an output difference Δy under random key KI of the FI function, there are possible input and output values. On average, only one input value can be found under KI.Given the input differenceΔx and the output difference Δy, traverse all input values v, and leave those that satisfy the following equation:
(5)FI(v)⊕FI(v⊕Δx)=Δy.Then the possible input values are deduced. As there are 216 output differences in total, for any v, the equation holds with probability 1/216. Noting that there are also 216 different vs, one could find 216×1/216=1 possible input value on average.


## 4. DFA on KASUMI

In this section, we describe the DFA on KASUMI in detail, including fault model, attack procedure, and complexity analysis.


### 4.1. Fault Model and Basic Assumption

As the computing unit of FO and FL function is 16-bit word, the basic storage cell of KASUMI is usually double bytes. So we assume that an attacker can induce a fault to a selected state making a 16-bit word corrupted. The location of the corrupted word may be known. For example, Fukunaga and Takahashi showed that they could control the location of a corrupted byte in [31]. Even if the attacker does not know which word is corrupted, he can repeat injecting until the target 16-bit word corrupted. The assumption is generic and reasonable for devices in which the intermediate values of the encryption are stored.


### 4.2. General Idea

Only four 16-bit key words are used in KASUMI-64. The general idea is to reduce the number of key candidates by fault injection. More precisely, injecting a 16-bit word fault to the output of the last but one round and making the most of the correct and faulty ciphertexts, the 64-bit key is determined by 32 bits. The possible key space is reduced from 264 to 232. Then the correct key can be obtained through exhaustive search.


### 4.3. Attacking Procedure and Complexity Analysis

For better understanding of our method, some notifications are introduced. As illustrated in Figure2, L and R are the inputs of the last round and CL and CR are the ciphertexts. We denote the inputs of FIi and FL by XFIi and XFL, respectively. The corresponding outputs are denoted by YFIi and YFL. M, N, and O stand for the intermediate states as shown in Figure 2. Δ is used to define the difference between the correct and faulty values of a state.Figure 2
DFA on KASUMI. (Red lines are affected by the fault while the blues are not.)Now the attack procedures are described as follows.Step 1 (obtain the correct and faulty ciphertexts).
For a randomly chosen plaintext, obtain the corresponding ciphertext under the unknown key. For the same plaintext, inject a 16-bit word fault to the position as shown in Figure2, so that the left 16-bit word of L is corrupted. Store the faulty ciphertext. Noting that L=CR, the corrupted value is known.Step 2 (guessK2 and K4 and deduce ΔYFI1).
The injected fault does not affect the value ofR. So we have ΔR=0 and ΔYFL=ΔCL. For any guesses of K2 and K4, as presented in Observation 2, ΔXFL as well as ΔO are deduced. As only the left 16-bit word of L is corrupted, we have ΔM=0. Thus the input and output differences of FI2 are both 0. Because
(6)ΔYFI1=ΔM⊕ΔN=ΔM⊕ΔYFI2⊕ΔO=ΔO,ΔYFI1 is determined by the guessing of K2 and K4.Step 3 (match the input and output difference ofFI1 and calculate K1).
From the key schedule of KASUMI, we can see that, in the last round,K4′ is used as KI1. However, K4 has been guessed in Step 2. Hence for FI1, the input and output differences as well as KI1 are all determined. As shown in Observation 5, there is a value XFI1 matching the input and output difference on average. Since L=CR and (K1⋘5)=LL⊕XFI1, the possible K1s are calculated.Step 4 (deduce the correct and corrupted inputs ofFI3, and determine K3).
K
1, K2, and K4 have been guessed or deduced in the above steps. So the correct and corrupted inputs of FI3 are known. As shown in Figure 3, Q is only affected by the input value of FI3. So Q is calculated and the input difference of the FI¯ is deduced. Note that the output difference of FI¯ is known by ΔXFL which has been calculated in Step 2. Through Observation 4, the possible input value XFI¯ is known. So KI3 is obtained by KI3=XFI¯⊕Q. Indeed, KI3 is K3′ in the last round. Thus K3 is also determined. Until now, all the information of key is determined by the guessing of K2 and K4.Figure 3
F
I
3 in the last round.Step 5 (verify the correctness of the guessed key).
Encrypt the plaintext with the key obtained in the above steps and check the correctness. If the key is not right, go back to Step2 with another guess of K2 and K4.
We will order the above description in Algorithm1 where a look-up table indexed by the output difference of FI1 is established before the guessing of K2 to reduce the computing complexity.
To evaluate the complexity of Algorithm1, we count the number of KASUMI encryptions. As we do checking operation for 216+16=232 times on average, the computing complexity is 232 encryptions. The memory requirement is 217 bytes since a table containing 216 16-bit words should be stored.Algorithm 1:DFA on KASUMI cipher.
Input:  CL,CR,ΔCLΔCR
Output:  (K1,K2,K3,K4)
(1)ΔLL∥ΔLR=ΔCR;
(2)for all  possible values of K4  do             # 216 times
(3) for  i=0;i<216;i++ do
(4)  Ti=Φ;                  # Initialize Ti as an empty set
(5) end for
(6) for  i=0;i<216;i++  do            # Construction of the Table
(7)  index←FI(i,K4′)⊕FI(i⊕ΔLL,K4′);
(8)  Tindex←Tindex∪{i};
(9) end for
(10)for all possible values of K2  do            # 216 times
(11)    Compute the differencesΔXFL.          # Observation 2
(12)for all  XFI1 in TΔYFI1  do           # Once on average
(13)K1←(LL⊕XFI1)⋙5;
(14)    DeduceQ and ΔQ as shown in Figure 3.
(15)    Get all possible inputs ofFI¯.           # Observation 4
(16)for all possible XFI¯  do            # Once on average
(17)K3′←Q⊕XFI¯;
(18)if  (K1,K2,K3,K4) is the right key  then      # Checking operation
(19)return  (K1,K2,K3,K4);
(20)end if
(21)end for
(22)end for
(23)end for
(24)end for


## 4.1. Fault Model and Basic Assumption

As the computing unit of FO and FL function is 16-bit word, the basic storage cell of KASUMI is usually double bytes. So we assume that an attacker can induce a fault to a selected state making a 16-bit word corrupted. The location of the corrupted word may be known. For example, Fukunaga and Takahashi showed that they could control the location of a corrupted byte in [31]. Even if the attacker does not know which word is corrupted, he can repeat injecting until the target 16-bit word corrupted. The assumption is generic and reasonable for devices in which the intermediate values of the encryption are stored.


## 4.2. General Idea

Only four 16-bit key words are used in KASUMI-64. The general idea is to reduce the number of key candidates by fault injection. More precisely, injecting a 16-bit word fault to the output of the last but one round and making the most of the correct and faulty ciphertexts, the 64-bit key is determined by 32 bits. The possible key space is reduced from 264 to 232. Then the correct key can be obtained through exhaustive search.


## 4.3. Attacking Procedure and Complexity Analysis

For better understanding of our method, some notifications are introduced. As illustrated in Figure2, L and R are the inputs of the last round and CL and CR are the ciphertexts. We denote the inputs of FIi and FL by XFIi and XFL, respectively. The corresponding outputs are denoted by YFIi and YFL. M, N, and O stand for the intermediate states as shown in Figure 2. Δ is used to define the difference between the correct and faulty values of a state.Figure 2
DFA on KASUMI. (Red lines are affected by the fault while the blues are not.)Now the attack procedures are described as follows.Step 1 (obtain the correct and faulty ciphertexts).
For a randomly chosen plaintext, obtain the corresponding ciphertext under the unknown key. For the same plaintext, inject a 16-bit word fault to the position as shown in Figure2, so that the left 16-bit word of L is corrupted. Store the faulty ciphertext. Noting that L=CR, the corrupted value is known.Step 2 (guessK2 and K4 and deduce ΔYFI1).
The injected fault does not affect the value ofR. So we have ΔR=0 and ΔYFL=ΔCL. For any guesses of K2 and K4, as presented in Observation 2, ΔXFL as well as ΔO are deduced. As only the left 16-bit word of L is corrupted, we have ΔM=0. Thus the input and output differences of FI2 are both 0. Because
(6)ΔYFI1=ΔM⊕ΔN=ΔM⊕ΔYFI2⊕ΔO=ΔO,ΔYFI1 is determined by the guessing of K2 and K4.Step 3 (match the input and output difference ofFI1 and calculate K1).
From the key schedule of KASUMI, we can see that, in the last round,K4′ is used as KI1. However, K4 has been guessed in Step 2. Hence for FI1, the input and output differences as well as KI1 are all determined. As shown in Observation 5, there is a value XFI1 matching the input and output difference on average. Since L=CR and (K1⋘5)=LL⊕XFI1, the possible K1s are calculated.Step 4 (deduce the correct and corrupted inputs ofFI3, and determine K3).
K
1, K2, and K4 have been guessed or deduced in the above steps. So the correct and corrupted inputs of FI3 are known. As shown in Figure 3, Q is only affected by the input value of FI3. So Q is calculated and the input difference of the FI¯ is deduced. Note that the output difference of FI¯ is known by ΔXFL which has been calculated in Step 2. Through Observation 4, the possible input value XFI¯ is known. So KI3 is obtained by KI3=XFI¯⊕Q. Indeed, KI3 is K3′ in the last round. Thus K3 is also determined. Until now, all the information of key is determined by the guessing of K2 and K4.Figure 3
F
I
3 in the last round.Step 5 (verify the correctness of the guessed key).
Encrypt the plaintext with the key obtained in the above steps and check the correctness. If the key is not right, go back to Step2 with another guess of K2 and K4.
We will order the above description in Algorithm1 where a look-up table indexed by the output difference of FI1 is established before the guessing of K2 to reduce the computing complexity.
To evaluate the complexity of Algorithm1, we count the number of KASUMI encryptions. As we do checking operation for 216+16=232 times on average, the computing complexity is 232 encryptions. The memory requirement is 217 bytes since a table containing 216 16-bit words should be stored.Algorithm 1:DFA on KASUMI cipher.
Input:  CL,CR,ΔCLΔCR
Output:  (K1,K2,K3,K4)
(1)ΔLL∥ΔLR=ΔCR;
(2)for all  possible values of K4  do             # 216 times
(3) for  i=0;i<216;i++ do
(4)  Ti=Φ;                  # Initialize Ti as an empty set
(5) end for
(6) for  i=0;i<216;i++  do            # Construction of the Table
(7)  index←FI(i,K4′)⊕FI(i⊕ΔLL,K4′);
(8)  Tindex←Tindex∪{i};
(9) end for
(10)for all possible values of K2  do            # 216 times
(11)    Compute the differencesΔXFL.          # Observation 2
(12)for all  XFI1 in TΔYFI1  do           # Once on average
(13)K1←(LL⊕XFI1)⋙5;
(14)    DeduceQ and ΔQ as shown in Figure 3.
(15)    Get all possible inputs ofFI¯.           # Observation 4
(16)for all possible XFI¯  do            # Once on average
(17)K3′←Q⊕XFI¯;
(18)if  (K1,K2,K3,K4) is the right key  then      # Checking operation
(19)return  (K1,K2,K3,K4);
(20)end if
(21)end for
(22)end for
(23)end for
(24)end for


## 5. Simulation Results

We simulate our DFA on KASUMI-64 with a random key for 1000 times. Each time is denoted as a sample. For each sample, the correct key can be recovered within a few minutes. The number of checking operations for every sample is illustrated in Figure4. All the numbers are around 232 and the correctness and complexity of our method are verified in practice.Figure 4
Simulation result.


## 6. Conclusion

This paper describes a DFA attack on KASUMI-64 which is the base of A5/3 cryptosystem used in GSM telephony. We show that only one 16-bit word fault is enough to perform a successful key recovery attack. More impressively, both the computing and memory complexity are practical and the secret key can be recovered in a few minutes. The correctness and complexity are further verified by the simulation results. We emphasize that when applying KASUMI-64, the last two rounds should be specially designed to protect against fault injection. This paper also demonstrates the efficiency of differential fault attack. When designing and realizing cryptosystems, this new kind of attack should also be taken into account.



---

*Source: 251853-2014-06-05.xml*