# Cryptanalysis of Loiss Stream Cipher-Revisited

Authors: Lin Ding; Chenhui Jin; Jie Guan; Qiuyan Wang
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Loiss is a novel byte-oriented stream cipher proposed in 2011. In this paper, based on solving systems of linear equations, we propose an improved Guess and Determine attack on Loiss with a time complexity of 2231 and a data complexity of 268, which reduces the time complexity of the Guess and Determine attack proposed by the designers by a factor of 216. Furthermore, a related key chosen IV attack on a scaled-down version of Loiss is presented. The attack recovers the 128-bit secret key of the scaled-down Loiss with a time complexity of 280, requiring 264 chosen IVs. The related key attack is minimal in the sense that it only requires one related key. The result shows that our key recovery attack on the scaled-down Loiss is much better than an exhaustive key search in the related key setting.


---

## Body

## 1. Introduction

Many stream ciphers have been proposed over the past 20 years. Most of them are constructed using a linear feedback shift register (LFSR), which is easily implemented in hardware, but the software implementations are mostly slow. In recent years, several word-oriented stream ciphers have been proposed and standardized, such as ZUC [1], proposed for use in the 4G mobile networks, SNOW3G [2] deployed in the 3GPP networks, and also four software-oriented finalists of eSTREAM project (i.e., SOSEMANUK [3], HC-128 [4], Rabbit [5], and Salsa 20/12 [6]).In 2011, the Loiss stream cipher [7] was proposed by a team from the State Key Laboratory of Information Security in China. Loiss is a novel byte-oriented stream cipher, which takes a 128-bit secret key and a 128-bit initial vector as inputs and outputs a keystream of bytes. Loiss is based on a linear feedback shift register and utilizes a structure called byte-oriented mixer with memory (BOMM) in the filter generator, which aims to improve the resistance against algebraic attacks, linear distinguishing attacks, and fast correlation attacks. The designers hope Loiss can enrich applications of orthomorphic permutations in cryptography and motivate the research on cryptographic properties of orthomorphic permutations. By exploiting some differential properties of the BOMM structure during the cipher initialization phase, two related key attacks on Loiss were independently proposed in [8, 9]. These results show that the additional design complication, that is, the addition of the BOMM mechanism, weakens the cipher instead of strengthening it. Naturally, an open problem was left for future research, that is, whether the scaled-down Loiss, obtained by getting rid of the BOMM from Loiss and keeping other parts same as Loiss, is resistant against related key attack.No attack on Loiss has been published except for the two related key attacks showed in [8, 9]. In the specification of Loiss stream cipher, the designers present a Guess and Determine attack on Loiss, which has a time complexity of 2
247 with a data complexity of 2
52. In fact, the time complexity can be reduced at the cost of increased data complexity. In this paper, based on solving systems of linear equations, we propose an improved Guess and Determine attack on Loiss, which has a time complexity of 2
231 with a data complexity of 2
68. Furthermore, by exploiting the weakness of a scaled-down version of Loiss during its initialization phase, a related key chosenIV attack on the scaled-down Loiss is given. The attack recovers the 128-bit secret key of the scaled-down Loiss with time complexity of 2
80, requiring one related key and 2
64 chosenIVs. The related key attack is minimal in the sense that it only requires one related key. The result shows that our key recovery attack on the scaled-down Loiss is much better than an exhaustive key search in the related key setting.The rest of the paper is organized as follows. A brief description of Loiss stream cipher is given in Section2. In Section 3, an improved Guess and Determine attack on full Loiss is presented. Section 4 gives a related key chosenIV attack on scaled-down Loiss. Concluding remarks are given in Section 5.


## 2. Brief Description of the Loiss Stream Cipher

In this section, we recall the Loiss stream cipher briefly; for more details, refer to [7]. Loiss consists of three parts: linear feedback shift register (LFSR), the nonlinear function F, and a structure called byte-oriented mixer with memories (BOMM) as a part of the nonlinear filter generator; see Figure 1 [7].Figure 1
The structure of Loiss stream cipher.


### 2.1. Keystream Generator of Loiss

