Analysis of SEED
March 24, 2003

Executive Summary
This report presents the results of a limited time evaluation of the block cipher
SEED.
SEED is a so-called Feistel cipher where the ciphertext is computed as afunction of the plaintext and the secret key in a number of rounds. The numberof rounds chosen for SEED is 16. The S-boxes used in SEED are reminiscentof that used in AES, the Advanced Encryption Standard, whereas the linear
transformation used to combine outputs of the S-boxes is new. SEED also
mixes the use of different group operations, a technique which seems to havebecome popular (although the AES does not do this).
The report contains analysis of SEED against the state-of-the-art attacks onblock ciphers. Our results are to a wide degree in line with the analysis doneby the authors.
In summary, our analysis does not show any important flaws nor weaknesses
in SEED. The best known attack at this point of time is an exhaustive search
for the key.
We note that the analysis was performed without access to complete computer code implementing the block cipher.
In the Appendix we give a compressed overview of the state-of-the-art inblock cipher cryptanalysis.

1Analysis of SEED

2

Contents
1 Introduction

32 Structural features and characteristics

3

3 Alternative, equivalent specification

44 Key-schedule4

5 Differential and linear cryptanalysis
5.1 Differential cryptanalysis . . . . . . . . . . . . . . . . . . . . . . .
5.2 Linear cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . .

88
96 Other cryptanalysis

10

7 Previous results on SEED11

A Block Ciphers in General
12
A.1 Exhaustive key search . . . . . . . . . . . . . . . . . . . . . . . . 12
A.2 The matching ciphertext attack . . . . . . . . . . . . . . . . . . . 13
A.3 Differential cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . 13
A.4 Truncated differentials . . . . . . . . . . . . . . . . . . . . . . . . 13
A.5 Impossible differentials . . . . . . . . . . . . . . . . . . . . . . . . 14
A.6 Higher-order differentials . . . . . . . . . . . . . . . . . . . . . . . 14
A.7 Linear cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . 15
A.8 Mod n cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . 15
A.9 Related-key attacks . . . . . . . . . . . . . . . . . . . . . . . . . . 15
A.10 Interpolation attack . . . . . . . . . . . . . . . . . . . . . . . . . 16
A.11 Non-surjective attack . . . . . . . . . . . . . . . . . . . . . . . . . 16
A.12 Slide attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
A.13 Integral Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

Analysis of SEED

1

3

Introduction

SEED is a 128-bit block cipher with a 128-bit key. The structure is the traditional Feistel network, an iterated cipher where the ciphertext is computed asa function of the plaintext and the key in a number of rounds. SEED has 16
rounds. In each round the inputs are divided into two halves of each 64 bits.
One half is input to a function F , whose output is exclusive-ored to the otherhalf of the input whereafter the halves are swapped. The function F divides
its input into two halves of each 32 bits. Each half is exclusive-ored with a
32-bit subkey, after which the right half is exclusive-ored to the left half. Thenthe texts enter a 3-stage mini-cipher using a function G and modular addition
modulo 232 .
The model for cryptanalysis in this report is the standard one for blockciphers, where it is assumed that the attacker has access to a black-box whichencrypts any chosen input or decrypts any chosen output using SEED with asecret, randomly chosen key.

2

Structural features and characteristics

The two S-boxes S1 and S2 used in the function G in SEED are defined asfollows: S1 (x) = A1 · x247 ⊕ b1 and S2 (x) = A2 · x251 ⊕ b2 , where A1 and A2 arebinary 8 × 8 matrices, xd denotes exponentiation in the finite field GF (28 ), “·”denotes the product of the matrix and the input x where the latter is viewed as
an 8-bit vector, and where b1 and b2 are constants.
rrr
It is well-known that (x ⊕ y)2 = x2 ⊕ y 2 in GF (2s ) for any integer valuesr, s. (In fact, a more general result applies but this is not relevant for thisdocument). The only nonlinear components in the S-boxes are the permutations
x247 and x251 in GF (28 ). It follows that both these functions are derived fromthe function x−1 = x254 in GF (28 ) and a linear function, since
x247 =

1= (x8 )−1 ,x8

1= (x4 )−1 ,x4
and both x8 and x4 are linear functions. All in all, an alternative descriptionof the S-boxes in SEED is the following: S1 (x) = A1 · (B1 · x)−1 ⊕ b1 andS2 (x) = A2 · (B2 · x)−1 ⊕ b2 , where B1 and B2 are binary 8 × 8 matrices,
representing x8 respectively x4 .
The function G is defined as follows. Let the 4-byte input be denoted(a, b, c, d), then the outputs (a0 , b0 , c0 , d0 ) are definedx251 =a0b0= (S1 (a)&m0 ) ⊕ (S2 (b)&m1 ) ⊕ (S1 (c)&m2 ) ⊕ (S2 (d)&m3 ),= (S1 (a)&m1 ) ⊕ (S2 (b)&m2 ) ⊕ (S1 (c)&m3 ) ⊕ (S2 (d)&m0 ),

(1)
(2)

c0
d0

= (S1 (a)&m2 ) ⊕ (S2 (b)&m3 ) ⊕ (S1 (c)&m0 ) ⊕ (S2 (d)&m1 ),= (S1 (a)&m3 ) ⊕ (S2 (b)&m0 ) ⊕ (S1 (c)&m1 ) ⊕ (S2 (d)&m2 ),

(3)
(4)

