MUGI is a pseudorandom number generator designed for use as a stream cipher. Was designed by Dai Watanabe, Soichi Furuya, Kazuo Takaragi, Bart Preneel, Hirotaka Yoshida, basing in Panama algorithm which can be used both as a hash function and a stream cipher and is aimed to be suitable for both of software and hardware. Was published in 2002 and has the standard ISO/IEC 18033-4 achieved in 2005.
MUGI is a PRNG with an128-bit secret key K (secret parameter) and an 128-bit initial vector I (public parameter). It generates 64-bit length random bit string for each round.
The process for encrypt a plaintext using MUGI is:
1.- Divide the plaintext data into 64-bit blocks.
2.- XOR to the output units generated by the secret key K and the initial vector I for each round.
The process for decrypt a plaintext using MUGI is:
The decryption can be implemented in the same manner.
The outline of the algorithm is as follows:
Input: Secret key K, Initial vector I, Output size n (units)
Output: Random number sequence Out[i] (0 ≤ i < n)
Output: Random number sequence Out[i] (0 ≤ i < n)
Algorithm
Initialization
1. First input the secret key K into state a. Then initialize buffer b with running ρ.
2. Add the initial vector I into state a and initialize state a with running ρ.
3. Mix whole internal state with running the update function of MUGI for bringing to completion.
3. Mix whole internal state with running the update function of MUGI for bringing to completion.
Random number generation
4. Run n rounds update function and output a part of the internal state (64-bit) for each round.
Here the explanation of some of this points/steps:
Input
MUGI has two input as a parameter, one is an 128-bit secret key K and the other is an128-bit initial vector I and is a public parameter. The higher and lower units of K are denoted by K0 and K1 respectively. In the same manner I0 and I1 are used.
MUGI has two input as a parameter, one is an 128-bit secret key K and the other is an128-bit initial vector I and is a public parameter. The higher and lower units of K are denoted by K0 and K1 respectively. In the same manner I0 and I1 are used.
State
State a consists of 3 units. Each of them is denoted by a0, a1, a2 inrotation , i.e.
a = [Higher] a0||a1||a2 [Lower]
State a consists of 3 units. Each of them is denoted by a0, a1, a2 inrotation , i.e.
a = [Higher] a0||a1||a2 [Lower]
Buffer
Buffer n consists of 16 units. Each of them is denoted by b0, . . . , b15 inrotation in the same manner as state a.
Buffer n consists of 16 units. Each of them is denoted by b0, . . . , b15 inrotation in the same manner as state a.
Random Number Generation
After the initialization of MUGI generates 64-bit random number and transform the internal state at all round. Denote the output at round t as Out[t], thenthe output is given as below:
Out[t] = a(t)
After the initialization of MUGI generates 64-bit random number and transform the internal state at all round. Denote the output at round t as Out[t], thenthe output is given as below:
Out[t] = a(t)
Rhoρ is the update function of state a. It is a kind of target heavy Feistel structure with two F-functions and uses buffer b as a parameter. The function ρ is described as follows:
C1, C2 in the equations above are constants. The F-function of MUGI reuses the components of AES.
Security and Attacks
MUGI is not yet broken.
The security was evaluated according to re-synchronization attack, related-key attack, and linear correlation of an output sequence.
- Randomness: An attacker fixes a secret key and an initial vector, and then he observes the relation in the output sequence.
- Re-synchronization attack: An attacker fixes a secret key, and then he observes the relation between initial vectors and output sequences.
- Related-key: An attacker fixes an initial vector, and then he observes the relation between keys and output sequences. The related-key attack includes observing the relation between keys and initial vectors.
An exhaustive key search require 2127 computations on average to find correct key. So an attack is efficient when it costs less than 2127 encryptions on average to find the correct key.
In the article, "Analysis of the Non-linear Part of Mugi" by Alex Biryukov and Adi Shamir, they say:
"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 214 steps of analysis if the cipher outputs any state word which is different than the one used in the actual design."
"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 214 steps of analysis if the cipher outputs any state word which is different than the one used in the actual design."
___________________________________________________________________________________
Enlaces:
Faltó lo del ejemplo paso por paso. Ya no puedes perder más puntos si no quieres arriesgar reprobación...
ResponderEliminar