A Note on the Block Cipher Camellia
Yiqun Lisa Yin
NTT Multimedia Communication Laboratories
250 Cambridge Avenue, Palo Alto, CA 94306
yiqun@nttmcl.com

Version 1.11 — August 18, 2000

Abstract. Camellia is a block cipher jointly developed by NTT and
Mitsubishi in 2000. In this note, we describe some observations on thedesign of the cipher.

1

Introduction

Camellia [1] is a block cipher jointly developed Nippon Telegraph and Telephone
Corporation and Mitsubishi Electric Corporation in 2000. It is one of the proposals submitted to ISO/IEC JTC 1/SC 27 for consideration as an international
encryption standard. The joint eﬀort combines expertise in cipher design fromboth companies. As a result, Camellia certainly bears some nice features of E2 [9](designed by NTT) and MISTY [5] (designed by Mitsubishi).
In this note, we describe some observations on Camellia in terms of its security. Our analysis is based on the speciﬁcation of Camellia [1], a short proposal
to ISO [11] as well as existing analysis on E2 [10] and MISTY [5]. The main
objectives of our analysis is to give some outsider’s opinions on the design ofCamellia and to contribute to the continued analysis of the cipher.
The note is organized as follows: In Sections 2 through 4 we make some observations and ask a few questions regarding the major components in Camellia,
and in Section 5 we draw some concluding remarks. Throughout the note, we
use the same terminology and notation as in [1] without restating the precisedeﬁnition.

2

The F -function, P -function, and S-function

The structure of Camellia is “almost” Feistel. Its round function F adopts theso-called “1-round substitution-and-permutation structure” (or 1-round SPN):
The S layer consists of 8 s-boxes each operating on a single byte, and the P layer
is a linear transformation from 8 input bytes to 8 output bytes.
1This version is based on the earlier note dated April 6, 2000.

2.1

A diﬀerent view of the s-boxes

There are four diﬀerent s-boxes called s1 , s2 , s3 , s4 in Camellia. They are closely
related to each other as follows:s1 (x) = h(g(f (x ⊕ a))) ⊕ b,s2 (x) = s1 (x)<
<
<1,
>
>1,
s3 (x) = s1 (x)>s4 (x) = s1 (x<<<1).
The functions f and h are linear mappings, g is an inverse over GF (28 ), and a, b
are two ﬁxed constants.
The above deﬁnition can be rewritten in the following way so that the one-bit
rotations are “implicit.”si (x) = hi (g(fi (x ⊕ ai ))) ⊕ bi , for i = 1, 2, 3, 4.

(1)Such a diﬀerent view might be useful in facilitating certain analysis.
Below, we describe some observations based on Murphy and Robshaw’s recent
work on one of the AES ﬁnalists Rijndael [2]. Rijndael has a single s-box deﬁned
ass(x) = L(G(x)) ⊕ c,where L is a linear mapping, G is an inverse over GF (28 ), and c is a constant.
Murphy and Robshaw [8] showed that the constant c can be incorporated into
the key schedule and the linear component L can be re-grouped with the linear
transformation layer in Rijndael. In eﬀect, the Rijndael s-box is just an inverse
function over the ﬁnite ﬁeld.
The above arguments on Rijndael also apply to Camellia if we use Equation 1
as the formulas for the s-boxes in Camellia. More speciﬁcally, the 8 constantsai , bi (for i = 1, 2, 3, 4) can be incorporated into the key schedule, and the linear
mappings fi , hi (for i = 1, 2, 3, 4) can be re-grouped with the linear transformation P . The re-grouping of linear layers in Camellia is a little more complicatedthan that of Rijndael. In the case of Rijndael, byte-oriented operations (overGF (28 )) are preserved. For Camellia, the original linear layer P can be describedas only exclusive-or of bytes, but after re-grouping P needs to be speciﬁed using
exclusive-or of bits, since fi , hi are deﬁned at the bit level.
In the speciﬁcation of Camellia [1], it states that one of the major design
rationales for the two linear functions f, h is to make the s-boxes more complicated. However, we have seen that the linear functions can be deprived fromthe s-boxes to combine with the linear layer instead. The implication of such a
diﬀerent view of the overall S-P layer in Camellia is not yet clear, and perhaps
some further analysis following techniques in [8] should be considered.
Finally, it seems that the two constants a, b in the s-box of Camellia are notneeded in terms of the security of the encryption function of Camellia since they
can be integrated into the key schedule.
22.2