Analysis of SEED

4

where (m0 , m1 , m2 , m3 ) = (f cx , f 3x , cfx , 3fx ) (subscript x denotes hexadecimal
notation) and “&” is the bitwise AND operation.
By a closer look at these computations it follows that the function G is abijective mapping. As an example, given a0 , b0 , c0 , d0 one can retrieve a as follows.
The sums a0 ⊕ b0 ⊕ c0 , a0 ⊕ b0 ⊕ d0 , a0 ⊕ c0 ⊕ d0 , and b0 ⊕ c0 ⊕ d0 contain disjoint
sets of two bits of S1 (a), and as a result all eight bits of S1 (a) can be computedfrom a0 , b0 , c0 , d0 . Since S1 is a permutation, a can be found. In similar manners
the values of b, c, and d can be found.
The function F is itself a 3-stage iterated cipher, and F is bijective only if
G is bijective.
Fixed points of the S-boxes: It is argued in [2] that one reason for modifying
the outputs of the power polynomials x247 and x251 by affine mappings wasto remove the fixed points 0 and 1. However, although these affine mappings
remove these two fixed points, it has also the effect that it introduces three otherfixed points, namely 23, 230, for S-box S1 and 28 for S-box S2 .

3Alternative, equivalent specification

In this section we give an alternative specification of SEED. This is not in itself
a weakness, but for some attacks it might be advantageous to use the alternativealgorithm.
Define S(x, y) = (x ⊕ y, y), GL (x, y) = (G(x), G(x) + y) and GR (x, y) =(G(y) + x, G(y)), where ’+’ is modular addition modulo 232 . Let fK1 ,K2 be thefunction of the exclusive-or of the two subkeys in the round function F .
Then the round function F can be described as follows
GL ◦ GR ◦ GL ◦ S ◦ fK1 ,K2 (x, y).
But also the following alternative description exists. Apply S to both 64-bit
halves of the plaintext, then perform 16 rounds of encryption in a Feistel network
using the function
S ◦ GL ◦ GR ◦ GL ◦ fK1 ⊕K2 ,K2 (x, y).
Finally, apply S to both 64-bit halves of the outputs of the last round to obtainthe ciphertext. In other words, it is possible to use the function S at the endof the function F instead of in the beginning with a small modification to the
key-schedule and with a simple initial and simple final transformation of theplaintext and ciphertext.

4Key-schedule

The key-schedule of SEED takes a 128-bit user-selected key and returns 16 pairsof round keys each of two times 32 bits, in total 1024 bits.
Let the round keys in round i be denoted ki,0 and ki,1 . They are generated
as follows. The user selected key is divided into four pieces, a, b, c, d, each of 32
bits.

Analysis of SEED

5

• for i:=1 to 16 do– ki,0 = G(a + c − kci )– ki,1 = G(b − d + kci )– if i odd do b||a = (b||a)>>8
else do d||c = (d||c)<<8 ,where kci for i = 1, . . . , 16 are round constants derived in a pseudo random
fashion. We refer to [1] for the notation used.
At a first glance it appears that there are no related keys for SEED becauseof the use of the highly nonlinear function G in the key-schedule. However, there
are keys whose subkeys are related. Notice that the generation of ki,0 depends
only on the rotated versions of a and c together with the round constant. Thus if
it holds for two user-selected keys K and K ∗ that a+c is always a constant, then∗∗the subkeys ki,0 for K and the subkeys ki,0for K ∗ are equal, i.e., ki,0 = ki,0for
i = 1, . . . , 16. If a + c is to be constant for all values of i, then it must hold that(b||a) = (b||a)<<8 = (d||c) = (d||c)<<8 , which means that if a = a0 , a1 , a2 , a3 ,where ai are byte valued, and similar for b, c, and d, then it must hold that forsome constant e that• ai + cj = e for all i, j = 0, 1, 2, 3,• ai + dj = e for all i, j = 0, 1, 2, 3,• bi + cj = e for all i, j = 0, 1, 2, 3,• bi + dj = e for all i, j = 0, 1, 2, 3,
Summing up, let the user-selected key be divided into the 32-bit words a, b, c, d.
Consider the keys obtained from having a0 = a1 = a2 = a3 = x for some value
x, b = a, c0 = c1 = c2 = c3 = y, for some value y, and d = c. Then it holds
that the keys for which x + y is a constant will produce the same values for ki,0for i = 1, . . . , 16. Thus, there are 216 keys which can be divided into 256 classesof each 256 keys, such that in one class all 256 keys produce identical values ofthe subkeys ki,0 for i = 1, . . . , 16. Table 1 lists three keys and the subkeys theygenerate.
It follows by very similar observations that there are 216 keys which can bedivided into 256 classes of each 256 keys, such that in one class all 256 keys
produce identical values of the subkeys ki,1 for i = 1, . . . , 16. Table 2 lists three(other) keys and the subkeys they generate.
Despite of these findings the key-schedule of SEED does not seem to allow
for related-key attacks. First of all, the “related keys” reported above are few,
second, the relations between them does not seem to be strong enough to allow
for these kinds of attacks.
The above phenomena are not a threat for SEED when used for encryption.
If a key is chosen uniformly at random, the probability to pick one of the above
keys is very small. Moreover it is not clear for which applications an attacker

Analysis of SEED

6

Key =
Round key no.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

