Security Analysis of theBlock Cipher SC2000

VERSION 1.1

FINAL REPORTAlex Biryukov
University of Luxembourg, Luxembourg
Ivica Nikolić
Nanyang Technological University, Singapore

Contents
1 Introduction
1.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Known Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Analysis of the Transformations . . . . . . . . . . . . . . . . . . .
1.3.1 S-box Analysis . . . . . . . . . . . . . . . . . . . . . . . .
1.3.2 Analysis of the Linear Transformations . . . . . . . . . .
1.3.3 Analysis of the Word-oriented Transformations in the Key
Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3
3
4
4
4
4

2 An Attack on SC2000-256
2.1 A Dedicated Attack on SC2000-256 . . . . . . . . . . . . . . . .
2.1.1 Description of the Framework . . . . . . . . . . . . . . . .
2.1.2 The Attack on SC2000-256 . . . . . . . . . . . . . . . . .
2.1.3 Other Attack Frameworks . . . . . . . . . . . . . . . . . .
2.1.4 Applications to SC2000-128 and SC2000-192 . . . . . . .

6
6
6
7
10
12

4

3 Analysis Against Various Attacks
13
3.1 Differential Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . 13
3.1.1 Single-key Differentials . . . . . . . . . . . . . . . . . . . . 13
3.1.2 Related-key Differentials . . . . . . . . . . . . . . . . . . . 14
3.2 Impossible Differential Attacks . . . . . . . . . . . . . . . . . . . 17
3.3 Slide Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.4 Rotational Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2

Chapter 1

Introduction
1.1

Description

SC2000 is 128-bit block cipher with a variable number of rounds that depends
on the key size: 6.5 rounds for 128-bit key, and 7.5 rounds for 192-bit and 256bit keys. The cipher is word-oriented – all of the transformations are word-wise,with the exception of the S-boxes which are applied to a subset of bits within asingle word. Each round of SC2000 is composed of two subkey addition layers
If unc , one S-box layer Bf unc , and two one-round Feistel layers Rf unc . The
layers can be described as follows:• If unc - XOR of 4 subkey words to the state words• Bf unc - application of S-boxes to the state words. First a matrix 4x32 is
produced from the state words, and then an S-box is applied to each 4-bit
column of the matrix• Rf unc - One round Feistel is applied to the four words. The round function
F is composed of S-box layer, and two linear layers
The key schedule of SC2000 expands the initial master key into subkeys in threesteps:
1. Extensions to 8 words. In the cases of 128-bit and 192-bit keys, the masterkey is extended to 8 words (256-bits) by copying words of the key
2. Intermediate key generation. The 8 words of the key are threated as 4pairs of words. Each pair undergoes a series of transformation (involving
S-boxes, linear transformations, XORs and modular additions) and foreach pair 3 intermediate keys are produced.
3. Extended key generation. The 12 intermediate keys are extended to 56(or 64) subkey words – each subkey word is generated from 4 intermediatewords with application of word-wise operations: modular addition, XOR,
and rotation.
3

SECURITY ANALYSIS OF THE BLOCK CIPHER SC2000

SC2000 applies unconventionally high number of distinct transformations,
including S-boxes of different sizes, bit-oriented matrix multiplication, logicaloperations AND,OR, XOR, NOT, word-oriented rotations, modular additions
and subtractions in the key schedule. This mixture of transforms makes SC2000
exceptionally hard to analyze.

1.2

Known Analysis

There are only a few published results on the analysis of SC2000 . All the attacks
are on round-reduced versions of the cipher: boomerang/rectangle attacks on
3.5 rounds [1], differential and linear attack on up to 4.5 rounds [5, 6] and adifferential attack on 5 rounds [4].

1.3

Analysis of the Transformations

To estimate the resistance of SC2000 against various attack, first we focus oneach of the transformations used in the cipher. In particular, we analyze the
S-boxes and the linear transformations.

1.3.1

S-box Analysis

The complexity of the differential attacks on a cipher is tightly related to thedifferential properties of the S-boxes used in the cipher. SC2000 applies four
different types of non-linear bijective S-boxes: one 6x6 S-box, one 5x5 S-box,
and two 4x4 S-boxes. The maximal differential propagation probabilities are
2−4 , 2−4 , 2−2 , respectively. Hence we can conclude that the S-boxes are optimal
against differential attacks.

1.3.2

Analysis of the Linear Transformations

