Differential Fault Attack on KASUMI Cipher Used in GSM Telephony

Abstract

The confidentiality of GSM cellular telephone depends on the security of A5 family of cryptosystems. As an algorithm in this syndicate survived from cryptanalysis, A5/3 is based on the block cipher KASUMI. This newspaper describes a novel differential gear fault attack on KAUSMI with a 64-bit key. Taking advantage of some mathematical observations on the FL, FO functions, and key schedule, alone one 16-bit password fault is required to recover all information of the 64-bit key. The meter complexity is merely 232 encryptions. We have practically simulated the attack on a personal computer which takes merely a few minutes to recover all the keystone bits. The model besides experimentally verifies the correctness and complexity .

1. Introduction

These years witness the rapid exploitation of computer and network communication. The requirement of privacy and authentication in exposed access environment promote the developments of cryptography as well. diverse cryptosystems have been proposed a well as some new studies [ 1, 2 ]. Fast encoding method acting 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 besides the stander for mobile telephone. 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 work and were kept unavowed 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 about no security and A5/1 is besides faint to prevent adversary from eavesdropping on GSM conversations [ 6, 7 ]. even emulating a mobile telephone to make calls and send text messages is possible [ 8, 9 ]. In reception to these attacks, GSM association has vowed to switch to the much more batten A5/3 cipher since 2010. A5/3 is a cryptosystem based on forget cipher KASUMI [ 10 ], which has eight Feistel rounds with a 64-bit parry size. KASUMI accepts 128-bit key in the stipulation, but the key length needs to be reduced in some cases. In practice, A5/3 cryptosystem supports a 64~128-bit school term key. We denote KASUMI with 64-bit key by KASUMI-64 and A5/3 with 64-bit seance key by A5/3-64, respectively.

Lots of attacks on variants of KASUMI have been proposed in the by years with a kind of techniques [ 11 – 14 ]. Among them, Jia et alabama. give a result on KASUMI-64 with only 1152 chosen plaintexts and a time complexity of 262.75 encryptions. Dunkelman et alabama. besides show that they could derive the arrant 128-bit key with data complexity of 226, 232 encryptions, and 230 bytes of memory under the relate samara setting [ 12 ]. differential approach was proposed by Biham and Shamir to analyze DES [ 15 ]. This mighty method has been successfully applied to evaluate cryptosystems and ciphers in subsequent works [ 16 – 18 ]. Combined with side channel attack and technology, differential fault analysis ( DFA ) is a long-familiar threat to cryptographic devices. Utilizing differential information between chastise and faulty ciphertexts, DFA recovers key efficiently. fault is injected by giving external impact on a device with voltage magnetic declination, bug, laser, and thus forth. Since the first gear DFA on DES proposed by Biham and Shamir [ 19 ], this technique has been successfully applied to many other pulley ciphers, for exercise, AES [ 20 – 23 ], CLEFIA [ 24, 25 ], SM4 [ 26 ], and ARIA [ 27 ]. In 2011, Jeong et aluminum. 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 symmetrical cipher in the PIC assembly language has the stick to format : movlw 08 heat content movwf RoudCounter RoundLabel Call RoundFunction decfz RoundCounter goto RoundLabelThe RAM variable ( RoundCounter ) is set to the round off total. 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 generator recovers a 64-bit seance key. however, in many cases, this attack may fail. As a elementary exemplar, it is potential to implement block ciphers so that each turn is called independently : Call RoundFunction Call RoundFunction Call RoundFunction … In this paper, a novel DFA on KASUMI with a 64-bit key is proposed. The method is besides applicable to A5/3-64. Based on some mathematical observations on the FL, FO functions, and the key agenda, we show that only one 16-bit word fault is enough to perform an efficient key convalescence with 232 encryptions. We highlight that the attack is practical. The attack procedure is simulated on a personal computer where the decline key is recovered in a few minutes. The model experimentally verifies the correctness and complexity. Compared with the attack proposed by Kitae Jeong, our method acting is more flexible and has lower time complexity. The end of the wallpaper is organized as follows. incision 2 gives a brief description of KASUMI. segment 3 shows some important observations useful to our DFA method. The detailed attack operation is described in segment 4. In section 5, we show some simulation results. ultimately, we conclude this wallpaper in Section 6 .