9b9b9b9b9b9b9b9b4124db1d9a0f9a3a
79efee8e57215006
03c24bbc
c0a53c4c
cf3ebb62
2a14ef6c
7b85aa09f527f311
4ee60e85
26d5c935
803e5e92c91d482b
0788fd30
f92d78ce

3451bd29
4b127456
273d39c9b12689b3
5f7092c7
2b831b79
d29fac9aa2c6cfe2
07894284
9100f2f914546a91
864101db
34e0e2c0
2b10ede5
2d60d71e
2bd7ef41

Key =Round key no.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3a3a3a3a3a3a3a3a4124db1d9a0f9a3a
79efee8e57215006
03c24bbc
c0a53c4c
cf3ebb62
2a14ef6c
7b85aa09f527f311
4ee60e85
26d5c935
803e5e92c91d482b
0788fd30
f92d78cee0ef1874
711b066c
5c178ff90b809197
26afe9b0
3c1b8a18573ddbb6
c0be0d1075080ba7
56ab375e
39e99972
1591baad
0ffc828b
2d9680fc
8e5a5bd0
5e235141

2a2a2a2a2a2a2a2a4124db1d9a0f9a3a
79efee8e57215006
03c24bbc
c0a53c4c
cf3ebb62
2a14ef6c
7b85aa09f527f311
4ee60e85
26d5c935
803e5e92c91d482b
0788fd30
f92d78ce

07460ff4
b82298f4
7ee3b13e46c3d6b0
4af65578
1bb446d4
0b5a1d9e
bfaa5324
4c16e012
1d68f56f
7def7131
52eff20b3c3c924e
e02f858f
74fd6be4
a9ccd586

Key =Round key no.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

11111111

11111111

72727272

72727272

82828282

82828282

Table 1: Examples of keys which produce equal first subkeys in every round.

Analysis of SEED

7

Key =
Round key no.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

9b9b9b9b9b9b9b9b68c9edf1
7e8e4d27
aa37e9ee
5da694ad
c61b186a
45dc4ae5
05ce5df3
9ab323b3
a08e3ccc
8c92b18477553f19
24e69b24
bca52806
dd2474e90eeecd5b
3685e91e

7d28cbaf
f9c76fad
f59dd258
7605924ab3c83014
bfb0fcbe
fd6a1882
6ef967c7d883dcd7
13ddd10c
af7cecc4
e007b43e
5f7651a0
1e09a2f2
9c28a623
bcad5740

Key =Round key no.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3a3a3a3a3a3a3a3a0d92c044
de60205ad9258549
9d84df1f
ea0a79a8
638fd5fa
470a077c
c252c5d8
a6b5f762
a55b43b7
ca3a056e
a678af9c
4aa21758
a0ab171a
1d432710
ad80bb01

7d28cbaf
f9c76fad
f59dd258
7605924ab3c83014
bfb0fcbe
fd6a1882
6ef967c7d883dcd7
13ddd10c
af7cecc4
e007b43e
5f7651a0
1e09a2f2
9c28a623
bcad5740

2a2a2a2a2a2a2a2af23c7655
0b5f9dbd
656eb6da
886b8015
caac1ba954d62348
a9bdeb44
8bb07ddf
661831f3
05090fea
60f094cc
3393a0f5770ab190
10702afd
0ef8e298
7c8e917d

7d28cbaf
f9c76fad
f59dd258
7605924ab3c83014
bfb0fcbe
fd6a1882
6ef967c7d883dcd7
13ddd10c
af7cecc4
e007b43e
5f7651a0
1e09a2f2
9c28a623
bcad5740

Key =Round key no.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

efefefef

efefefef

8e8e8e8e8e8e8e8e7e7e7e7e7e7e7e7e

Table 2: Examples of keys which produce equal second subkeys in every round.

Analysis of SEED

8

would be able to exploit the use of such keys. On the other hand, such similarities between the subkeys of different keys do not appear in other modern blockciphers and could probably have been prevented.

5Differential and linear cryptanalysis

5.1

Differential cryptanalysis

In differential cryptanalysis one talks about an active S-box if the inputs to the
S-box are different. The branch number [9] of a function consisting of several
S-boxes is defined to be the least number of active S-boxes in any inputs and in
the corresponding outputs for the particular function. The branch number ofthe function G in SEED is four. This is an easy exercise to show. If the inputs
to G have only one active S-box then the outputs have four active S-boxes, intotal five active S-boxes. If the inputs to G have two active S-boxes then the
outputs have at least two active S-boxes, in total at least four active S-boxes in
the inputs and outputs, which is an effect of the used masks, m0 , m1 , m2 , m3 .
If the inputs to G have three active S-boxes then the outputs have at least one
active S-boxes, in total at least four active S-boxes, which follows from the factthat G is a bijective mapping. So, clearly the branch number is four.
Next we consider the function F which has three applications of the bijectivefunction G. It follows by a closer look that the number of active G-functions in
F is at least two. In other words, for any pair of different inputs to the function
F there will be different inputs to at least two of the three G functions.
Let us first look at a simplified version of SEED, where the modular additions
are replaced by exclusive-ors, as was done in [1]. Let us denote by F 0 the
resulting modified function of F . From the branch number of the function G it
follows that the number of active S-boxes in total for the function F 0 is always
at least four.
Since the function F 0 is bijective for a r-round characteristic for SEED there
will be different inputs to at least br/3c · 2 F 0 -functions. SEED has 16 rounds
and previous experience show that in a successful differential attack one needs
to be able to specify a characteristic over at least 13 rounds (but possible up
to 15 in case of SEED). This means that in at least eight of the rounds the
inputs to F are different. As a consequence, it is estimated that in a successful
differential attack the characteristics involved will give rise to 32 active S-boxes.
The best characteristic over one S-box in SEED has a probability of 2−6 , whichmeans that a characteristic with 32 active S-boxes will have a probability of
2−192 . This is certainly low enough to conclude that a differential attack on
the modified version of SEED based on characteristics, as outlined here, is very
unlikely to be possible.
However, from this analysis of SEED using the modified function F 0 one cannot conclude directly a similar result for unmodified SEED. The reason for thisis the mixed use of the group operations, modular addition and exclusive-or. In
the above differential analysis of modified SEED we used the exclusive-or of twoAnalysis of SEED

