Fault Analysis on Stream Cipher MUGI

Fault Analysis on Stream Cipher MUGI

Junko Takahashi 1 , 2 , Toshinori Fukunaga 1 , and Kazuo Sakiyama 2

1 NTT Information Sharing Platform Laboratories, NTT Corporation,
3-9-11, Midori-cho Musashino-shi, Tokyo 180-8585, Japan
{ takahashi.junko,fukunaga.toshinori } @lab.ntt.co.jp
2 Department of Informatics, The University of Electro-Communications,
1-5-1, Chofugaoka Chofu, Tokyo 182-8585, Japan
{ junko,saki } @ice.uec.ac.jp

Abstract. This paper proposes differential fault analysis, which is a
well-known type of fault analysis, on a stream cipher MUGI, which uses
two kinds of update functions of an intermediate state. MUGI was pro-
posed by Hitachi, Ltd. in 2002 and it is specified as ISO/IEC 18033-4 for
keystream generation. Fault analysis is a side-channel attack that uses
the faulty output obtained by inducing faults into secure devices. To
the best knowledge of the authors, this is the first paper that proposes
applying fault analysis to MUGI. The proposed attack uses the relation
between two kinds of the update functions that are mutually dependent.
As a result, our attack can recover a 128-bit secret key using 12.54 pairs
of correct and faulty outputs on average within 1 sec.

Keywords: Fault analysis, Differential fault analysis (DFA), Stream ci-
pher, Side-channel analysis.

1 Introduction

Nowadays, side-channel attacks are considered to be serious attacks because the
secret keys embedded in a secure computing device such as smart cards and
RFID tags can be recovered within a feasible computational time. Fault analysis
is one type of side-channel attacks which deduces the secret key by deliberately
inducing faults into the secure device during its cryptographic computation.
Differential fault analysis (DFA) proposed by Biham et al. [1] is the most well-
known fault analysis. In their attack, the secret key of DES can be recovered by
comparing the correct and faulty output results after injecting faults into the
secure device. Previously, DFA on some symmetric ciphers was proposed with
some success in recovering secret keys [1,2,3,4,5,6,7,8]. Recently, fault analyses
against stream ciphers have been proposed in [9,10,11,12,13,14,15].
At FSE 2002, Hitachi, Ltd. proposed the pseudo-random number generator
(PRNG) MUGI [16]. MUGI uses a 128-bit secret key and a 128-bit initial vector.
It generates 64-bit random output and transforms the internal state [17]. MUGI
is specified as ISO/IEC 18033-4 for keystream generation. Its structure is based
on the Panama PRNG [18] the design for which targets suitability for both
software and hardware implementations, and the design principle is based on a