# Slide Attack on Full-Round ULC Lightweight Block Cipher Designed for IoT

Authors: Kai Zhang; Xuejia Lai; Lei Wang; Jie Guan; Bin Hu
Journal: Security and Communication Networks
 (2022)

---

## Abstract

To meet the security demand for IoT devices, many new lightweight block ciphers are proposed. ULC is a lightweight block cipher designed for the IoT. It has many advantages in terms of memory use, efficiency, and security. In this paper, a slide attack on full-round ULC is proposed in a related key setting. First, two properties on ULC are discovered. The first property is presented to illustrate the property of a slid pair for ULC. The second property is introduced to construct a link between some round key bits and some master key bits. Based on these properties, a key recovery attack on ULC is proposed. In this attack, with the condition of one related key, all the 80 master key bits can be recovered with the data complexity ofO(232), the memory complexity of O(232), and the time complexity of O(263). The result of this paper indicates that ULC can’t resist slide attack in related key settings.


---

## Body

## 1. Introduction

With the rapid development of the Internet of Things (IoT), it is getting deep into all fields of people’s lives. However, the devices used in the IoT are usually microcomputing equipment, which have weak computing power. Unlike traditional computers and high-performance computers, the computing and storage capacity for those devices in IoT are limited. So, it is very important to propose some better lightweight ciphers and guarantee the security of IoT devices. In order to solve this problem, the topic of lightweight block ciphers has been a hot topic for the last several years, and a number of new lightweight block ciphers have been proposed, which are represented by PRESENT [1], Lblock [2], RECTANGLE [3], TWINE [4], Piccolo [5], SIMON [6], Lilliput [7], SPECK [6], Simeck [8], HIGHT [9], LEA [10], etc. Among these ciphers, lightweight block ULC [11] is proposed in 2021 and designed for IoT. When compared with traditional block ciphers, it has many advantages in terms of performance, memory usage, and security level. However, a thorough security evaluation of these lightweight block ciphers is essential before actual usage.Slide attack [12] is proposed by Biryukov and Wagner at FSE 1999. In the Journal of Cryptology (2018), more efficient slide attacks are proposed to reduce the time complexity of the slide attack [13]. At Eurocrypt 2020, several new types of slide attacks are proposed to overcome the asymmetry of the last round [14]. In recent years, quantum slide attacks have been proposed for better results [15, 16]. This attack has been applied successfully on many ciphers such as Keeloq, GOST, FF3, Trivium, IEC 62055-41, CLX-128, Spectr-H64, SHACAL-1, and WG-16 [17–24]. Among these results, the most notable ones are breaking the block ciphers Keeloq, FF3, and GOST, which are real-life cryptosystems. Keeloq is used to protect cars against theft and also is used in garage door openers. FF3 is the format-preserving encryption scheme selected as a US standard [25] by NIST. The GOST block cipher is a Russian encryption standard. The basic idea of slide attack is to use the property of a slid pair to derive some information about the key bits.Our contribution is as follows: our overall contribution is proposing a slide attack on full-round ULC. First, two properties under ULC are presented. The first property is presented to illustrate the property of a slid pair for ULC. The second property is introduced to construct a link between some round key bits and the master key bits, which will be used in our attack. Based on these properties, a key recovery attack on ULC is proposed. In this attack, with the condition of one related key, 80-bit master key bits can be recovered with the data complexity ofO(232), the memory complexity of O(232), and the time complexity of O(263).The comparison between our results and some previous cryptanalytic results is illustrated in Table1.Table 1
Summary of the attacks on ULC.
CipherType of attackAttacked/total roundsTime complexityReferenceULCLinear attack10/15O(276)[11]Slide attack15/15O(263)Section5Outline. This paper is organized as follows: the notations used in this paper are illustrated in Section 2. Section 3 gives a brief description of slide attack and ULC. Section 4 proposes two properties on ULC. A key recovery attack on ULC is presented in Section 5. Section 6 concludes the paper.


## 2. Notations