Two types of linear transformations are used in the round function: Mf unc
and Lf unc . The branch number of the matrix multiplication Mf unc , i.e. theminimal number of active input and output bits, is 9. This is sub-optimal, as
the maximal branch number for this type of transformations is 33, and in thelinear case it is 12. Low branch number could lead to potential (impossible)
differential attacks on higher number of rounds, due to the low diffusion of thebits. Lf unc can be seen as another matrix (64x64) multiplication with a branchnumber 2. However, we believe its main purpose is to introduce diffusion of bits
between two words, rather than diffusion within a single word.

1.3.3

Analysis of the Word-oriented Transformations in
the Key Schedule

Besides the previously mentioned transformations, the key schedule of SC2000
applies additional operations such as modular additions, subtractions, and ro4

SECURITY ANALYSIS OF THE BLOCK CIPHER SC2000

tations. The rotation constant is always one, hence the avalanche effect of the
combination rotation-addition is insufficient. This leads to the case where in thelast transformation of the key schedule (the extended key generation) can beseen (almost) as a T-function[2], i.e. the more significant bits of the output do
not depend on the less significant bits of the input. Additionally, the additionrotation-XOR transforms are known to be susceptible to rotational attacks.

5

Chapter 2

An Attack on SC2000-256
2.1

A Dedicated Attack on SC2000-256

In this section we present an attack on SC2000 with 256-bit keys. The attack
exploits a weakness in the key-schedule which leads to key collisions for the
cipher with practical complexity.

2.1.1

Description of the Framework

Further we define the attack framework and give complexities for the genericcase.
Definition 1 The triplet (P, K1 , K2 ) is called a key collision for the cipher
EK (P ) if K1 6= K2 and EK1 (P ) = EK2 (P ).
The basic idea of the key collisions is that it is hard to find two distinct
keys and a plaintext that will produce the same ciphertext. There is no known
algorithm that can produce such tripplet with a time complexity faster than
2n/2 for an ideal n-bit block cipher – this number is related to the complexityof producing collisions for an n-bit hash function.
Definition 2 The tuple (K1 , K2 , P1 , P2 , . . . , Pm ) is called m-multi key collision
for the cipher EK (P ) if K1 6= K2 , Pi 6= Pj , i 6= j and EK1 (Pi ) = EK2 (Pi ), i =1, 2, . . . , m.
Note that producing multi key collision for an ideal cipher requires more
complexity than producing a collision as the later is a particular case of theformer for m = 1. The complexity of producing m-multi key collisions for an
ideal cipher can be estimated as the complexity of producing m multicollisions
m−1
for a hash function, which is around 2 m n for an n-bit hash function.
Observation 1 If for an n-bit block cipher EK (P ), there exist two master keys
K1 , K2 such that the key schedule algorithm KS(K) of the cipher produces thesame set of subkeys, i.e. ∃K1 , K2 , K1 6= K2 and KS(K1 ) = KS(K2 ), then the6

SECURITY ANALYSIS OF THE BLOCK CIPHER SC2000

complexity of producing 2n -multi key collisions is not higher then the complexityof of finding K1 , K2 that satisfy KS(K1 ) = KS(K2 ).
This comes from the fact that once the two distinct master keys produce thesame set of subkeys, the encryption with K1 for any plaintext P will produce
the same ciphertext as the encryption with K2 . Hence the set of multi key
collisions is maximal – its size equals to the size of the whole codebook.

2.1.2

The Attack on SC2000-256

For SC2000-256 we are able to find two distinct master keys that produce thesame subkey words and hence obtain the maximal 2128 -multi key collisions. To
do so we have to analyze the two steps of the subkeys generation. The coreidea is to produce carefully chosen pair of intermediate keys with a particulardifference, such that when key pair is supplied to the extended key generation
function, this procedure would cancel the difference. With superscripts 1 and
2 we denote the various master, intermediate and extended keys for the firstand respectively the second master key, e.g. a20 is the first intermediate key
produced from the second master key. The following observation will be usedin the attack:Observation 2 Let each pair (X1 , X2 ) of the intermediate key pairs (a1i , a2i ),(b1i , b2i ), (c1i , c2i ), (d1i , d2i ), i = 0, 1, 2 satisfies the conditions:
X2 = X1 + 3(2.1)

X1 ∧ 0x8000000f = 0x80000003(2.2)

