ArticlesAll Issue
ArticlesRelated-Key Amplified Boomerang Attack on Full-Round MM-128
• Hyejin Eom, Byoungjin Seok, and Changhoon Lee*

Human-centric Computing and Information Sciences volume 12, Article number: 03 (2023)
https://doi.org/10.22967/HCIS.2023.13.003

Abstract

Recently, the use of open platforms with various network functions and hardware interfaces has been increasing in various fields such as the Internet of Things, smart buildings, and industrial automation. In this new device environment, data-dependent operation (DDO) usage-based cryptographic design based on the control element have been introduced, which is suitable for ensuring high-efficiency performance and network security of the CIA (confidentiality, integrity, accessibility) security model. Among them, the MM-128 proposed by Hieu and his colleagues is a high-speed block cipher that uses the latest FPGA devices to increase the hardware implementation efficiency of block ciphers. It is composed of 9 rounds and uses a 256-bit key. However, most data-dependent permutation (DDP), DDO, and switchable data-dependent operation (SDDOS)-based block ciphers are vulnerable to related-key attacks owing to their simple key scheduling processes, including this paper’s target algorithm MM-128. This paper presents a related-key amplified boomerang attack that is more efficient than an exhaustive attack as the first known result. The attack on MM-128 requires 2^72.5 related-key chosen plaintexts and 2^132.5 encryptions. In future research, this work is expected to be extended and improved with the latest boomerang connectivity table (BCT) and differential-linear connectivity table (DLCT) techniques to obtain better cryptanalytic results.

Keywords

Block Cipher, MM-128, Related-key Amplified Boomerang Attack, Controlled Substitution-Permutation Network (CSPN), Data-Dependent Operations (DDOs)

Introduction

As a result of the rapid development of Internet of Things (IoT) technology, sensor networks, healthcare, distributed control systems and virtual physical systems, which belong to related industrial fields, are growing together. The majority of devices that use IoT technology in these fields are small computing devices used in everyday life. These IoT devices risk exposure to various types of hacking and cracking because they use big data such as the sensitive personal information of users, voice/video DB, and various life information in order to provide users with convenient and useful services. However, since the available resources of IoT devices are limited, it is difficult to secure safety with the encryption algorithm used in the existing server or the PC environment as it is. Therefore, in a restricted IoT environment, the network not only handles unauthorized access to systems and data, but also requires specific security requirements to ensure suitability, portability and applicability for software and hardware performance when operating and integrating in these environments. In addition, the need for encryption algorithms that can guarantee an appropriate level of safety and efficiency at a lower cost than existing algorithms is increasing, and this is becoming increasingly important as IoT technology continues to develop. To address such issues, the most prominent solution focuses on improving the protection of cipher designs by distinct switch operations and functions; for example, data-dependent permutation (DDP)-based constructions such as CIKS-1 [1], Cobra-H64/128 [2] and SCO-family [3]; advanced data-dependent operations (DDO) designs such as CIKS-1 [1], CIKS-128 [4], MD-64 [5], DDP-64 [6], TMN-64, and TMN-128 [7]; or switchable data-dependent operations (SDDO) designs such as XO-64 [8] and BM123-64 [9]. Because these algorithms use a very simple key schedule, they are highly efficient when applied to an environment in which the secret key is frequently changed. However, most algorithms are vulnerable to differential cryptanalysis attacks due to the linearity and simply designed key schedule of DDPs [1017]. To overcome these problems, Hieu et al. [18] proposed a new DDO-based block cipher, MM-128, which has a block size of 128 bits and consists of a 256-bit secret key and 9 rounds. It was designed by combining new concepts in an attempt to obtain better capabilities and properties in DDO and CSPN (controlled substitution-permutation network) frameworks. The authors introduced a new class of $F_{(2/4)}$ type CE (controlled elements) as cryptographic primitives suitable for the design of FPGA-efficient DDO boxes. $F_{(2/4)}$ shows higher nonlinearity and improved hardware implementation efficiency. However, this paper shows that their simple key schedules and structural weaknesses make this cipher vulnerable to related-key attacks. The proposed amplified boomerang attack requires about $2^{72.5}$ in terms of the complexity of data, $2^{76.5}$ memory bytes and $2^{132.5}$ encryptions for MM-128. This cryptanalytic result means that the MM-128 constructions, as in existing studies of DDP-based or DDO-based schemes, are still vulnerable to and insecure against related-key differential cryptanalysis. This paper is organized as follows. Section 2 describes the related-key amplified boomerang attack; Section 3 briefly introduces the block cipher, MM-128; Sections 4 and 5 introduces the extended associated key boomerang attack on MM-128; and, finally, Section 6 presents the conclusion.