The LFSR contains 32-byte registers. Denote by(
s
0
(
t
)
,
s
1
(
t
)
,
…
,
s
31
(
t
)
) the state of LFSR at time t (t
⩾
0). Then the state at time t
+
1 satisfies
(1)
s
31
(
t
+
1
)
=
s
29
(
t
)
⊕
α
s
24
(
t
)
⊕
α
-
1
s
17
(
t
)
⊕
s
15
(
t
)
⊕
s
11
(
t
)
⊕
α
s
5
(
t
)
⊕
s
2
(
t
)
⊕
α
-
1
s
0
(
t
)
,
s
i
(
t
+
1
)
=
s
i
+
1
(
t
)
,
i
=
0,1
,
2
,
…
,
30
,
where α is a root of the primitive polynomial π
(
x
)
=
x
8
+
x
7
+
x
5
+
x
3
+
1 in F
2
8.The nonlinear functionF (the dotted rectangle in Figure 1) is a compressing function from 32 bits to 8 bits, which contains a 32-bit memory unit R. Denote by R
(
t
) and R
(
t
+
1
) the values of the memory unit R at times t and t
+
1, respectively. Let w be the output of F. The output of the nonlinear function is obtained as w
(
t
)
=
T
(
R
(
t
)
), where T
(
·
) is a truncation function which truncates the leftmost 8 bits from R
(
t
) as output. Then, the state of the memory unit R is updated by
(2)
R
(
t
+
1
)
=
θ
(
γ
(
X
⊕
R
(
t
)
)
)
,
where X
=
s
31
(
t
)
∥
s
26
(
t
)
∥
s
20
(
t
)
∥
s
7
(
t
). γ is obtained by paralleling 4 S-box S
1 of size 8
×
8; that is,
(3)
γ
(
x
1
∥
x
2
∥
x
3
∥
x
4
)
=
S
1
(
x
1
)
∥
S
1
(
x
2
)
∥
S
1
(
x
3
)
∥
S
1
(
x
4
)
,
where x
i (0
⩽
i
⩽
3) is a byte. θ is a linear transformation on 32-bit strings defined as
(4)
θ
(
x
)
=
x
⊕
(
x
⋘
2
)
⊕
(
x
⋘
10
)
⊕
(
x
⋘
18
)
⊕
(
x
⋘
24
)
,
where ⋘ denotes the left cyclic shift on 32-bit strings. As for the BOMM structure, it utilizes 16-byte memory units, denoted by y
i
,
0
⩽
i
⩽
15. Let w
(
t
) and v
(
t
) be the input and the output of BOMM at timet, respectively. BOMM works as follows:
(5)
h
(
t
)
=
w
(
t
)
≫
4
,
l
(
t
)
=
w
(
t
)
mod
⁡
16
,
(6)
v
(
t
)
=
y
h
(
t
)
⊕
w
(
t
)
,
(7)
y
l
(
t
+
1
)
=
y
l
(
t
)
⊕
S
2
(
w
(
t
)
)
,
(8)
y
h
(
t
+
1
)
=
{
y
h
(
t
)
⊕
S
2
(
y
l
(
t
+
1
)
)
,
if
h
≠
l
,
y
l
(
t
+
1
)
⊕
S
2
(
y
l
(
t
+
1
)
)
,
if
h
=
l
,
(9)
y
i
(
t
+
1
)
=
y
i
(
t
)
,
for
i
=
0,1
,
…
,
15
,
i
≠
h
,
l
,
where the symbol ≫ denotes the right shift operator and S
2 is an S-box of size 8
×
8.


### 2.2. Initialization and Keystream Generation

#### 2.2.1. Initialization

The initialization process of Loiss consists of two stages.In the first stage, it initializes LFSR using a 128-bit secret key and a 128-bit initial vector and then setsR
(
0
)
=
0.Set(10)
I
K

=

I
K
0
∥
I
K
1
∥
⋯
∥
I
K
15
,
I
V

=

I
V
0
∥
I
V
1
∥
⋯
∥
I
V
15
,
where both I
K
i and I
V
i are bytes, 0
⩽
i
⩽
15.Denote the initial states of LFSR by(
s
0
(
0
)
,
s
1
(
0
)
,
…
,
s
31
(
0
)
). Then, for 0
⩽
i
⩽
15,
(11)
s
i
(
0
)
=
I
K
i
,
s
16
+
i
(
0
)
=
I
K
i
⊕
I
V
i
.After that, Loiss runs 64 times without the keystream generated and the output of BOMM takes part in the feedback calculation of LFSR.


#### 2.2.2. Keystream Generation

After the initialization process, Loiss starts to generate keystream. Loiss generates one byte of keystream when it runs one time. Letz
(
t
) be the output of Loiss at time t
(
t
⩾
0
). Then,
(12)
z
(
t
)
=
s
0
(
t
)
⊕
v
(
t
)
,
where s
0
(
t
) and v
(
t
) are the value of the register s
0 of LFSR and the output of BOMM, respectively, at time t.


### 2.3. Scaled-Down Loiss

The scaled-down Loiss is obtained by getting rid of the BOMM from Loiss and keeping other parts same as Loiss. For convenience, the scaled-down Loiss is denoted by SD-Loiss in the paper. SD-Loiss consists of two parts: LFSR and the nonlinear functionF; see Figure 2.Figure 2
The structure of SD-Loiss stream cipher.


## 2.1. Keystream Generator of Loiss

The LFSR contains 32-byte registers. Denote by(
s
0
(
t
)
,
s
1
(
t
)
,
…
,
s
31
(
t
)
) the state of LFSR at time t (t
⩾
0). Then the state at time t
+
1 satisfies
(1)
s
31
(
t
+
1
)
=
s
29
(
t
)
⊕
α
s
24
(
t
)
⊕
α
-
1
s
17
(
t
)
⊕
s
15
(
t
)
⊕
s
11
(
t
)
⊕
α
s
5
(
t
)
⊕
s
2
(
t
)
⊕
α
-
1
s
0
(
t
)
,
s
i
(
t
+
1
)
=
s
i
+
1
(
t
)
,
i
=
0,1
,
2
,
…
,
30
,
where α is a root of the primitive polynomial π
(
x
)
=
x
8
+
x
7
+
x
5
+
x
3
+
1 in F
2
8.The nonlinear functionF (the dotted rectangle in Figure 1) is a compressing function from 32 bits to 8 bits, which contains a 32-bit memory unit R. Denote by R
(
t
) and R
(
t
+
1
) the values of the memory unit R at times t and t
+
1, respectively. Let w be the output of F. The output of the nonlinear function is obtained as w
(
t
)
=
T
(
R
(
t
)
), where T
(
·
) is a truncation function which truncates the leftmost 8 bits from R
(
t
) as output. Then, the state of the memory unit R is updated by
(2)
R
(
t
+
1
)
=
θ
(
γ
(
X
⊕
R
(
t
)
)
)
,
where X
=
s
31
(
t
)
∥
s
26
(
t
)
∥
s
20
(
t
)
∥
s
7
(
t
). γ is obtained by paralleling 4 S-box S
1 of size 8
×
8; that is,
(3)
γ
(
x
1
∥
x
2
∥
x
3
∥
x
4
)
=
S
1
(
x
1
)
∥
S
1
(
x
2
)
∥
S
1
(
x
3
)
∥
S
1
(
x
4
)
,
where x
i (0
⩽
i
⩽
3) is a byte. θ is a linear transformation on 32-bit strings defined as
(4)
θ
(
x
)
=
x
⊕
(
x
⋘
2
)
⊕
(
x
⋘
10
)
⊕
(
x
⋘
18
)
⊕
(
x
⋘
24
)
,
where ⋘ denotes the left cyclic shift on 32-bit strings. As for the BOMM structure, it utilizes 16-byte memory units, denoted by y
i
,
0
⩽
i
⩽
15. Let w
(
t
) and v
(
t
) be the input and the output of BOMM at timet, respectively. BOMM works as follows:
(5)
h
(
t
)
=
w
(
t
)
≫
4
,
l
(
t
)
=
w
(
t
)
mod
⁡
16
,
(6)
v
(
t
)
=
y
h
(
t
)
⊕
w
(
t
)
,
(7)
y
l
(
t
+
1
)
=
y
l
(
t
)
⊕
S
2
(
w
(
t
)
)
,
(8)
y
h
(
t
+
1
)
=
{
y
h
(
t
)
⊕
S
2
(
y
l
(
t
+
1
)
)
,
if
h
≠
l
,
y
l
(
t
+
1
)
⊕
S
2
(
y
l
(
t
+
1
)
)
,
if
h
=
l
,
(9)
y
i
(
t
+
1
)
=
y
i
(
t
)
,
for
i
=
0,1
,
…
,
15
,
i
≠
h
,
l
,
where the symbol ≫ denotes the right shift operator and S
2 is an S-box of size 8
×
8.


## 2.2. Initialization and Keystream Generation

### 2.2.1. Initialization

The initialization process of Loiss consists of two stages.In the first stage, it initializes LFSR using a 128-bit secret key and a 128-bit initial vector and then setsR
(
0
)
=
0.Set(10)
I
K

=

I
K
0
∥
I
K
1
∥
⋯
∥
I
K
15
,
I
V

=

I
V
0
∥
I
V
1
∥
⋯
∥
I
V
15
,
where both I
K
i and I
V
i are bytes, 0
⩽
i
⩽
15.Denote the initial states of LFSR by(
s
0
(
0
)
,
s
1
(
0
)
,
…
,
s
31
(
0
)
). Then, for 0
⩽
i
⩽
15,
(11)
s
i
(
0
)
=
I
K
i
,
s
16
+
i
(
0
)
=
I
K
i
⊕
I
V
i
.After that, Loiss runs 64 times without the keystream generated and the output of BOMM takes part in the feedback calculation of LFSR.


### 2.2.2. Keystream Generation

After the initialization process, Loiss starts to generate keystream. Loiss generates one byte of keystream when it runs one time. Letz
(
t
) be the output of Loiss at time t
(
t
⩾
0
). Then,
(12)
z
(
t
)
=
s
0
(
t
)
⊕
v
(
t
)
,
where s
0
(
t
) and v
(
t
) are the value of the register s
0 of LFSR and the output of BOMM, respectively, at time t.


## 2.2.1. Initialization

The initialization process of Loiss consists of two stages.In the first stage, it initializes LFSR using a 128-bit secret key and a 128-bit initial vector and then setsR
(
0
)
=
0.Set(10)
I
K

=

I
K
0
∥
I
K
1
∥
⋯
∥
I
K
15
,
I
V

=

I
V
0
∥
I
V
1
∥
⋯
∥
I
V
15
,
where both I
K
i and I
V
i are bytes, 0
⩽
i
⩽
15.Denote the initial states of LFSR by(
s
0
(
0
)
,
s
1
(
0
)
,
…
,
s
31
(
0
)
). Then, for 0
⩽
i
⩽
15,
(11)
s
i
(
0
)
=
I
K
i
,
s
16
+
i
(
0
)
=
I
K
i
⊕
I
V
i
.After that, Loiss runs 64 times without the keystream generated and the output of BOMM takes part in the feedback calculation of LFSR.


## 2.2.2. Keystream Generation

After the initialization process, Loiss starts to generate keystream. Loiss generates one byte of keystream when it runs one time. Letz
(
t
) be the output of Loiss at time t
(
t
⩾
0
). Then,
(12)
z
(
t
)
=
s
0
(
t
)
⊕
v
(
t
)
,
where s
0
(
t
) and v
(
t
) are the value of the register s
0 of LFSR and the output of BOMM, respectively, at time t.


## 2.3. Scaled-Down Loiss

The scaled-down Loiss is obtained by getting rid of the BOMM from Loiss and keeping other parts same as Loiss. For convenience, the scaled-down Loiss is denoted by SD-Loiss in the paper. SD-Loiss consists of two parts: LFSR and the nonlinear functionF; see Figure 2.Figure 2
The structure of SD-Loiss stream cipher.


## 3. Improved Guess and Determine Attack on Full Loiss

Guess and Determine attack is a common attack on stream ciphers. Guess and Determine attacks exploit the relationship between internal and the keystream values. In Guess and Determine attacks, some internal values are guessed, and then other internal values are determined using keystream values. Guess and Determine attacks generally consist of three phases, that is, guessing, determining, and the test phase. The efficiency of Guess and Determine attacks can be discussed in terms of two complexities, namely, a time and a data complexity. Guess and Determine attack is one of the general attacks which have been effective on some stream ciphers, for example, A5/1 [10], SNOW 1.0 [11], Sober-t32 [12], SOSEMANUK [13], Rabbit [14], ZUC [15], and so forth.In the specification of Loiss stream cipher [7], the designers present a Guess and Determine attack on Loiss which has a time complexity of 2
247 with a data complexity of 2
52. In fact, the time complexity can be reduced at the cost of increased data complexity.Here, we assume that the attacker has observed a portion of keystream words{
z
t
}, t
=
1,2
,
…
,
N, where N is large enough for the attack to succeed. For convenience, we denote by A
⇒
(
*
)
B the deduction of B from A by equation (
*
).For convenience, we denote by(
s
(
t
)
,
s
(
t
+
1
)
,
…
,
s
(
t
+
31
)
) the state of LFSR in Loiss at time t
(
t
⩾
0
). Then the state at time t
+
1 is (
s
(
t
+
1
)
,
s
(
t
+
2
)
,
…
,
s
(
t
+
32
)
). The recurrence function of LFSR is redefined as follows:
(13)
s
(
t
+
32
)
=
s
(
t
+
29
)
⊕
α
s
(
t
+
24
)
⊕
α
-
1
s
(
t
+
17
)
⊕
s
(
t
+
15
)
⊕
s
(
t
+
11
)
⊕
α
s
(
t
+
5
)
⊕
s
(
t
+
2
)
⊕
α
-
1
s
(
t
)
.Before the description of our attack, we make an assumption as follows.Assumption 1.
The following conditions occur at nine successive times starting from timet:(1)
h
(
t
)
=
l
(
t
), where h
(
t
)
=
w
(
t
)
≫
4, l
(
t
)
=
w
(
t
)
mod
⁡
16;
(2)
w
(
t
)
=
w
(
t
+
1
)
=
⋯
=
w
(
t
+
8
).In the attack, the attacker guesses the values ofh
(
t
), s
(
t
), s
(
t
+
12
), s
(
t
+
13
), s
(
t
+
21
), s
(
t
+
25
), s
(
t
+
26
), s
(
t
+
27
) and the values of the rightmost three bytes of each R
(
t
+
i
) (2
⩽
i
⩽
5). The whole description of our Guess and Determine attack on Loiss can be divided into three phases as follows.Phase One. For a given guess, all the bits of the following components can be immediately determined by exploiting the relationships in the cipher:(i)
z
(
t
)
,
s
(
t
)
⇒
(
12
)
v
(
t
);
(ii)
v
(
t
)
,
w
(
t
)
⇒
(
6
)
y
h
(
t
)
(
t
);
(iii)
y
h
(
t
)
(
t
)
⇒
(
7,8
)
y
h
(
t
)
(
t
+
1
);
(iv)
y
h
(
t
+
1
)
(
t
+
1
)
,
w
(
t
+
1
)
⇒
(
6
)
v
(
t
+
1
);
(v)
z
(
t
+
1
)
,
v
(
t
+
1
)
⇒
(
12
)
s
(
t
+
1
).The last three steps above can be repeated fori
=
1
,
…
,
7 to determine more components:(i)
y
h
(
t
)
(
t
+
i
)
⇒
(
7,8
)
y
h
(
t
)
(
t
+
i
+
1
);
(ii)
y
h
(
t
+
i
+
1
)
(
t
+
i
+
1
)
,
w
(
t
+
i
+
1
)
⇒
(
6
)
v
(
t
+
i
+
1
);
(iii)
z
(
t
+
i
+
1
)
,
v
(
t
+
i
+
1
)
⇒
(
12
)
s
(
t
+
i
+
1
).After that, we deduce more components as follows:(i)
R
(
t
+
2
)
,
R
(
t
+
3
)
⇒
(
1
)
s
(
t
+
33
)
,
s
(
t
+
28
)
,
s
(
t
+
22
)
,
s
(
t
+
9
);
(ii)
R
(
t
+
3
)
,
R
(
t
+
4
)
⇒
(
1
)
s
(
t
+
34
)
,
s
(
t
+
29
)
,
s
(
t
+
23
)
,
s
(
t
+
10
);
(iii)
R
(
t
+
4
)
,
R
(
t
+
5
)
⇒
(
1
)
s
(
t
+
35
)
,
s
(
t
+
30
)
,
s
(
t
+
24
)
,
s
(
t
+
11
).Phase Two. Then, we can determine more components as follows.We know that(14)
R
(
t
+
2
)
=
θ
(
γ
(
s
(
t
+
32
)
⊕
R
3
(
t
+
1
)
∥
s
(
t
+
27
)
⊕
R
2
(
t
+
1
)
∥
v
v
v
v
v
v
s
(
t
+
21
)
⊕
R
1
(
t
+
1
)
∥
s
(
t
+
8
)
⊕
R
0
(
t
+
1
)
)
)
,
where R
(
t
+
i
) are divided into four bytes as R
(
t
+
i
)
=
R
3
(
t
+
i
)
∥
R
2
(
t
+
i
)
∥
R
1
(
t
+
i
)
∥
R
0
(
t
+
i
).Thus,(i)
R
(
t
+
2
)
⇒
(
1
)
s
(
t
+
32
)
⊕
R
3
(
t
+
1
)
,
s
(
t
+
27
)
⊕
R
2
(
t
+
1
)
,
s
(
t
+
21
)
⊕
R
1
(
t
+
1
)
,
s
(
t
+
8
)
⊕
R
0
(
t
+
1
);
(ii)
R
3
(
t
+
1
)
,
s
(
t
+
27
)
,
s
(
t
+
21
)
,
s
(
t
+
8
)
⇒
(
1
)
s
(
t
+
32
)
,
R
2
(
t
+
1
)
,
R
1
(
t
+
1
)
,
R
0
(
t
+
1
).SinceR
(
t
+
1
) has been recovered, then(i)
R
(
t
+
1
)
⇒
(
1
)
s
(
t
+
31
)
⊕
R
3
(
t
)
,
s
(
t
+
26
)
⊕
R
2
(
t
)
,
s
(
t
+
20
)
⊕
R
1
(
t
)
,
s
(
t
+
7
)
⊕
R
0
(
t
),
(ii)
R
3
(
t
)
,
s
(
t
+
31
)
⊕
R
3
(
t
)
⇒
(
1
)
s
(
t
+
31
),
(iii)
s
(
t
+
26
)
,
s
(
t
+
26
)
⊕
R
2
(
t
)
⇒
(
1
)
R
2
(
t
),
(iv)
s
(
t
+
7
)
,
s
(
t
+
7
)
⊕
R
0
(
t
)
⇒
(
1
)
R
0
(
t
).We know that(15)
R
(
t
+
6
)
=
θ
(
γ
(
s
(
t
+
36
)
⊕
R
3
(
t
+
5
)
∥
s
(
t
+
31
)
⊕
R
2
(
t
+
5
)
∥
v
v
v
v
v
v
s
(
t
+
25
)
⊕
R
1
(
t
+
5
)
∥
s
(
t
+
12
)
⊕
R
0
(
t
+
5
)
)
)
=
θ
(
S
1
(
s
(
t
+
36
)
⊕
R
3
(
t
+
5
)
)
∥
S
1
(
s
(
t
+
31
)
⊕
R
2
(
t
+
5
)
)
∥
v
v
v
S
1
(
s
(
t
+
25
)
⊕
R
1
(
t
+
5
)
)
∥
S
1
(
s
(
t
+
12
)
⊕
R
0
(
t
+
5
)
)
)
.In this equation, the values ofs
(
t
+
31
), s
(
t
+
25
), and s
(
t
+
12
) have been obtained and the values of R
2
(
t
+
5
)
,
R
1
(
t
+
5
), and R
0
(
t
+
5
) have been guessed, and R
3
(
t
+
6
) is also known. Thus, we can easily recover the value of S
1
(
s
(
t
+
36
)
⊕
R
3
(
t
+
5
)
) by solving a system of eight bitwise linear equations. After that, we can recover the value of s
(
t
+
36
), since R
3
(
t
+
5
) is known. At last, we can recover the value of R
(
t
+
6
).Similarly, we can recover the values ofs
(
t
+
37
) and R
(
t
+
7
).Phase Three. Then, we can determine the remaining components as follows. In this phase, we have to solve two systems of three byte-wise linear equations.The first system is described as follows:(16)
α
-
1
s
(
t
+
17
)
⊕
s
(
t
+
15
)
=
s
(
t
+
32
)
⊕
s
(
t
+
29
)
⊕
α
s
(
t
+
24
)
⊕
s
(
t
+
11
)
⊕
α
s
(
t
+
5
)
⊕
s
(
t
+
2
)
⊕
α
-
1
s
(
t
)
,
α
-
1
s
(
t
+
19
)
⊕
s
(
t
+
17
)
=
s
(
t
+
34
)
⊕
s
(
t
+
31
)
⊕
α
s
(
t
+
26
)
⊕
s
(
t
+
13
)
⊕
α
s
(
t
+
7
)
⊕
s
(
t
+
4
)
⊕
α
-
1
s
(
t
+
2
)
,
s
(
t
+
19
)
⊕
s
(
t
+
15
)
=
s
(
t
+
36
)
⊕
s
(
t
+
33
)
⊕
α
s
(
t
+
28
)
⊕
α
-
1
s
(
t
+
21
)
⊕
α
s
(
t
+
9
)
⊕
s
(
t
+
6
)
⊕
α
-
1
s
(
t
+
4
)
.In this system, only three variables are unknown, that is,s
(
t
+
19
), s
(
t
+
17
), and s
(
t
+
15
). Obviously, this system can be easily solved. Thus, we can recover the values of s
(
t
+
19
), s
(
t
+
17
), and s
(
t
+
15
) by solving this system.Then, we deduces
(
t
+
38
) as follows:(i)
s
(
t
+
35
)
,
s
(
t
+
30
)
,
s
(
t
+
23
)
,
s
(
t
+
21
)
,
s
(
t
+
17
)
,
s
(
t
+
11
)
,
s
(
t
+
8
)
,
s
(
t
+
6
)
⇒
(
13
)
s
(
t
+
38
).We know that(17)
R
(
t
+
8
)
=
θ
(
γ
(
s
(
t
+
38
)
⊕
R
3
(
t
+
7
)
∥
s
(
t
+
33
)
⊕
R
2
(
t
+
7
)
∥
v
v
v
v
v
v
s
(
t
+
27
)
⊕
R
1
(
t
+
7
)
∥
s
(
t
+
14
)
⊕
R
0
(
t
+
7
)
)
)
=
θ
(
S
1
(
s
(
t
+
38
)
⊕
R
3
(
t
+
7
)
)
∥
S
1
(
s
(
t
+
33
)
⊕
R
2
(
t
+
7
)
)
∥
v
v
v
S
1
(
s
(
t
+
27
)
⊕
R
1
(
t
+
7
)
)
∥
S
1
(
s
(
t
+
14
)
⊕
R
0
(
t
+
7
)
)
)
.In this equation, the values ofs
(
t
+
38
)
,
s
(
t
+
33
), and s
(
t
+
27
) have been obtained and the value of R
(
t
+
7
) has been determined, and R
3
(
t
+
8
) is also known. Thus, we can easily recover the value of S
1
(
s
(
t
+
14
)
⊕
R
0
(
t
+
7
)
) by solving a system of eight bitwise linear equations. After that, we can recover the value of s
(
t
+
14
), since R
0
(
t
+
7
) is known. At last, we can recover the value of R
(
t
+
8
).Then, we should solve another system of three linear equations, which is described as follows:(18)
α
-
1
s
(
t
+
18
)
⊕
s
(
t
+
16
)
=
s
(
t
+
33
)
⊕
s
(
t
+
30
)
⊕
α
s
(
t
+
25
)
⊕
s
(
t
+
12
)
⊕
α
s
(
t
+
6
)
⊕
s
(
t
+
3
)
⊕
α
-
1
s
(
t
+
1
)
,
α
-
1
s
(
t
+
20
)
⊕
s
(
t
+
18
)
=
s
(
t
+
35
)
⊕
s
(
t
+
32
)
⊕
α
s
(
t
+
27
)
⊕
s
(
t
+
14
)
⊕
α
s
(
t
+
8
)
⊕
s
(
t
+
5
)
⊕
α
-
1
s
(
t
+
3
)
,
s
(
t
+
20
)
⊕
s
(
t
+
16
)
=
s
(
t
+
37
)
⊕
s
(
t
+
34
)
⊕
α
s
(
t
+
29
)
⊕
α
-
1
s
(
t
+
23
)
⊕
α
s
(
t
+
10
)
⊕
s
(
t
+
7
)
⊕
α
-
1
s
(
t
+
5
)
.In this system, only three variables are unknown, that is,s
(
t
+
20
)
,
s
(
t
+
18
), and s
(
t
+
16
). Obviously, this system can be easily solved. Thus, we can recover the values of s
(
t
+
20
)
,
s
(
t
+
18
), and s
(
t
+
16
) by solving this system.Finally, we deduceR
(
t
) as follows, since the value of s
(
t
+
20
) has been recovered:(i)
R
(
t
+
1
)
,
s
(
t
+
31
)
,
s
(
t
+
26
)
,
s
(
t
+
20
)
,
s
(
t
+
7
)
⇒
(
1
)
R
(
t
).Thus, all internal states of LFSR andF, that is, s
(
t
)
,
s
(
t
+
1
)
,
…
,
s
(
t
+
31
)
,
R
(
t
), have been recovered. After all the internal states of LFSR and F are recovered, the attacker runs Loiss for about another 128 times and then can recover the values of all memory units of BOMM.Up to now, all internal states of LFSR,F, and BOMM have been recovered. And then the attacker has to check the correctness of those values by producing a keystream using the above recovered values and comparing it with the observed keystream. If the keystreams agree, it shows that the recovered states are correct. If the keystreams do not agree, then we will repeat the above process until the correct internal state is found. Since the probability that the assumption satisfies is 2
-
68 and the attacker has to guess 156-bit internal state in the guessing stage, so the time complexity of our Guess and Determine attack on Loiss is 2
68
·
2
156
·
2
7
=
2
231 with a data complexity of 2
68. Compared with the Guess and Determine attack proposed by the designers, the time complexity of our attack on Loiss has been reduced by a factor of 2
16.


## 4. Related Key ChosenIV Attack on Scaled-Down Loiss

By exploiting some differential properties of the BOMM structure during the cipher initialization phase, two related key attacks on Loiss were independently proposed in [8, 9]. These results show that the additional design complication, that is, the addition of the BOMM mechanism, weakens the cipher instead of strengthening it. Naturally, an open problem was left for future research, that is, whether the scaled-down Loiss, obtained by getting rid of the BOMM from Loiss and keeping other parts same as Loiss, is resistant against related key attack. In this section, based on the idea of slide (key,IV) pairs, a related key chosenIV attack on scaled-down Loiss is presented.


### 4.1. Some Properties of SD-Loiss

In this subsection, we will present some properties of SD-Loiss. LetI
(
t
) be the internal state of SD-Loiss at time t. Denote by I
(
0
) and I
(
64
) the internal state of SD-Loiss just after the first stage of initialization and the full initialization, respectively. Let I
K and I
V be the 128-bit secret key and a 128-bit initial vector into the memory units of LFSR. Let (
I
K
′
,
I
V
′
) pair be the related pair of (
I
K
,
I
V
). The relation between them is defined as follows:
(19)
I
K
′
=
I
K
⋘
16
=
I
K
2
∥
I
K
3
∥
⋯
∥
I
K
15
∥
I
K
0
∥
I
K
1
I
V
′
=
I
V
⋘
16
=
I
V
2
∥
I
V
3
∥
⋯
∥
I
V
1
5
∥
I
V
0
∥
I
V
1LetI
′
(
t
) be the internal state of SD-Loiss at time t using (
I
K
′
,
I
V
′
) pair. Then, we can get the following proposition which discusses the probability that I
(
2
)
=
I
′
(
0
) holds.Proposition 2.
For the fixed key IK and 248 chosenIVs where I
V
0
=
I
V
1
=
0, (
I
V
4
,
I
V
5
,
I
V
11
,
I
V
13
,
I
V
14
,
I
V
15
) are all 48-bit values and the remaining bytes are fixed to c
∈
{
0,1
,
…
,
255
}; there exactly exists oneIV satisfying I
(
2
)
=
I
′
(
0
).Proof.
According to the structure of SD-Loiss, we knowI
(
2
)
=
I
′
(
0
) can be written as the following system of 33 equations:
(20)
s
i
(
2
)
=
s
i
′
(
0
)
,
i
=
0,1
,
2
,
…
,
31
,
R
(
2
)
=
R
′
(
0
)
.
Since there are 29 equations which always hold in system (20), we can simplify the system (20) as follows:
(21)
I
V
0
=
I
V
1
=
0
,
s
30
(
2
)
=
s
31
(
1
)
=
(
I
K
13
⊕
I
V
13
)
⊕
α
(
I
K
8
⊕
I
V
8
)
⊕
α
-
1
(
I
K
1
⊕
I
V
1
)
⊕
I
K
15
⊕
I
K
11
⊕
α
(
I
K
5
)
⊕
I
K
2
⊕
α
-
1
(
I
K
0
)
⊕
w
(
0
)
=
I
K
0
⊕
I
V
0
,
s
31
(
2
)
=
(
I
K
14
⊕
I
V
14
)
⊕
α
(
I
K
9
⊕
I
V
9
)
⊕
α
-
1
(
I
K
2
⊕
I
V
2
)
⊕
I
K
1
⊕
I
V
1
⊕
I
K
12
⊕
α
(
I
K
6
)
⊕
I
K
3
⊕
α
-
1
(
I
K
1
)
⊕
w
(
1
)
=
I
K
1
⊕
I
V
1
R
(
2
)
=
θ
(
γ
(
X
(
1
)
⊕
R
(
1
)
)
)
=
0
,
where w
(
0
)
=
0 and w
(
1
)
=
T
(
R
(
1
)
).
Sinceθ is a linear transformation on 32-bit strings, we can simplify the equation R
(
2
)
=
0 as
(22)
γ
(
X
(
1
)
⊕
R
(
1
)
)
=
0
.
That is,(23)
γ
[
(
s
31
(
1
)
∥
I
K
11
⊕
I
V
11
∥
I
K
5
⊕
I
V
5
∥
I
K
8
)
V
V
⊕
θ
(
γ
(
∥
I
K
15
⊕
I
V
15
∥
I
K
10
⊕
I
V
10
∥
I
K
4
⊕
I
V
4
∥
I
K
7
)
)
(
s
31
(
1
)
∥
I
K
11
⊕
I
V
11
∥
I
K
5
⊕
I
V
5
∥
I
K
8
)
]
=
0
.
LetY
=
Y
0
∥
Y
1
∥
Y
2
∥
Y
3
=
θ
(
γ
(
I
K
15
⊕
I
V
15
∥
I
K
10
⊕
I
V
10
∥
I
K
4
⊕
I
V
4
∥
I
K
7
)
) be a 32-bit string, where Y
i
(
0
⩽
i
⩽
3
) is a byte. According to the S-box S
1 in Loiss, we know that S
1
-
1
(
0
)
=
0
x
17.
Then, we know(24)
s
31
(
1
)
⊕
Y
0
=
0
x
17
,
I
K
11
⊕
I
V
11
⊕
Y
1
=
0
x
17
,
I
K
5
⊕
I
V
5
⊕
Y
2
=
0
x
17
,
I
K
8
⊕
Y
3
=
0
x
17
.
Thus, when we try all 32-bit values of(
I
V
4
,
I
V
5
,
I
V
11
,
I
V
15
), there exists exactly oneIV satisfying the system (24). Considering the second and third equations of system (21), when we try 2
48 chosenIVs where I
V
0
=
I
V
1
=
0, (
I
V
4
,
I
V
5
,
I
V
11
,
I
V
13
,
I
V
14
,
I
V
15
) are all 48-bit values and the remaining bytes are fixed to c
∈
{
0,1
,
…
,
255
}; there exactly exists oneIV satisfying I
(
2
)
=
I
′
(
0
).IfI
(
2
)
=
I
′
(
0
) holds, we easily know I
(
i
)
=
I
′
(
i
-
2
) always holds for 2
⩽
i
⩽
64. Similarly, ifIV satisfies I
(
i
)
=
I
′
(
i
-
2
), we say that theIVisvalid. Otherwise, we say that theIV isinvalid.LetZ and Z
′ be keystream sequences generated from (
I
K
,
I
V
) and (
I
K
′
,
I
V
′
), respectively. Let Z
[
t
,
L
] be the keystream sequences generated from time t to t
+
L; that is, Z
[
t
,
L
]
=
(
z
(
t
)
,
z
(
t
+
1
)
,
…
,
z
(
t
+
L
-
1
)
). Similarly, let Z
′
[
t
,
L
] be the keystream sequences generated from time t to t
+
L; that is, Z
′
[
t
,
L
]
=
(
z
′
(
t
)
,
z
′
(
t
+
1
)
,
…
,
z
′
(
t
+
L
-
1
)
). Then, we know that I
(
65
) and I
(
66
) are updated by the keystream generation mode, while I
′
(
63
) and I
′
(
64
) are updated by the initialization mode. Thus, both I
(
65
)
=
I
′
(
63
) and I
(
66
)
=
I
′
(
64
) hold, if and only if both w
′
(
63
)
=
0 and w
′
(
64
)
=
0 hold. If w
′
(
63
)
=
w
′
(
64
)
=
0, I
(
i
)
=
I
′
(
i
-
2
) always holds for i
⩾
65, and then Z
[
2
,
L
]
=
Z
′
[
0
,
L
] always holds, for L
⩾
1 (we call itIV-Test).Theoretically, the probability that a validIV passes theIV-Test is equal to Pr
(
w
′
(
63
)
=
w
′
(
64
)
=
0
)
=
2
-
16, and then there exists oneIV passingIV-Test among 2
16 validIVs. Thus, we can find at least oneIV passingIV-Test with high probability among 2
64 chosenIVs where I
V
0
=
I
V
1
=
0; (
I
V
4
,
I
V
5
,
I
V
10
,
I
V
11
,
I
V
12
,
I
V
13
,
I
V
14
,
I
V
15
) are all 64-bit values and the remaining bytes are fixed to c
∈
{
0,1
,
…
,
255
}, while for an invalidIV, after the initialization of SD-Loiss, z
(
i
+
2
)
=
z
′
(
i
) is uniformly distributed for 0
⩽
i
⩽
L
-
1. Thus, an invalidIV passesIV-Test with probability 2
-
8
L. Obviously, when L is large enough, the probability 2
-
8
L is much smaller than 2
-
16, which means that we can distinguish validIV and invalidIVs with very high probability.


### 4.2. Related Key ChosenIV Attack on Scaled-Down Loiss

Our attack on SD-Loiss can be divided into two phases. In the first phase, we should find a validIV. In the second phase, we will recover the 128-bit secret keyIK.We choose2
64
IVs where I
V
0
=
I
V
1
=
0; (
I
V
4
,
I
V
5
,
I
V
10
,
I
V
11
,
I
V
12
,
I
V
13
,
I
V
14
,
I
V
15
) are all 64-bit values and the remaining bytes are fixed to c
∈
{
0,1
,
…
,
255
}. Then, we can find a validIV among these 2
64 chosenIVs by the Finding ValidIV algorithm for SD-Loiss which is described as follows.Finding Valid IV Algorithm for SD-Loiss
(1)
For each IV in these2
64 chosen IVs, repeat the following:
(a)
generateL
+
2 bytes of keystream Z
[
2
,
L
] by using (
I
K
,
I
V
);
(b)
generateL bytes of keystream Z
′
[
0
,
L
] by using (
I
K
′
,
I
V
′
);
(c)
checkIV-Test for Z
[
2
,
L
] and Z
′
[
0
,
L
]; if they passIV-Test, go to Step (
2
); otherwise, return to Step (
1
) and choose anotherIV.
(2)
Return ValidIV and store thisIV.This algorithm requires2
64 chosenIVs and runs the encryption process of SD-Loiss 2
64
+
2
64
=
2
65 times. Thus, the time complexity of this algorithm is 2
65. Then, for each single key andIV, this algorithm only requires L
+
2 bytes of keystream at most. To make the probability that an invalidIV passesIV-Test negligible, we chooseL to be 15, and then 2
-
8
L is equal to 2
-
120 which is small enough to distinguish validIVs and invalidIVs with very high probability. Hence, our attack requires 17 bytes of keystream at most for each single key andIV.In the second phase, using the Finding ValidIV algorithm for SD-Loiss above, we can recover the 128-bit secret keyIK using a simple Guess and Determine attack. We guess the values of I
K
1, I
K
2, I
K
3, I
K
4, I
K
6, I
K
7, I
K
9, I
K
10, I
K
12, and I
K
15 (a total of 80 bits). Then, we can determine the remaining 48 bits of the secret keyIK by system (21) easily.Recall the two phases of our attack on SD-Loiss. The time complexity of our attack on SD-Loiss is2
65
+
2
80
≈
2
80, requiring 2
64 chosenIVs. The result shows that slide (key,IV) pairs can be also used for related key attack.


## 4.1. Some Properties of SD-Loiss

In this subsection, we will present some properties of SD-Loiss. LetI
(
t
) be the internal state of SD-Loiss at time t. Denote by I
(
0
) and I
(
64
) the internal state of SD-Loiss just after the first stage of initialization and the full initialization, respectively. Let I
K and I
V be the 128-bit secret key and a 128-bit initial vector into the memory units of LFSR. Let (
I
K
′
,
I
V
′
) pair be the related pair of (
I
K
,
I
V
). The relation between them is defined as follows:
(19)
I
K
′
=
I
K
⋘
16
=
I
K
2
∥
I
K
3
∥
⋯
∥
I
K
15
∥
I
K
0
∥
I
K
1
I
V
′
=
I
V
⋘
16
=
I
V
2
∥
I
V
3
∥
⋯
∥
I
V
1
5
∥
I
V
0
∥
I
V
1LetI
′
(
t
) be the internal state of SD-Loiss at time t using (
I
K
′
,
I
V
′
) pair. Then, we can get the following proposition which discusses the probability that I
(
2
)
=
I
′
(
0
) holds.Proposition 2.
For the fixed key IK and 248 chosenIVs where I
V
0
=
I
V
1
=
0, (
I
V
4
,
I
V
5
,
I
V
11
,
I
V
13
,
I
V
14
,
I
V
15
) are all 48-bit values and the remaining bytes are fixed to c
∈
{
0,1
,
…
,
255
}; there exactly exists oneIV satisfying I
(
2
)
=
I
′
(
0
).Proof.
According to the structure of SD-Loiss, we knowI
(
2
)
=
I
′
(
0
) can be written as the following system of 33 equations:
(20)
s
i
(
2
)
=
s
i
′
(
0
)
,
i
=
0,1
,
2
,
…
,
31
,
R
(
2
)
=
R
′
(
0
)
.
Since there are 29 equations which always hold in system (20), we can simplify the system (20) as follows:
(21)
I
V
0
=
I
V
1
=
0
,
s
30
(
2
)
=
s
31
(
1
)
=
(
I
K
13
⊕
I
V
13
)
⊕
α
(
I
K
8
⊕
I
V
8
)
⊕
α
-
1
(
I
K
1
⊕
I
V
1
)
⊕
I
K
15
⊕
I
K
11
⊕
α
(
I
K
5
)
⊕
I
K
2
⊕
α
-
1
(
I
K
0
)
⊕
w
(
0
)
=
I
K
0
⊕
I
V
0
,
s
31
(
2
)
=
(
I
K
14
⊕
I
V
14
)
⊕
α
(
I
K
9
⊕
I
V
9
)
⊕
α
-
1
(
I
K
2
⊕
I
V
2
)
⊕
I
K
1
⊕
I
V
1
⊕
I
K
12
⊕
α
(
I
K
6
)
⊕
I
K
3
⊕
α
-
1
(
I
K
1
)
⊕
w
(
1
)
=
I
K
1
⊕
I
V
1
R
(
2
)
=
θ
(
γ
(
X
(
1
)
⊕
R
(
1
)
)
)
=
0
,
where w
(
0
)
=
0 and w
(
1
)
=
T
(
R
(
1
)
).
Sinceθ is a linear transformation on 32-bit strings, we can simplify the equation R
(
2
)
=
0 as
(22)
γ
(
X
(
1
)
⊕
R
(
1
)
)
=
0
.
That is,(23)
γ
[
(
s
31
(
1
)
∥
I
K
11
⊕
I
V
11
∥
I
K
5
⊕
I
V
5
∥
I
K
8
)
V
V
⊕
θ
(
γ
(
∥
I
K
15
⊕
I
V
15
∥
I
K
10
⊕
I
V
10
∥
I
K
4
⊕
I
V
4
∥
I
K
7
)
)
(
s
31
(
1
)
∥
I
K
11
⊕
I
V
11
∥
I
K
5
⊕
I
V
5
∥
I
K
8
)
]
=
0
.
LetY
=
Y
0
∥
Y
1
∥
Y
2
∥
Y
3
=
θ
(
γ
(
I
K
15
⊕
I
V
15
∥
I
K
10
⊕
I
V
10
∥
I
K
4
⊕
I
V
4
∥
I
K
7
)
) be a 32-bit string, where Y
i
(
0
⩽
i
⩽
3
) is a byte. According to the S-box S
1 in Loiss, we know that S
1
-
1
(
0
)
=
0
x
17.
Then, we know(24)
s
31
(
1
)
⊕
Y
0
=
0
x
17
,
I
K
11
⊕
I
V
11
⊕
Y
1
=
0
x
17
,
I
K
5
⊕
I
V
5
⊕
Y
2
=
0
x
17
,
I
K
8
⊕
Y
3
=
0
x
17
.
Thus, when we try all 32-bit values of(
I
V
4
,
I
V
5
,
I
V
11
,
I
V
15
), there exists exactly oneIV satisfying the system (24). Considering the second and third equations of system (21), when we try 2
48 chosenIVs where I
V
0
=
I
V
1
=
0, (
I
V
4
,
I
V
5
,
I
V
11
,
I
V
13
,
I
V
14
,
I
V
15
) are all 48-bit values and the remaining bytes are fixed to c
∈
{
0,1
,
…
,
255
}; there exactly exists oneIV satisfying I
(
2
)
=
I
′
(
0
).IfI
(
2
)
=
I
′
(
0
) holds, we easily know I
(
i
)
=
I
′
(
i
-
2
) always holds for 2
⩽
i
⩽
64. Similarly, ifIV satisfies I
(
i
)
=
I
′
(
i
-
2
), we say that theIVisvalid. Otherwise, we say that theIV isinvalid.LetZ and Z
′ be keystream sequences generated from (
I
K
,
I
V
) and (
I
K
′
,
I
V
′
), respectively. Let Z
[
t
,
L
] be the keystream sequences generated from time t to t
+
L; that is, Z
[
t
,
L
]
=
(
z
(
t
)
,
z
(
t
+
1
)
,
…
,
z
(
t
+
L
-
1
)
). Similarly, let Z
′
[
t
,
L
] be the keystream sequences generated from time t to t
+
L; that is, Z
′
[
t
,
L
]
=
(
z
′
(
t
)
,
z
′
(
t
+
1
)
,
…
,
z
′
(
t
+
L
-
1
)
). Then, we know that I
(
65
) and I
(
66
) are updated by the keystream generation mode, while I
′
(
63
) and I
′
(
64
) are updated by the initialization mode. Thus, both I
(
65
)
=
I
′
(
63
) and I
(
66
)
=
I
′
(
64
) hold, if and only if both w
′
(
63
)
=
0 and w
′
(
64
)
=
0 hold. If w
′
(
63
)
=
w
′
(
64
)
=
0, I
(
i
)
=
I
′
(
i
-
2
) always holds for i
⩾
65, and then Z
[
2
,
L
]
=
Z
′
[
0
,
L
] always holds, for L
⩾
1 (we call itIV-Test).Theoretically, the probability that a validIV passes theIV-Test is equal to Pr
(
w
′
(
63
)
=
w
′
(
64
)
=
0
)
=
2
-
16, and then there exists oneIV passingIV-Test among 2
16 validIVs. Thus, we can find at least oneIV passingIV-Test with high probability among 2
64 chosenIVs where I
V
0
=
I
V
1
=
0; (
I
V
4
,
I
V
5
,
I
V
10
,
I
V
11
,
I
V
12
,
I
V
13
,
I
V
14
,
I
V
15
) are all 64-bit values and the remaining bytes are fixed to c
∈
{
0,1
,
…
,
255
}, while for an invalidIV, after the initialization of SD-Loiss, z
(
i
+
2
)
=
z
′
(
i
) is uniformly distributed for 0
⩽
i
⩽
L
-
1. Thus, an invalidIV passesIV-Test with probability 2
-
8
L. Obviously, when L is large enough, the probability 2
-
8
L is much smaller than 2
-
16, which means that we can distinguish validIV and invalidIVs with very high probability.


## 4.2. Related Key ChosenIV Attack on Scaled-Down Loiss

Our attack on SD-Loiss can be divided into two phases. In the first phase, we should find a validIV. In the second phase, we will recover the 128-bit secret keyIK.We choose2
64
IVs where I
V
0
=
I
V
1
=
0; (
I
V
4
,
I
V
5
,
I
V
10
,
I
V
11
,
I
V
12
,
I
V
13
,
I
V
14
,
I
V
15
) are all 64-bit values and the remaining bytes are fixed to c
∈
{
0,1
,
…
,
255
}. Then, we can find a validIV among these 2
64 chosenIVs by the Finding ValidIV algorithm for SD-Loiss which is described as follows.Finding Valid IV Algorithm for SD-Loiss
(1)
For each IV in these2
64 chosen IVs, repeat the following:
(a)
generateL
+
2 bytes of keystream Z
[
2
,
L
] by using (
I
K
,
I
V
);
(b)
generateL bytes of keystream Z
′
[
0
,
L
] by using (
I
K
′
,
I
V
′
);
(c)
checkIV-Test for Z
[
2
,
L
] and Z
′
[
0
,
L
]; if they passIV-Test, go to Step (
2
); otherwise, return to Step (
1
) and choose anotherIV.
(2)
Return ValidIV and store thisIV.This algorithm requires2
64 chosenIVs and runs the encryption process of SD-Loiss 2
64
+
2
64
=
2
65 times. Thus, the time complexity of this algorithm is 2
65. Then, for each single key andIV, this algorithm only requires L
+
2 bytes of keystream at most. To make the probability that an invalidIV passesIV-Test negligible, we chooseL to be 15, and then 2
-
8
L is equal to 2
-
120 which is small enough to distinguish validIVs and invalidIVs with very high probability. Hence, our attack requires 17 bytes of keystream at most for each single key andIV.In the second phase, using the Finding ValidIV algorithm for SD-Loiss above, we can recover the 128-bit secret keyIK using a simple Guess and Determine attack. We guess the values of I
K
1, I
K
2, I
K
3, I
K
4, I
K
6, I
K
7, I
K
9, I
K
10, I
K
12, and I
K
15 (a total of 80 bits). Then, we can determine the remaining 48 bits of the secret keyIK by system (21) easily.Recall the two phases of our attack on SD-Loiss. The time complexity of our attack on SD-Loiss is2
65
+
2
80
≈
2
80, requiring 2
64 chosenIVs. The result shows that slide (key,IV) pairs can be also used for related key attack.


## 5. Conclusions

In this paper, an improved Guess and Determine attack on Loiss is proposed, which reduces the time complexity of the attack proposed by the designers by a factor of2
16. Furthermore, by exploiting the weakness of a scaled-down version of Loiss during its initialization phase, a related key chosenIV attack on the scaled-down Loiss is given. The attack recovers the 128-bit secret key of the scaled-down Loiss with time complexity of 2
80, requiring one related key and 2
64 chosenIVs. We hope our results can be helpful in evaluating the security of the Loiss stream cipher against Guess and Determine attack and related key attack, and we look forward to further works evaluating it against other kinds of cryptanalytic attacks.



---

*Source: 457275-2014-05-27.xml*