SupposeE is an n-bit block cipher of R rounds, the following notations are used throughout this paper.(i)
P: plaintext;(ii)
C: ciphertext;(iii)
K: 80-bit master key, Kt represents the 80-bit key register at the t-th round and Ki:j represents the i-th bit to the j-th bit of K;(iv)
RKi: 64-bit round key at the i-th round;(v)
“≪<i”: left rotation with i bits;(vi)
“⊕”: XOR operation.


## 3. Preliminary

### 3.1. General Procedures of a Slide Attack

In this section, the general procedures of a typical slide attack are illustrated. As is known to all, a block cipher uses a relatively weak round function iteratively to reach a strong security strength. According to the original slide attack, all the round functions of a block cipherEk are supposed to be the same, which can be denoted as fk. Ek can be written as(1)Ek=fk∘fk∘fk∘⋯∘fk.The key point for a slide attack is seeking a sliding pair. If two plaintextsP, P′ satisfy the equation P′ = fk (P), (P, P′) is a slid pair. If a slid pair appears, for the two ciphertexts of P and P′, C = Ek (P), C′ = Ek(P′), the conclusion C′ = fk(C) can be derived. This procedure is demonstrated in Figure 1 and all the intermediate states in the same nibble marked in red lines are totally the same.Figure 1
Encryption similarity for slide attack.It is difficult for an attacker to figure out which pair is a slid pair. So, we have to construct a set containing sufficient plaintext-ciphertext pairs. According to the birthday paradox, if the block size ofEk is n and the set contains 2n/2 plaintext-ciphertext pairs, a slid pair is expected to appear with a high probability (about 63%). If a slide appears, as P, P′, C, C′ are all known, we can solve k from the following equation:(2)fkP=P′,fkC=C′.For some block ciphers, the round keys for different rounds are not always the same. According to the key schedule, we can use the condition of related keys to makefki, have a dynamic match to construct a slid pair.


### 3.2. Related Key Attack

The related key attack model is a class of cryptanalytic attacks that correspond to the “single key attack model.” In the related key attack model, the attacker can know or choose the relationship between several keys, and the target of the attacker is to find the correct secret key.The related key attack model is important in the area of cryptanalysis. For slide attacks, the condition of “related key” usually appears, and the idea of using a related key in slide attack has been used in much previous literature. Besides, the security level of related key attacks is included as a rationale in many design specifications of block ciphers.


### 3.3. Brief Description on ULC

The structure of ULC is SPN. The idea of the ULC originated from the PRESENT and the RECTANGLE. The block size of ULC is 64 bits, and there are altogether 15 rounds. The round function is composed of three layers: the key addition layer, the substitution layer, and the bit permutation layer. In the key addition layer, the 64-bit round key is XORed into the internal state. In the substitution layer, a bit-sliced four-bit Sbox is used in parallel to introduce nonlinearity. In the bit permutation layer, an involutive 64-bit permutation is used to bring in quicker diffusion. The round function of ULC is illustrated in Figure2.Figure 2
Round function of ULC.The key schedule of ULC is modified from an ISO standard block cipher, PRESENT. First, the 80-bit register is initialized with the master key. We substitute the four most significant bits of the key register with the Sbox, then rotate the register by 61 bits on the left. Finally, the 64 most significant bits of the key register are extracted as the round keyRK. The mathematical form of this key register updating progress can be illustrated as follows:(1)
[k79k78k77k76] = S[k79k78k77k76](2)
[k79k78,…,k1k0] = [k18k17,…,k20k19](3)
RK63:0i = [k79k78,…,k17k16]


## 3.1. General Procedures of a Slide Attack