Then the extended key generation will produce the same extended keys (subkey
words), i.e. eki1 = eki2 , i = 0, . . . , 63.
In short, the observation claims that if the most significant bits of eachintermediate key word produced from the fist master key are set to 1, and thefour last significant bits are set to 3, then to pass the extended key generation
with probability 1, it is sufficient to find a second master key that will produce
intermediate key words that are modular addition of the negation of the firstintermediate key words and the value 3.
We will not prove formally this observation – it can be checked with a simple
experiment on a PC. It is based on the properties of modular addition, rotation
to the left by one bit and XOR. Indeed, the exact values of the key bits (1 for
MSB and 3 for the four LSB), and the value 3 where obtained with a limited
brute-force of the space of all values that pass the extended key generation withprobability 1. Besides these, many more different values pass the generation
with probability 1 – we have chosen our values randomly from the set of allvalues that satisfy similar observation.
Our next task is to produce a pair of intermediate key words that satisfies
the conditions from the observation. For the sake of simplicity, we will take into
account only the first condition, i.e. X2 = X1 + 3 and only later reintroduce
the second condition. Let u1i , i = 0, . . . , 7 be the words of the first master key

7

SECURITY ANALYSIS OF THE BLOCK CIPHER SC2000

K1 , and u2i , i = 0, . . . , 7 be the words of the second master key K2 . Let Ui
be the corresponding words of the master keys after the application of Sf unc
and Mf unc , i.e. Uij = Mf unc (Sf unc (uji ))), i = 0, . . . , 7, j = 1, 2. Also, let Ki =Mf unc (Sf unc(4 · i)), i = 0, 1, 2. Then, taking into account the intermediate key
generation procedure, the condition 1 of the observation for the pairs (a1i , a2i ), i =0, 1, 2 is equivalent to solving the following system of equations:(U01 + K1 ) ⊕ U11 = A1

(2.3)

(U01 + K2 ) ⊕ 2 · U11 = B 1(U01 + K3 ) ⊕ 3 · U11 = C 1(U02 + K1 ) ⊕ U11 = A2
(U02 + K2 ) ⊕ 2 · U11 = B 2(U02 + K3 ) ⊕ 3 · U11 = C 2−1
1
A2 = Sf−1
unc (Mf unc (Mf unc (Sf unc (A )) + 3))

(2.4)

(2.9)

−1
1
B 2 = Sf−1
unc (Mf unc (Mf unc (Sf unc (B )) + 3))(2.10)−1
1= Sf−1
unc (Mf unc (Mf unc (Sf unc (C )) + 3))(2.11)

C

2

(2.5)
(2.6)
(2.7)
(2.8)

−1
Let G(x) = Sf−1
unc (Mf unc (Mf unc (Sf unc (x)) + 3)). Then the system can be
rewritten as:(U01 + K1 ) ⊕ U11 = G((U02 + K1 ) ⊕ U11 )(2.12)(U01 + K2 ) ⊕ 2 · U11 = G((U02 + K2 ) ⊕ 2 · U11 )(U01 + K3 ) ⊕ 3 · U11 = G((U02 + K3 ) ⊕ 3 · U11 )(2.13)(2.14)

Hence, it is a system of three equations with four unknowns – theoretically, it
has 232 solutions for any values of K1 , K2 , K3 and a bijective function G1 . To
find a solutions we will use to following algorithm:
1. Fix random A1 , B1
2. Find U01 , U11 that satisfy the first two equations, i.e. (2.3),(2.4)
3. Produce C1 from U01 , U11
4. Produce A2 , B2 from A1 , B1 with the function G
5. Find U02 , U12 from A2 , B2
6. Produce C2 from U02 , U12
7. Produce C˜2 from C2 with the function G
1 This is not always the case as the authors have tried to launch a much simpler attack
with A1 = A2 , B 1 = B 2 , C 1 = C 2 and failed due to the fact that no solutions exist for such
system.

8

SECURITY ANALYSIS OF THE BLOCK CIPHER SC2000

8. If C2 is not equal to C˜2 go to step 1
9. The quartet (U01 , U11 , U02 , U12 ) is the solution for the system
The values of C2 and C˜2 coincide with probability 2−32 hence the steps 1-7
have to be repeated at most 232 times.
To use our algorithm we should be able to efficiently find solutions for thesystem of type:(U0 + K1 ) ⊕ U1 = A(2.15)(U0 + K2 ) ⊕ 2 · U1 = B(2.16)

