# Improved Single-Key Attacks on 2-GOST

Authors: Qiuhua Zheng; Yinhao Hu; Tao Pei; Shengwang Xu; Junzhe Yu; Ting Wu; Yanzhao Shen; Yingpei Zeng; Tingting Cui
Journal: Security and Communication Networks
 (2020)

---

## Abstract

GOST, known as GOST-28147-89, was standardized as the Russian encryption standard in 1989. It is a lightweight-friendly cipher and suitable for the resource-constrained environments. However, due to the simplicity of GOST’s key schedule, it encountered reflection attack and fixed point attack. In order to resist such attacks, the designers of GOST proposed a modification of GOST, namely, 2-GOST. This new version changes the order of subkeys in the key schedule and uses concrete S-boxes in round function. But regarding single-key attacks on full-round 2-GOST, Ashur et al. proposed a reflection attack with data of232 on a weak-key class of size 2224, as well as the fixed point attack and impossible reflection attack with data of 264 for all possible keys. Note that the attacks applicable for all possible keys need the entire plaintext space. In other words, these are codebook attacks. In this paper, we propose single-key attacks on 2-GOST with only about 232 data instead of codebook. Firstly, we apply 2-dimensional meet-in-the-middle attack combined with splice-cut technique on full-round 2-GOST. This attack is applicable for all possible keys, and its data complexity reduces from previous 264 to 232. Besides that, we apply splice-cut meet-in-the-middle attack on 31-round 2-GOST with only data of 232. In this attack, we only need 8 bytes of memory, which is negligible.


---

## Body

## 1. Introduction

