DBST: a lightweight block cipher based on dynamic S-box

Liuyan YAN , Lang LI , Ying GUO

Front. Comput. Sci. ›› 2023, Vol. 17 ›› Issue (3) : 173805

PDF (6943KB)
Front. Comput. Sci. ›› 2023, Vol. 17 ›› Issue (3) : 173805 DOI: 10.1007/s11704-022-1677-5
Information Security
RESEARCH ARTICLE

DBST: a lightweight block cipher based on dynamic S-box

Author information +
History +
PDF (6943KB)

Abstract

IoT devices have been widely used with the advent of 5G. These devices contain a large amount of private data during transmission. It is primely important for ensuring their security. Therefore, we proposed a lightweight block cipher based on dynamic S-box named DBST. It is introduced for devices with limited hardware resources and high throughput requirements. DBST is a 128-bit block cipher supporting 64-bit key, which is based on a new generalized Feistel variant structure. It retains the consistency and significantly boosts the diffusion of the traditional Feistel structure. The SubColumns of round function is implemented by combining bit-slice technology with subkeys. The S-box is dynamically associated with the key. It has been demonstrated that DBST has a good avalanche effect, low hardware area, and high throughput. Our S-box has been proven to have fewer differential features than RECTANGLE S-box. The security analysis of DBST reveals that it can against impossible differential attack, differential attack, linear attack, and other types of attacks.

Graphical abstract

Keywords

internet of things / 5G / dynamic S-box / bit-slice technology / lightweight block cipher

Cite this article

Download citation ▾
Liuyan YAN, Lang LI, Ying GUO. DBST: a lightweight block cipher based on dynamic S-box. Front. Comput. Sci., 2023, 17(3): 173805 DOI:10.1007/s11704-022-1677-5

登录浏览全文

4963

注册一个新账户 忘记密码

1 Introduction

5G communication technology is widespread and very popular. 5G is significantly faster than 4G, which ensures real-time data transmission. We are at a critical juncture of the fourth industrial revolution that still revolves around the Internet of Things (IoT) technology. 5G communication technology must be promoted and developed on this basis. When 5G wireless networks transfer, the massive data stream contains much private and sensitive information. It is critical to prevent any information leaks. Therefore, IoT confidential communication has been proposed under 5G. In this case, the encryption algorithms must adapt to the high throughput communication environment and the limited hardware resources.

Recently, several papers on lightweight block ciphers have been published in the international academic community such as PRESENT [1], SCENERY [2], WARP [3], SIMON and SPECK [4], Shadow [5], VH [6], BORON [7], CHAM [8], LVPDA [9], GIFT [10], QTL [11], FPL [12], SFN [13], and RECTANGLE [14]. Bogdanov et al. [1] proposed the lightweight block cipher PRESENT in CHES 2007. The hardware implementation of PRESENT requires 1570GE, which makes it appropriate for severely constrained environments such as sensor networks and RFID tags. In this article, the proposed DBST is based on dynamic S-box for 5G IoT confidential communication devices, which requires high throughput and low hardware implementation. The main design goal of DBST is the dynamic S-box based on bit-slice technology. The bit-slice technology was introduced by Elie Biham [15] to accelerate the implementation of DES. For DBST, we allow the data and the subkey to perform block-to-block logical operations to complete the SubColumns. The approach can obtain different replacing results according to different subkeys in the SubColumns process.

The non-linear S-box is an important component of lightweight block ciphers, which directly affects the security of entire algorithms. An S-box can be classified as either a static or dynamic S-box according to whether the state value is fixed or not. Previous S-boxes are generally static, which must have the smallest differential propagation probability and the lowest linear correlation. Besides, the mixing layer associated with the S-box should propagate the nonlinearity to the entire algorithm. The advantage of static S-boxes is that they can directly demonstrate resistance to linear and differential attacks. Nonetheless, they require more rounds to ensure security and the fixed structure allows for potential attacks [16]. S-box analysis requires analysis of specific S-boxes whether it is differential cryptanalysis or linear cryptanalysis. Hence, the dynamic S-box of DBST improves security and compensates for the shortcomings of static S-boxes.