9

inputs as the definition of a difference of two inputs. However, when two halvesin F are combined with the modular addition operation, the number of active
S-boxes can change and in fact decrease. This has the effect that the number ofactive S-boxes in total for the function F can be less than the above stated 4.
We illustrate this with an example which has been found in experiments. Let
the (exclusive-or) differences in the two inputs to the function F be 000011d4x
and 000011d4x , that is, there are equal differences in the two halves. Clearly,
the differences are unchanged after the exclusive-or of the subkeys. The next
operation is to exclusive-or the right half of the input to the left half. As aconsequence the inputs to the first application of G are equal as are the outputs, and the number of active S-boxes are zero. In the following operation theleft half is added (mod 232 ) to the right half. With some high probability thismeans that there are two active S-boxes in the inputs to the second applicationof G. As explained above (and in [1]) there is a positive probability that in the
outputs of G there are again two active S-boxes. The next operation is to add
the right half to the left half. In the example, the left halves (in the two texts
considered) are equal at this point, and with a positive probability the modular
addition can have the effect that there is only one active S-box in the inputs
to the third application of G. In the example, the differences in the two halvesat this point were 0000f f 00x and 00010100x . It follows that in total for thisdifferential there were only three active S-boxes in the G functions. Therefore
one cannot directly take the analysis of SEED using the modified function F 0
and transfer them to SEED with the unmodified function F .
A complete analysis of F and SEED with respect to differential cryptanalysis
is very complex and involved and it is unlikely that one can ever conclude having
found the best differentials for SEED. However, it seems highly unlikely that
one can find differentials with only 3 active S-boxes per round for an r-rounddifferential for large values of r. An estimate that at least three active S-boxes
are needed in two of every three rounds of a differential still gives a low, best
differential probability. As an example, in a 13-round differential the inputs
to at least eight F functions will be different, which using the new bound will
give rise to at least 24 active S-boxes. The best characteristic over one S-box in
SEED has a probability of 2−6 , which means that a differential over 13 rounds
will have a probability of at most 2−144 , which is low enough to conclude thata differential attack is unlikely to be found on SEED with the current state-ofthe-art.

5.2

Linear cryptanalysis

As for differential cryptanalysis one speaks about active S-boxes in the linear
characteristics considered. In this case, an S-box is called active if one or more
bits in the linear approximations are used as input or output of the particular
S-box. For the function F a linear approximation must involve bits in the inputs
and outputs of at least two of the three G functions, as also stated in [1].
It is possible to build linear approximations across one G-function with only
one active S-box. For example, above it is shown that the sum of three output

Analysis of SEED

10

bytes of G give two bits of one of the bytes output from an S-box. However, itappears to be very difficult to build good linear approximations for the function
F and for several rounds of SEED using approximations with only one active
S-box per active G function. The best approach seems to be that of [1] which
involves two active S-boxes per G function involved in the approximation. It is
possible at this point to give an upper bound to the best linear approximations
for r rounds of SEED using arguments similar to the ones in the differential
analysis above.
Let us first consider a version of SEED where the modular additions are
replaced by exclusive-or operations. A linear approximation across r rounds will
involve the inputs to at least br/3c · 2 F 0 -functions. Previous experience show,
as in differential cryptanalysis, that for a 16-round Feistel cipher a successful
linear attacker needs to be able to specify a characteristic over at least 13 rounds.
This means that in at least eight of the rounds the inputs to F are involved. In
each of these rounds it is safe to estimate that there will be at least four active
S-boxes. Since the linear probability, see e.g., [1] for a definition, for one S-box
is at most 2−6 , one gets an estimate for 13 rounds of 2−192 . These estimates
were made on a simplified version of SEED without incorporating the effectof the modular additions. The mixed use of exclusive-or operations and themodular additions is likely to complicate a linear attack even further. Where
this mixed use of operations could potentially help an attack in a differential
attack it seems it will only worsen things for an attacker in a linear attack.
Modular additions introduce carry bits which will lower the probabilities of theinvolved characteristics. We believe that it is safe to conclude that it is very
unlikely that SEED is vulnerable to a linear attack.

6

Other cryptanalysis