With basic algebraic transformations this system can be reduced to the form:
U1 = ((K1 − K2 ) + (2 · U1 ⊕ B)) ⊕ A(2.17)

U0 = (A ⊕ U1 ) − K1

(2.18)

Hence we can solve the system if we can solve the equation (2.17).
Lemma 1 There is an algorithm that with complexity linear in the size of thewords can find the unique solution for the equation:
X = ((2 · X ⊕ B) + C) ⊕ A,

(2.19)

where A, B, C are some word constants.
Proof: We solve the equation bit by bit starting from the least significant
and moving towards to most significant bit. We use subscripts to denote thebits within a word, e.g. X5 is the sixth least significant bit of the word X. Notethat the expression 2 · X is a simple shift by one position to the left of X andtherefore the s-th bit of 2 · X is actually the (s − 1)-th bit of X. Further, we
present the algorithm inductively, i.e. we show how to find the LSB (i.e. 0-thbit) and, assuming we have solved for t-th, we show for (t + 1)-th bit.
• Bit 0. For the LSB, the equation (2.19) takes form:
X0 = B0 ⊕ C0 ⊕ A0 ,hence the LSB of X0 can be uniquely determined with a simple XOR of
three bits. We also compute the carry (cr) from the addition (2·X⊕B)+C,
i.e. cr0 = B0 · C0 .
• Bit t + 1. We assume we have the previous carry crt , and we have foundthe value for Xt . Then for the bit t + 1, we have:
Xt+1 = Xt ⊕ Bt+1 ⊕ Ct+1 ⊕ crt ⊕ At+1
and for the carry we get crt+1 = m(Xt ⊕Bt+1 , Ct+1 , crt ), where m(x, y, z) =xy ⊕ xz ⊕ yz. Again, Xt+1 , crt+1 are determined uniquely with constantnumber of operations.
9

SECURITY ANALYSIS OF THE BLOCK CIPHER SC2000

As each step of the algorithm requires constant number of operations, and there
are in total n steps (n is the word size), we can claim that the complexity offinding the unique solution is linear in the size of the words.
The lemma gives us the complexity for the step 2 of the algorithm, i.e. we
can solve to system for any A, B with a constant complexity (as n = 32).
Now we can return to the condition 2 of the observation 2. We only have toslightly tweak our algorithm in order to satisfy this condition as well. Further
we present the full algorithm for producing the intermediate key words:
1. Fix random A1 , B1 such that the MSB of A1 , B1 are 1, and the four leastsignificant bits are 3
2. Find U01 , U11 that satisfy the first two equations
3. Produce C1 from U01 , U11
4. Produce A2 , B2 from A1 , B1 using the function F
5. Find U02 , U12 from A2 , B2
6. Produce C2 from U02 , U12
7. Produce C˜2 from C2 using the function F
8. If C2 is not equal to C˜2 , or the MSB of C2 is 0, or the four LSB are not3, go to step 1
9. The quartet (U01 , U11 , U02 , U12 ) is a solution for the system
Note, the additional conditions introduced in the step 1, do not change thecomplexity of the algorithm. On the other hand, the conditions in the step 8
increase the frequency of repeating steps 1-7 by a factor of 25 – this comes fromthe fact that there are conditions on 5 bits of C2 . Hence, the total complexityof the algorithm is 232 · 25 = 237 . Since we have to solve for four branches of
the intermediate keys, i.e. a, b, c, d, the total complexity of finding intermediate
key words is 4 · 237 = 239 . Once we have the pairs (Ui1 , Ui2 ), i = 0, . . . , 7, we
can easily produce the pairs (u1i , u2i ) by inverting the transformations at the
beginning of the intermediate key generation, i.e. Sf unc , Mf unc , thus finding
the the pair of master keys.
We have implemented our attack on a PC and found pair of master keys
(K1 , K2 ) that produce the same extended keys. The words of the master keys
are given in Tbl. 2.1.

2.1.3

Other Attack Frameworks

The attack can trivially be extended to the case of finding multicollisions for thehash function produced with SC2000-256 in Davies-Meyer mode, i.e. H(M ) =EM (H0 ) ⊕ H0 . As in the original attack the difference is only in the keys, inthe hash function mode the difference will be only in the message words and

10

SECURITY ANALYSIS OF THE BLOCK CIPHER SC2000

