Fault Analysis on Stream Cipher MUGI

21. Henricksen, M., Dawson, E.: Rekeying Issues in the MUGI Stream Cipher. In:
Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 175-188. Springer,
Heidelberg (2006)
22. Hoch, Y.: Fault Analysis of Stream Ciphers M.Sc. Thesis, Weizmann Institute of
Science, Israel
23. Golic, J.D.: A Weakness of the Linear Part of Stream Cipher MUGI. In: Roy, B.,
Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 178-192. Springer, Heidelberg
(2004)
24. Biryukov, A., Shamir, A.: Analysis of the Non-linear Part of MUGI. In: Gilbert, H.,
Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 320-329. Springer, Heidelberg
(2005)

Appendix A: Probability of the Number of Solutions for
the S-Box Equation in Sec.5.2

In order to obtain the probability that we obtain 2 or 4 solutions for the S-box
equation (2) in Sec. 5.2, we describe the characteristics of the equation for the
S-box used in MUGI. Let us consider the simple 1-byte S-box model shown in
Fig.7. When we know a pair of inputs, y i (8) and y j (8) , and know the output
difference, δ ij (8) , we can obtain a set of unknown candidates of x (8) by solving
the following equation.

S [ y i (8) ⊕ x (8) ] ⊕ S [ y j (8) ⊕ x (8) ]= δ ij (8) (4)

The number of key candidates depends on y i (8) , y j (8) ,and δ ij (8) , and the struc-
ture of the S-box. By solving (4), we examine the size of the candidates of the

Table 2. S-Box Statistics

|x (8) | NC PP |x (8) | =0 E( |x (8) | )

0 8,486,400 0.506 - -

2 8,225,280 0.490 0.992 1.984

4 65,280 0.004 0.008 0.031

256 256 0.000 0.000 0.010

Total 16,777,216 1 1 2.024

(= 2 24 ) (= 2 1 . 02 )

x

8

8 8

y

⊕

S

Sx y [ ⊕ ]

Fig. 7. One-byte S-box model