GOST block cipher [1] is known as GOST-28147-89 designed during the 1970s by the Soviet Union. It was standardized as the Russian encryption standard in 1989. As a lightweight-friendly block cipher, GOST is suitable for the resource-constrained environments such as RFID tags and sensor nodes.GOST’s block size is 64 bits and key size is 256 bits. Round function adopts Feistel construction, in which there are a modular addition with subkey, 8 S-boxes and one rotation operation. However, the S-boxes used in GOST are not specified in the standard document. Each industry can use its own secret favored set of S-boxes to enhance the security of GOST. For example, the S-boxes used in the Central Bank of the Russian Federation is known in [2]. Besides that, the key schedule of GOST is extremely simple. 256-bit master key is divided into eight 32-bit words; then the 32-bit subkeys used in different round functions directly extract from these 8-word keys according to a special order.Due to the simplicity of GOST’s key schedule, two attacks on full-round GOST were published by Isobe in [3] and Dinur et al. in [4] in 2011. In [3], Isobe combined the reflection property and meet-in-the-middle (MITM) attack to propose the single-key attack on full-round GOST. As a result, the key can be recovered with 2224 computations and 232 known plaintexts. In [4], Dinur et al. introduced a new fixed point property as well as a better way to improve the attacks on full-round GOST. Given 232 data, the memory complexity can reduce from 264 to 236 with the same time complexity 2224. Given 264 data, the time complexity can be down to 2192. Although these attacks are not practical, they indicate the a priori in security of GOST.In order to resist reflection attack and fixed point attack, the designers of GOST proposed a modification of GOST block cipher, named, 2-GOST [5]. In the new modification, there are two differences from original GOST. Firstly, the authors retained the same principle for key schedule as in GOST but changed the order of subkeys against existed attacks. Secondly, two concrete S-boxes were specified in the design document of 2-GOST for convenient cryptanalysis and better implementation.Unfortunately, full-round 2-GOST still encounters reflection attack and fixed point attack. At FSE’17, Ashur et al. [6] proposed single-key attacks on it. Given 232 data, the key can be recovered with 2192 computations by reflection attack. However, this attack only works for 2224 out of 2256 possible keys, which means this is a weak-key attack. For sake of valid for all possible keys, the authors proposed impossible reflection attack and fixed point attack. Both need 264 known plaintexts. In other words, these are codebook attacks, since they use the entire plaintext space. These results are summarized in Table 1.Table 1
Summary of attacks on 2-GOST under single-key setting.
Attack typeRoundsDataTimeMemory (bytes)No. of keysSourceReflection32232KP2190.2268.62224[6]Impossible reflection32263CP2252.52166.62256−2224[6]Impossible reflection32264KP2253.52166.62256−2224[6]Fixed point32264KP22362138.2All[6]2-D MITM32232CP22522228AllSection4MITM31232CP2252.98AllSection5(i) The unit of time complexity is one full-round encryption; (ii) 2D MITM: 2-dimensional meet-in-the-middle attack; (iii) CP: chosen plaintext; KP: known plaintext.In this paper, our motivation is to propose attacks on 2-GOST with about232 data instead of codebook, further to indicate that the key schedule in modification version 2-GOST is not a good choice yet. Our contributions are summarized as follows:2-dimensional MITM attack on full-round 2-GOST2-dimensional MITM attack was proposed by Zhu and Gong in [7] to attack KATAN. Then, it has been applied on TWINE [8], GOST [4], and so on. This attack can improve the performance of general MITM attack, but attackers must be careful about the time complexity of accessing tables. In this paper, we apply 2-dimensional MITM attack combined with splice-cut technique [9] on full-round 2-GOST exploiting the weakness in key schedule. This attack is applicable for all possible keys with time complexity of 2252 full-round encryptions and memory complexity of 2228 bytes. Furthermore, the data reduced from previous 264 (codebook) to 232 chosen plaintexts under single-key setting. The result is shown in Table 1.Splice-cut MITM attack on 31-round 2-GOSTBased on some observations on key schedule and modular addition in the round function of 2-GOST. We apply MITM attack combined with splice-cut technique on reduced 31-round 2-GOST (0∼30 rounds). This attack is applicable for all possible keys with data complexity of 232 chosen plaintexts and time complexity of 2252.9 full-round encryptions. It is important to stress that we only use 8-byte memory in this attack which is negligible. The result is shown in Table 1.This paper is organized as follows. In Section2, we introduce the specifications of GOST and 2-GOST. Then, in Section 3, we briefly describe the general MITM attack, splice-cut MITM attack, and 2-dimensional MITM attack. In Sections 4 and 5, we propose the 2-dimensional MITM attack on full-round 2-GOST and splice-cut MITM attack on 31-round 2-GOST, respectively. Lastly, we summarize this paper in Section 6.


## 2. Specifications of GOST and 2-GOST

GOST [1] is a bit-wise lightweight block cipher proposed by the Soviet Union. Its block size is 64 bits, key size is 256 bits, and total rounds are 32. GOST adopts Feistel construction as its round function, in which there are a nonlinear layer composed of eight bijective 4-bit S-boxes Si,i=0,1,…,7 and a linear layer only containing a left rotation ⋘11. Especially, subkeys are mixed with internal state by modular addition ⊞ instead of traditional XOR. Please see the round function depicted in Figure 1.Figure 1
Round function of GOST.The S-boxesSi:F24⟶F24,i=0,1,…,7 used in GOST are bijective but not specified in the standard document. Each industry can choose its own secret favored set of S-boxes to enhance the security of GOST. Please refer to an example, the S-boxes used in the Central Bank of the Russian Federation in [2].GOST’s key schedule is extremely simple. Each subkey uses one word (32 bits) of master key directly. Assume the master keyK is divided into eight words K=K0K1K7, each subkey ki used in round function Fi,i=0,1,…,31 adopts one of K0, K1, …, K7. In detail, the first 24 rounds periodically use K0, K1, …, K7 as subkeys in ascending order; that is, that ki+8j = Ki, where i=0,1,…,7 and j=0,1,2. The last 8 rounds use K0, K1, …, K7 as subkeys in descending order; that is, that ki = K31−i, i=24,25,…,31. All subkeys are summarized in Table 2.Table 2
Key schedule of GOST.
Round012345678910111213141516171819202122232425262728293031SubkeyK0K1K2K3K4K5K6K7K0K1K2K3K4K5K6K7K0K1K2K3K4K5K6K7K7K6K5K4K3K2K1K02-GOST [5] is the modified version of GOST. It was proposed by the same designers of GOST for the purposed of fixing weaknesses in key schedule against reflection attack and fixed point attack. The differences between 2-GOST and GOST are selection of S-boxes and the order of subkeys in the key schedule. Unlike uncertain S-boxes used in GOST, 2-GOST adopts two concrete bijective S-boxes. Since we only use the bijective property of S-box in this paper, we omit the specification of S-box here. Besides that, 2-GOST uses another order of subkeys comparing with GOST, which is summarized in Table 3.Table 3
Key schedule of 2-GOST.
Round012345678910111213141516171819202122232425262728293031SubkeyK0K1K2K3K4K5K6K7K3K4K5K6K7K0K1K2K5K6K7K0K1K2K3K4K6K5K4K3K2K1K0K7