In this section, the general procedures of a typical slide attack are illustrated. As is known to all, a block cipher uses a relatively weak round function iteratively to reach a strong security strength. According to the original slide attack, all the round functions of a block cipherEk are supposed to be the same, which can be denoted as fk. Ek can be written as(1)Ek=fk∘fk∘fk∘⋯∘fk.The key point for a slide attack is seeking a sliding pair. If two plaintextsP, P′ satisfy the equation P′ = fk (P), (P, P′) is a slid pair. If a slid pair appears, for the two ciphertexts of P and P′, C = Ek (P), C′ = Ek(P′), the conclusion C′ = fk(C) can be derived. This procedure is demonstrated in Figure 1 and all the intermediate states in the same nibble marked in red lines are totally the same.Figure 1
Encryption similarity for slide attack.It is difficult for an attacker to figure out which pair is a slid pair. So, we have to construct a set containing sufficient plaintext-ciphertext pairs. According to the birthday paradox, if the block size ofEk is n and the set contains 2n/2 plaintext-ciphertext pairs, a slid pair is expected to appear with a high probability (about 63%). If a slide appears, as P, P′, C, C′ are all known, we can solve k from the following equation:(2)fkP=P′,fkC=C′.For some block ciphers, the round keys for different rounds are not always the same. According to the key schedule, we can use the condition of related keys to makefki, have a dynamic match to construct a slid pair.


## 3.2. Related Key Attack

The related key attack model is a class of cryptanalytic attacks that correspond to the “single key attack model.” In the related key attack model, the attacker can know or choose the relationship between several keys, and the target of the attacker is to find the correct secret key.The related key attack model is important in the area of cryptanalysis. For slide attacks, the condition of “related key” usually appears, and the idea of using a related key in slide attack has been used in much previous literature. Besides, the security level of related key attacks is included as a rationale in many design specifications of block ciphers.


## 3.3. Brief Description on ULC

The structure of ULC is SPN. The idea of the ULC originated from the PRESENT and the RECTANGLE. The block size of ULC is 64 bits, and there are altogether 15 rounds. The round function is composed of three layers: the key addition layer, the substitution layer, and the bit permutation layer. In the key addition layer, the 64-bit round key is XORed into the internal state. In the substitution layer, a bit-sliced four-bit Sbox is used in parallel to introduce nonlinearity. In the bit permutation layer, an involutive 64-bit permutation is used to bring in quicker diffusion. The round function of ULC is illustrated in Figure2.Figure 2
Round function of ULC.The key schedule of ULC is modified from an ISO standard block cipher, PRESENT. First, the 80-bit register is initialized with the master key. We substitute the four most significant bits of the key register with the Sbox, then rotate the register by 61 bits on the left. Finally, the 64 most significant bits of the key register are extracted as the round keyRK. The mathematical form of this key register updating progress can be illustrated as follows:(1)
[k79k78k77k76] = S[k79k78k77k76](2)
[k79k78,…,k1k0] = [k18k17,…,k20k19](3)
RK63:0i = [k79k78,…,k17k16]


## 4. Slide Properties on ULC

