A Single-Key Attackon the Full GOST Block Cipher
Takanori IsobeSony Corporation
1-7-1 Konan, Minato-ku, Tokyo 108-0075, Japan
Takanori.Isobe@jp.sony.com

Abstract. The GOST block cipher is the Russian encryption standard
published in 1989. In spite of considerable cryptanalytic eﬀorts over the
past 20 years, a key recovery attack on the full GOST block cipher without any key conditions (e.g., weak keys and related keys) has not been
published yet. In this paper, we show a ﬁrst single-key attack, whichworks for all key classes, on the full GOST block cipher. To construct
the attack, we develop a new attack framework called Reflection-Meet-inthe-Middle Attack. This approach combines techniques of the reﬂection
attack and the meet-in-the-middle attack. We apply it to the GOST
block cipher with further novel techniques which are the eﬀective MITM
techniques using equivalent keys on short rounds. As a result, a key canbe recovered with 2225 computations and 232 known plaintexts.
Key words: block cipher, GOST, single-key attack, reﬂection attack,meet-in-the-middle attack, equivalent keys

1

Introduction

The GOST block cipher [22] is known as the former Soviet encryption standard
GOST 28147-89 which was standardized as the Russian encryption standard in
1989. It is based on a 32-round Feistel structure with 64-bit block and 256-bit
key size. The round function consists of a key addition, eight 4 × 4-bit S-boxes
and a rotation. Since values of S-boxes are not speciﬁed in the GOST standard[22], each industry uses a diﬀerent set of S-boxes. For example, one of the S-boxes
used in the Central Bank of the Russian Federation is known as in [27].
The GOST block cipher is well-suited for compact hardware implementations due to its simple structure. Poschmann et al. showed the most compact
implementation requiring only 651 GE [24]. Therefore, the GOST block cipher
is considered as one of ultra lightweight block ciphers such as PRESENT [6] andKATAN family [8], which are suitable for the constrained environments including RFID tags and sensor nodes. Note that for the remainder of this paper werefer to the GOST block cipher as GOST.
Over the past 20 years, several attacks on GOST have been published. A
diﬀerential attack on 13-round GOST was proposed by Seki and Kaneko [28]. In
the related-key setting, an attack is improved up to 21 rounds. Ko et al. showedTable 1. Key recovery attack on GOST

Key setting
Single key

Type of attack

Round Complexity

Diﬀerential

13

Not given

Slide

24

263

30

253.7

Slide

2

224

Data
51

2

Paper

CP

[28]

263 ACP

[2]

2

63

ACP

[2]

32

KP

[17]

Reﬂection30

2

Reﬂection-Meet-in-the-Middle

32

2225

232 KP This paper

Single key

Slide (2128 weak keys)

32

263

263 ACP(Weak key)

224

32

192

Related key

Reﬂection (2weak keys)

Diﬀerential
Diﬀerential†

Boomerang ‡2

21

Not given

32

2

244

32

2248

2

[2]

32

CP

[17]

56

CP

[28]

35

CP

[19]

27.5 CP

[15]

2
2
2

CP : Chosen plaintext, ACP : Adaptive chosen plaintext, KP : Known plaintext.
† The attack can recover 12 bits of the key with 236 computations and 235 CP.
‡ The attack can recover 8 bits of the key with 27.5 computations and 27.5 CP.