## 3. Meet-in-the-Middle Attack

In this section, we will briefly recall general meet-in-the-middle (MITM) attack [10] combined with splice-cut technique [9] and 2-dimensional MITM attack [7].


### 3.1. General MITM Attack

The general MITM attack has two phases, one is the MITM phase and the other one is the brute-force testing phase.Assume ann-bit block cipher ℰ with k-bit secret key K is divided into two subciphers ℰ1, ℰ2, while K is divided into three key parts K1, K2, and K3. K1 is only used in ℰ1 and K2 is only used in ℰ2 and K3 is the rest of K. The framework of general MITM attack is shown in Figure 2 and the steps of this attack is summarized as follows.Figure 2
General MITM attack.(i)
MITM phase: given a plaintext-ciphertextP,C.(1)
For each possibleK3, guess each possible K1, then compute v=ℰ1P, and store all possible K1 into a table S indexed by v.(2)
For each possibleK2, compute the v′=ℰ2−1C, then access the v′-th entity of table S to extractK1. Current (K1, K2, and K3) is a candidate key.(ii)
Brute-force testing phase:(1)
Test every candidate key with other plaintext/ciphertext pairs until only the right key is remained.After the MITM phase, we get2k−n=2K1+K2/2n×2K3 candidate keys. In brute-force testing phase, the attacker exhaustively searches the true key by using extra plaintext/ciphertext pairs. Finally, the time complexity Ccomp of the attack in total is(1)Ccomp=2K3×2K1+2K2︸MITM phase+2k−n+2k−2n+2k−3n+⋯︸brute−force testing phase.The required plaintext/ciphertext pairs isk/n, while the memory cost is min(2K1, 2K2) memory blocks.Note that the “Partial Matching” technique [9] can be used to improve the performance of some MITM attacks. In such case, the matching point v,v′ is only l bits instead of n bits, so some bits of key in K1, K2, and K3 need not be involved in.


### 3.2. Splice-Cut MITM Attack

In the chosen plaintext and chosen ciphertext settings, the first and the last rounds of the block cipher can be regarded as two successive rounds. Aoki and Sasaki applied splice-cut technique into MITM attack [9].Assume ann-bit block cipher ℰ with k-bit secret key K is divided into three subciphers ℰ1, ℰ2, and ℰ3, while K is divided into three key parts K1, K2, and K3. K1 is only used in ℰ1 and ℰ3, K2 is only used in ℰ2, and K3 is the rest of K. The framework of splice-cut MITM attack is shown in Figure 3, and the steps of the attack are summarized as follows:Figure 3
Splice-cut MITM attack.(i)
MITM phase:For each possibleK3, (1)
Choose ann-bit state value P′.(2)
Guess each possibleK1, then compute the v=ℰ3−1∘ℰ∘ℰ1−1P′, and store all K1 into a table S indexed by v.(3)
For each possibleK2, compute the v′=ℰ2P′, then access the v′-th entity of table S to extract K1. Current (K1, K2, K3) is a candidate key.(iii)
Brute-force testing phase:(1)
Test every candidate key with other plaintext/ciphertext pairs until only the right key is remained.The time and memory complexities are same as those in general MITM attack. However, the data complexity depends onℰ1 and K1. Assume that m bits of plaintext P are not affected by K1 when we compute P=ℰ1−1P′; we can fix such m bits of plaintext as a constant in advance and then choose suitable P′. As a result, the data complexity is 2n−m.