The choice of the 1-round SPN structure

One of the major changes from E2 [9] to Camellia is that the 2-round SPN
structure for the round function is replaced by the 1-round SPN structure. Herewe consider some pros and cons for such a choice by analyzing the upper boundon the maximum diﬀerential and linear probabilities. To simplify discussions, wewill just focus on diﬀerential probabilities.
Recently, Kanda presented some new results on how to evaluate 1-round SPN
round functions in terms of diﬀerential and linear attacks [4]. Let y = P (x) be
the linear layer in an SPN round function. He deﬁned the diﬀerential branchnumber Pd of P as
Pd =

min
(#changed input bytes + #changed output bytes).
all (x, x ) s.t. x = x

He showed that for Feistel ciphers with 1-round SPN round function, the minimum number of active s-boxes in r rounds is roughly proportional to 4r × Pd .
The analysis was actually quite involved.
The minimum number of s-boxes in Feistel ciphers with 2-round SPN structure can be quite easily analyzed using two simple facts. First, in any threeconsecutive rounds of a Feistel cipher, there are at least two rounds with nonzero input diﬀerence for any plaintext diﬀerence. Second, if input diﬀerence to around is non-zero in 2-SPN, then the minimum number of active s-boxes is Pd inthat round. Combining the above two facts, we can conclude that the minimum
number of active s-boxes in r rounds is roughly proportional to 2r
3 × Pd in Feistel
ciphers with 2-round SPN structure.
Based on the above discussion, we know that the minimum number of active
s-boxes over r rounds for the 2-round SPN structure is about 83 = 2.33 times
as much as that for the 1-round SPN structure. On the other hand, the total
number of s-boxes over r rounds the former is only twice as much as the latter.
So it seems that choosing a 2-round SPN structure may be better than a 1round SPN in a Feistel cipher, at least asymptotically. In practice, though, someboundary conditions and implementation issues might make the two comparable
the latter more favorable.
2.3

Camellia vs. E2

The most eﬀective existing attack on E2 is truncated diﬀerential cryptanalysis [7]. We’d like to know how eﬀective the attack is on Camellia.
It would also be interesting to consider variants of Camellia. For example,
we can analyze Camellia without the irregular rounds, or Camellia with the
P function being the same as that in E2, or Camellia with a 2-round SPN
structure, or Camellia with all the s-boxes set to s1 . In terms of truncateddiﬀerential cryptanalysis, would the above variants be stronger, comparable, or
weaker than the original Camellia? Such a study can help to better understandeach components of the cipher.
33

The F L-function and F L− -function

The pair of functions F L and F L−1 are “inserted” between every six rounds ofthe encryption routine to provide some non-regularity across rounds. One of theobvious goals for such a design is to thwart future unknown attacks.
We observe that the function F L can be viewed as a two-round 64-bit Feistel<<1 and the second one set
network with the ﬁrst round function set to F1 = ∩<to F2 = ∪, and similarly for F L−1 . We will often refer to the pair (F L, F L−1 )as an irregular round. Such an irregular round is much simpler compared withthe regular round function F of Camellia.
Below, we analyze the eﬀect of irregular rounds in terms of several known
attacks. In our analysis, we assume that there is an attack of a certain type on
Camellia when the irregular rounds are omitted and try to see what strength
the irregular rounds can add to the cipher.
Let us ﬁrst consider the two bitwise logical operations used in F L and F L−1 .
y = x ∩ roundkey, andy = x ∪ roundkey.
For an n-bit vector x, we use x[i] to denote the ith bit of x. Some basic properties
for the two operations are summarized in Table 1 and Table 2.

∩

roundkey[i]01input/output diﬀerence∆x[i] = 1 → ∆y[i] = 0∆x[i] = 1 → ∆y[i] = 1

aﬀect analysis
yes
no

∪

roundkey[i]01input/output diﬀerence∆x[i] = 1 → ∆y[i] = 1∆x[i] = 1 → ∆y[i] = 0

aﬀect analysisnoyes

Table 1. How ∩ and ∪ aﬀect diﬀerential cryptanalysis∩

roundkey[i]01input/output valuey[i] = 0, independent of x[i]y[i] = x[i]∪roundkey[i]01input/output value
aﬀect analysis
y[i] = x[i]noy[i] = 1, independent of x[i]yesaﬀect analysis
yesnoTable 2. How ∩ and ∪ aﬀect linear cryptanalysis

4

3.1

Diﬀerential and truncated diﬀerential cryptanalysis

For a random round key, the bit roundkey[i] is either 0 or 1 with probability
1/2. From Table 1 we know that a diﬀerence ∆x[i] may be canceled by thecorresponding key bit roundkey[i]. In particular, if ∆x has Hamming weight hthen we have ∆y = 0 with probability 2−h for a random round key.
In the case of truncated diﬀerentials, there is a similar eﬀect.
∆x
n Suppose
is n-bit long. If ∆x = 0, then ∆y = 0 with probability 21n i=1 ni 2−i for arandom round key. For example, if we choose n = 8 (for byte characteristics),
then the above probability is about 0.1.
Therefore, the diﬀerential paths as well as their associated probabilities varyfrom one key to another when irregular rounds are inserted. On one hand, this
could make the analysis more diﬃcult since the diﬀerential paths are key dependent. On the other hand, one might be able to take advantage of such key
dependencies and try to deduce the round keys used in the irregular rounds by
detecting which diﬀerential paths are valid.
Overall, it is not very clear whether such eﬀects from the two logical operations will make it easier or harder to construct useful diﬀerential characteristics
or truncated diﬀerentials.
3.2

Impossible diﬀerential cryptanalysis

As we have just seen, when an irregular round is inserted between regular rounds,the ∩roundkey and the ∪roundkey operation can change existing diﬀerential
paths and their probabilities. So the irregular rounds also make impossible differential paths key dependent. Since the associate probability for an impossible
diﬀerential path is zero, any change in the probability makes it no longer an
impossible diﬀerential path. Therefore, for most round keys, the use of F L and
F L−1 will destroy impossible diﬀerential paths, making impossible diﬀerential
cryptanalysis infeasible.
3.3

Linear cryptanalysis

Now we take a look at Table 2. Depending on the value of roundkey[i] and thelogical operation, the value of the output bit y[i] can be independent of the
input bit x[i]. If this happens, the pair of bits (x[i], y[i]) cannot be included in
any linear approximation. Therefore, for a random round key on average about
half of the (x[i], y[i]) pairs cannot be use to form linear approximations. This
makes linear approximations highly key dependent, and more importantly, itreally limits the ways that linear approximations can be constructed.
By similar argument, the use of both ∩ and ∪ will also reduce the eﬀect oflinear hulls (if any) since many of the linear hull paths are destroyed.
Overall, the irregular rounds should provide some extra strength for the
cipher against linear cryptanalysis.
5

3.4

Small avalanche eﬀect

Here we want to point out some mathematical properties of the F L function.
Following the notation in [1], let XL , XR be the two 32-bit inputs to F L, and let
YL , YR be the two 32-bit outputs from F L. We use 0t x and 1t x to denote 32-bit
binary vectors in which the ﬁrst t ≤ 32 bits are set to all 0s or 1s, respectively.
We observe that no matter what the values of the two round keys are in
F L, the inputs (XL , XR ) = (032 , 132 ) always produce the outputs (YL , YR ) =(132 , 132 ). That is, for such input values, the two round keys have no eﬀect tothe round.
More generally, we have the property that any inputs of the form (XL , XR ) =(0t x, 1t y) always produce outputs of the form (YL , YR ) = (0t−1 x , 1t−1 y  ). So
only the lower (31 − t) bits of two round keys have an impact on the results of
the outputs.
The above properties of F L show that for certain input values, the function
F L can have a very small avalanche eﬀect. It is not clear yet whether suchproperties can be used in some attacks.
3.5

Remarks¿From the above analysis, we ﬁnd some quite interesting properties of the irregular round (F L, F L−1 ). Sometimes, the round key bits can cancel the corresponding input bits, making certain diﬀerential and linear paths key dependent.
On the ﬂip side, the input bits can also cancel the corresponding round key bits,
making certain output bits key independent.
Such properties are generally not possessed by the regular round function F
in Camellia for which the round keys are exclusive-ored with the inputs. It canbe expected that the diﬀerent ways of how round keys are used in regular andirregular rounds will help prevent future attacks.

4

The key schedule

The key schedule of Camellia is quite simple and resembles that of MISTY [5]to a certain degree. The procedure can be divided into two steps. First, deriveone (or two) 128-bit key materials KA (and KB ) from the original secret key
K. (Let us call K, KA , KB as the subkeys.) Second, generate all round keys byrotating the subkeys K, KA , KB by various amounts. The key schedule is slightly
diﬀerent for 128-bit keys and 192/256-bit keys.
Here, we will focus on the key schedule of Camellia for 128-bit keys. In thiscase, the size of the subkeys (K, KA ) is 256 bits, and 26 64-bit round keys are
generated — 13 of them are rotations of K and the other 13 the rotation of KA .
4.1

Structures in round keys

The round keys are rotations of K or KA with rotation amounts diﬀering by 15
or 17. The rotation can result in some structures among the round keys.
6

First, let G be some bit pattern (e.g., consecutive 0s of a certain length)that occurs with probability p for a random 64-bit word. If both K and KA
have pattern G (which happens with probability p2 ), then all of the round keys
will have patten G (or its rotated form). Note that if the 26 round keys are
independent, then the probability that all of them possess the same pattern G
is only p26 , which is much smaller than p2 . We are not sure if one can takeadvantage of such a structure in the round keys in a real attack yet. But if one
can ﬁnd some pattern G of the round key for which attacking a single round
function with such a key is easier than random round keys, then from the above
analysis we know that a fair percentage of the keys will be weak under this
attack.
Second, we observe that if K or KA has a repetitive pattern of length 15 or
17, the some of the round keys can be exactly the same. That is, the same roundkey may be used in diﬀerent round. The property does not seem to cause any
immediate problem especially because it happens with very small probability.
4.2

Deriving the secret key from round keys

As we can see, the major design goals for the key schedule in Camellia is fast
speed, small RAM requirement, and compact hardware design. So “one-wayness”
was not a concern, but let us just quickly analyze the amount of work needed toderive the original secret key K from some round keys.
Assume that some bits of a round key ki are obtained (from an attack). If ki
is a rotation from (half of) K, then obviously the key space of K is immediately
reduced. Or, if we can obtain two round keys ki , kj that allow us to recover allbits of KA , then we can ﬁnd K much faster than exhaustive search. In particular,
it is not hard to see that one can derive K from KA in 264 steps by guessing
either the left half or the right half of K.
4.3

Related-key attacks

There are probably two problems to consider here. First, given two related secretkeys K and K  , what relation can one get for the corresponding KA and KA?
Second, given two sets of round keys that are related to each other, how can one
attack Camellia?
In Camellia, the subkey KA is derived from K using a 4-round Feistel network. The round function is just the F -function that is used in encryption andthe round keys are ﬁxed constants. We observe that if ∆K is set to (0, ∆) fora 64-bit ∆, then after 2 rounds and xoring K, the input diﬀerence to the thirdround becomes (∆ , 0) where ∆ = F (∆). Hence, the eﬀect 4-round Feistel network is really just 2 rounds. It seems that for any ∆ = 0, most of the bytes(exactly how many?) of KA will diﬀer even after 2 rounds of F . So even when
K and K  are closely related, KA and KA
are likely to diﬀer a lot.
Overall, we have not been able to come up with a related-key attacks evenon the reduced round version of Camellia.
74.4

Camellia vs. MISTYFor MISTY, four criteria were set up for designing the key schedule.
1. The size of secret key K is 128 bits.
2. The size of subkey materials is 256 bits.
3. Every round is aﬀected by all bits of K.
4. Every round is aﬀected by as many subkey bits.
Now let us consider again the key schedule of Camellia for 128-bit secret key.
We see that criteria 1 and 2 above are also satisﬁed, but criteria 3 and 4 are not.
In particular, half of the round keys (rotations of K) only depend on half of thebits of K. Even though we cannot see any problem with this, but it seems to
us that criterion 3 is a good property for key schedule to have in general. Since
Camellia certainly adopts some design ideas from MISTY in key schedule, we
wonder if this criterion was intentionally ignored due to eﬃciency concerns.

5Conclusion

We have described our initial observations on the major components of Camellia.
We have focused our analysis mostly on the key schedule and on the F L, F L−1
functions, since we think they are relatively new components. We have tried
to compare the components in Camellia with existing components in E2 andMISTY and raise some questions on the design rationale.
We have not yet considered the implementation aspect of Camellia. We notethat in [11] it is mentioned that Camellia achieves the smallest hardware design(only 10K gates) among all existing block ciphers. In comparison, the mosthardware-compact AES ﬁnalist still needs about 400K gates according to [3]. So
we feel that Camellia can be a nice complement cipher to the AES winner(s).
(This could be a good marketing point to make.)
Finally, we wish Camellia the best in various standardization eﬀort.

References
1. K. Aoki, T. Ichikawa, M. Kanda, M. Matsui, S. Moriai, J. Nakajima, T. Tokita.
Camellia – a 128-bit block cipher suitable for multiple platforms (Extended abstract). To appear in SAC 2000.
2. J. Daemen and V. Rijmen. AES proposal: Rijndael. Version 2. 1999.
3. T. Ichikawa, T. Kasuya, M. Matsui. Hardware Evaluation of the AES Finalists. In
Proceedings of the third AES conference. March 2000.
4. M. Kanda. Practical security evaluation of Feistel ciphers with SPN round function
against diﬀerential and linear attacks. To appear in SAC 2000.
5. M. Matsui. New Block Encryption Algorithm MISTY. In Proceedings of the 4th
Fast Software Encryption Workshop, 1997.
6. M. Matsui and T. Tokita. Cryptanalysis of a reduced version of the block cipher
E2. In Proceedings of the 6th Fast Software Encryption, March, 1999.

8

7. S. Moriai, M. Sugita, K. Aoki, and M. Kanda. Security of E2 against truncateddiﬀerential cryptanalysis. In Proceedings of the 6th International Workshop on
Selected Areas in Cryptography. August 1999.
8. S. Murphy and M. Robshaw. New observations on Rijndael. Research manuscript.
August 7, 2000. Available at http://isg.rhbnc.ac.uk/mrobshaw/.
9. Nippon Telegraph and Telephone Corporation. Speciﬁcation of E2 – a 128-bit Block
Cipher. 1999. Available at http://info.isl.ntt.co.jp/e2/.
10. Nippon Telegraph and Telephone Corporation. Supporting document on E2. 1999.
Available at http://info.isl.ntt.co.jp/e2/.
11. Nippon Telegraph and Telephone Corporation and Mitsubishi Electric Corporation. A Contribution on New Work Item Proposal on “Encryption Algorithms”.
March 10, 2000.

This article was processed using the LaTEX macro package with LLNCS style9