A strength evaluation of a pseudorandom number generator MUGI against linear cryptanalysis
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 lambda and a non-linear function rho. The non-linear function rho and the linear function I have already been analyzed, independently. In this paper, whole MUGI is analyzed by truncated linear cryptanalysis. The analysis of lambda function is based on the state variables method. The result is combined to the result of the analysis of rho 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.
pseudorandom number generator mugi stream cipher truncated linear cryptanalysis