a related-key diﬀerential attack on the full GOST [19]. These results work on
only the GOST that employs the S-boxes of the Central Bank of the RussianFederation [27]. Fleischmann et al. presented a related-key boomerang attackon the full GOST which works for any S-boxes [15]. As other types of attacks,
Biham et al. showed slide attacks on the reduced GOST [2]. Their attack utilizes
self similarities among round functions of the encryption process, and does notalso depend on used values of S-boxes. Even if an attacker does not know thevalues of S-boxes, the 24-round GOST can be attacked by this approach. If thevalues are known, this attack can be improved up to 30 rounds. In addition, fora class of 2128 weak keys, the full GOST can be attacked by this approach. After
that, Kara proposed a reﬂection attack on 30-round GOST [17]. This attack
also uses self similarities among round functions, and works for any bijective
S-boxes. The diﬀerence from the slide attack proposed by Biham et al. [2] is
to use similarities of both encryption and decryption processes. The reﬂection
attack utilizes these similarities in order to construct ﬁxed points of some round
functions. Moreover, for a class of 2224 weak keys, the full GOST can be attacked
by using the reﬂection technique.
In spite of considerable cryptanalytic eﬀorts, a key recovery attack on thefull GOST without any key assumptions (e.g., weak keys and related keys) has
not been published so far. Furthermore, a weak-key attack and a related-key
attack are arguable in the practical sense, because of their strong assumptions.
A weak-key attack is generally applicable to very few keys, e.g., in the attack of[17], the rate of weak keys is 2−32 (= 2224 /2256 ). Hence, almost all keys, (2256 −2224 ) ≈ 2256 keys, can not be attacked by [17]. Besides, the attacker can noteven know whether a target key is included in a weak key class or not. A relatedkey attack assumes that the attacker can access to the encryption/decryption
under multiple unknown keys such that the relation between them is known
to the attacker. Though this type of attack is meaningful during the designand certiﬁcation of ciphers, it does not lead to a realistic threat in practicalsecurity protocols which use the block cipher in a standard way as stated in[13]. Therefore, the security under the single-key setting is the most important
issue from the aspect of the practical security. In particular, an ultra lightweightblock cipher does not need a security against related-key attacks in many cases.
For example, in low-end devices such as a passive RFID tag, the key may not
be changed in its life cycle as mentioned in [6, 8]. Indeed, KTANTAN supports
only a ﬁxed key [8] and the compact implementation of GOST proposed by
Poschmann et al. also uses a hard-wired ﬁxed key [24]. Therefore, it can be said
that GOST has not been theoretically broken.
Recently, Bogdanov and Rechberger showed a new variant of the Meet-inthe-Middle (MITM) attack on block ciphers called 3-subset MITM attack [7];it was applied to KTANTAN [8]. This attack is based on the techniques of therecent MITM preimage attacks on hash functions [1, 25]. It seems to be eﬀective for the block cipher whose key schedule is simple, e.g., a bit or a word
permutation. In fact, the key schedule function of KTANTAN consists of a bit
permutation. Since GOST also has a simple key schedule function, which is aword permutation, the 3-subset MITM attack seems applicable to it. However,it does not work well on the full GOST, because the key dependency of the full
GOST is stronger than that of KTANTAN due to the iterative use of key words
during many round functions.
Our Contributions. In this paper, we ﬁrst introduce a new attack framework
called Reflection-Meet-in-the-Middle (R-MITM) Attack ; it is a combination of
the reﬂection attack and the 3-subset MITM attack. The core idea of this combination is to make use of ﬁxed points of the reﬂection attack to enhance the
3-subset MITM attack. If some round functions have ﬁxed points, we can probabilistically remove these rounds from the whole cipher. Since this skip usingﬁxed points allows us to disregard the key bits involved in the removed rounds,
the key dependency is consequently weakened. Thus, our attack is applicable
to more rounds compared to the original 3-subset MITM attack if ﬁxed points
can be constructed with high probability. Then, we apply it to the full GOST
block cipher with further novel techniques which make the MITM approach more
eﬃcient by using equivalent keys on short rounds. As a result, we succeed in constructing a ﬁrst key recovery attack on the full GOST block cipher in the single
key setting. It can recover a key with 2225 computations and 232 known plaintext/ciphertext pairs. An important point to emphasize is that our attack does
not require any assumptions for a key unlike the previous attacks. In addition,
our attack can be applied to any S-boxes as long as they are bijective. These
results are summarized in Table 1.

Table 2. Key schedule of GOST

Round 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Key k1 k2 k3 k4 k5 k6 k7 k8 k1 k2 k3 k4 k5 k6 k7 k8
Round 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
Key k1 k2 k3 k4 k5 k6 k7 k8 k8 k7 k6 k5 k4 k3 k2 k1

Outline of the Paper. This paper is organized as follows. A brief descriptionof GOST, a 3-subset MITM attack and a reﬂection attack are given in Section
2. The R-MITM attack is introduced in Section 3. In Section 4, we present a
R-MITM attack on the full GOST. Finally, we present conclusions in Section 5.

2

Preliminaries

In this section, we give a brief description of GOST, a 3-subset MITM attack
and a reﬂection attack.
2.1

Description of GOST

GOST is a block cipher based on a 32-round Feistel structure with 64-bit blockand 256-bit key size. The F -function consists of a key addition, eight 4 × 4-bit
S-boxes Sj (1 ≤ j ≤ 8) and a 11-bit left rotation (See Fig.1).
Li

F - function

<<<11

S1
S2

Ri
ki

S8

L i+1

R i+1

Fig. 1. One round of the GOST block cipher

The 256-bit master key K is divided into eight 32-bit words, i.e., K =(k1 , k2 , . . . , k8 ), ki ∈ {0, 1}32 . Each ki is used as a round key in each round
function as shown in Table 2.
In the GOST standard [22], the S-boxes are not speciﬁed. Each industry uses
a diﬀerent set of S-boxes. In this paper, we do not care about speciﬁc values of
the S-boxes as long as they are bijective.

2.2

3-Subset MITM Attack