Related-Key Amplified Boomerang Attack

The related-key differential cryptanalysis was introduced by Biham [19]. It is an upgraded model of the related key boomerang attack developed by Wagner [20] and Biham et al. [21] as a pure adaptive chosen-plaintext attack. In particular, it has become an effective cryptographic analysis technique, and has been applied to a variety of cryptographic mechanisms, as the target of the attack aims to exploit two uniquely related key differential properties to find the correct quartet with a high probability. This attack scenario provides high efficiency and high probability for certain DDO-based ciphers, such as DDO-64 [6], XO-64 [8], MD-64 [5], BM123-64 [9],TMN-64 [7], and TMN-128 [7].

Fig. 1. Related-key amplified boomerang distinguisher.

If the plaintext quartet (P, $P^*$, $P^{'}$, $P^{'*}$) goes through three steps, the related key amplified boomerang attack model outputs the correct quartet. A correct plaintext quartet must satisfy the following four conditions for a delta test:

MM-128 Block Cipher Description

Preliminaries
In this section, we notice some notations being used through the whole paper. The cipher X=($x_1$,…,$x_n$) is assigned with $x_1$ and $x_n$ which are the most significant bit and the least significant bit, respectively.
The related-key amplified boomerang attack is combined with the related differential components of block ciphers, like the input, output, and key of a round function.
- r: round function of a block cipher.
- Δ$Q_r$, Δ$U_r$ : round key difference values for each round r.
- Δ$X_r$ / Δ$Y_r$ : input / output difference values for each round r.
- $e_{i,j}$: binary data bits adjusted for round r, as active bit values i and j; at the i^th and j^th value are ones, and the others are zeros for each block data (e.g., $e_{2.3}$ = (0, 1, 1, 0, 0,…, 0)).
- ⨁ : bitwise XOR operation.
- ＜＜ : cyclic rotation to the left by b bits.

MM-128 Construction

Fig. 2 Round function $Crypt^{(e)}$ of MM-128.

Fig. 3 (a) Controlled elements $F_{2/4}$. (b) Expressed in the form of a pair of Boolean functions. (c) Variants of the differences for CEs $F_{2/4}$.
Fig. 4
Fig. 5

To analyze the properties of CEs $F_{2/4}$ defined by the F(i) correction set, we describe the first and second output values of i=0,1,2,…,15 CEs $F_{2/4}$. The Boolean functions (BFs) $f_1$ and $f_2$ can be built easily for a set of 16 ordered pairs of BFs in two variables, each describing one of the 16 modified F(i) cases, where i=0,1,2,…,15, which defines several variants of the element $F_{2/4}$. There are 10 different BF pairs in two variables, which describes the basic S-box, which is the involution. Each of the 10 possible BF pairs in the two variables describing the modification of F(i) (i=0,1,2,…,15) can be constructed easily using their schematic representation, as shown in Fig. 6.

Fig. 6 Schematic representation of the various conventional transformations ($x_1$,$x_2$)→($y_1$,$y_2$) that are the involution.

The concrete format of the two BFs for implementing CEs $F_{2/4}$ can then be obtained from the following two formulae:

The CEs $F_{2/4}$, related to variant 4 of Table 1, was used to design the block cipher MM-128, which stands for an eight-round repeating block cipher with a block of 128-bit data. Fig. 3(c) shows the variants of all possible differences related to the $F_{2/4}$ type CEs. The key schedule of MM-128 is constructed in a very simple manner, where the 256-bit secret key K is split into four 64-bit sub-keys; K=($K_1$,$K_2$,$K_3$,$K_4$). The key schedule of the algorithm is specified as shown in Table 2.

Table 1. Examples of the sets of F(i) modifications
 No. The value of the non-inearity  of BF NL($f_1$)- NL($f_2$)-NL($f_3$) Set of modifications 1 22-24-22 a/b/d/e/f/g/h/i/a/b/c/e/f/g/e/j 2 22-24-22 a/b/d/e/f/g/h/j/a/d/e/f/g/h/g/i 3 24-22-22 a/b/d/e/f/h/i/j/a/b/c/e/g/h/g/j 4 22-22-24 a/b/d/e/g/h/i/j/b/d/e/f/g/h/i/g

