cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

, MUGI is a

pseudorandom number generator A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...

(PRNG) designed for use as a

stream cipher stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream ...

. It was among the cryptographic techniques recommended for Japanese government use by

CRYPTREC CRYPTREC is the Cryptography Research and Evaluation Committees set up by the Japanese Government to evaluate and recommend cryptographic techniques for government and industrial use. It is comparable in many respects to the European Union's NESSIE ...

in 2003, however, has been dropped to "candidate" by CRYPTREC revision in 2013. MUGI takes a 128-bit secret

key Key or The Key may refer to: Common meanings * Key (cryptography), a piece of information that controls the operation of a cryptography algorithm * Key (lock), device used to control access to places or facilities restricted by a lock * Key (map ...

and a 128-bit initial vector (IV). After a key- and IV- setup process, MUGI outputs 64-bit output strings based on the internal state, while updating the internal state after each output block. MUGI has a 1216-bit internal state; there are three 64-bit registers (the "state") and 16 64-bit registers (the "buffer"). MUGI uses the non-linear

S-box In cryptography, an S-box (substitution-box) is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext, thus ensuring Sha ...

that was originally defined in

Advanced Encryption Standard The Advanced Encryption Standard (AES), also known by its original name Rijndael (), is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001. AES is a variant ...

(AES). A part of the linear transformation also reuses the

MDS matrix An MDS matrix (maximum distance separable) is a matrix representing a function with certain diffusion properties that have useful applications in cryptography. Technically, an m \times n matrix A over a finite field K is an MDS matrix if it is the ...

of AES. The basic design is influenced by that of

Panama Panama ( , ; es, link=no, Panamá ), officially the Republic of Panama ( es, República de Panamá), is a transcontinental country spanning the southern part of North America and the northern part of South America. It is bordered by Cos ...

Security

As of September 2006, there are no known attacks against MUGI that are faster than serial brute-force of the key space or of the internal state. In the paper, "A weakness of the linear part of stream cipher MUGI", by Golic Jovan Dj, Roy Bimal and Meier Willi, the abstract claims: "The linearly updated component of the stream cipher MUGI, called the buffer, is analyzed theoretically by using the generating function method. In particular, it is proven that the intrinsic response of the buffer, without the feedback from the nonlinearly updated component, consists of binary linear recurring sequences with small linear complexity 32 and with extremely small period 48. It is then shown how this weakness can in principle be used to facilitate the linear cryptanalysis of MUGI with two main objectives: to reconstruct the secret key and to find linear statistical distinguishers." In the paper, "Analysis of the Non-linear Part of Mugi" by

Alex Biryukov Alex Biryukov is a cryptographer, currently a full professor at the University of Luxembourg. His notable work includes the design of the stream cipher LEX, as well as the cryptanalysis of numerous cryptographic primitives. In 1998, he developed imp ...

and

Adi Shamir Adi Shamir ( he, עדי שמיר; born July 6, 1952) is an Israeli cryptographer. He is a co-inventor of the Rivest–Shamir–Adleman (RSA) algorithm (along with Ron Rivest and Len Adleman), a co-inventor of the Feige–Fiat–Shamir identificat ...

, the abstract claims: "This paper presents the results of a preliminary analysis of the stream cipher Mugi. We study the nonlinear component of this cipher and identify several potential weaknesses in its design. While we can not break the full Mugi design, we show that it is extremely sensitive to small variations. For example, it is possible to recover the full 1216-bit state of the cipher and the original 128-bit secret key using just 56 words of known stream and in 2¹⁴ steps of analysis if the cipher outputs any state word which is different than the one used in the actual design. If the linear part is eliminated from the design, then the secret non-linear 192-bit state can be recovered given only three output words and in just 2³² steps. If it is kept in the design but in a simplified form, then the scheme can be broken by an attack which is slightly faster than exhaustive search."

References

* * *

External links

MUGI homepage
{{Cryptography navbox , stream Stream ciphers