The basic concept of the MITM attack was proposed by Diﬃe and Helman[12]. So far, this attack has been applied to several block ciphers [9–11, 13, 14,16]. Furthermore, over the past few years, this attack has been improved ina line of preimage attacks on hash functions, and several novel techniques are
introduced, e.g., a partial matching [1] and an initial structure [25]. Recently, byusing these novel techniques, Bogdanov and Rechberger showed a new variant of
MITM attack on block ciphers called 3-subset MITM attack [7]; it was applied
to KTANTAN [8].
This attack consists of two stages: a MITM stage and a key testing stage.
First, the MITM stage ﬁlters out part of wrong keys from key candidates byusing MITM techniques. Then, the key testing stage ﬁnds a correct key from thesurviving key candidates in a brute force manner.
Let EK : {0, 1}b → {0, 1}b be a block cipher with an l-bit key K and a b-bit
block. Assume that EK is a composition of round functions as follows;
EK (x) = Fkr ◦ Fkr−1 ◦ · · · ◦ Fk1 (x), x ∈ {0, 1}b ,where r is the number of rounds, k1 ,. . . ,kr are round keys and Fki is the i-thround function, Fki : {0, 1}b → {0, 1}b . The composition of j − i + 1 functions
starting from i is denoted by FK [i, j] deﬁned as
FK [i, j](x) = Fkj ◦ · · · ◦ Fki (x), 1 ≤ i < j ≤ r.
In the following, we give details of each stage of the 3-subset MITM attack.
MITM stage : Ek (X) is divided into two functions as EK (X) = FK [a + 1, r] ◦FK [1, a], 1 < a < r − 1 1 . Let K1 and K2 be sets of key bits used in FK [1, a] andFK [a + 1, r], respectively. A0 = K1 ∩ K2 is the common set of key bits used inboth FK [1, a] and FK [a + 1, r]. A1 = K1 \ K1 ∩ K2 and A2 = K2 \ K1 ∩ K2 are
the sets of key bits used in only FK [1, a] and only FK [a + 1, r], respectively. In
this stage, we use only one plaintext/ciphertext pair (P, C).
The procedure of the MITM stage is as follows. Fig. 2 shows the overview ofthe MITM stage.
1. Guess a value of A0 .
2. Compute v = FK [1, a](P ) for all values of A1 and make a table of (v, A1 )pairs. In this step, 2|A1 | pairs are generated, where |Ai | is the bit length of
Ai and 2|Ai | is the number of elements of Ai .
−1
3. Compute u = FK
[a + 1, r](C) for all values of A2 . In this step, 2|A2 | pairs
are generated.
4. Add key candidates for which the equation v = u is satisﬁed to the list of
surviving keys.
The number of surviving keys is 2|A1 |+|A2 | /2b .
1

As in the attack of KTANTAN [7], by using the partial matching technique, EK isdivided into FK [1, a] and FK [a + t, r], t > 1. However, in this paper, we consider
only the case of t = 1, because we do not use the partial matching.

K1(A0 , A1)P
Plaintext

FK[1, a]K2
(A0 , A2)v u

FK[a + 1, r]CCiphertext

matching

Fig. 2. Meet-in-the-middle stage

5. Repeat 2-4 for each diﬀerent value of A0 . (2|A0 | times)
In this stage, 2l−b key candidates survive, because 2|A1 |+|A2 | /2b × 2|A0 | =2 /2b .
l

Key testing stage : We test surviving keys in a brute force manner by using
additional plaintext/ciphertext pairs.
We evaluate the cost of this attack. The whole attack complexity Ccomp isestimated as
Ccomp = 2|A0 | (2|A1 | + 2|A2 | ) + (2l−b + 2l−2b + . . .).
{z
} |
{z
}
|
MITM stage

Key testing stage

The number of required plaintext/ciphertext pair is d bl e. The required memory
is max(2|A1 | , 2|A2 | ), which is the cost of the table used in the MITM stage.
When min(|A1 |, |A2 |) > 1 the attack is more eﬀective than an exhaustive search.
Therefore, the point of the 3-subset MITM attack is to ﬁnd independent sets ofmaster key bits such as A1 and A2 .
2.3

Reﬂection Attack

The reﬂection attack was ﬁrst introduced by Kara and Manap [18]; it was applied
to Blowﬁsh [26]. After that, the attack was generalized by Kara [17]. In thissection, we introduce a basic principle of the reﬂection attack used in our attack.
See [17, 18] for details about the reﬂection attack.
The reﬂection attack is a kind of a self-similarity attack such as the slide
attack [4, 5]. Though the reﬂection attack utilizes similarities of some round
functions of both encryption and decryption processes, the slide attack exploits
similarities among the round functions of only the encryption process. In thereﬂection attack, by using these similarities, ﬁxed points of some round functions
are constructed.
Let UK (i, j) be the set of ﬁxed points of the function FK [i, j] deﬁned asfollows;
UK (i, j) = {x ∈ {0, 1}n | FK [i, j](x) = x}.

Fixed Point

Xinx

Fk i-tFk i-1Xout

FK[i, j]Fk j+1

Fixed Point

Fk j+1-1

Fk j+tx-1

Fk j+tFK[i - t, j + t]
Fig. 3. Basic principle of the reﬂection attack