Table 2.1: Example of colliding pair of master keys for SC2000-256
K1
K2
ek 1 , ek 2

0x59d0d459
0x8ff60b58
0x10672240
0xf9e9f251
0xff582ab3
0x0997d523
0x18121223
0x4d148522
0x3953dbc3
0x45ba8593
0xd7b48013
0x4f279343
0xae1a47e3
0xf1633b43
0x8fc44d93
0xe7dd8fe3
0x10a9a642
0x3941d142
0x766512c3
0x9ca25a32

0x4473d8dd
0xe9dc073d
0xb94214ff
0x921811fa
0x4d261f23
0xc42fc563
0x9d034e02
0xd9247b13
0xb2f85ee2
0x14eb6423
0xb5a368a3
0xb4a34873
0x3285cd02
0x0664d382
0x2fe1e763
0xe4503972
0x9db60612
0xd961e823
0x6d9e3863
0xd6a613e2

110xcc7d3064
0x8776c115
0x2bc72c50
0x35bf5b7f
0xcb9f9ad3
0x2172df72
0x1baa1423
0xb49e6723
0x0c17c0a2
0xe4780213
0xc47fffc3
0xe2881a63
0x96418533
0x35fb0a83
0xd2823073
0xad5f9022
0x3ea3de03
0x43df53b2
0xaacccc73
0x94819ca3

0xd3bbda93
0x743c9cfe
0x539cdd3e
0x82ab8bdd
0x7c81f9c2
0x95d8dcb3
0xe9190113
0xa393b3e3
0x29d7a162
0xdf8f8b23
0xdee3ff23
0x0c1b8372
0x8a904d03
0xe246b6c2
0x530dffc2
0xdebed232
0x5ed728a2
0x7d7f7a82
0xf74a2b92
0xc98a4542

SECURITY ANALYSIS OF THE BLOCK CIPHER SC2000

thus multicollisions can be produced with complexity of 239 calls to the hashfunction, beating even the generic bound 264 for a single collision. Our attack
can be seen as a related-key differential attack, where a non-zero input differencein the master key is canceled by the key schedule. Hence, if a high probability
trail with a non-zero input difference and zero output difference can be built,
this would lead to a related-key differential attack on SC2000-256 . We haveinvestigated this possibility, however we were unable to find such trail. The
main obstacles are the two S-box layers in the intermediate key generation andinability to solve the main system probabilistically – each significantly reduces
the probability of the differential trail resulting in trails below 2−256 .

2.1.4

Applications to SC2000-128 and SC2000-192

For the cases of 128-bit and 192-bits, the last four, respectively two, words
entering the intermediate key generation are copies of the original master key
words. Hence in these cases two, respectively one, branches of the intermediate
key generation has to be satisfied probabilistically. As there are 96 conditions
per branch, and the remaining freedom per branch is 232 , and the branches arecross dependent, i.e. for 128-bit key, the third branch depend on the keys ofthe first branch, and for 128-bit and 192-bit keys, the fourth branch depends on
the second branch, the attack cannot be extended to SC2000 with 128-bit and192-bit keys.

12

Chapter 3

Analysis Against Various
Attacks
Further we present the resistance of SC2000 against different single-key andrelated-key attacks. In particular, we focus on:• Classical Differential Cryptanalysis• Impossible Differential Cryptanalysis• Slide Attacks• Rotational Attacks

3.1

Differential Cryptanalysis

Differential attacks are the most popular form of cryptanalysis for block ciphers.
A widely accepted approach for designing a cipher resistant against differential
attacks is the wide trail strategy used in AES. However, this design techniquerequires byte-oriented ciphers. Additionally, a few approaches were proposed
for analysis of the resistance of a cipher against differential attacks, however
they all assume the underlying cipher is byte-oriented. As SC2000 fails to meetthis requirement, the only known approach to analyze the cipher is ad-hoc, i.e.
trying to build a differential trail (or possible a differential) using some heuristics
and assumptions.

3.1.1

Single-key Differentials

In the single-key scenario we assume there is no difference in the key, and there
some initial difference in the plaintext.

13

SECURITY ANALYSIS OF THE BLOCK CIPHER SC2000