DBST adopted a new 4-branch generalized Feistel variant structure to balance among security, cost and efficiency. A 2-branch XOR operation was used in the middle part of the structure, which made all branches related to each other. The algorithm passes the avalanche effect requirement and the strict avalanche effect criterion in the second round. The round function has a good avalanche effect and diffusion. It has been demonstrated that DBST has 1697.13GE of hardware resources and 1446.552 Mbps of throughput, so DBST is suitable for high throughput and low hardware resource devices under 5G IoT. DBST primarily includes two aspects: (1) novel generalized Feistel variant structure, and (2) dynamic S-box. The algorithm uses a combination of the bit-slice technique and subkeys to construct a novel dynamic S-box structure.

The layout of the article is as follows: Section 2 discusses the entire design and implementation process of DBST. The design principles for each level are presented in Section 3. Section 4 employs a variety of analysis methods to assess the algorithm’s security. Section 5 discusses its implementation in terms of hardware resources and the comparison of resource consumption between algorithms, and Section 6 summarizes it.

2 The block cipher of DBST

We illustrate the basic process of DBST.

2.1 Symbol definition

We give the definition of all symbols in Tab.1.

2.2 Encryption process

The block size of DBST is 128bit with 32 rounds, which supports 64-bit key. The encryption is shown in Fig.1 and the encryption procedure of DBST is presented in Tab.2.

SubColumns: A 32-bit intermediate calculation data and a 32-bit subkey data are involved in the SubColumns.

Let w31||||w1||w0 represent an intermediate calculation data. The first 8 bits w7||||w1||w0 are treated as W0, the next 8 bits w15||||w9||w8 are treated as W1, so analogy. A 32-bit intermediate calculation data can be depicted as a 4×8 matrix, as shown in Fig.2. Let r31||||r1||r0 represent a subkey data. A 32-bit subkey data can be depicted as a 4×8 matrix in the above way, as illustrated in Fig.3. For convenience, the matrices are presented in two-dimensions, as shown in Fig.4.

Let Wi=wi,7||||wi,1||wi,0 and Ri=ri,7||||ri,1||ri,0 represent the ith rows (i=0,1,2,3). Let W0,W1,W2,W3 and R0,R1,R2,R3 be a 64-bit input and B0,B1,B2,B3 be the 32-bit output of the SubColumns. Let Tj(j=0,,25,26) represent 8-bit temporary variables. The SubColumns can be achieved by the following logical operations of Tab.3.

Function F1: 32-bit subkey XOR first, then Each row is cyclically shifted to the left. Let <<<x represent a circular left shift of x bit(s). Let Bi=ti,7||ti,1||ti,0(i=0,1,2,3) represent the ith row. Except for row 0 without shifting, the remaining rows 1, 2 and 3 are cyclically shifted left by 1, 4 and 5 bits respectively. The steps of function F1 are as follows:

B0=t0,7||t0,1||t0,0<<<0B0=t0,7||t0,1||t0,0,

B1=t1,6||t1,0||t1,7<<<1B1=t1,7||t1,1||t1,0,

B2=t2,3||t2,5||t2,4<<<4B2=t2,7||t2,1||t2,0,

B3=t3,2||t3,4||t3,3<<<5B3=t3,7||t3,1||t3,0.

Function F2: 32-bit subkey XOR first, then Each row is cyclically shifted to the left. Let <<<x represent a circular left shift of x bit(s). Let Bi=ti,7||ti,1||ti,0(i=0,1,2,3) represent the ith row. Except for row 0 without shifting, the remaining rows 1, 2, and 3 are cyclically shifted left by 2, 3, and 6 bits respectively. The steps of function F2 are as follows:

B0=t0,7||t0,1||t0,0<<<0B0=t0,7||t0,1||t0,0,

B1=t1,5||t1,7||t1,6<<<2B1=t1,7||t1,1||t1,0,

B2=t2,4||t2,6||t2,5<<<3B2=t2,7||t2,1||t2,0,

B3=t3,1||t3,3||t3,2<<<6B3=t3,7||t3,1||t3,0.

2.3 Key schedule

DBST accepts 64-bit key. The initial key K=k63||k1||k0 is firstly saved in a key register of the same bit size and formed as a 4×16 matrix, as shown in Fig.5.