There are trivial attacks on all block ciphers. An exhaustive search for thesecret key of SEED can be done using only a few known plaintexts and theircorresponding ciphertexts in time about 2128 . Also, the “matching ciphertext
attack” applies in the Electronic Code Book and Cipher Block Chaining modes
and requires about 264 ciphertext blocks to succeed with good probability andwhich enables the attacker to deduce information about the plaintext blocks.
Higher order differentials. This attack applies to ciphers which uses nonlinear
components of a low algebraic degree. The S-boxes of SEED have an algebraic
degree of seven, which is the maximum degree for a bijective S-box on 8 bits.
There are three layers of S-boxes in every F -function of one round and a total of
16 rounds. Therefore since an attack based on dth order differentials requires acollection of 2d texts, it is very likely that the algebraic degree of the ciphertexts
as a function of plaintexts is high enough to prevent a higher order differential
attack from being practical, if possible at all.
The integral attacks apply to only a few rounds of SEED. It is conjectured
that reduced versions of SEED with up to six rounds is vulnerable to these
attacks but not versions with more than six rounds.

Analysis of SEED11

The interpolation attacks apply to ciphers which use simple mathematical
functions only. The S-boxes in SEED are constructed from the inverse function
in a finite field, which has a simple description. However, the fact that both the
inputs and outputs are mixed with affine mappings makes the description much
more complex. This together with the mixed use of exclusive-ors and modular
additions make the interpolation attacks very unlikely to be applicable.
The slide attacks apply best to ciphers with very simple key-schedules. However, the key-schedule of SEED uses both the S-boxes and different round constants, which are good means to prevent these attacks from being effective.
The non-surjective attacks are not applicable as the round function is bijective and thus not vulnerable to these attacks.

7

Previous results on SEEDAs far as we are informed the only public analysis of SEED is that of the authors
themselves [1]. The analysis in this paper is much in line with this analysis by
the authors. However, we reported on a few things which the authors do notseem to have noticed.
First of all, the S-boxes are both derived from the inverse function in a
Galois field. This makes the S-boxes similar to those of the AES. For the
AES several reports have indicated that the use of linear transformations of theinverse in a Galois field as the only nonlinear component in a block cipher might
be dangerous. However, one important difference between SEED and AES inthis respect is that the former uses a mix of group operations, the exclusive-or
and additions modulo 232 . Therefore, the concerns for the AES that it might
be possible to express the ciphertexts as a simple mathematical expression of
the plaintext and the key do not apply in the same degree for SEED.
For the key-schedule it was shown in [1] that related-key attacks are notapplicable and that no weak or semi-weak keys exist. In our report we notedthat there are keys which produce sets of subkeys with many common elements.
This feature was not exploited in any attacks and might not appear to be serious
for SEED, however they do illustrate properties for keys which are not usuallyseen in modern block ciphers.
In [1] it was concluded that SEED is not vulnerable to a differential attack.
To facilitate an easier analysis the authors first consider a simplified version of
SEED. For this version a search was made for the best differential characteristics and subsequently these characteristics were considered for (the unmodified)
SEED. However we demonstrated that this approach might not always lead tothe best characteristics. There are cases where the elements in the unmodified
SEED not present in the simplified SEED have an important influence on theexistence of certain differential characteristics. However a full differential analysis of unmodified SEED is a very difficult, if not impossible, task. Our estimatesof bounds on the success of differential attacks are more crude than those of [1]but still with a sufficiently wide security margin.
The previous statement applies also linear attacks. The analysis in [1] isAnalysis of SEED

12

more detailed that our analysis, but our estimates more crude. Both analyses
conclude that SEED does not seem vulnerable to a linear attack.
Finally, one reason for the linear transformations applied to the power polynomials in the S-boxes of SEED was to remove the two fixed points 0 and
1. However, even though the chosen linear transformations remove these fixed
points, they introduce three other fixed points. It is not clear why the authors
are more concerned about the fixed points 0 and 1 than about other fixed points.

A

Block Ciphers in GeneralIn the following we give a compressed overview of the state-of-the-art of blockcipher cryptanalysis, and outline the following known attacks.
1. Exhaustive Key Search
2. Matching Ciphertext Attacks
3. Differential Cryptanalysis
4. Truncated Differential Attacks
5. Higher-order Differential Attacks
6. Linear Cryptanalysis
7. Related-key Attacks
8. Non-surjective Attacks
9. Interpolation Attacks
10. Mod-n Attacks
11. Slide Attacks
12. Integral Attacks

A.1

Exhaustive key searchThis attack needs only a few known plaintext-ciphertext pairs. An attacker
simply tries all keys, one by one, and checks whether the given plaintext encrypts
to the given ciphertext. For a block cipher with a k-bit key and n-bit blocks thenumber of pairs of texts needed to determine the key uniquely is approximately
dk/ne. Also, if the plaintext space is redundant, e.g., consists of English or
Japanese text, the attack will work if only some ciphertext blocks is available.
The number of ciphertext blocks needed depends on the redundancy of thelanguage.

Analysis of SEED

A.2

13

The matching ciphertext attack

The matching ciphertext attack is based on the fact that for block ciphers of m
bits used in the modes of operations for the DES [26] after the encryption of
2m/2 blocks, equal ciphertext blocks can be expected and information is leaked
about the plaintexts [7, 15, 24].

A.3

Differential cryptanalysis