The basic principle of the reﬂection attack is given by the following Lemma.
Lemma 1 [17] Let i and j be integers such that 0 ≤ j − i < i + j < r. Assume
that Fki−t = Fk−1
for all t : 1 ≤ t < i. If FK [i − t, i − 1](x) ∈ Uk (i, j), thenj+tx ∈ Uk (i − t, j + t) for all t : 1 < t < i. In addition, if x ∈ UK (i − t, j + t) for
certain t : 1 < t < i, then FK [i − t, i − 1](x) ∈ UK (i, j).
From Lemma 1, if the round functions hold the conditions, a local ﬁxed
point is expanded to previous and next rounds as shown in Fig. 3. Roughly
speaking, ﬁxed points of some round functions can be constructed easily in thecertain setting. These ﬁxed points enable us to probabilistically skip the round
functions from a whole cipher.
We give an example to explain this skip in detail. Let i and j be integers
such that 0 < j − i < i + j < r. Assume that Fki−t = Fk−1
for all t : 1 < t < i,j+t
and EK (x) is expressed as follows;
EK (x) = FK [j + i, r] ◦ FK [j + 1, j + i − 1] ◦ FK [i, j] ◦ FK [1, i − 1](x),−1= FK [j + i, r] ◦ FK
[1, i − 1] ◦ FK [i, j] ◦ FK [1, i − 1](x).
Besides, assuming FK [1, i−1](x) ∈ UK (i, j), then FK [1, j +i−1](x) = x (Lemma
1). Thus EK (x) is expressed as
EK (x) = F [j + i, r](x).
In this case, the round functions FK [1, j + i − 1] can be skipped from EK . The
probability Pref of that above skip occurs for arbitrary x is |UK (i, j)|/2b . If
Pref > 2−b (i.e., |UK [i, j]| > 1), this skip occurs at FK [1, j + i − 1] with higher
probability than a random function.

3

Reflection-Meet-in-the-Middle Attack

We propose a new attack framework called reflection-meet-in-the-middle (RMITM) attack, which is a combination of the reﬂection attack and the 3-subset
MITM attack. As mentioned in Section 2.2, the point of the 3-subset MITM
attack is to construct independent sets of master key bits. In general, if themaster key bits are used iteratively in each round and the use of key bits is notbiased among rounds 2 , it seems to be diﬃcult to ﬁnd the independent sets ofmaster key bits, because such cipher have the strong key dependency on evensmall number of rounds.
To overcome this problem, we utilize the technique of the reﬂection attack. In
the reﬂection attack, some rounds satisfying certain conditions can be skippedfrom the whole cipher with the probability Pref . From now on, we call this skipa reflection skip. Since key bits used in skipped round functions can be omitted,
it becomes easier to construct independent sets of master key bits. This is theconcept of the R-MITM attack. In the following, we give the detailed explanationof the attack.
3.1

Details of the R-MITM Attack

Suppose that EK is expressed as follows;
EK (x) = FK [a3 + 1, r] ◦ FK [a2 + 1, a3 ] ◦ FK [a1 + 1, a2 ] ◦ FK [1, a1 ](x),where 2 < a1 + 1 < a2 < a3 − 1 < r − 2 and the reﬂection skip occurs at
FK [a2 + 1, a3 ] with the probability Pref . Then, EK can be redescribed as follows
0
and denoted by EK (x),0EK (x) = FK [a3 + 1, r] ◦ FK [a1 + 1, a2 ] ◦ FK [1, a1 ](x).
The R-MITM attack consists of three stages; a data collection stage, a RMITM stage and a key testing stage. In the following, we explain each stage.
Data collection stage : We collect plaintext/ciphertext pairs to obtain a pairin which the reﬂection skip occurs at FK [a2 + 1, a3 ]. Since the probability of this−1
event is Pref , the number of required plaintext/ciphertext pairs is Pref.
After that, the R-MITM stage and the key testing stage are executed for all
plaintext/ciphertext pairs obtained in the data collection stage.
R-MITM stage : We divide EK into two functions: FK [1, a1 ] and FK [a1 +1, r]3 . In this stage, we ignore FK [a2 + 1, a3 ] as follows;0FK[a1 + 1, r] = FK [a3 + 1, r] ◦ FK [a1 + 1, a2 ],2

In KTANTAN [8], 6 bits of master key are not used in the ﬁrst 111 rounds and other6 bits of master key are also not used in the last 131 rounds. The attack of [7] utilizes
this bias of used key bits among rounds.
3
Though there are many choices of divisions, we use it as an example.

K1(A0 , A1)P
Plaintext

FK[1, a1]

K2
(A0 , A2)v u

FK[a1 +1, a2]

K2(A0 , A2)

Reflection skip
(Fixed point)
FK[a2 +1, a3]FK[a3 +1, r]CCiphertext

matching

Fig. 4. Reﬂection-meet-in-the-middle stage

assuming that the reﬂection skip occurs. Let K1 and K2 be sets of key bits0
[a1 + 1, r], respectively. A0 = K1 ∩ K2 is the set ofused in FK [1, a1 ] and FK
key bits used in both FK [1, a1 ] and F 0 K [a1 + 1, r]. A1 = K1 \ K1 ∩ K2 andA2 = K2 \ K1 ∩ K2 are the sets of key bits used in only FK [1, a1 ] and only
F 0 K [a1 + 1, r], respectively. Figure 4 illustrates the R-MITM stage.
The procedure of the R-MITM stage is almost same as the MITM stageof Section 2.2. The diﬀerence is that in the R-MITM stage, we assume thatreﬂection skip occurs, i.e., FK [a2 + 1, a3 ] is ignored. After this stage, 2l−b key
candidates survive.
Key testing stage : We test surviving keys in a brute force manner by using
plaintext/ciphertext pairs.

