A Strength Evaluation of a Pseudorandom Number Generator MUGI against Linear Cryptanalysis

Hiroki SEKINE  Tetsuro NOSAKA  Yasuo HATANO  Masaki TAKEDA  Toshinobu KANEKO 

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences  Vol.E88-A  No.1  pp.16-24
Publication Date: 2005/01/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Symmetric Key Cryptography
Keyword: 
truncated linear cryptanalysis,  stream cipher,  pseudorandom number generator,  MUGI, 

Full Text: PDF(727.1KB)

Summary: 
This paper reports the strength of a pseudorandom number generator MUGI, which was published as a stream cipher by Hitachi, Ltd. in 2001, against linear cryptanalysis. MUGI is one of the recommended ciphers of CRYPTREC, which is a project for the e-Government in Japan. It has two internal states called state and buffer, which are updated by a linear function λ and a non-linear function ρ. The non-linear function ρ and the linear function λ have already been analyzed, independently. In this paper, whole MUGI is analyzed by truncated linear cryptanalysis. The analysis of λ function is based on the state variables method. The result is combined to the result of the analysis of ρ function to make a trellis diagram. Viterbi search is conducted on the diagram to find the best possible linear path under 64-bit truncated linear cryptanalysis. As the result, the upper bound of the maximum linear characteristic probability is estimated as less than 2-138. Therefore, MUGI is secure against linear cryptanalysis.