The jth row is represented by Yj=kj,15||kj,1||kj,0(0j3). At round i(i=0,1,,31), the 32-bit subkey is composed of the last 2 rows of the key register in the current state, i.e., rkeyi=Y3||Y2. The key register is refreshed in the following way after rkeyi has been extracted:

1) The rkeyi and the rightmost 8 columns of the matrix are involved in dynamic SubColunmns. Let Bj=bj,7||bj,1||bj,0(j=0,1,2,3) be outputs. The permutation result is shown in Fig.6.

2) Completing a linear transformation.

Y0:=(Y0<<<7)Y1

Y1:=Y2

Y2:=(Y2<<<13)Y3

Y3:=Y0

3) Part of key state (k3,15||||k3,10) is XORed with Rcon[t]=t+1(t=0,1,30,31).

k3,15||||k3,10=(k3,15||||k3,10)Rcon[t].

2.4 Decryption process

Due to the high symmetry of the round function, the decryption process of DBST is identical to the encryption process, which simply uses the encryption key in reverse.

3 Design rationale

3.1 DBST structure

The most used structures of lightweight block ciphers are Feistel and SPN. DBST uses a novel generalized Feistel variant structure with 4 high-symmetry branches, which improves the diffusivity of traditional Feistel structures. The Subcolumns is implemented based on bit-slice technology. Due to the structural characteristics, there is no need to consider the inverse process of the SubColumns and the entire decryption algorithm can also recycle the encryption process.

3.2 Dynamic S-box structure based on bit-slice technology

3.2.1 Design criteria

For a n×m S-box, an n-bit binary input will produce an m-bit binary output. From a security performance aspect, the larger the n and m values are, the higher the degree of non-linearity and obfuscation is. From the perspective of implementation efficiency, the larger the S-box used in block ciphers, the more resources it consumes and the lower the cryptographic algorithm implementation efficiency. DBST decided to use the 4×4 S-box to achieve high-efficiency hardware performance and meet lightweight block cipher standards after considerable thought on choosing the size of the S-box.

Definition 1 Permutation. Let S:F2nF2n. For any x,xF2n and xx, there is S(x)S(x), then S is said to be a permutation.

Definition 2 [17] Differential Uniformity. Let f be a function defined on F2nF2n. For any difference corresponding to (a,b)F2n×F2n, define the set Df(ab)={x F2n|f(xa)f(x)=b}and the number of elements in the set Df(ab) as δf(a,b), then the difference uniformity of the function f is δ(f)=maxa0,bδf(a,b) and the function f is said to be δ(f)-uniform.

Definition 3 [17] Linearity. Let f be a function defined on F2nF2n. For any linear combination, define the Walsh transform as:

F2n×F2nZ(a,b)λf(a,b)=xF2n(1)<b,f(x)><a,x>.

Then the linearity of the function f is λ(f)=maxa,bF2n,b0|λf(a,b)| where <b,f(x)> and <a,x> denote the inner product operation.

Definition 4 The difference distribution table of an S-box. Let m,nN, the non-linear mapping from F2n to F2n (also known as the S-box) be denoted as: S:F2nF2n. Given αF2n,βF2n, construct 2n×2n tables with α as the input differential of the S-box and β as the output differential of the S-box. The intersection of rows and columns takes the value Ns(α,β).

INs(α,β)={xF2n:S(xα)S(x)=β},Ns(α,β)=INs(α,β).

Definition 5 Linear approximation table for an S-box. Let m,nN, the non-linear mapping from F2n to F2n (also known as the S-box) be denoted as: S:F2nF2n. Given αF2n,βF2n, construct 2n×2n tables with α as the input mask of the S-box and β as the output mask of the S-box. The intersection of rows and columns takes the value Ns(α,β)2n1.

INs(α,β)={xF2n:αx=βS(x)},Ns(α,β)=INs(α,β).

The design standards of the S-box of DBST are as follows:

1) The S-box satisfies the substitution criterion of Definition 1.

2) The S-box is a 4×4 S-box with differential uniformity δ(s)=maxa0,bδs(a,b)4.

3) The S-box is a 4×4 S-box with linearity λ(S)= maxa,bF24,b0|λs(a,b)|8.

3.2.2 Design of dynamic S-box