3.2

Evaluation of the R-MITM Attack

We evaluate the cost of the R-MITM attack. The whole attack complexity Ccomp
is estimated as−1
Ccomp = ((2|A0 | (2|A1 | + 2|A2 | )) + (2l−b + 2l−2b + . . .)) × Rref
.
|
{z
} |
{z
}
R-MITM stage

Key testing stage−1
The number of required plaintext/ciphertext pair is max(dl/be, Rref). The|A1 | |A2 |required memory is max(2,2), which is the cost of the table in the R−1
MITM stage. When min(2|A1 | , 2|A2 | , 2b ) > (Rref), the attack is more eﬀective
than an exhaustive search.
Compared with the basic 3-subset MITM attack in Section 2.2, the numberof required plaintext/ciphertext pairs increases, because the R-MITM attack
utilizes the probabilistic event, i.e., reﬂection skip. In addition, more independent
key bits are needed for the successful attack. However, this attack has a distinct
advantage, which is to be able to skip some round functions by the reﬂection
skip. Recall that the most important point of the 3-subset MITM attack is
to ﬁnd independent sets of master key bits. Since the reﬂection skip enables
us to disregard key bits involved in some round, it obviously becomes easier toconstruct such independent sets. Thus, this attack seem to be applicable to morerounds than the 3-subset MITM attack when the reﬂection skip occurs with highprobability.

4

R-MITM Attack on the Full GOST Block Cipher

In this section, we apply the R-MITM attack to the full GOST block cipher [22].
From Table. 2, in full 32 rounds, the master key is iteratively used four times
and all master key bits are involved in every 8 rounds. The basic 3-subset MITM
attack in Section 2.2 is not applicable to the full GOST, because independent
sets of master key bits can not be constructed in any divisions of 32 rounds.
However, by using the R-MITM attack, we can construct independent sets andmount a key recovery attack on the full GOST.
We ﬁrst introduce the reﬂection property of GOST proposed by Kara [17]to construct the reﬂection skip. Next, we present eﬀective MITM techniques toenhance the R-MITM stage. These techniques make use of the equivalent keysof short round functions. Finally, we evaluate our attack.
4.1

Reﬂection Property of GOST

The reﬂection attack on GOST has been proposed by Kara [17] 4 . The GOST
block cipher EK : {0, 1}64 → {0, 1}64 is expressed as
EK = S ◦ FK [25, 32] ◦ FK [17, 24] ◦ FK [9, 16] ◦ FK [1, 8],−1= FK[1, 8] ◦ S ◦ FK [1, 8] ◦ FK [1, 8] ◦ FK [1, 8],
where S is the swap of the Feistel structure.
S has 232 ﬁxed points, because the probability of that the right halves equal−1
to the left halves is 2−32 . From Lemma 1, FK[1, 8] ◦ S ◦ FK [1, 8] also has 232
32
ﬁxed points, i.e., |UK (17, 32)| = 2 . Thus, with the probability Pref = 2−32 (=(232 /264 )), FK [17, 32] can be ignored. EK is redescribed as follows and denoted
0
by EK
0

EK = FK [1, 8] ◦ FK [1, 8].
Figure 5 shows this reﬂection skip of GOST.
−1
Therefore, in the data collection stage, we need to collect Pref
= 232 plaintext/ciphertext pairs. In 232 collected pairs, there is a pair in which the reﬂection
0
skip occurs, i.e., last 16 rounds can be removed as EK .
4.2

Eﬀective MITM Technique using Equivalent Keys on Short
Rounds0

In the R-MITM stage, we mount the MITM approach on only EK = FK [1, 8] ◦FK [1, 8] for all 232 collected pairs.
As mentioned in Section 3.2, we need to construct independent sets A1 and A2
which hold the condition, min(2|A1 | , 2|A2 | ) > 232 . However, despite the reduction
4

The similar technique for constructing a ﬁxed point is also used in the attacks on
the GOST hash function [20, 21].

Reflection skip
(Fixed point)P
Plaintext

FK[1, 8]FK[9, 16]
=FK[1, 8]

R-MITM stage

CFK[17, 32]

C
Ciphertext

Pref = 2 -32

Fig. 5. Reﬂection skip of GOST

of rounds by the reﬂection skip, in the straightforward method, we can not ﬁndsuch sets in any divisions of 16 rounds, due to the strict condition of independentsets.
We introduce eﬀective MITM techniques which make use of equivalent keys ofshort round functions (i.e., 4 round). The aim of these techniques is to ignore theﬁrst and the last 4 rounds and to mount the MITM approach in only intermediate
8 rounds. These techniques enable us to construct independent sets enough forthe successful attack.
0
We treat EK as following four-round units;0