The most well-known and general method of analysing conventional cryptosystems today is differential cryptanalysis, published by Biham and Shamir in 1990.
Differential cryptanalysis is universal in the sense that it can be used against
any cryptographic mapping which is constructed from iterating a fixed round
function. One defines a difference between two bit strings, X and X 0 of equal
length as∆X = X ⊗ (X 0 )−1 ,(5)where ⊗ is the group operation on the group of bit strings used to combine
the key with the text input in the round function and where (X)−1 is theinverse element of X with respect to ⊗. The idea behind this is, that thedifferences between the texts before and after the key is combined are equal,i.e., the difference is independent of the key. To see this, note that(X ⊗ K) ⊗ (X 0 ⊗ K)−1 = X ⊗ K ⊗ K −1 ⊗ X 0−1 = X ⊗ (X 0 )−1 = ∆X.
In a differential attack one exploits that for certain input differences the distribution of output differences of the non-linear components is non-uniform.
Definition 1 An s-round characteristic is a series of differences defined as ans + 1-tuple {α0 , α1 , . . . , αs }, where ∆P = α0 , ∆Ci = αi for 1 ≤ i ≤ s.
Here ∆P is the difference in the plaintexts and ∆Ci is the difference in the
ciphertexts after i rounds of encryption. Thus, the characteristics are lists of
expected differences in the intermediate ciphertexts for an encryption of a pairof plaintexts. In essence one specifies a characteristic for a number of rounds
and searches for the correct key in the remaining few rounds. In some attacks
it is not necessary to predict the values α1 , . . . , αs−1 in a characteristic. The
pair (α0 , αs ) is called a differential. The complexity of a differential attack isapproximately the inverse of the probability of the characteristic or differential
used in the attack.

A.4

Truncated differentials

For some ciphers it is possible and advantageous to predict only the values ofparts of the differences after each round of the cipher. The notion of truncateddifferentials was introduced by Knudsen [17]:Analysis of SEED

14

Definition 2 A differential that predicts only parts of an n-bit value is calleda truncated differential. More formally, let (a, b) be an i-round differential. If
a0 is a subsequence of a and b0 is a subsequence of b, then (a0 , b0 ) is called an
i-round truncated differential.
A truncated differential can be seen as a collection of differentials. As an example, consider an n-bit block cipher and the truncated differential (a0 , b), wherea0 specifies the least n0 < n significant bits of the plaintext difference and b
specifies the ciphertext difference of length n. This differential is a collection
0of all 2n−n differentials (a, b), where a is any value, which truncated to the n0
least significant bits is a0 .

A.5

Impossible differentials

A special type of differentials are those of probability zero. The attack was first
applied to the cipher DEAL [18] and later to Skipjack [4]. The main idea isto specify a differential of probability zero over some number of rounds in theattacked cipher. Then by guessing some keys in the rounds not covered by thedifferential one can discard a wrong value of the key if it would enable the cipher
to take on the differences given in the differential.

A.6

Higher-order differentials

An sth-order differential is defined recursively as a (conventional) differentialof the function specifying an (s − 1)st order differential. In order words, an
sth order differential consists of a collection of 2s texts of certain pairwise,predetermined differences. We refer to [20, 17] for a more precise definition ofhigher order differentials.
In most cases one considers differences induced by the exclusive-or operationand the field of characteristic 2. The nonlinear order of a function f : GF (2n ) →GF (2n ) is defined as follows. Let the output bits yj be expressed as multivariate
polynomials qj (x) ∈ GF (2)[x1 , . . . , xn ], where x1 , . . . , xn are the input bits. The
nonlinear order of f is then defined to be the minimum total degree of any linear
combination of these polynomials. The higher order differential attacks exploit
the following result.
Corollary 1 Let f : GF (2n ) → GF (2n ) be a function of nonlinear order d.
Then any dth order differential is a constant. Consequently, any (d + 1)st orderdifferential is zero.
The boomerang attack [28] can be seen as a special type of a second-orderdifferential attack. This variant applies particularly well to ciphers for which
one particular (first-order) differential applies well to one half of the cipher, andwhere another particular (first-order) differential applies well to the other halfof the cipher.

Analysis of SEED

A.7

15

Linear cryptanalysis

Linear cryptanalysis was proposed by Matsui in 1993 [21]. A preliminary versionof the attack on FEAL was described in 1992 [23]. Linear cryptanalysis [21] isa known plaintext attack in which the attacker exploits linear approximationsof some bits of the plaintext, some bits of the ciphertext and some bits of thesecret key. In the attack on the DES (or on DES-like iterated ciphers) the linear
approximations are obtained by combining approximations for each round under
the assumption of independent round keys. The attacker hopes in this way tofind an expression(P · α) ⊕ (C · β) = (K · γ)
(6)which holds with probability pL 6= 12 over all keys [21], such that |pL − 12 |, called
the bias, is maximal. In (6) P, C, α, β, γ are m-bit strings and ‘·’ denotes thedot product. The bit strings α, β, γ are called masks.
Definition 3 An s-round linear characteristic is a series of masks defined asan (s + 1)-tuple {α0 , α1 , . . . , αs }, where α0 is the mask of the plaintexts and αiis the mask of the ciphertexts after i rounds of encryption for 1 ≤ i ≤ s.
As for differential cryptanalysis one specifies a linear characteristics for a numberof rounds and searches for the keys in the remaining rounds, we refer to [21] formore details. A linear attack needs approximately about b−2 known plaintexts
to succeed, where b is the bias of the linear characteristic used.
Also, the concepts of linear hulls, the analogue to differentials as opposed tocharacteristics in differentials cryptanalysis, has been defined in [25].
Finally, in [22] it has been shown that if one defines the quantity q = (2p−1)2where p is the probability of a linear characteristic or hull, then when combining
several linear characteristics one can multiply their q values to get the q-valueof the combination. Sometimes the q values are referred to as the “linear probability”, which is somewhat misleading, but nevertheless seems to be widely
used.