The Subcolumns implemented by lookup tables is public in most algorithms. An S-box can be classified as either a static or dynamic S-box whether the state value in the table is fixed or not. Previous algorithm S-boxes are generally static, which must have the smallest differential propagation probability and the lowest linear correlation [16]. In the algorithm, bit-slice technology is introduced into the S-box, so that the SubColumns can be completed not only by the traditional lookup table method but also by logical operations. Moreover, subkeys are added into the logical operations, which makes the S-box present a dynamic form. It compensates for the shortcomings of static S-boxes and lookup tables. We allow the data and the subkey to perform block-to-block logical operations to complete the S-box operation. The S-box is a dynamic related to the key. The dynamic S-box not only has high randomness but also improves algorithm security. In addition, it can effectively resist cipher attacks based on specific S-box analysis. We finally selected four S-boxes to construct the dynamic S-box of DBST after the continuous screening. The experimental results show that DBST S-box has fewer differential features than RECTANGLE S-box, which in turn has higher security.

3.3 F1 and F2 functions structure

In the DBST encryption process, the data is diffused by F1 and F2 functions after the SubColumns. Actually, the SubColumns is equivalent to each column substitution independently. The F1 and F2 functions make each output column depend on other columns, which provide the necessary spread. They use different flows to make the 4-branches of the algorithm round function different. And beyond that, the round key XOR operation also provides good security.

4 Security evaluation

4.1 Avalanche effect

The avalanche effect is an important metric for cryptographic algorithms. Kam, Davida [18] and H. Feistel [19] first proposed the concepts of dependency and the avalanche effect. Afterward, Webster and Tavares [20] introduced the strict avalanche criterion. For DBST, we tested it for completeness dc, avalanche effect da, and strict avalanche effect dsa.

We selected 1000 specific plaintext blocks and randomly changed 1 bit to be some test cases. Tab.4 and Tab.5 show the test results of DBST and PRESENT [21], respectively.

From Tab.4 and Tab.5, we can get that DBST fully meets the dependency requirement and the strict avalanche effect from the 2nd round. The PRESENT fully meets the dependency requirement from the 9th round. The number of rounds for PRESENT and DBST is 31 and 32. So we fully believe that the 32-round DBST meets the avalanche effect criterion.

4.2 Differential cryptanalysis

Differential cryptanalysis [22] is a selective plaintext attack method. The essence of differential cryptanalysis is to study the propagation characteristics of differences in the encryption (decryption) process. The section mainly introduces the differential cryptanalysis of DBST.

We assume that the input difference is a half byte activity. The output differentials are obtained by the S-box differential distribution table. We track the iterative process of 32-round DBST and traverse 360 differential trails, while each round takes the maximum difference probability through the S-box. Finally, The different probability values are shown in Tab.6.

When we use differential attack methods to attack n-bit block ciphers, there must be very few rounds of differential features greater than 21n in the entire encryption process. For DBST, we take the largest differential probability feature. The upper limit of the 32-round difference is 2170<2127. This differential probability is very small, so the 32-round DBST has enough ability to resist differential attack.

4.3 Linear cryptanalysis

In this paper, we obtain the S-box linear approximation table through linear analysis [23] and assume S-box input mask value. Subsequently, The output mask values are determined according to the linear approximation table. We track the iterative process of the DBST round function, traverse 360 input masks, and take the maximum linear approximation probability of the S-box in each round. The results of linear distribution are shown in Tab.7. The upper limit of linear feature probability is 2165. It is very small, so the 32-round DBST has sufficient resistance ability of linear analysis.

4.4 Impossible differential cryptanalysis

Impossible differential cryptanalysis [24] uses a zero difference probability to eliminate a large quantity of candidate keys. The most effective method of finding impossible differences is the intermediate encounter.

Here, we give out the DBST algorithm for 6 rounds of impossible difference. Cross transforms were considered in the final round. 3 rounds of the different trail with the probability of 1 were taken along the encryption direction and 3 rounds of different trail with the probability of 1 were taken along the decryption direction. The result is shown in Tab.8, where “*” represents an uncertain bit. It can be seen that there is a contradiction in round 3. So, once the 3 rounds of DBST reach full dependence, then 32-round DBST will be safe enough to resist impossible differential attack.

4.5 Algebraic cryptanalysis