To better illustrate the slide attack on ULC, two properties are presented in this section. The first property is to illustrate the concrete conditions for a slid pair on ULC. The second property is to demonstrate the relationship between some subkey bits of the last round and some master key bits that will be used in our attack.Property 1.
(Sufficient prerequisite for a slid pair on ULC). For ULC, given two plaintext pairs (P, P′) and a related key K,K′, K′=K⋘61,K79:76′=SboxK79:76′, C = ULC(P, K), C′ = ULC(P′, K′), the sufficient prerequisite for a slid pair is as follows:(3)RK1=Sbox−1∘Perm−1P′⊕P.
If equation (3) is satisfied, the following equation (4) must also hold(4)RK′16=PermSboxC⊕C′.Proof.
if we want to construct a slid pair for one round, the intermediate value after the first round must be equal toP′. This implies that P′=PermSboxP⊕RK1. Using the inverse operation of Perm and Sbox, equation (3) can be derived as(5)RK1=Sbox−1∘Perm−1P′⊕P.
Based on the condition of equation (3), P and P′ must constitute a slid pair under the related key K,K′.
To make it more intuitive, this process is shown in Figure3. As P′ equals to the intermediate value after the first-round encryption of (P, K), the state for the key register of the first round, i.e., K1, K1=K⋘61, and K79:761=, SboxK79:761 According to the relationship of the related key, K′, equals to K1. Therefore, the first 14 rounds for the encryption process of (P′, K′) (with a round key RK′15, added after) are totally the same as 2–15 rounds encryption of (P, K) (the RK16, is added after which is equals to RK′15.). This similarity is illustrated in the red box in Figure 3.
Based on this observation, for the encryption of (P′, K′), the intermediate value after adding the round key RK′15 must be C. This indicates the following equation must hold.(6)C′=PermSboxC⊕RK′16.Figure 3
Encryption similarity of a slid pair.Property 2.
(Relationship ofRK′16, RK1 and K). If a slid pair appears, given RK′16, the round key bits RK47:01 and master key bits K79:19,2:0 can be determined according to the following equation:(7)Ki+3:j+3=Sbox−1RKi−16:j−16′16i:j∈Ω1,Ki+3mod80=RKi−16′16i∈79,77or56,54or37,35or18,16.(8)RKi+16′16=RKi1i∈47,45or44,41or24,22or5,3,Sbox−1RKi+16:j+16′16=RKi:j1i:j∈Ω2,Sbox−1RK18:15′16m3=RK2:01.
Ω1=34:31,30:27,26:23,22:19,53:50,49:46,45:42,41:38,76:73,72:69,68:65,64:61,60:57;
Ω2=21:18,40:37,17:14,36:33,13:10,32:29,28:25,9:6 (a)m3.
represents the three most significant bits ofa.Proof.
The 64 round key bits ofRK′16, are focused according to the key schedule. In this property, a link between the master key and round key bits for the first and last round is illustrated.
To better illustrate the relevance of these bits between different key registers, Figure4 is presented to depict the path for these concerned key bits. In this figure, each row represents a state of the 80-bit key register at different rounds, and each nibble represents a bit for the key register. The colored nibbles represent the concerned round key bits at different rounds. The orange nibbles represent that these bits go through an Sbox. The rest of the concerned bits are marked in blue.
Through deduction, it is found that for the 64 bits of the round keyRK′16, 12 bits are totally the same from single-shift operation and the other 52 bits go through a single Sbox. Each four of the 52 bits go through the Sbox at rounds 1, 3–5, 7–9, 11–13, and 15-16 (these round numbers are defined according to the key K). The relationship between the master key bits and the bits going through each Sbox is calculated as follows:(9)K60:571=SboxK79:76,K60:573=SboxK37:34,K60:574=SboxK56:53,K60:575=SboxK75:72,K60:577=SboxK33:30,K60:578=SboxK52:49,K60:579=SboxK71:68,K60:5711=SboxK29:26,K60:5712=SboxK48:45,K60:5713=SboxK67:64,K60:5715=SboxK25:22,K60:5716=SboxK44:41,K60:57′16=SboxK63:60.
The relationship between the key registerK′16 and K60:571,3,4,5,7,8,9,11,12,13,15,16 is as follows:(10)K76:73′16=K60:571,K34:31′16=K60:573,K53:50′16=K60:574,K72:69′16=K60:575,K30:27′16=K60:577,K49:46′16=K60:578,K68:65′16=K60:579,K26:23′16=K60:5711,K45:42′16=K60:5712,K64:61′16=K60:5713,K22:19′16=K60:5715,K41:38′16=K60:5716,K60:57′16=K60:57′16,
According to the relationship between the round key, related key, and key register, the following equations can be obtained.(11)RK60:57′16=K76:73′16=K60:571=SboxK79:76,RK18:15′16=K34:31′16=K60:573=SboxK37:34,RK37:34′16=K53:50′16=K60:574=SboxK56:53,RK56:53′16=K72:69′16=K60:575=SboxK75:72,RK14:11′16=K30:27′16=K60:577=SboxK33:30,RK33:30′16=K49:46′16=K60:578=SboxK52:49,RK52:49′16=K68:65′16=K60:579=SboxK71:68,RK1:7′16=K26:23′16=K60:5711=SboxK29:26,RK29:26′16=K45:42′16=K60:5712=SboxK48:45,RK48:45′16=K64:61′16=K60:5713=SboxK67:64,RK6:3′16=K22:19′16=K60:5715=SboxK25:22,RK25:22′16=K41:38′16=K60:5716=SboxK44:41,RK44:41′16=K60:57′16=K60:57′16=SboxK63:60.
After applying the Sbox−1 on both two sides of the equations, the conclusion of equation (7) in Property 2 can be derived (those bits from only shift operation can be calculated directly).(12)Sbox−1RK60:57′16=K79:76,Sbox−1RK18:15′16=K37:34,Sbox−1RK37:34′16=K56:53,Sbox−1RK56:53′16=K75:72,Sbox−1RK14:11′16=K33:30,Sbox−1RK33:30′16=K52:49,Sbox−1RK52:49′16=K71:68,Sbox−1RK10:7′16=K29:26,Sbox−1RK29:26′16=K48:45,Sbox−1RK48:45′16=K67:64,Sbox−1RK6:3′16=K25:22,Sbox−1RK25:22′16=K44:41,Sbox−1RK44:41′16=K63:60.
As the round key bits ofRK47:01 and K have the following relations:(13)RK44:411=SboxK79:76,RK47:451=K2:0,RK40:01=K75:35.
So the round key bits ofRK47:01 and K′16 have the following relation, and the conclusion of (7) in Property 2 can be derived.(14)RK60:57′16=SboxK79:76=RK44:411,RK63:61′16=K2:0=RK47:451,RK40:38′16=K59:57=RK24:221,RK21:19′16=K40:38=RK5:31,Sbox−1RK18:15′16=K37:34⟶RK2:01,Sbox−1RK37:34′16=K56:53=RK21:181,Sbox−1RK56:53′16=K75:72=RK40:371,Sbox−1RK33:30′16=K52:49=RK17:141,Sbox−1RK52:49′16=K71:68=RK36:331,Sbox−1RK29:26′16=K48:45=RK13:101,Sbox−1RK48:45′16=K67:64=RK32:291,Sbox−1RK44:41′16=K63:60=RK28:251,Sbox−1RK25:22′16=K44:41=RK9:61.
There are two ways to further utilize Property2:(1)
If a slid pair appears, givenRK16 and RK1, all the 80 master key bits of K can be recovered.(2)
If a slid pair appears, 48 bits ofRK1 can be determined according to RK′16. This can be viewed as a distinguisher to eliminate wrong slid pair candidates.Figure 4
Relationship between some master key bits and round key bits.