### 3.3. Dimensional MITM Attack

This attack was proposed in [7]. It is suitable to attack ciphers whose key size is larger than block size.Assume ann-bit block cipher ℰ with k-bit secret key K is divided into four subciphers ℰ1, ℰ2, ℰ3, and ℰ4. Key part Ki is used in subcipher ℰi, i=1,2,3,4. The framework of 2-dimensional MITM attack is shown in Figure 4 and the steps of the attack is summarized as follows.Figure 4
2-dimensional MITM attack.(i)
MITM phase:(1)
For each possibleK1, compute v1=ℰ1P, and put K1 into table S1 indexed by the value of v1;(2)
For each possibleK4, compute v2=ℰ4−1C, and put K4 into table S2 indexed by the value of v2;(3)
For each possible value ofa:(a)
For each possibleK2, compute the v1′=ℰ2−1a, and check if v1′ is in table S1. If so, put (K1,K2) into table S3.(b)
For each possibleK3, compute v2′=ℰ3a and check if v2' is in table S2. If so, check if (K3,K4) is also in table S3. If true, current (K1, K2, K3, K4) is a candidate key.(ii)
Brute-force testing phase:(1)
Test every candidate key with other plaintext/ciphertext pairs until only the right key is remained.For each possible value of a, there are2k−v1−v2 candidate keys remained. After the MITM phase, we totally get 2a×2k−v1−v2=2a+k−v1−v2 candidate keys. In brute-force testing phase, the attacker exhaustively searches the true key by using extra plaintext/ciphertext pairs. Finally, the time complexity Ccomp of the attack in total is(2)Ccomp=2K1+2K4+2a×2K2+2K3︸MITM phase+2a+k−v1−v2+2a+k−v1−v2−n+2a+k−v1−v2−2n+⋯︸brute−force testing phase.In such attack, the data complexity isk/n, while the memory complexity happens to store tables Si, i=1,2,3.Remark.
In the 2-dimensional MITM attack model, the time of accessing tables is omitted in step 3b. However, it is much possible to be the main time complexity in some attacks. For example, Wen et al. indicated in [11] that the actual time complexity of 2-dimensional MITM attack on TWINE proposed in [8] exceeded the brute-force time. So in our attack on 2-GOST, we will take this part time into consideration.


## 3.1. General MITM Attack

The general MITM attack has two phases, one is the MITM phase and the other one is the brute-force testing phase.Assume ann-bit block cipher ℰ with k-bit secret key K is divided into two subciphers ℰ1, ℰ2, while K is divided into three key parts K1, K2, and K3. K1 is only used in ℰ1 and K2 is only used in ℰ2 and K3 is the rest of K. The framework of general MITM attack is shown in Figure 2 and the steps of this attack is summarized as follows.Figure 2
General MITM attack.(i)
MITM phase: given a plaintext-ciphertextP,C.(1)
For each possibleK3, guess each possible K1, then compute v=ℰ1P, and store all possible K1 into a table S indexed by v.(2)
For each possibleK2, compute the v′=ℰ2−1C, then access the v′-th entity of table S to extractK1. Current (K1, K2, and K3) is a candidate key.(ii)
Brute-force testing phase:(1)
Test every candidate key with other plaintext/ciphertext pairs until only the right key is remained.After the MITM phase, we get2k−n=2K1+K2/2n×2K3 candidate keys. In brute-force testing phase, the attacker exhaustively searches the true key by using extra plaintext/ciphertext pairs. Finally, the time complexity Ccomp of the attack in total is(1)Ccomp=2K3×2K1+2K2︸MITM phase+2k−n+2k−2n+2k−3n+⋯︸brute−force testing phase.The required plaintext/ciphertext pairs isk/n, while the memory cost is min(2K1, 2K2) memory blocks.Note that the “Partial Matching” technique [9] can be used to improve the performance of some MITM attacks. In such case, the matching point v,v′ is only l bits instead of n bits, so some bits of key in K1, K2, and K3 need not be involved in.