A.8

Mod n cryptanalysis

In [13] a generalisation of the linear attacks is considered. This attack is applicable to ciphers for which some words (in some intermediate ciphertext) are biased
modulo n, where n typically is a small integer. It has been shown that cipherswhich uses only bitwise rotations and additions modulo 232 are vulnerable tothese kinds of attacks.

A.9

Related-key attacks

There are several variants of this attack depending on how powerful the attacker
is assumed to be.
1. Attacker gets encryptions under one key.
2. Attacker gets encryptions under several keys.

Analysis of SEED

16(a) Known relation between keys.
(b) Chosen relation between keys.
Knudsen used the methods of 1 by giving a chosen plaintext attack of the firstkind on LOKI’91 [14], reducing an exhaustive key search by almost a factor offour. The concept “related-key attack” was introduced by Biham [3], who also
introduced the attack scenarios of 2, where the encryptions under several keys
are requested. Knudsen later described a related key attack on SAFER K [16]and Kelsey, Schneier, and Wagner [12] applied the related key attacks to a wide
range of block ciphers. It may be argued that the attacks with a chosen relation
between the keys are unrealistic. The attacker need to get encryptions under
several keys, in some attacks even with chosen plaintexts. However there exist
realistic settings, in which an attacker may succeed to obtain such encryptions.
Also, there exists quite efficient methods to preclude the related key attacks[12, 10].

A.10

Interpolation attack

In [11] Jakobsen and Knudsen introduced the interpolation attack on blockciphers. The attack is based on the following well-known formula. Let R be afield. Given 2n elements x1 , . . . , xn , y1 , . . . , yn ∈ R, where the xi s are distinct.
DefinenXYx − xjf (x) =yi.
(7)xi − xj
i=1
1≤j≤n,j6=i

f (x) is the only polynomial over R of degree at most n − 1 such that f (xi ) = yi
for i = 1, . . . , n. Equation (7) is known as the Lagrange interpolation formula(see e.g.,[6, page 185]). In the interpolation attack an attacker constructs polynomials using pairs of plaintexts and ciphertexts. This is particularly easy if
the components in the cipher can be expressed as easily described mathematical functions. The idea of the attack is, that if the constructed polynomials
have a small degree, only few plaintexts and their corresponding ciphertexts arenecessary to solve for the (key-dependent) coefficients of the polynomial, e.g.,using Lagrange’s interpolation. To recover key bits one expresses the ciphertext
before the last round as a polynomial of the plaintext.

A.11

Non-surjective attack

In [27] Rijmen-Preneel-De Win described the non-surjective attack on iterated
ciphers. It is applicable to Feistel ciphers where the round function is not surjective and therefore statistical attacks become possible. In a Feistel cipher one cancompute the exclusive-or of all outputs of the round functions from the plaintexts and the corresponding ciphertexts. Thus, if the round functions are notsurjective this gives information about intermediate values in the encryptions,which can be used to get information about the secret keys.

Analysis of SEED

A.12

17

Slide attacks

In [5] the “slide attacks” were introduced, based on earlier work in [3, 14]. In
particular it was shown that iterated ciphers with identical round functions,that is, equal structures plus equal subkeys in the rounds, are susceptible toslide attacks. Let Fr ◦ Fr−1 ◦ · · · ◦ F1 denote an r-round iterated cipher, where
all Fi s are identical. The attacker tries to find pairs of plaintext P, P ∗ andtheir corresponding ciphertexts C, C ∗ , such that F1 (P ) = P ∗ and Fr (C) = C ∗ .
Subsequently, an attacker has twice both the inputs and outputs of one roundof the cipher. If the round function is simple enough, this can lead to very
efficient attacks. To find such pairs of texts, one can in the worst case apply thebirthday paradox, such that one such pair is expected from a collection of 2n/2
texts, where n is the block size.

A.13

Integral Attacks

These attacks are sometimes referred to as the “Square attack”, since it was first
applied to the block cipher Square [8]. The attack on Square slightly modified
also applies to the block ciphers Crypton and Rijndael [9].
In [19] these attacks are generalised under the name of “integral cryptanalysis”. In differential attacks one considers differences of texts, in integral cryptanalysis one considers sums of texts. In ciphers where all nonlinear functions
are bijective, it is sometimes possible to predict a sum of texts, even in the cases
where differential attacks are not applicable. The main observations are that ina collection of texts which in a particular word take all values exactly equally
many times, the value of the words after a bijective function also take all values
exactly equally many times. Also, assume that s words have this property andthat in the cipher a linear combination of the s words are computed (with respect to the group operation considered). Then it is possible to determine also
the sum of all linear combinations in a collection of texts. This attack is still
today the best attack reported on Rijndael which has been the selected for the
Advanced Encryption Standard.

References[1] ANNEX. The analyses of SEED. Document.
[2] KOREAN CONTRIBUTION ON NP 18033 ”ENCRYPTION ALGORITHM”. Document.
[3] E. Biham. New types of cryptanalytic attacks using related keys. In T. Helleseth, editor, Advances in Cryptology: EUROCRYPT’93, LNCS 765, pages
398–409. Springer Verlag, 1993.
[4] E. Biham, A. Biryukov, and A. Shamir. “Impossible” cryptanalysis. Presented at the rump session of CRYPTO’98.