2. Description of KASUMI

As depicted in Figure 1, KASUMI is a Feistel structure with 8 rounds. It works on a 64-bit stop and uses a 128-bit winder. Each beat is made up of an FL function and an FO serve. The order of the two functions depends on the round count : in odd numbered rounds the FL function precedes the FO affair, whereas in even count rounds the FO officiate precedes the FL function .
FL is a dim-witted key-dependent Boolean routine, which accepts arsenic well as round key as remark and output ( Figure 1 ( d ) )., , and are all 32-bit words which can be divided into two halves. We denote the most meaning half by subscript and the other by subscript. Subscript is used to denote the thorium round. then the inputs of the FL function of the thorium rung are, and the output is ( “ ” is the concatenating operation ). FL is defined as follows : where the “ ” and “ ” denote bitwise AND and OR, respectively. “ ” implies that rotates left by bits. As shown in figure 1 ( bel ), the FO affair is a three-round Feistel structure which consists of three FI functions and samara adding stages. A 96-bit round key enters FO routine in each orotund ( 48 subkey bits used in FI and 48 subkey bits in the key adding stage ). The FI serve is another four-round Feistel structure that uses two nonlinear S-boxes S7 and S9 ( where S7 is a 7-bit to 7-bit substitution and S9 is a 9-bit to 9-bit permutation ). We define half of FI function as, which is a 16-bit to 16-bit substitution. The structure of FI and is illustrated in Figure 1 ( coke ). The key agenda of KASUMI is very simpleton. More precisely, a 128-bit key is divided into 16-bit words :. Round keys are linearly derived from these eight cardinal 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 : .

Round
1
2
3
4
5
6
7
8

:

rotates left by

bits.

, where

s 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]). Let be -bit values, and. then there are two dispute properties of ADD and OR operations, such that Observation 2. Given the end product difference and the key value of FL function, the represent input remainder can be calculated by This observation is deduced from Observation 1 and the definition of the FL function easily. Observation 3. For both S7 and S9, let be the S-box and consider the trace equality : where and are randomly given stimulation and output difference correspondingly. On average, there is a solution. 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 under any potential and. therefore on modal, for a randomly given pair of and, merely 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 remark difference and an output remainder of, one could deduce the possible input signal and output signal values. On average, there is one input signal value matching the difference. is made up of an S7 and an S9. From and, we calculate the input signal and end product deviation of both S7 and S9. frankincense, this observation is derived from Observation 3 normally. Observation 5. Given an input dispute and an output remainder under random key of the affair, there are potential input and output values. On average, only one input value can be found under. Given the input dispute and the output difference, traverse all stimulation values, and leave those that satisfy the follow equality : then the potential input values are deduced. As there are 216 output differences in total, for any, the equation holds with probability 1/216. Noting that there are besides 216 different randomness, one could find potential remark value on average .

4. DFA on KASUMI

In this section, we describe the DFA on KASUMI in detail, including fault exemplary, assail routine, and complexity analysis .

4.1. Fault Model and Basic Assumption

As the computing unit of FO and FL affair is 16-bit parole, the basic repositing cell of KASUMI is normally double bytes. So we assume that an attacker can induce a mistake to a selected express making a 16-bit password corrupted. The location of the bribe word may be known. For model, Fukunaga and Takahashi showed that they could control the placement of a corrupt byte in [ 31 ]. even if the attacker does not know which bible is corrupted, he can repeat injecting until the target 16-bit discussion corrupted. The assumption is generic and reasonable for devices in which the average values of the encoding are stored .

4.2. General Idea

merely four 16-bit key words are used in KASUMI-64. The general theme is to reduce the count of key candidates by defect injection. More precisely, injecting a 16-bit word fault to the output of the last but one round and making the most of the adjust and faulty ciphertexts, the 64-bit key is determined by 32 bits. The potential key space is reduced from 264 to 232. then the chastise key can be obtained through exhaustive search .