Algebraic Attack is proposed by Courtois and Pieprzyk in the analysis of AES [25]. It is to transform the attack problem on a cryptographic system into solving corresponding algebraic equations. The S-box is the only nonlinear part of algorithms, which determines the security of DBST. A 4-bit S-box can be indicated by more than 21 quadratic equations. DBST has 4 dynamic S-boxes, so the entire cipher block has m×21 quadratic equations in m×4 variables (m is the number of S-box usage in DBST). DBST has a total of m=24×8+23×8=376 4-bit S-boxes, which is 7896 equations in 1504 variables. Literature [25] uses the working factor to estimate the XSL attack complexity on a block cipher. For DBST, this paper estimates as follows:

Γ=((tr)/s)((tr)/s),WFΓw(Blocksize)wtrs(Numberofrounds)2wtrs>2625.

This far exceeds 2128 operations required for exhaustive search, so the DBST is able to resist algebra attack.

5 Hardware performance

We mainly carry out ASIC and FPGA of DBST to verify its performance. DBST is implemented by Verilog-HDL. In the FPGA hardware implementation, the performance analysis of DBST comprehensive download is performed by ISE14.6 with the FPGA model Xilinx Virtex-5VLX50T. DBST consumes FF, LUTS, and Slices of 199,320, and 102, respectively. Through the test, we found that the clock period of DBST was 2.765 ns. The clock frequency was 361.638 MHz and the throughput was 1446.552 Mbps. In the ASIC hardware implementation, DBST is simulated by ModelSim SE-64 10.4 evaluation, and synthesized into a standard library based on SMIC 0.18 μm CMOS technology. Fig.7 illustrates the datapath of DBST.

During the encryption process, the 128-bit plaintext of DBST requires 576GE for the register. 32-bit data XOR requires 85.44GE and the SubColumns requires 90.57GE. The F1 and F2 functions require the same area resources, respectively 85.44GE. Branch XOR requires 170.88GE. The Hardware implementation of permutation and row shifting is through connection operation, so the hardware resources are 0GE.

The specific resources occupied in the key schedule are described as follows: the 64-bit key is kept in the register and it requires 384GE. The SubColumns requires 90.57GE. One round of Feistel requires 85.44GE. Round counter XOR requires 13.35GE. In the algorithm implementation, a total of 30GE is required for the control logic unit and the counter. The sum of hardware resources is 1697.13GE, as shown in Tab.9. Tab.10 shows the implementation comparison between DBST and other ciphers.

In conclusion, the DBST algorithm has the characteristics of high throughput and low hardware consumption.

6 Conclusion

The proposed DBST is a dynamic S-box lightweight block cipher based on bit-slice technology. Our S-box is key-dependent, which increases the difficulty of differential and linear analysis. The round function consists of a novel generalized Feistel variant structure. It is more diffusible than the traditional Feistel structure. After analysis, we found that DBST met the avalanche effect in the second round. The hardware resources of DBST require 1697.13GE that conforms to low hardware implementation requirements (2000GE). Simultaneously, DBST has a throughput of 1446.552 Mbps, which is higher than most algorithms. It is suitable for 5G IoT devices. Eventually, DBST achieves not only high symmetry but also high security.

References

[1]

Bogdanov A, Knudsen L R, Leander G, Paar C, Poschmann A, Robshaw M J B, Seurin Y, Vikkelsoe C. PRESENT: an ultra-lightweight block cipher. In: Proceedings of the 9th International Workshop on Cryptographic Hardware and Embedded Systems. 2007, 450–466

[2]

Feng J, Li L . SCENERY: a lightweight block cipher based on Feistel structure. Frontiers of Computer Science, 2022, 16( 3): 163813

[3]

Banik S, Bao Z, Isobe T, Kubo H, Liu F, Minematsu K, Sakamoto K, Shibata N, Shigeri M. WARP: revisiting GFN for lightweight 128-bit block cipher. In: Proceedings of the 27th International Conference on Selected Areas in Cryptography. 2020, 535–564

[4]

Beaulieu R, Shors D, Smith J, Treatman-Clark S, Weeks B, Wingers L. The SIMON and SPECK lightweight block ciphers. In: Proceedings of the 52nd Annual Design Automation Conference. 2015, 175

[5]

Guo Y, Li L, Liu B . Shadow: a lightweight block cipher for IoT nodes. IEEE Internet of Things Journal, 2021, 8( 16): 13014–13023