Analysis of SEED

18

[5] A. Biryukov and D. Wagner. Slide attacks. In L. R. Knudsen, editor, Fast
Software Encryption, Sixth International Workshop, Rome, Italy, March
1999, LNCS 1636, pages 245–259. Springer Verlag, 1999.
[6] P.M. Cohn. Algebra, Volume 1. John Wiley & Sons, 1982.
[7] D. Coppersmith, D.B. Johnson, and S.M. Matyas. Triple DES cipher blockchaining with output feedback masking. Technical Report RC 20591, IBM,
October 1996. Presented at the rump session of CRYPTO’96.
[8] J. Daemen, L. Knudsen, and V. Rijmen. The block cipher Square. In
E. Biham, editor, Fast Software Encryption, Fourth International Workshop,
Haifa, Israel, January 1997, LNCS 1267, pages 149–165. Springer Verlag,
1997.
[9] J. Daemen and V. Rijmen.
AES proposal: Rijndael.
Submitted
as an AES Candidate Algorithm. Description available from NIST, see
http://www.nist.gov/aes.
[10] I.B. Damgård and L.R. Knudsen. Two-key triple encryption. The Journalof Cryptology, 11(3):209–218, 1998.
[11] T. Jakobsen and L. Knudsen. The interpolation attack on block ciphers. In
E. Biham, editor, Fast Software Encryption, Fourth International Workshop,
Haifa, Israel, January 1997, LNCS 1267, pages 28–40. Springer Verlag, 1997.
[12] J. Kelsey, B. Schneier, and D. Wagner. Key-schedule cryptanalysis of IDEA,
G-DES, GOST, SAFER, and triple-DES. In Neal Koblitz, editor, Advancesin Cryptology: CRYPTO’96, LNCS 1109, pages 237–251. Springer Verlag,
1996.
[13] J. Kelsey, B. Schneier, and D. Wagner. Mod n cryptanalysis, with applications against RC5P and M6. In L. Knudsen, editor, Fast Software Encryption, Sixth International Workshop, Rome, Italy, March 1999, LNCS 1636,
pages 139–155. Springer Verlag, 1999.
[14] L.R. Knudsen. Cryptanalysis of LOKI’91. In J. Seberry and Y. Zheng,
editors, Advances in Cryptology, AusCrypt 92, LNCS 718, pages 196–208.
Springer Verlag, 1993.
[15] L.R. Knudsen. Block Ciphers – Analysis, Design and Applications. PhD
thesis, Aarhus University, Denmark, 1994.
[16] L.R. Knudsen. A key-schedule weakness in SAFER K-64. In Don Coppersmith, editor, Advances in Cryptology - CRYPTO’95, LNCS 963, pages
274–286. Springer Verlag, 1995.
[17] L.R. Knudsen. Truncated and higher order differentials. In B. Preneel,
editor, Fast Software Encryption - Second International Workshop, Leuven,
Belgium, LNCS 1008, pages 196–211. Springer Verlag, 1995.

Analysis of SEED

19[18] L.R. Knudsen. DEAL - a 128-bit block cipher. Technical Report 151,
Department of Informatics,University of Bergen, Norway, February 1998.
Submitted as an AES candidate by Richard Outerbridge.
[19] L.R. Knudsen and D. Wagner. Integral cryptanalysis. In FSE 2002.
[20] X. Lai. Higher order derivatives and differential cryptanalysis. In R. Blahut,
editor, Communication and Cryptography, Two Sides of One Tapestry.
Kluwer Academic Publishers, 1994. ISBN 0-7923-9469-0.
[21] M. Matsui. Linear cryptanalysis method for DES cipher. In T. Helleseth,editor, Advances in Cryptology - EUROCRYPT’93, LNCS 765, pages 386–
397. Springer Verlag, 1993.
[22] M. Matsui. New structure of block ciphers with provable security against
differential and linear cryptanalysis. In D. Gollman, editor, Fast Software
Encryption, Third International Workshop, Cambridge, UK, February 1996,
LNCS 1039, pages 205–218. Springer Verlag, 1996.
[23] M. Matsui and A. Yamagishi. A new method for known plaintext attackof FEAL cipher. In R. Rueppel, editor, Advances in Cryptology - EUROCRYPT’92, LNCS 658, pages 81–91. Springer Verlag, 1992.
[24] U.M. Maurer. New approaches to the design of self-synchronizing stream
ciphers. In D.W. Davies, editor, Advances in Cryptology - EUROCRYPT’91,
LNCS 547, pages 458–471. Springer Verlag, 1991.
[25] K. Nyberg. Linear approximations of block ciphers. In A. De Santis,
editor, Advances in Cryptology - EUROCRYPT’94, LNCS 950, pages 439–
444. Springer Verlag, 1995.
[26] National Bureau of Standards. DES modes of operation. Federal Information Processing Standard (FIPS), Publication 81, National Bureau of Standards, U.S. Department of Commerce, Washington D.C., December 1980.
[27] V. Rijmen, B. Preneel, and E. De Win. On weaknesses of non-surjectiveround functions. Designs, Codes, and Cryptography, 12(3):253–266, 1997.
[28] D. Wagner. The boomerang attack. In L. R. Knudsen, editor, Fast Software
Encryption, Sixth International Workshop, Rome, Italy, March 1999, LNCS
1636, pages 156–170. Springer Verlag, 1999.