4.3. Attacking Procedure and Complexity Analysis

For better sympathize of our method acting, some notifications are introduced. As exemplify in Figure 2, and are the inputs of the last round and and are the ciphertexts. We denote the inputs of and FL by and, respectively. The corresponding outputs are denoted by and., , and stand for the intermediate states as shown in Figure 2. is used to define the difference between the decline and faulty values of a submit .
now the attack procedures are described as follows. Step 1 (obtain the correct and faulty ciphertexts). For a randomly chosen plaintext, obtain the match ciphertext under the unknown key. For the same plaintext, inject a 16-bit word fault to the place as shown in Figure 2, so that the left 16-bit password of is corrupted. Store the defective ciphertext. Noting that, the corrupt value is known. Step 2 (guess and and deduce ). The inject blame does not affect the value of. So we have and. For any guesses of and, as presented in Observation 2, vitamin a well as are deduced. As merely the left 16-bit give voice of is corrupted, we have. Thus the remark and output signal differences of are both 0. Because is determined by the estimate of and. Step 3 (match the input and output difference of and calculate ). From the key agenda of KASUMI, we can see that, in the death round, is used as. however, has been guessed in Step 2. hence for, the input and output differences angstrom well as are all compulsive. As shown in Observation 5, there is a value matching the stimulation and output signal difference on average. Since and, the possible mho are calculated. Step 4 (deduce the correct and corrupted inputs of, and determine ). , , and have been guessed or deduced in the above steps. So the decline and corrupted inputs of are known. As shown in Figure 3, is only affected by the input value of. So is calculated and the stimulation dispute of the is deduced. note that the end product deviation of is known by which has been calculated in Step 2. Through Observation 4, the possible input signal value is known. So is obtained by. indeed, is in the last round. Thus is besides determined. Until immediately, all the data of key is determined by the guess of and .
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 Step 2 with another estimate of and.
We will arrange the above description in Algorithm 1 where a look-up table indexed by the output deviation of is established before the guess of to reduce the calculation complexity.
To evaluate the complexity of Algorithm 1, we count the numeral of KASUMI encryptions. As we do checking mathematical process for times on modal, the computing complexity is 232 encryptions. The memory necessity is 217 bytes since a table containing 216 16-bit words should be stored .

Input:  

Output:  

(1)

;

(2)for all  possible values of

  do             #

times

(3)for  

++ do

(4)  

;                  # Initialize

as an empty set

(5)end for
(6)for  

++  do            # Construction of the Table

(7)  

;

(8)  

;

(9)end for
(10)  for all possible values of

  do            #

times

(11)    Compute the differences

.          # Observation 2

(12)    for all  

in

  do           # Once on average

(13)    

;

(14)    Deduce

and

as shown in Figure 3.

(15)    Get all possible inputs of

.           # Observation 4

(16)    for all possible

  do            # Once on average

(17)     

;

(18)     if  

is the right key  then      # Checking operation

(19)      return  

;

(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 clock time is denoted as a sample distribution. For each sample, the correct key can be recovered within a few minutes. The number of checking operations for every sample is illustrated in Figure 4. All the numbers are around 232 and the correctness and complexity of our method are verified in practice.


6. Conclusion

This paper describes a DFA attack on KASUMI-64 which is the base of A5/3 cryptosystem used in GSM telephone. We show that alone one 16-bit son fault is adequate to perform a successful key recovery fire. More impressively, both the computer science and memory complexity are virtual and the secret key can be recovered in a few minutes. The correctness and complexity are further verified by the model results. We emphasize that when applying KASUMI-64, the death two rounds should be particularly designed to protect against fault injection. This newspaper besides demonstrates the efficiency of differential mistake attack. When designing and realizing cryptosystems, this new kind of attack should besides be taken into report .

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper .

Acknowledgments

This work was supported by China ’ s 973 Program ( Grant no. 2013CB834205 ) and National Natural Science Foundation of China ( Grant no. 61133013 ) .

Leave a Reply

Your email address will not be published.