EK = FK [5, 8] ◦ FK [1, 4] ◦ FK [5, 8] ◦ FK [1, 4].
In the following, we ﬁrst explain equivalent keys used in our attack. Then, we
present detail of the R-MITM stage using the equivalent keys.
Equivalent Keys on Short Rounds. Deﬁne a set of equivalent keys on
FK [i, j] as Z(FK [i, j], x, y) as follows:
Z(FK [i, j], x, y) = {ek ∈ {0, 1}256 | Fek [i, j](x) = y},where (x, y) ∈ {0, 1}64 . Note that the class of keys deﬁned above is the equivalent
keys with respect to only one input/output pair. To put it more concretely, if
equivalent keys ek ∈ Z(FK [i, j], x, y) are used, input x is always transformed toy in FK [i, j]. For other input/output pairs, these relations do not hold even if
the same equivalent keys are used.
GOST has an interesting property regarding the equivalent keys on shortrounds as described in the following observation.
−1
Observation 1 : Given any x and y, Z(FK [1, 4], x, y) and Z(FK[5, 8], x, y)
can be easily obtained, and the number of each equivalent keys is 264 .

For FK [1, 4], k1 , k2 , k3 and k4 are added in each round. Given the values of k1
and k2 , the other values of k3 and k4 are determined from FK [1, 2](x) and y as
follows:
k3 = F −1 (zL + yL ) − zR ,k4 = F −1 (zR + yR ) − yR ,

(1)
(2)

xL

xR
k1

k1 : guessed
(232)

F

k2

k2 : guessed
(232)

F
zL

k3

zR

F

k3 : determined-1(k3 = F (zL + yL) - zR )k4F

k4 : determined-1(k4 = F (zR + yR) - yL )yL

yRFig. 6. Equivalent keys of 4 rounds

where F −1 is the inverse of F function, yL and yR are left and right halves ofy, and zL and zR are those of FK [1, 2](x). Since values of (k1 , k2 ) are 64 bits,
the number of Z(FK [1, 4], x, y) is 264 . Figure 6 shows this procedure. A similar−1
property holds for FK[5, 8].
From Observation 1, we can easily obtain 264 equivalent keys of the ﬁrst and−1
the last 4 rounds for any inputs and outputs. Moreover, FK [1, 4] and FK[5, 8] use
diﬀerent master key bits each other, Ka = (k1 ||k2 ||k3 ||k4 ) and Kb = (k5 ||k6 ||k7 ||k8 ),−1
respectively. Thus, Z(FK [1, 4], x, y) and Z(FK[5, 8], x, y) are expressed by setsof only Ka and Kb as follows;
ZKa (FK [1, 4], x, y) = {eka ∈ {0, 1}128 | Feka [1, 4](x) = y},−1−1
ZKb (FK
[5, 8], x, y) = {ekb ∈ {0, 1}128 | Fek[5, 8](x) = y}.
b
Since Ka and Kb are independent sets of mater key, ZKa (FK [1, 4], x, y) and−1
ZKb (FK
[5, 8], x, y) are also independent sets.
Detail of the R-MITM Stage using Equivalent Keys. Let S and T be
FK [1, 4](P ) and F −1 [5, 8](C), which are input and output values of 8 intermediate rounds, i.e., FK [5, 12] = FK [1, 4] ◦ FK [5, 8].
From Observation 1, given values of P , C, S and T , two sets of 264 equivalent−1
keys, ZKa (FK [1, 4], P, S) and ZKb (FK[5, 8], C, T ), can be easily obtained.

Ka
k1||k2||k3||k4PPlaintext

FK[1, 4]Equivalent keys
ZKa(F[1, 4], P, S)-1S

ZKb(F [5, 8], C, T)

ZKa(F[1, 4], P, S)

FK[5, 8]FK[1, 4]v u
Matching

Kb
k5||k6||k7||k8
T

FK[5, 8]C
Ciphertext

Equivalent keys
-1

ZKb(F [5, 8], C, T)

Fig. 7. R-MITM stage using equivalent keys

−1
When ZKa (FK [1, 4], P, S) and ZKb (FK[5, 8], C, T ) are used, S and T are
not changed. Thus by using these equivalent keys, the ﬁrst and the last 4 roundcan be ignored, and we can mount the MITM attack between FK [5, 8](S) and−1
FK[1, 4](T ). The number of elements in each independent set is 264 , which isenough for the successful attack.