## 3.2. Splice-Cut MITM Attack

In the chosen plaintext and chosen ciphertext settings, the first and the last rounds of the block cipher can be regarded as two successive rounds. Aoki and Sasaki applied splice-cut technique into MITM attack [9].Assume ann-bit block cipher ℰ with k-bit secret key K is divided into three subciphers ℰ1, ℰ2, and ℰ3, while K is divided into three key parts K1, K2, and K3. K1 is only used in ℰ1 and ℰ3, K2 is only used in ℰ2, and K3 is the rest of K. The framework of splice-cut MITM attack is shown in Figure 3, and the steps of the attack are summarized as follows:Figure 3
Splice-cut MITM attack.(i)
MITM phase:For each possibleK3, (1)
Choose ann-bit state value P′.(2)
Guess each possibleK1, then compute the v=ℰ3−1∘ℰ∘ℰ1−1P′, and store all K1 into a table S indexed by v.(3)
For each possibleK2, compute the v′=ℰ2P′, then access the v′-th entity of table S to extract K1. Current (K1, K2, K3) is a candidate key.(iii)
Brute-force testing phase:(1)
Test every candidate key with other plaintext/ciphertext pairs until only the right key is remained.The time and memory complexities are same as those in general MITM attack. However, the data complexity depends onℰ1 and K1. Assume that m bits of plaintext P are not affected by K1 when we compute P=ℰ1−1P′; we can fix such m bits of plaintext as a constant in advance and then choose suitable P′. As a result, the data complexity is 2n−m.


## 3.3. Dimensional MITM Attack

This attack was proposed in [7]. It is suitable to attack ciphers whose key size is larger than block size.Assume ann-bit block cipher ℰ with k-bit secret key K is divided into four subciphers ℰ1, ℰ2, ℰ3, and ℰ4. Key part Ki is used in subcipher ℰi, i=1,2,3,4. The framework of 2-dimensional MITM attack is shown in Figure 4 and the steps of the attack is summarized as follows.Figure 4
2-dimensional MITM attack.(i)
MITM phase:(1)
For each possibleK1, compute v1=ℰ1P, and put K1 into table S1 indexed by the value of v1;(2)
For each possibleK4, compute v2=ℰ4−1C, and put K4 into table S2 indexed by the value of v2;(3)
For each possible value ofa:(a)
For each possibleK2, compute the v1′=ℰ2−1a, and check if v1′ is in table S1. If so, put (K1,K2) into table S3.(b)
For each possibleK3, compute v2′=ℰ3a and check if v2' is in table S2. If so, check if (K3,K4) is also in table S3. If true, current (K1, K2, K3, K4) is a candidate key.(ii)
Brute-force testing phase:(1)
Test every candidate key with other plaintext/ciphertext pairs until only the right key is remained.For each possible value of a, there are2k−v1−v2 candidate keys remained. After the MITM phase, we totally get 2a×2k−v1−v2=2a+k−v1−v2 candidate keys. In brute-force testing phase, the attacker exhaustively searches the true key by using extra plaintext/ciphertext pairs. Finally, the time complexity Ccomp of the attack in total is(2)Ccomp=2K1+2K4+2a×2K2+2K3︸MITM phase+2a+k−v1−v2+2a+k−v1−v2−n+2a+k−v1−v2−2n+⋯︸brute−force testing phase.In such attack, the data complexity isk/n, while the memory complexity happens to store tables Si, i=1,2,3.Remark.
In the 2-dimensional MITM attack model, the time of accessing tables is omitted in step 3b. However, it is much possible to be the main time complexity in some attacks. For example, Wen et al. indicated in [11] that the actual time complexity of 2-dimensional MITM attack on TWINE proposed in [8] exceeded the brute-force time. So in our attack on 2-GOST, we will take this part time into consideration.