One-round Differential TrailAs Rf unc is a single-round Feistel, to produce the best trail for one round of
SC2000 we want a difference only in the second Rf unc . Hence we introduce
difference at the same bit position in the words a, b, c, d of the plaintext. The
S-box of Bf unc converts the difference into a single bit difference in a, the firstRf unc is passed for free, and only in the second Rf unc , there is only one active
S-box. Hence, the probability of this trail is at least 2−3 · 2−4 = 2−7 .
Two and more round Differential Trails
Note that as there are two S-box layers per round, and the S-boxes are bijective,in any two-round differential trail, there have to be at least 4 active S-boxes. It
is trivial however to see that such two-round trail does not exist. Moreover, due
to the multiple linear diffusion layers, finding an optimal trail for two-rounds
is infeasible. Hence, we cannot prove that our trails are optimal, i.e. trailswith better probability might exist. One strategy to build a two-round trail
is to start with a difference at the beginning of the second round, and expand
the difference forward through the second round, and backwards through thefirst round, thus obtaining the initial starting and ending difference of the trail.
We would want to avoid as many active S-boxes as possible, in order to get a
trail with a higher probability. Let this difference be one bit difference in a.
Then, in the forward direction, there would be only two active S-boxes, hence
the probability in round 2 is 2−7 . In the backward direction, due to the branchnumber of Mf unc , is follows that at the input of Mf unc , there have to be atleast 8 active bits, which means there where at least two active S-boxes in the
F , thus the probability of F is at most 2−8 . If the 8 bits were from only two
distinct S-boxes, it means at the input where might have been only 2 active bits.
Thus in Bf unc of round 1, there were two active S-boxes, hence the probabilityof this part is at most 2−6 . In total, we get that this type of two-round trail
has a probability of at most 2−7−8−6 = 2−23 . It is unclear if a trail with suchprobability exist at all (there might be inconsistencies with the linear layers in
the first round). For trails on more than two rounds, the above analysis does
not produce any meaningful results as there are two many possible ways thebranching could occur.

3.1.2

Related-key Differentials

To analyze the resistance of SC2000 against related-key attacks we focus on thehighly non-linear key schedule and try to build differential trails with maximal
probability only for the key schedule. For the differential probability of theactive S-boxes we take 2−4 , and assume the probability of modular additions tobe as the one presented in [3], i.e. if two words X, Y , have a difference ∆X, ∆Y ,then the best probability for the difference in Z = X+Y is 2−hamming(∆X⊕∆Y ) .

14

SECURITY ANALYSIS OF THE BLOCK CIPHER SC2000