The procedure of the R-MITM stage is as follows and illustrated in Fig. 7.
1. Guess the values S and T .
−1
2. Compute v = FK [5, 8](S) with 264 Kb in ZKb (FK[5, 8], C, T ) and make atable of (v, Kb ) pairs.
−1
3. Compute u = FK[1, 4](T ) with 264 Ka in ZKa (FK [1, 4], P, S).
4. Add key candidates for which the equation v = u is satisﬁed to the list of
surviving keys. The number of surviving keys is 264+64 /264 = 264 .
5. Repeat 2-4 with the diﬀerent values of S and T . (2128 times).
After this procedure, 2192 (=264 × 2128 ) key candidates survive. These key candidates are evaluated in the key testing stage.
The R-MITM stage utilizes equivalent-key sets of ZKa (FK [1, 4], P, S) and−1
ZKb (FK
[5, 8], C, T ), 0 ≤ S, T < 264 , where each set includes 264 elements. For
ZKa (FK [1, 4], P, S), 0 ≤ S < 264 , all elements of every set are diﬀerent, because if
the values of S are diﬀerent, equivalent keys of FK [1, 4] are surely diﬀerent from
Eq. (1) and (2) as long as S-boxes are bijective. Thus, ZKa (FK [1, 4], P, S), 0 ≤S < 264 covers all 2128 (= 264 × 264 ) values of Ka . A similar property holds
for Kb . Therefore, all possible values for the master key are tested and the setof surviving key candidates surely contain the correct key if the reﬂection skip
occurs.

4.3

Evaluation

The whole attack complexity Ccomp is estimated as
Ccomp = ((2128 (264 + 264 )) + (2256−64 + 2256−128 + . . .)) × 232 ,
|
{z
} |
{z
}
R-MITM stage

=2

225

Key testing stage.

−1
The number of required known plaintext/ciphertext pairs is max(dl/be, Rref
)=
32
32
64 64
64
max(d256/64e, 2 ) = 2 . The required memory is max(2 , 2 ) = 2 , whichis the cost of the table used in the R-MITM stage. Therefore, this attack canrecover a key with 2225 computations, 232 known plaintext/ciphertext pairs and
264 memory. It is more eﬀective than an exhaustive attack.

5

Conclusion

This paper has presented a ﬁrst single-key attack on the full GOST block cipher without relying on weak key classes. To build the attack, we introduced a
new attack framework called Reflection-Meet-in-the-Middle Attack, which is the
combination of the reﬂection and the 3-subset MITM attacks. The advantageof this attack over the basic 3-subset MITM attack, some rounds can be probabilistically removed from the whole cipher. Since this allows us to disregard
the key bits involved in the removed rounds, it becomes easier to construct theindependent sets of the key bits. Thus, our attack seems to be applicable to morerounds when the reﬂection skip occurs with high probability. Then we applied
it to the full GOST block cipher with further novel techniques which make useof equivalent keys of short round functions (i.e., 4 rounds). These techniques
enable us to mount the eﬀective MITM approach. As a result, we succeededin constructing a ﬁrst key recovery attack on the full GOST without any key
conditions, which works for any bijective S-boxes. Our result shows that GOST
does not have the 256-bit security for all key classes, even if a ﬁxed key is usedsuch as [24].
The idea of the R-MITM attack seems applicable to other block ciphers inwhich the ﬁxed point can be constructed with high probability and its key schedule is simple in the sense that the key dependency is not strong. Furthermore,
the basic principle of the attack does not constrain the reﬂection property andﬁxed points. Other non-random properties of round functions may also be able
to be utilized as the skip techniques, e.g., the strong correlations among round
functions.

Acknowledgments We would like to thank to Taizo Shirai, Kyoji Shibutani,Özgül Küçük, and anonymous referees for their insightful comments and suggestions.