[6]

Dai X, Huang Y, Chen L, Lu T, Su F. VH: a lightweight block cipher based on dual pseudo-random transformation. In: Proceedings of the 1st International Conference on Cloud Computing and Security. 2015, 3–13

[7]

Bansod G, Pisharoty N, Patil A . BORON: an ultra-lightweight and low power encryption design for pervasive computing. Frontiers of Information Technology & Electronic Engineering, 2017, 18( 3): 317–331

[8]

Koo B, Roh D, Kim H, Jung Y, Lee D G, Kwon D. CHAM: a family of lightweight block ciphers for resource-constrained devices. In: Proceedings of the 20th International Conference on Information Security and Cryptology. 2017, 3–25

[9]

Zhang J, Zhao Y, Wu J, Chen B . LVPDA: a lightweight and verifiable privacy-preserving data aggregation scheme for edge-enabled IoT. IEEE Internet of Things Journal, 2020, 7( 5): 4016–4027

[10]

Banik S, Pandey S K, Peyrin T, Sasaki Y, Sim S M, Todo Y. GIFT: a small present: towards reaching the limit of lightweight encryption. In: Proceedings of the 19th International Conference on Cryptographic Hardware and Embedded Systems. 2017, 321–345

[11]

Li L, Liu B, Wang H . QTL: a new ultra-lightweight block cipher. Microprocessors and Microsystems, 2016, 45: 45–55

[12]

Kwon J, Lee B, Lee J, Moon D. FPL: white-box secure block cipher using parallel table look-ups. In: Proceedings of Cryptographers’ Track at the RSA Conference. 2020, 106–128

[13]

Li L, Liu B, Zhou Y, Zou Y . SFN: a new lightweight block cipher. Microprocessors and Microsystems, 2018, 60: 138–150

[14]

Zhang W, Bao Z, Lin D, Rijmen V, Yang B, Verbauwhede I . RECTANGLE: a bit-slice lightweight block cipher suitable for multiple platforms. Science China Information Sciences, 2015, 58( 12): 1–15

[15]

Biham E. A fast new DES implementation in software. In: Proceedings of the 4th International Workshop on Fast Software Encryption. 1997, 260–272

[16]

Chen L K, Zhang R T . Novel software block cipher using dynamic s-box and p-box. Computer Science, 2009, 36( 2): 78–81

[17]

Chabaud F, Vaudenay S. Links between differential and linear cryptanalysis. In: Proceedings of Workshop on the Theory and Application of Cryptographic Techniques. 1994, 356–365

[18]

Kam J B, Davida G I . Structured design of substitution-permutation encryption networks. IEEE Transactions on Computers, 1979, C-28( 10): 747–753

[19]

Feistel H . Cryptography and computer privacy. Scientific American, 1973, 228( 5): 15–23

[20]

Webster A F, Tavares S E. On the design of S-boxes. In: Williams H C, ed. Advances in Cryptology — CRYPTO ’85 Proceedings. Berlin: Springer, 1985, 523–534

[21]

Huang Y H, Dai X J, Shi Y Y, Liu N Z, Zeng Q X, Su F . Ultra-lightweight block cipher algorithm (PFP) based on feistel structure. Computer Science, 2017, 44( 3): 163–167

[22]

Tiwari V, Singh A, Tentu A N . Differential cryptanalysis on DES cryptosystem up to eight rounds. International Journal of Information Privacy, Security and Integrity, 2019, 4( 1): 1–29

[23]

Ashur T, Dunkelman O, Masalha N. Linear cryptanalysis reduced round of piccolo-80. In: Proceedings of the 3rd International Symposium on Cyber Security Cryptography and Machine Learning. 2019, 16–32

[24]

Tolba M, Abdelkhalek A, Youssef A M. Impossible differential cryptanalysis of reduced-round SKINNY. In: Proceedings of the 9th International Conference on Cryptology in Africa. 2017, 117–134

[25]

Courtois N T, Pieprzyk J. Cryptanalysis of block ciphers with overdefined systems of equations. In: Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security. 2002, 267–287

RIGHTS & PERMISSIONS

Higher Education Press

AI Summary AI Mindmap
PDF (6943KB)

2561

Accesses

0

Citation

Detail

Sections
Recommended

AI思维导图

/