Table 2. Key scheduling in MM-128
 j=1 j=2 j=3 j=4 j=5 j=6 j=7 j=8 j=9 $K_1$ $K_2$ $K_3$ $K_4$ $K_4$ $K_1$ $K_3$ $K_4$ $K_1$ $K_3$ $K_4$ $K_2$ $K_1$ $K_2$ $K_3$ $K_2$ $K_3$ $K_2$ $K_1$ $K_3$ $K_2$ $K_3$ $K_2$ $K_1$ $K_2$ $K_4$ $K_3$ $K_2$ $K_4$ $K_3$ $K_1$ $K_4$ $K_4$ $K_3$ $K_2$ $K_1$

The extension box E is defined as

where represents the cyclic rotation of the vector X=($x_1$,…,$x_{32}$) to the left by b bits. The permutation involution I_1 is described as follows:

(1)(2,9)((3,17)(4,25)(5,33)(6,41)(7,49)(8,57)(10)(11,18)(12,26)(13,34)(14,42) (15,50)(16,58)(19)(20,27)(21,35)(22,43)(23,51)(24,59)(28)(29,36)(30,44)(31,52) (32,60)(37)(38,45)(39,53)(40,61)(46)(47,54)(48,62)(55)(56,63)(64).

Related-Key Amplified Boomerang Characteristics of MM-128

This section discusses the way of establishing the related-key differential boomerang characteristics with high probability based on the differential properties of MM-128.

Key Recovery Attacks on MM-128

This section presents a key recovery attack on MM-128 using a related-key amplified boomerang distinguisher.

Related-Key Amplified Boomerang Key Recovery Attack

Table 3. Two related-key differential characteristics with a probability of approximately $2^{-5}$ of the 7.5 round MM-128

Fig. 7. Related-key amplified boomerang distinguisher of MM-128.

The first related-key differential characteristic for $E^0$ is ($e_{64}$,0) → (0,0) with probability 1 because the input difference to round 1 is canceled by the key difference of the first round, and the zero difference remains up to the output of the second to third rounds. The resultant probability p is 1. The second related-key differential characteristic for rounds 4–7.5($E^1$) is ($e_{64}$, $e_{64}$,) → ($e_{64}$,0) with probability (36/64)^6 (≈2^(-5)). The details of this result are presented in Figs. 8–10. The difference between the input of the 4^th round ($e_{64}$,$e_{64}$) and the sub-key difference of the $4^{th}$ round ($e_{64}$,0) is the probability $2^{-5}$, and the output difference becomes (0,$e_{64}$). Also, the input difference of round 5 is canceled by the sub-key difference of round 5, and zero difference is maintained until round 7, after which the input difference of the 7.5th round is (e_64,0), and the sub-key difference of the 8^th round is ($e_{64}$,0). The resulting probability q is also ≈ $2^{-5}$.

Fig. 8. Propagation in the MM-128 round function in the first round and for the $2^{nd}$→7.$5^{th}$ rounds.

Fig. 9.

Fig. 10. Differential distribution table of $F_{2/4}$.

where t = $2^{143}$.
In fact, for some incorrect key guesses (especially those whose differences from the right key are small), decrypted cipher-text quartets do not behave randomly; however, for each such key the probability that a decrypted cipher-text quartet passes Step 2(b) is still much lower than the probability of the proposed 7.5-round related-key amplified boomerang distinguisher; in this study’s observation, its probability is less than or equal to the earlier case due to the differential properties of the DDO-boxes. Thus, the probability that the output of the above attack algorithm is a wrong sub-key quartet is upper bounded by

where t = $2^{143}$.
On the other hand, the probability that the number of quartets for the right sub-key is no less than 6 is about

where t = $2^{143}$, as each decrypted cipher-text quartet for the right key passes Step 2(b) with a probability of ≈ $2^{-128}$ due to the proposed 7.5-round related-key amplified boomerang distinguisher. Therefore, the success rate of this attack is about 0.99.

Conclusion

Previously, the DDO-based cipher MM-128 was designed to realize the rapid implementation of hardware and a high level of security by using a new class of $F_{2/4}$ type CE suitable for FPGA. However, this paper discusses the first cryptanalytic result of the MM-128 cipher, and constructs the differential characteristics of a full 9-round of MM-128 cipher with high probability base on some differential properties combined with a simple key schedule within the MM-128 structure. It then presents a related-key amplified boomerang attack on a full-round MM-128 with $2^{72.5}$ related-key chosen plaintexts, $2^{76.5}$ memory bytes, and time complexity of $2^{132.5}$. Our cryptanalytic result means that the full-round reduced MM-128 can be distinguished from an ideal cipher very efficiently, but remains vulnerable to related-key differential attacks owing to its simple key schedule algorithms and structural weaknesses. Future research could include a better primitive approach to the design of the block ciphers, especially structures based on the DDP, DDO or SDDO functions.

Author’s Contributions

Conceptualization, HE, CR. Funding acquisition, CR. Investigation and methodology, HE, CR. Project administration, HE. Resources, HE, BS. Supervision, CR. Writing of the original draft, HE. Writing of the review and editing, HE. Software, HE, BS. Validation, HE, BS. Formal analysis, CR. Data curation, HE, BS. Visualization, HE.

Funding

This research was supported by the Energy Cloud R&D Program (No. 2019M3F2A1073386) through the NRF (National Research Foundation of Korea), both of which are funded by the Ministry of Science and ICT.

Competing Interests

The authors declare that they have no competing interests.

Author Biography

Name: Hyejin Eom
Affiliation: Seoul National University of Science & Technology
Biography: Hyejin Eom received her B.A in Mathematics and M.A in Statistics from Hanyang University. She is pursuing the Ph.D degree in Computer Science and Engineering with Cryptography and Information Security(CIS) Lab. in Seoul National University of Science & Technology, Seoul, South Korea. Her current research interests are information security, cryptography.

Name: Byoungjin Seok
Affiliation: Seoul National University of Science & Technology
Biography: Byoungjin Seok received the B.S and M.S. degree in Computer Science and Engineering from Seoul National University of Science & Technology, Seoul, South Korea. He is a Ph.D candidate at Computer Science and Engineering with Cryptography and Information Security(CIS) Lab in Seoul National University of Science & Technology, Seoul, South Korea. His current research interests include Information Security, Cryptography, and Digital Forensics.

Name: Changhoon Lee
Affiliation: Seoul National University of Science & Technology
Biography: He received his Ph.D. degree in Graduate School of Information Management and Security (GSIMS) from Korea University, Korea. In 2008, he was a research professor at the Center for Information Security Technologies in Korea University. In 2009-2011, he was a professor in the School of Computer Engineering in Hanshin University. He is now a professor at the Department of Computer Science and Engineering, Seoul National University of Science and Technology(SeoulTech), Korea. He has been serving not only as chairs, program committee, or organizing committee chair for many international conferences and workshops but also as a (guest) editor for international journals by some publishers. His research interests include Cyber Threats Intelligence(CTI), Information Security, Cryptography, Digital Forensics, IoT Security, Computer Theory etc. He is currently a member of the IEEE, IEEE Computer Society, IEEE Communications, IACR, KIISC, KDFS, KIPS, KITCS, KMMS, KONI, and KIIT societies.

References

[1] A. A. Moldovyan and N. A. Moldovyan, “A cipher based on data-dependent permutations,” Journal of Cryptology, vol. 15, no. 1, pp. 61-72, 2002.
[2] N. Sklavos, N. A. Moldovyan, and O. Koufopavlou, “High speed networking security: design and implementation of two new DDP-based ciphers,” Mobile Networks and Applications, vol. 10, no. 1, pp. 219-231, 2005.
[3] N. A. Moldovyan, “On cipher design based on switchable controlled operations,” in Computer Network Security. Heidelberg, Germany: Springer, 2003, pp. 316-327.
[4] N. A. Iavos, N. A. Moldovyan, and O. Koufopavlou, “A new DDP based cipher CIKS-128h architecture design LSI implementation optimization of CBC encryption hashing over 1Gbps,” in Proceedings of 2003 46th Midwest Symposium on Circuits and Systems, Cairo, Egypt, 2003, pp. 463-466.
[5] N. H. Minh, D. Bac, and H. Duy, “New SDDO-based block cipher for wireless sensor network security,” International Journal of Computer Science and Network Security, vol. 10, no. 3, pp. 54-60, 2010.
[6] N. A. Moldovyan and A. A. Moldovyan, Data-Driven Ciphers for Fast Telecommunication Systems. Boca Raton, FL: Auerbach Publications, 2008.
[7] P. M. Tuan, B. Do Thi, M. N. Hieu, and N. Do Thanh, “New block ciphers for wireless moblile netwoks,” in Advances in Information and Communication Technology. Cham, Switzerland: Springer, 2017, pp. 393-402.
[8] N. H. Minh, H. N. Duy, and L. H. Dung, “Design and estimate of a new fast block cipher for wireless communication devices,” in Proceedings of 2008 International Conference on Advanced Technologies for Communications, Hanoi, Vietnam, 2008, pp. 409-412.
[9] B. D. Thi and M. N. Hieu, “High-speed block cipher algorithm based on hybrid method,” in Ubiquitous Information Technologies and Applications. Heidelberg, Germany: Springer, 2014, pp. 285-291.
[10] T. S. D. Phuc, Y. H. Shin, and C. Lee, “Recovery-key attacks against TMN-family framework for mobile wireless networks,” KSII Transactions on Internet and Information Systems (TIIS), vol. 15, no. 6, pp. 2148-2167, 2021.
[11] Y. Ko, C. Lee, S. Hong, J. Sung, and S. Lee, “Related-key attacks on DDP based ciphers: CIKS-128 and CIKS-128H,” in Progress in Cryptology – INCOCRYPT 2004. Heidelberg, Germany: Springer, 2004, pp. 191-205.
[12] C. Lee, J. Kim, J. Sung, S. Hong, S. Lee, and D. Moon, “Related-key differential attacks on Cobra-H64 and Cobra-H128,” in Cryptography and Coding. Heidelberg, Germany: Springer, 2005, pp. 201-219.
[13] J. Kang, K. Jeong, C. Lee, and S. Hong, “Distinguishing attack on SDDO-based block cipher BMD-128,” in Ubiquitous Information Technologies and Applications. Heidelberg, Germany: Springer, 2014, pp. 595-602.
[14] T. S. D. Phuc, N. N. Xiong, and C. Lee, “Cryptanalysis of the XO-64 suitable for wireless systems,” Wireless Personal Communications, vol. 93, no. 2, pp. 589-600, 2017.
[15] C. Lee, J. Kim, S. Hong, J. Sung, and S. Lee, “Security analysis of the full-round DDO-64 block cipher,” Journal of Systems and Software, vol. 81, no. 12, pp. 2328-2335, 2008.
[16] J. Kang, K. Jeong, S. S. Yeo, and C. Lee, “Related-key attack on the MD-64 block cipher suitable for pervasive computing environments,” in Proceedings of 2012 26th International Conference on Advanced Information Networking and Applications Workshops, Fukuoka, Japan, 2012, pp. 726-731.
[17] J. Kelsey, T. Kohno, and B. Schneier, “Amplified boomerang attacks against reduced-round MARS and Serpent,” in Fast Software Encryption. Heidelberg, Germany: Springer, 2000, pp. 75-93.
[18] M. N. Hieu, D. H. Ngoc, C. H. Ngoc, T. D. Phuong, and M. T. Cong, “New primitives of controlled elements F2/4 for block ciphers,” International Journal of Electrical and Computer Engineering, vol. 10, no. 5, pp. 5470-5478, 2020.
[19] E. Biham, “New types of cryptanalytic attacks using related keys,” Journal of Cryptology, vol. 7, no. 4, pp. 229-246, 1994.
[20] D. Wagner, “The boomerang attack,” in Fast Software Encryption. Heidelberg, Germany: Springer, 1999, pp. 156-170.
[21] E. Biham, O. Dunkelman, and N. Keller, “Related-key boomerang and rectangle attacks,” in Advances in Cryptology - EUROCRYPT 2005. Heidelberg, Germany: Springer, 2005, pp. 507-525.
[22] C. Cid, T. Huang, T. Peyrin, Y. Sasaki, L. Song, “Boomerang Connectivity Table: A New Cryptanalysis Tool,” in: J. Nielsen, V. Rijmen (eds), Advances in Cryptology-EUROCRYPT 2018, LNCS 10821, 683-714, 2018.
[23] A. Bar-On, O. Dunkelman, N. Keller, A. Weizman, “DLCT: A new tool for differential-linear cryptanalysis,” in : Y. Ishai, V. Rijmen (Eds): EUROCRYPT 2019, LNCS 11476, pp. 313-342, 2019.

Hyejin Eom, Byoungjin Seok, and Changhoon Lee*, Related-Key Amplified Boomerang Attack on Full-Round MM-128, Article number: 12:03 (2023) Cite this article 2 Accesses