References
1. K. Aoki and Y. Sasaki. Preimage Attacks on One-Block MD4, 63-Step MD5 andMore. In R.M. Avanzi, L. Keliher, and F. Sica, editors, SAC, volume 5381 of
Lecture Notes in Computer Science, pages 103–119. Springer, 2008.
2. E. Biham, O. Dunkelman, and N. Keller. Improved Slide Attacks. In Biryukov [3],pages 153–166.
3. A. Biryukov, editor. Fast Software Encryption, 14th International Workshop, FSE
2007, Luxembourg, Luxembourg, March 26-28, 2007, Revised Selected Papers, volume 4593 of Lecture Notes in Computer Science. Springer, 2007.
4. A. Biryukov and D. Wagner. Slide Attacks. In L. R. Knudsen, editor, FSE, volume
1636 of Lecture Notes in Computer Science, pages 245–259. Springer, 1999.
5. A. Biryukov and D. Wagner. Advanced Slide Attacks. In B. Preneel, editor,
EUROCRYPT, volume 1807 of Lecture Notes in Computer Science, pages 589–
606. Springer, 2000.
6. A. Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. B. Robshaw, Y. Seurin, and C. Vikkelsoe. PRESENT: An Ultra-Lightweight Block Cipher.
In P. Paillier and I. Verbauwhede, editors, CHES, volume 4727 of Lecture Notes in
Computer Science, pages 450–466. Springer, 2007.
7. A. Bogdanov and C. Rechberger. A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN. In Alex Biryukov, Guang
Gong, and Douglas R. Stinson, editors, Selected Areas in Cryptography, volume6544 of Lecture Notes in Computer Science, pages 229–240. Springer, 2010.
8. C. D. Cannière, O. Dunkelman, and M. Knezevic. KATAN and KTANTAN - A
Family of Small and Eﬃcient Hardware-Oriented Block Ciphers. In C. Clavier and
K. Gaj, editors, CHES, volume 5747 of Lecture Notes in Computer Science, pages
272–288. Springer, 2009.
9. D. Chaum and J. Evertse. Crytanalysis of DES with a Reduced Number of Rounds:
Sequences of Linear Factors in Block Ciphers. In H.C. Williams, editor, CRYPTO,
volume 218 of Lecture Notes in Computer Science, pages 192–211. Springer, 1985.
10. H. Demirci and A. A. Selçuk. A Meet-in-the-Middle Attack on 8-Round AES. In
Nyberg [23], pages 116–126.
11. H. Demirci, I. Taskin, M. Çoban, and A. Baysal. Improved Meet-in-the-Middle
Attacks on AES. In B. K. Roy and N. Sendrier, editors, INDOCRYPT, volume5922 of Lecture Notes in Computer Science, pages 144–156. Springer, 2009.
12. W. Diﬃe and M. E. Hellman. Exhaustive Cryptanalysis of the NBS Data Encryption Standard. Computer, 10:74–84, 1977.
13. O. Dunkelman, N. Keller, and A. Shamir. Improved Single-Key Attacks on 8Round AES-192 and AES-256. In Masayuki Abe, editor, ASIACRYPT, volume
6477 of Lecture Notes in Computer Science, pages 158–176. Springer, 2010.
14. O. Dunkelman, G. Sekar, and B. Preneel. Improved Meet-in-the-Middle Attacks
on Reduced-Round DES. In K. Srinathan, C.P. Rangan, and Moti Yung, editors,
INDOCRYPT, volume 4859 of Lecture Notes in Computer Science, pages 86–100.
Springer, 2007.
15. E. Fleischmann, M. Gorski, J. Hüehne, and S. Lucks. Key Recovery Attack on full
GOST. Block Cipher with Negligible Time and Memory. In Western European
Workshop on Research in Cryptology (WEWoRC), volume 6429 of LNCS. Springer,
2009 (to appear).
16. S. Indesteege, N. Keller, O. Dunkelman, E. Biham, and B. Preneel. A Practical
Attack on KeeLoq. In N.P. Smart, editor, EUROCRYPT, volume 4965 of Lecture
Notes in Computer Science, pages 1–18. Springer, 2008.

17. O. Kara. Reﬂection Cryptanalysis of Some Ciphers. In D.R. Chowdhury, V. Rijmen, and A. Das, editors, INDOCRYPT, volume 5365 of Lecture Notes in Computer Science, pages 294–307. Springer, 2008.
18. O. Kara and C. Manap. A New Class of Weak Keys for Blowﬁsh. In Biryukov [3],pages 167–180.
19. Y. Ko, S. Hong, W. Lee, S. Lee, and J-S. Kang. Related Key Diﬀerential Attacks on
27 Rounds of XTEA and Full-Round GOST. In B.K. Roy and W. Meier, editors,
FSE, volume 3017 of Lecture Notes in Computer Science, pages 299–316. Springer,
2004.
20. F. Mendel, N. Pramstaller, and C. Rechberger. A (Second) Preimage Attack on
the GOST Hash Function. In Nyberg [23], pages 224–234.
21. F. Mendel, N. Pramstaller, C. Rechberger, M. Kontak, and J. Szmidt. Cryptanalysis of the GOST Hash Function. In David Wagner, editor, CRYPTO, volume 5157
of Lecture Notes in Computer Science, pages 162–178. Springer, 2008.
22. National Bureau of Standards. Federal Information Processing StandardCryptographic Protection - Cryptographic Algorithm. GOST 28147-89, 1989.
23. K. Nyberg, editor. Fast Software Encryption, 15th International Workshop, FSE
2008, Lausanne, Switzerland, February 10-13, 2008, Revised Selected Papers, volume 5086 of Lecture Notes in Computer Science. Springer, 2008.
24. A. Poschmann, S. Ling, and H. Wang. 256 Bit Standardized Crypto for 650 GE GOST Revisited. In S. Mangard and F-X. Standaert, editors, CHES, volume 6225
of Lecture Notes in Computer Science, pages 219–233. Springer, 2010.
25. Y. Sasaki and K. Aoki. Finding Preimages in Full MD5 Faster Than Exhaustive Search. In A. Joux, editor, EUROCRYPT, volume 5479 of Lecture Notes in
Computer Science, pages 134–152. Springer, 2009.
26. B. Schneier. Description of a New Variable-Length Key, 64-bit Block Cipher (Blowﬁsh). In R. J. Anderson, editor, FSE, volume 809 of Lecture Notes in Computer
Science, pages 191–204. Springer, 1993.
27. B. Schneier. Applied Cryptography (2nd ed.): Protocols, Algorithms, and Source
Code in C. John Wiley & Sons, Inc., New York, NY, USA, 1995.
28. H. Seki and T. Kaneko. Diﬀerential Cryptanalysis of Reduced Rounds of GOST.
In D.R. Stinson and S.E. Tavares, editors, SAC, volume 2012 of Lecture Notes in
Computer Science, pages 315–323. Springer, 2000.