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

Hiroki SEKINE; Tetsuro NOSAKA; Yasuo HATANO; Masaki TAKEDA; Toshinobu KANEKO

doi:10.1093/ietfec/e88-a.1.16

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

Hiroki SEKINE, Tetsuro NOSAKA, Yasuo HATANO, Masaki TAKEDA, Toshinobu KANEKO

Full Text Views

0

Cite this

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.1 pp.16-24

Publication Date: 2005/01/01

Publicized

Online ISSN

DOI: 10.1093/ietfec/e88-a.1.16

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category: Symmetric Key Cryptography

Cite this

Copy

Hiroki SEKINE, Tetsuro NOSAKA, Yasuo HATANO, Masaki TAKEDA, Toshinobu KANEKO, "A Strength Evaluation of a Pseudorandom Number Generator MUGI against Linear Cryptanalysis" in IEICE TRANSACTIONS on Fundamentals, vol. E88-A, no. 1, pp. 16-24, January 2005, doi: 10.1093/ietfec/e88-a.1.16.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e88-a.1.16/_p

Copy

@ARTICLE{e88-a_1_16,
author={Hiroki SEKINE, Tetsuro NOSAKA, Yasuo HATANO, Masaki TAKEDA, Toshinobu KANEKO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Strength Evaluation of a Pseudorandom Number Generator MUGI against Linear Cryptanalysis},
year={2005},
volume={E88-A},
number={1},
pages={16-24},
abstract={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.},
keywords={},
doi={10.1093/ietfec/e88-a.1.16},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - A Strength Evaluation of a Pseudorandom Number Generator MUGI against Linear Cryptanalysis
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 16
EP - 24
AU - Hiroki SEKINE
AU - Tetsuro NOSAKA
AU - Yasuo HATANO
AU - Masaki TAKEDA
AU - Toshinobu KANEKO
PY - 2005
DO - 10.1093/ietfec/e88-a.1.16
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E88-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2005
AB - 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.
ER -