## 5. Key Recovery Attack on ULC

In this section, a key recovery attack on ULC is proposed based on the properties in Section4. With our method, the full-round ULC can be attacked and all the 80-bit master keys can be recovered. The details of the attack are illustrated in Algorithm 1.Algorithm 1: Key recovery attack on ULC.
Input: randomly choose an 80-bit master key K;Output: the recovered 80-bit master key.Preliminary:randomly choose 232 plaintext-ciphertext pairs (Pi, Ci) (encrypted with K) to construct a set δ;set related keyK′=K⋘61,K79:76'=SboxK79:76.Step 1. Choose two plaintext-ciphertext pairs (Pi, Ci) and (Pj, Cj) from δ;Step 2. Calculate Ci′=ULCPi,K′, Cj′=ULCPj,K′;Step 3. Suppose (Pi, Pj) is a slid pair. Calculate RK'16=PermSboxCi⊕Cj′ , RK1=Sbox−1∘Perm−1Pj⊕Pi. Test whether the relationship of RK'16 and RK1 satisfies the equation (4) in Property 2.(a)
If the relationship ofRK'16 and RK1 satisfies the condition, recover 80-bit K″ according to Property 2, and go to Step 5.(b)
Otherwise, go to Step 1.Step 4. Suppose (Pj, Pi) is a slid pair. Calculate RK'16=PermSboxCj⊕Ci′, RK1=Sbox−1∘Perm−1Pi⊕Pj. Test whether the relationship of RK'16 and RK1 satisfies the equation (5) in Property 2.(a)
If the relationship ofRK'16 and RK1 satisfies the condition, recover 80-bit K″ according to Property 2 and go to Step 5.(b)
Otherwise, go to Step1.Step 5. Encrypt Pi with K″ and ciphertext Ci′ can be derived.(a)
IfCi=Ci′, K″ is the correct master key and output K″;(b)
Otherwise, go to Step 1.The target of Algorithm 1 is to recover the master keyK. There are two preconditions. The first one is a set δ consisting of 232 plaintext-ciphertext pairs encrypted with the master key K and the second one is a related key K′. In our attack, we regard the chosen two plaintexts Pi and Pj as two potential slid pairs with each other, i.e., both (Pi, Pj) and (Pj, Pi) are potential slid pairs. This strategy will improve the search efficiency by about two times faster.The general procedures of the attack are as follows: first, we choose two plaintexts from the setδ, and regard these two plaintexts as two potential slid pairs. We use the two properties in Section 4 to eliminate those nonslid pairs and recover the 80-bit master key as a key candidate. Then we test the remaining key candidates through a plaintext-ciphertext pair to guarantee the correctness of the recovered master key. To sum up, the complexities of our attack are summarized in Table 2.Table 2
Complexities and summary of our attack.
Block cipherRounds attacked/total roundsData complexityMemory complexityTime complexityNumber of related-keysULC15/15O(232)O(232)O(263)1


