Fault Analysis on Stream Cipher MUGI

block cipher. Therefore, the evaluation techniques for a block cipher are consid-
ered to be applicable to MUGI. Some cryptographic evaluations of MUGI have
been reported [19,20,21,22,23,24]; however, the success of side-channel analysis
such as fault analysis on MUGI has not yet been proposed. Hoch [22] considers
differential fault analysis on MUGI to be dicult because it is hard to obtain
sucient information to achieve a successful attack using only the evaluation
techniques of the block ciphers.
In this paper, we propose DFA on MUGI. To the best knowledge of the au-
thors, this is the first paper that proposes DFA on a stream cipher MUGI and
the proposed attack uses the characteristics that two kinds of update functions
are mutually dependent, i.e., each update function operates using another in-
termediate state as a parameter. In the proposed attack, we employ a random
fault model in which the intermediate states are randomly corrupted and the at-
tacker does not need to know the values of the faults. We note that the random
fault model is more practical compared to the 1-bit flip fault injection frequently
used in the DFA on other stream ciphers [12,14,15]. The proposed attack requires
only 12.54 pairs of correct and faulty outputs on average to recover the complete
internal states and the 128-bit secret key.
The remainder of this paper is organized as follows. Notations are defined in
Sec. 2. We review the description of MUGI in Sec. 3. We describe the concept
behind the proposed attack in Sec. 4. We describe the proposed attack in Sec.
5 and the evaluation of the proposed attack in Sec. 6. Finally, we conclude the
paper in Sec. 7. Some additional calculations and evaluations are given in the
appendix.

2No ons

In this section, we give some notations used in this paper.

a ( t )
i

: An 8-byte state in round t where i =0 , ··· , 2

b ( t )
i

: An 8-byte buffer in round t where i =0 , ··· , 15

X || Y : Concatenation

X ⊕ Y : Bitwise exclusive-OR operation

≫ n : Circular rotations of n bits to the right (in the 64-bit register)
≪ n : Circular rotations of n bits to the left (in the 64-bit register)

3 Description of MUGI

In this section, we review the description of MUGI [17]. MUGI has two inputs as
parameters, 128-bit secret key K and 128-bit initial vector I , which is a public
parameter. It generates a 64-bit length random bit string for each round. The
structure of MUGI is shown in Fig.1(a). The data size of MUGI is 64 bits, which
is referred to as a unit. As shown in Fig.1(a), the internal state is divided into
two parts: state a and buffer b . State a consists of 3 units, a = a 0 || a 1 || a 2 ,where

each element a i is 64 bits. Buffer b consists of 16 units, b 0 , ... , b 15 where each