Intermediate Key Generation
First let us focus on the intermediate key exchange procedure within a single
branch (out of the four branches) and assume there is a difference only in oneof the two input master words. By running a brute force on the space of all
single-word input differences in the first master key of the branch, we have foundthe best probability of a differential trail to be 2−25 for a single intermediate
key. By launching an additional brute force, we have found the accumulated
probability of all three intermediate keys for a branch – the best probability is2−38 . The significant improvement over the theoretical 2−25·3 = 2−75 , is dueto the fact that S-boxes in first Sf unc are counted only once. Similarly, when
the difference is in the second key of the branch, then the best probability is2−24 for constants 1 and 2, and 2−25 for constant 3, while the accumulated
probability for all of the three intermediate keys in the branch 2−34 . As all of
the transformations are bijective, it means that each of the single word casedifference results in a situation where all three output words have difference,e.g. if there is difference only in uk[0] (or only in uk[1]) then there would be adifference in a[0], a[1], a[2]. To summarize, we get:Observation 3 If in the intermediate key generation, there is a difference onlyin the first word of the branch, then the probability of the differential trail in thisbranch is at most 2−38 , and all three intermediated subkey words would have a
difference.
Observation 4 If in the intermediate key generation, there is a difference onlyin the second word of the branch, then the probability of the differential trail inthis branch is at most 2−34 , and all three intermediated subkey words would havea difference.
Therefore, if we count only the intermediate key generation, and there isdifference in a single word even in all of the four branches the probability of thebest trail is 2−34·4 = 2−132 > 2−256 . Hence theoretically related-key differential
attacks are possible and thus we have to investigate more complex cases (andtake into account the probability of the extended key generation as well).
When there is difference in both of the input words of the branch, the situation becomes more complicated and the brute force space is too large for practical implementations as there are 264 possible output differences after the first
S-box layer. First, let us focus on the number of active words per branch – for thesake of simplicity we analyze on the first branch. Let U0 , U1 be the values Uij =Mf unc (Sf unc (uk j [i]), i = 1, 2, j = 1, 2, where (uk 0 [0], uk 1 [0]), (uk 0 [1], uk 1 [1])are the pairs of related key words with a non-zero difference. Also let Ki =Mf unc (Sf unc (4 ∗ i)). If we require zero differences in all three words of theoutput of the intermediate key generation, then this can be translated into the15

SECURITY ANALYSIS OF THE BLOCK CIPHER SC2000

following system of equations:(U00 + K0 ) ⊕ U10 = (U01 + K0 ) ⊕ U11(3.1)(U00 + K1 ) ⊕ 2U10 = (U01 + K1 ) ⊕ 2U11
(U00 + K2 ) ⊕ 3U10 = (U01 + K2 ) ⊕ 3U11

(3.2)
(3.3)

Now, let us take only the first two equations of this system, i.e. (3.1), (3.2).
Observation 5 The system (3.1), (3.2) has a unique trivial solution U00 =U01 , U10 = U11 .
Proof: Let us first find the value of the least significant bits (LSB). From (3.2),
it follows that for the LSB U00 = U01 , as multiplication by 2 is simple shift tothe left, hence the LSB of U10 , U11 play no role in this equation. Therefore, from
(3.1), for the LSB is follows that U10 = U11 , and thus the LSB of the related
master words must coincide.
If we repeat the following process iteratively, we will obtain that for each
bit, it has to hold a similar fact, hence the related master key words coincide,and therefore the input difference is zero. This contradicts the initial condition
that the input difference was non-zero. Thus we get that the difference in the output words a[0], a[1] cannot be
simultaneously zero. A similar observation holds if we try to solve the systemcomposed of the equations (3.2), (3.3), i.e.:
Observation 6 The system (3.2), (3.3) has a unique trivial solution U00 =U01 , U10 = U11 .
The last possible system, composed of (3.1),(3.3) can have a non-trivial solution
however, i.e.:
Observation 7 The system (3.1), (3.3) always has a non-trivial solution.
Based on the above observations we can conclude that:
Observation 8 If in the intermediate key generation, there is a difference inboth of the incoming words of the branch, then either all three intermediatedsubkey words have a difference result in a trail with a maximal probability of
2−20 , or only one word does not have a difference (trail with probability of at
most 2−16 or only the first and the third word does not have a difference - trailwith probability of 2−12 .
Extended Key Generation
In the extended key generation the XOR difference can go through three different
operations: XOR, modular addition and rotations. Only the modular addition
are passed probabilistically. As we are looking for the upper bound, we assume
that if two words contain difference, this difference passes the modular addition
with probability 1, i.e. the case when ∆X = ∆Y from [3]. However, once the16

SECURITY ANALYSIS OF THE BLOCK CIPHER SC2000

equality is fixed, then if the words are matched again (through other words) withrotation 1, then we take the probability 2−1 . For example, if in the generationof the extended key words, we have the sum a[0] ≪ 1 + b[2], and both a[0] andb[2] contain difference, then we can assume they have the same difference (withthe first difference rotated on one bit to the right), thus the modular additionis passed with probability 1. However, if in some other extended key generation
words we also assume that both a[0] ≪ 1 + c[2] and d[1] ≪ 1 + b[2] arepassed with probability 1, then the probability of the difference in the additionc[2] ≪ 1 + d[1] cannot be 1 anymore (unless the difference was 111 . . . 1, butthen the probability of the intermediate key generation would have been much
lower).
If only one of the terms in the addition has a difference, then the probabilityof the modular addition is at most 2−1 .
The Complete Key Schedule
To find the upper bound on the probability we have implemented a brute force
on all the possible combinations of active words at the input of the key schedule.
In the search we use the results of observations 3,4,8. Depending on the numberof active input words in a branch, we produce all the possible output (at the intermediate key generation) combinations of active words (with the probabilities
mentioned in the observations). Then, we add the probability of the extended
key generation to produce the final probability, i.e. upper bound on the probability of the best trail in the key schedule. The search resulted in a best trailwith probability 2−29 . It is achieved when the third branch contains two input
active words, that after the intermediate key generation produce difference inall of the three words of the third branch.
Related-key Differential Trails
Obviously the upper bound on the probability of the best trail in the key schedule , i.e. 2−29 , is insufficient to give any meaningful results as the claim, thatthe probability of the best related-key differential trails cannot be higher than
2−29 , gives no security margin for SC2000 in the related-key scenario. The
biggest obstacle again is the complexity of both the key schedule and the statetransformation, in particular the linear layers Mf unc and Lf unc . We cannot
exclude the possibility of launching related-key attacks as it seems that highprobability differential trails might exist in the key schedule. On the other
hand it is unclear how to combine these trails with the trails in the state since
the word-oriented state transformations do not allow feasible exhaustive searchof all possible combinations of trails in the key schedule and in the state.

3.2

Impossible Differential Attacks

Impossible differentials can be very powerful form of attacks but mainly on byteoriented ciphers. In the case of word-oriented ciphers, the diffusion between the17

SECURITY ANALYSIS OF THE BLOCK CIPHER SC2000

words is much faster, and usually full active state is reached in a few rounds
making the cipher resistant against impossible attacks even with a small numberof rounds. This is the case for SC2000 as well. First we examine related-key
impossible differential attacks. Note, one can build probability 1 differentials forthe keys schedule only with respect to active (non-active) words, i.e. truncateddifferentials, as the transformations in the key schedule are non-linear. When
there is difference either in a single word within the branch, or in both wordsof the branch, all three intermediate keys in the branch will have difference.
Hence, even if there is an input difference in only one of the branches, due tothe extended key generation procedure, there would be a difference in all of thesubkey words. Therefore, related-key impossible differentials would not give any
advantage to the attacker over the single-key impossible differentials. Thus itis sufficient to examine only the single-key differentials and ignore the subkey
additions in each round.
Each round begins with a Bf unc which besides non-linearity introduces anadditional diffusion between the bits (at the same position) of all four words inthe state. Therefore, if there is even only a single bit difference in the plaintext,
after the application of Bf unc , each of the four words will have at least one bit
undetermined. The Ff unc assures that this single bit difference in one word
would make the difference in the whole (or at least the big part) word undetermined. Since Ff unc is applied to all four of the state (in two applications of the
Rf unc ), all (or the big part) of the bits in the four words will be undetermined.
Therefore, probability 1 differential can be built not more than on one round,and thus we expect that no impossible differential are achievable on more than
two rounds of SC2000 . With various techniques a round at the beginning andat the end might be skipped – however, the high security margin guarantees
that no impossible differential attack can be mounted on the full-round cipher.

3.3

Slide Attacks

Slide attacks are applicable to ciphers that have similar rounds. This is not thecase for SC2000 mainly because of the key schedule – there is no simple relation
between two consecutive subkeys. The extended key generation procedure produces extended keys (round subkeys) that depend on the intermediate keys in arandom manner. This results in a situation where two consecutive subkeys haveno simple relation. Hence, we can conclude that SC2000 is resistant against
single-key and related-key slide attacks.

3.4

Rotational Attacks

The addition-rotation-XOR structure of the extended key generation procedure
is highly susceptible to rotational attacks. However, the vast use of S-boxes (inparticular S-boxes of different size) in the key schedule as well as in the state,
make SC2000 resistant against rotational attacks.

18

Bibliography[1] O. Dunkelman, N. Keller, et al. Boomerang and rectangle attacks on sc2000.
2001.
[2] A. Klimov and A. Shamir. Cryptographic applications of t-functions. In
M. Matsui and R. J. Zuccherato, editors, Selected Areas in Cryptography,
volume 3006 of Lecture Notes in Computer Science, pages 248–261. Springer,
2003.
[3] H. Lipmaa and S. Moriai. Efficient algorithms for computing differential
properties of addition. In M. Matsui, editor, FSE, volume 2355 of Lecture
Notes in Computer Science, pages 336–350. Springer, 2001.
[4] J. Lu. Differential attack on five rounds of the sc2000 block cipher. In
F. Bao, M. Yung, D. Lin, and J. Jing, editors, Inscrypt, volume 6151 of
Lecture Notes in Computer Science, pages 50–59. Springer, 2009.
[5] H. Raddum and L. R. Knudsen. A differential attack on reduced-roundsc2000. In S. Vaudenay and A. M. Youssef, editors, Selected Areas in Cryptography, volume 2259 of Lecture Notes in Computer Science, pages 190–198.
Springer, 2001.
[6] H. Yanami, T. Shimoyama, and O. Dunkelman. Differential and linear cryptanalysis of a reduced-round sc2000. In J. Daemen and V. Rijmen, editors, FSE, volume 2365 of Lecture Notes in Computer Science, pages 34–48.
Springer, 2002.

19