### 5.1. Complexity Analysis

With Algorithm 1, we can recover all the 80 master key bits. As the slide attack has no constraint on the number of rounds, this implies that our attack can be applied to arbitrary rounds. In this paper, as ULC has a total of 15 rounds, we set the number of our attacks to be 15 as well.As our attack needs 232 plaintext-ciphertext pairs, it means the data complexity is O(232) and memory complexity is also O(232), which is used to store these pairs. According to the birthday paradox, the success probability of the attack is about 63%. There are altogether 232∗ (232 − 1)/2≈263 different pairs of (Pi, Pj) originated from δ. So, the time complexity for our attack is O(263).In addition, if the slid pair does not occur,RK1 and RK′16 can be viewed as random. This implies that if we use (5) of Property 2 as a distinguisher and the slid pair does not occur, the probability of a wrong key candidate to pass the test of the distinguisher is about 2−48. This means we still need an extra plaintext-ciphertext pair to eliminate all the possible wrong key candidates, and this is realized by Step 5 of Algorithm 1.


## 5.1. Complexity Analysis

With Algorithm 1, we can recover all the 80 master key bits. As the slide attack has no constraint on the number of rounds, this implies that our attack can be applied to arbitrary rounds. In this paper, as ULC has a total of 15 rounds, we set the number of our attacks to be 15 as well.As our attack needs 232 plaintext-ciphertext pairs, it means the data complexity is O(232) and memory complexity is also O(232), which is used to store these pairs. According to the birthday paradox, the success probability of the attack is about 63%. There are altogether 232∗ (232 − 1)/2≈263 different pairs of (Pi, Pj) originated from δ. So, the time complexity for our attack is O(263).In addition, if the slid pair does not occur,RK1 and RK′16 can be viewed as random. This implies that if we use (5) of Property 2 as a distinguisher and the slid pair does not occur, the probability of a wrong key candidate to pass the test of the distinguisher is about 2−48. This means we still need an extra plaintext-ciphertext pair to eliminate all the possible wrong key candidates, and this is realized by Step 5 of Algorithm 1.


## 6. Conclusion

In this paper, a related key slide attack on full-round ULC is proposed. As a first step, a property on ULC is presented to characterize a slid pair on ULC. As a second step, a relationship between some of the first round, last round, and master key bits is constructed. Finally, we propose a key recovery attack based on these two properties. Our attack can attack a full-round cipher and recover all the 80 master key bits. For improving the security of ULC, on the one hand, the security margin for ULC is too small, the number of total rounds should be increased. On the other hand, to prevent ULC from slide attack, at least different constants should be added for each round. As related keys are a relatively strong condition for cryptanalysis, other better single key attacks can be explored, which is left as future work.



---

*Source: 4291000-2022-04-23.xml*