## 4. 2-Dimensional MITM Attack on Full-Round 2-GOST

In this section, we apply 2-dimensional MITM attack combined with splice-cut technique on full-round 2-GOST.Before formally introducing the attack, we firstly illustrate how to decide the partial matching (meeting) point. Along the forward direction, each bit on (XiL, XiR) can be deduced from (Xi−1L, Xi−1R) and subkey Ki as follows:(3)XiLa=Xi−1Ra,XiRa=Xi−1La⊕SXi−1R4j+3∼0⊞Ki4j+3∼0a−11,where 4j≤a−11mod32<4j+4, Xa and Xa∼b denote the a-th bit and the a-th to b-th bits of state X, respectively. From (3), we can find that no bits of Ki are needed to deduce every bit on XiL and at least 4 bits of Ki are involved to deduce one bit on XiR from (Xi−1L, Xi−1R). Especially, only XiRa, 11≤14, j=0 can be deduced by 4 bits of Ki, that is, Ki3∼0. In order to guess key bits as few as possible to reduce the attack’s time complexity, (XiL, XiR14∼11 is a good candidate as matching point. Along the backward direction, the way that each bit on (XiL, XiR) deduced from (Xi+1L, Xi+1R) and subkey Ki+1 is similar with that along the forward direction because round function of 2-GOST adapts Feistel construction. Therefore, (XiL14∼11, XiR) is a good candidate as matching point as well. In a short, we select matching points from (XiL, XiR14∼11) and (XiL14∼11, XiR) in our attack.Next, we start to describe our attack on full-round 2-GOST. Its framework is shown in Figure5. Firstly, we divide full-round 2-GOST into 5 subciphers: Round 0, Rounds 1∼12, Rounds 13∼18, Rounds 19∼24, and Rounds 25∼31, denoted as ℰ1, ℰ2, ℰ3, ℰ4, and ℰ5, respectively. The actual start point P′ is the input of round 1 instead of the plaintext and two matching points are (X13L14∼11, X13R) and (X25LX25R14∼11) depicted as in Figures 6 and 7, where Xa∼b denotes the a-th to b-th bits of state X. In order to meet on (X13L14∼11, X13R), there are 224 bits key K1=K1,K2,K3,K4,K5,K6,K7 involved in subciphers ℰ2 and 164 bits of key K2=K03∼0,K1,K2,K5,K6,K7 involved in subcipher ℰ3. Similarly, In order to meet on (X25L, X25R14∼11), there are 164 bits of key K3=K0,K1,K2,K3,K4,K63∼0 involved in subcipher ℰ4, and 224 bits key K4=K0,K1,K2,K3,K4,K5,K7 involved in subciphers ℰ5 and ℰ1. The attack steps are as follows:Figure 5
Splice-cut 2-dimensional MITM attack on full-round 2-GOST.Figure 6
36-bit matching point on the input of round 25 in 2-GOST.Figure 7
36-bit matching point on the input of round 13 in 2-GOST.(1)
Guess each possibleK1, compute the value of (X13L14∼11, X13R) by v1=ℰ2P′, and put all possible (K3, K4) into table S1 indexed by (v1, K1, K2, K5, K6¸ K7).(2)
Guess each possibleK4, compute the value of (X25L, X25R14∼11) by v2=ℰ5−1∘ℰ∘ℰ1−1P′, and put (K5, K7) into table S2 indexed by (v2, K0, K1, K2, K3, K4).(3)
For each possible value ofa,(a)
Guess each possibleK2 compute the value of (X13L14∼11, X13R) by v1′=ℰ3−1a, then extract the entity with index from table S1, and store (K03∼0, K6) into table S3 indexed by (K1, K2, K3, K4, K5, K7).(b)
Guess each possibleK3, compute the value of (X25L, X25R14∼11) by v2′=ℰ4a, then extract the entity from table S2 by index.(c)
For each compatibleK3∪K4 from step 3b, access table S3 by index. If K3∪K4 is compatible with K1∪K2, current K1∪K2∪K3∪K4 is a candidate key. Test the candidate key with other plaintext/ciphertext pairs.In Step 1, the time complexity to build tableS1 is 2224×12/32≈2222.6 full-round encryptions. Since there are 2196 entities in table S1, on average, every entity contains 22864-bit values (K3, K4). Therefore, the memory complexity is 2224×8=2227 bytes. Similarly, in Step 2, the time complexity is about 2224×7/32≈2221.8 full-round encryptions, and the memory complexity is 2227 bytes.Under each possible value ofa, on average, 2164×228=2192 possible K1∪K2 will be stored into table S3 in Step 3a. Since table S3 has 2192 entities by index, each entity contains one value (K03∼0, K6) on average. Thus, the time complexity of Step 3a is 2164×6/32=2161.6 full-round encryptions and 2192 accesses. Assume one access roughly equals to one-round encryption. Then Step 3a needs 2161.6+2187≈2187 full-round encryptions under each possible a. Next, in Step 3b, the time complexity is 2164×6/32≈2161.6 full-round encryptions. Since there are 2192 possible K3∪K4 remained after step 3b, the time complexity is 2192 accesses in Step 3c, that is, 2187 full-round encryptions. As a result, the time complexity of MITM phase is 2222.6+2221.8+264×2187+2161.6+2187≈2252 full-round encryptions. Meanwhile, there are 2248 candidate key remained. In the brute-force testing phase, we need 4 plaintext/ciphertext pairs to filter such candidate keys. The time complexity is 2248+2248−64+2248−64×2+2248−64×3≈2248. Totally, the time complexity of the whole attack on full-round GOST2 is 2252+2248≈2252 full-round encryptions. The memory complexity happens to build tables S1, S2, and S3, which is about 2227+2227+2196×5≈2228 bytes. Because P=ℰ1−1P′ and 32-bit K0 involved in ℰ1−1, the data complexity is 232 chosen plaintexts.


## 5. MITM Attack on 31-Round 2-GOST

2-GOST is a modified version of GOST by changing the key schedule to avoid reflection attack and fixed point attack. In this section, we apply the general MITM attack combined with splice-cut technique on 31-round 2-GOST due to the new order of subkeys. By analyzing the key schedule of 2-GOST, we observe the fact thatK1 has no chance to be used from Round 2 to Round 13. On the other hand, K7 has no chance to be used from Round 19 to Round 30 as well. Furthermore, Round 0 to Round 2 could be computed without K7. Based on those observations, we construct a MITM attack on the reduced 31-round 2-GOST. Figure 8 shows an overview of the attack.Figure 8
Overview of the splice-cut MITM attack on 31-round 2-GOST.In this attack, we divide 31-round 2-GOST into three subciphers: Rounds0∼1, Rounds 2∼15, and Rounds 16∼30, denoted by ℰ1, ℰ2, and ℰ3, respectively. The actual start point P′ is on (X2L, X2R), and matching point is on X16R14∼11. In order to compute the value of X16R14∼11 from (X2L, X2R) forward, there are 124 bits of key except K131∼28 involved, while from ciphertext backward, there are 124 bits of key except K731∼28 involved. Let K1 denote the key bits only used in ℰ2, K2 denote the key bits only used in ℰ3 and ℰ1, and K3 denote common key part among three subciphers. Here, K1 = K731∼28, K2 = K131∼28, and K3=K0,K127∼0,K2,K3,K4,K5,K6,K727∼0. In detail, the attack process is as follows (Figure 9).Figure 9
Partial matching on the input of round 16 in 2-GOST.


### 5.1. Complexity Evaluation

According to (2), in the MITM phase, the time complexity is about 2248×24 14-round encryptions and 2248×24 15-round encryptions, which is equal to 2251.9 31-round encryptions. Meanwhile, in the brute-force testing phase, the time complexity is about 2252 31-round encryptions. Totally, the time complexity of the whole attack is 2251.9+2252≈2252.9 31-round encryptions. Since X0L14∼11, X0R31∼11, and X0R6∼0 are not affected by K1=K131∼28 (depicted in Figure 10); these 32 bits of plaintext can be fixed in advance. Therefore, the data complexity in MITM phase is 232 chosen plaintexts. Regarding the required memory, it mainly happens to build table S, which needs about 8 bytes (=24×4 bits).Figure 10
P=ℰ1−1P′ in 2-GOST.(i)
MITM phase:For each possibleK3,(1)
Choose ann-bit state value P′ on the input of round 2.(2)
Guess each possibleK1, then compute the value v=ℰ2P′ on X16R14∼11 and store K1 into a table S indexed by v.(3)
For each possibleK2, compute the v′=ℰ3−1∘ℰ∘ℰ1−1P′, then check whether there is any value of K1 in the v′-th entity of S. If so, current (K1, K2, K3) is a candidate key.(ii)
Brute-force testing phase:(1)
Test every candidate key with other plaintext-ciphertext pairs until only the right key is remained


## 5.1. Complexity Evaluation

According to (2), in the MITM phase, the time complexity is about 2248×24 14-round encryptions and 2248×24 15-round encryptions, which is equal to 2251.9 31-round encryptions. Meanwhile, in the brute-force testing phase, the time complexity is about 2252 31-round encryptions. Totally, the time complexity of the whole attack is 2251.9+2252≈2252.9 31-round encryptions. Since X0L14∼11, X0R31∼11, and X0R6∼0 are not affected by K1=K131∼28 (depicted in Figure 10); these 32 bits of plaintext can be fixed in advance. Therefore, the data complexity in MITM phase is 232 chosen plaintexts. Regarding the required memory, it mainly happens to build table S, which needs about 8 bytes (=24×4 bits).Figure 10
P=ℰ1−1P′ in 2-GOST.(i)
MITM phase:For each possibleK3,(1)
Choose ann-bit state value P′ on the input of round 2.(2)
Guess each possibleK1, then compute the value v=ℰ2P′ on X16R14∼11 and store K1 into a table S indexed by v.(3)
For each possibleK2, compute the v′=ℰ3−1∘ℰ∘ℰ1−1P′, then check whether there is any value of K1 in the v′-th entity of S. If so, current (K1, K2, K3) is a candidate key.(ii)
Brute-force testing phase:(1)
Test every candidate key with other plaintext-ciphertext pairs until only the right key is remained


## 6. Conclusion

In this paper, we improve the single-key attacks on 2-GOST, a modification of GOST, with data of232 for all possible keys. Firstly, we apply 2-dimensional MITM attack combined with splice-cut technique on full-round 2-GOST. Its time and memory complexities are 2252 encryptions and 2223 256-bit blocks, respectively. Then, we apply splice-cut MITM attack on reduced 31-round 2-GOST. The time complexity is 2252.9 encryptions and memory complexity is negligible. Note that these attacks are still not practical to be implemented, but they indicate that the key schedule in the modification version 2-GOST is not a good choice yet.



---

*Source: 8886032-2020-10-15.xml*