Copyright NTT and Mitsubishi Electric Corporation 2000-2001

Camellia: A 128-Bit Block Cipher

Suitable for Multiple Platforms

Kazumaro Aokiy Tetsuya Ichikawaz Masayuki Kanday
Mitsuru Matsuiz Shiho Moriaiy Junko Nakajimaz Toshio Tokitaz
Nippon Telegraph and Telephone Corporation
1-1 Hikarinooka, Yokosuka, Kanagawa, 239-0847 Japanyfmaro,kanda,shihog@isl.ntt.co.jp

Mitsubishi Electric Corporation
5-1-1 Ofuna, Kamakura, Kanagawa, 247-8501 Japanzfichikawa,matsui,june15,tokitag@iss.isl.melco.co.jp

Ver 1.0: July 13, 2000
Ver 2.0: September 26, 2001

Abstract.

We present a new 128-bit block cipher called Camellia. Camellia
supports 128-bit block size and 128-, 192-, and 256-bit keys, i.e. the same interface
speci cations as the Advanced Encryption Standard (AES). Eciency on both software and hardware platforms is a remarkable characteristic of Camellia in addition
to its high level of security. It is con rmed that Camellia provides strong security
against di erential and linear cryptanalysis. Compared to the AES nalists, i.e.
MARS, RC6, Rijndael, Serpent, and Two sh, Camellia o ers at least comparable
encryption speed in software and hardware. An optimized implementation of Camellia in assembly language can encrypt on a Pentium III (1.13GHz) at the rate of 471
Mbits per second. In addition, a distinguishing feature is its small hardware design.
A hardware implementation, which includes encryption, decryption, and the keyschedule for 128-bit keys, occupies only 8.12K gates using a 0.18m CMOS ASIC
library. This is in the smallest class among all existing 128-bit block ciphers.

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

Contents

1 Introduction
2 Design Rationale

1
3

3 Performance Figures

5

4 Software Implementation Techniques

11

5 Hardware Evaluations

20

6 Security

26

7 Conclusion
A History

35
41

2.1
2.2
2.3
2.4
2.5

F -function : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :P -function : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :s-boxes : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :F L- and F L01 -functions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :Key Schedule : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :3.1 Software Performance : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :3.2 Hardware Performance : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

3
3
3
3
4

5
5

4.1 Setup : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11
4.2 Data Randomization : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 12
4.3 General Guidelines : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 18
5.1
5.2
5.3
5.4

Type 1: Fast Implementation-1 (Fully loop unrolled architecture) : : : : : : : : :Type 2: Small Implementation-1 (Loop architecture) : : : : : : : : : : : : : : : :Type 3: Small Implementation-2 (Special Case for FPGA, Loop architecture) : :Type 4: Fast Implementation-2 (Pipeline architecture) : : : : : : : : : : : : : : :6.1 Di erential and Linear Cryptanalysis : : : : : : : : : : : : : : : : : : : : : : : : :6.2 Truncated Di erential Cryptanalysis : : : : : : : : : : : : : : : : : : : : : : : : :6.3 Truncated Linear Cryptanalysis : : : : : : : : : : : : : : : : : : : : : : : : : : : :6.4 Cryptanalysis with Impossible Di erential : : : : : : : : : : : : : : : : : : : : : :6.5 Boomerang Attack : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :6.6 Higher Order Di erential Attack : : : : : : : : : : : : : : : : : : : : : : : : : : :6.7 Square Attack : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :6.8 Interpolation Attack and Linear Sum Attack : : : : : : : : : : : : : : : : : : : :6.9 No Equivalent Keys : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :6.10 Slide Attack : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :6.11 Related-key Attack : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :6.12 Statistical Tests : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :6.13 Implementation Attacks : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :6.14 Brute Force Attacks : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

i

20
21
22
24

26
27
29
29
29
30
30
31
31
31
32
32
32
33

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

1 Introduction
This paper presents a 128-bit block cipher called Camellia, which was jointly developed by NTT
and Mitsubishi Electric Corporation. Camellia supports 128-bit block size and 128-, 192-, and256-bit key lengths, and so o ers the same interface speci cations as the Advanced Encryption
Standard (AES). The design goals of Camellia are as follows.

High level of security. The recent advances in cryptanalytic techniques are remarkable. A
quantitative evaluation of security against powerful cryptanalytic techniques such as di erential
cryptanalysis [BS93] and linear cryptanalysis [M94] is considered to be essential in designing any
new block cipher. We evaluated the security of Camellia by utilizing state-of-art cryptanalytic
techniques. We have con rmed that Camellia has no di erential and linear characteristics that
hold with probability more than 20128 . Moreover, Camellia was designed to o er security against
other advanced cryptanalytic attacks including higher order di erential attacks [K95, JK97],
interpolation attacks [JK97, A00], related-key attacks [B94, KSW96], truncated di erential attacks [K95, MT99], boomerang attacks [W99], and slide attacks [BW99, BW00].
Eciency on multiple platforms. As cryptographic systems are needed in various appli-

cations, encryption algorithms that can be implemented eciently on a wide range of platforms
are desirable, however, few 128-bit block ciphers are suitable for both software and hardware
implementation. Camellia was designed to o er excellent eciency in hardware and software
implementations, including gate count for hardware design, memory requirements in smart card
implementations, as well as performance on multiple platforms.
Camellia consists of only 8-by-8-bit substitution tables (s-boxes) and logical operations thatcan be eciently implemented on a wide variety of platforms. Therefore, it can be implementedeciently in software, including the 8-bit processors used in low-end smart cards, 32-bit processors widely used in PCs, and 64-bit processors. Camellia doesn't use 32-bit integer additions andmultiplications, which are extensively used in some software-oriented 128-bit block ciphers. Such
operations perform well on platforms providing a high degree of support, e.g., Pentium II/III or
Athlon, but not as well on others. These operations can cause a longer critical path and larger
hardware implementation requirements.
The s-boxes of Camellia are designed to minimize hardware size. The four s-boxes areane equivalent to the inversion function in the nite eld GF(28 ). Moreover, we reduced theinversion function in GF(28 ) to a few GF(24) arithmetic operations. It enabled us to implement
the s-boxes by fewer gate counts.
The key schedule is very simple and shares part of its procedure with encryption. It supports
on-the-key subkey generation and subkeys are computable in any order. The memory requirement for generating subkeys is quite small; an ecient implementation requires about 32-byte
RAM for 128-bit keys and about 64-byte RAM for 192- and 256-bit keys.

Standardization activities. In March 2000 NTT and Mitsubishi Electric Corporation pro-

posed Camellia in response to the call for contributions from ISO/IEC JTC 1/SC 27, aiming at
its being adopted as an international standard. In September 2000, we submitted Camellia to1

Copyright NTT and Mitsubishi Electric Corporation 2000-2001
NESSIE (New European Schemes for Signature, Integrity, and Encryption) project as a strong
cryptographic primitive. In September 2001, Camellia was selected as a candidates for the 2nd
Phase of the NESSIE project.

Outline of the paper. This paper is organized as follows: Section 2 describes the rationale

behind Camellia's design. Section 3 discusses the performance of Camellia. Section 4 contains
the techniques for software implementation. In Section 5 we discuss our hardware evaluations.
In Section 6 we evaluated Camellia's strength against known attacks. We conclude in Section 7.
For the speci cation of Camellia, please see the separate document titled \Speci cation of
Camellia { a 128-bit Block Cipher." We will follow the de nitions and notation given in thisseparate paper.

2

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

2 Design Rationale
F -function
The design strategy of the F -function of Camellia follows that of the F -function of E2 [KMA+ 98].
The main di erence between E2 and Camellia is the adoption of the 1-round (conservative) SPN(Substitution-Permutation Network), not the 2-round SPN, i.e. S-P-S. When the 1-round SPN
is used as the round function in a Feistel cipher, the theoretical evaluation of the upper boundof di erential and linear characteristic probability becomes more complicated, but the speed
under the same level of \real" security is expected to be improved. See Section 6 for detailed
discussions on security.
2.1

P -function
The design rationale of the P -function is similar to that of the P -function of E2. That is, for computational eciency, it should be represented using only bytewise exclusive-ORs and for security
against di erential and linear cryptanalysis, its branch number should be optimal [KTM+ 99].
From among the linear transformations that satisfy these conditions, we chose one considering
highly ecient implementation on 32-processors [AU00] and high-end smart cards, as well as
8-bit processors.
2.2

s-boxes
As the s-boxes we adopted functions ane equivalent to the inversion function in GF(28 ) for
enhanced security and small hardware design.
It is well known that the smallest of the maximum di erential probability of functions in
GF(28 ) was proven to be 206, and the smallest of the maximum linear probability of functions in
GF(28 ) is conjectured to be 206 . There is a function ane equivalent to the inversion function
in GF(28 ) that achieves the best known of the maximum di erential and linear probabilities,
206 . We choose this kind of functions as s-boxes. Moreover, the high degree of the Boolean
polynomial of every output bit of the s-boxes makes it dicult to attack Camellia by higher orderdi erential attacks. The two ane functions that are performed at the input and output of theinversion function in GF(28 ) complicates the expressions of the s-boxes in GF(28), which makes
interpolation attacks ine ective. Making the four s-boxes di erent slightly improves security
against truncated di erential cryptanalysis [MT99].
For small hardware design, the elements in GF(28) can be represented as polynomials withcoecients in the sub eld GF(24 ). In other words, we can implement the s-boxes by using a few
operations in the sub eld GF(24) [MIYY88]. Two ane functions at the input and output of
the inversion function in GF(28) also play a role in complicating the expressions of the s-boxes
in GF(24).
2.3

F L- and F L01-functions
F L- and F L01 -functions are \inserted" between every 6 rounds of a Feistel network to provide
non-regularity across rounds. One of the goals for such a design is to thwart future unknown
attacks. It is one of merits of regular Feistel networks that encryption and decryption procedures
2.4

3

Copyright NTT and Mitsubishi Electric Corporation 2000-2001
are the same except for the order of the subkeys. In Camellia, F L=F L01-function layers areinserted every 6 rounds, but this property is still preserved.
The design criteria of F L- and F L01-functions are similar to those of the F L-function of
MISTY [M97]. The di erence between MISTY and Camellia is the addition of 1-bit rotation.
This is expected to make bytewise cryptanalysis harder, but it has no negative impact on
hardware size or speed. The design criteria are that these functions must be linear for any xed
key and that their forms depend on key values. Since these functions are linear as long as the key
is xed, they do not make the average di erential and linear probabilities of the cipher higher.
Moreover, these functions are fast in both software and hardware since they are constructed bylogical operations such as AND, OR, XOR, and rotations.
2.5 Key Schedule

The design criteria of the key schedule are as follows.
1. It should be simple and share part of its procedure with encryption/decryption.
2. Subkey generation for 128-, 192- and 256-bit keys can be performed by using the same keyschedule (circuit). Moreover, the key schedule for 128-bit keys can be performed by using
a part of this circuit.
3. Key setup time should be shorter than encryption time.
In cases where large amounts of data are processed with a single secret key, the setup time
for key scheduling may be unimportant. On the other hand, in applications in which the
key is changed frequently, key agility is a factor. One basic component of key agility is key
setup time.
4. It should support on-the- y subkey generation.
5. On-the- y subkey generation should be computable in the same way in both encryption
and decryption.
Some ciphers have separate key schedules for encryption and decryption. In otherciphers, e.g., Rijndael [DR98] or Serpent [ABK98], subkeys are computable in the forward
direction only and require unwinding for decryption.
6. There should be no equivalent keys.
7. There should be no related-key attacks or slide attacks.
Criteria 1 and 2 mainly address small hardware requirements, Criteria 3, 4, and 5 are advantageous in terms of practical applications, and Criteria 6 and 7 are for security.
The memory requirement for generating subkeys is quite small. An ecient implementationof Camellia for 128-bit keys requires 16 bytes (=128 bits) for the original secret key, KL , and 16
bytes (=128 bits) for the intermediate key, KA . Thus the required memory is 32 bytes. Similarly,
an ecient implementation of Camellia for 192- and 256-bit keys needs only 64 bytes.

4Copyright NTT and Mitsubishi Electric Corporation 2000-2001

3 Performance Figures
3.1 Software Performance

Table 1 summarizes the current software performance of Camellia on the commonly-used 32-bit
and 64-bit processors. Table 2 shows the software performance on the microprocessors used forsmart cards and embedded systems, which are equipped with the restricted memory. Generally
speaking, the rst priority of the former is \Speed," while that of the latter is \RAM Usage and
ROM Usage." Some of the data are published in [AIK+ 00a, C01, ISKM01, AIK+ 00b, Y01a,
Y01b], but the others have not been published yet.
The tables show that Camellia can be eciently implemented on low-end smart cards, 32-bit
and 64-bit processors. We use the abbreviations M (mega) for 106 and m (milli) for 1003 in thetables.

Optimization level. When we coded programs using assembly language, we tried to use
many techniques described in Section 4 to achieve the best performance. However, there is aroom for further improvement.
On the other hand, depending on the C compiler used, di erent assembly codes are produced
from the same C code. This means that the assembly codes are not guaranteed to be optimal,
even if the C code is optimized. Thus, we did not spend a long time on optimizing C code.
How to measure speed. It is dicult to measure speed on modern processors since there

are many elements, for example, status of cache, that are beyond the users control and thatin uence speed. We decided to measure speed under the following conditions and assumptions: All codes and data are correctly aligned.
 Input and output texts and codes are preloaded to the rst level cache.
 Branch predictions are correct.
 Setup function (except for on-the- y implementations) generates subkey-dependent constants from the secret key, and the constants are used by encryption or decryption function.
 Encryption (decryption) function except for on-the- y implementations can encrypt (decrypt) an integral number of blocks.
 We measured the speed many times, and chose the best result to eliminate cache hit misses
and other uncontrollable factors.
 We averaged the speed numbers for large block encryption, but the values include all
overheads including loop and function calls.

3.2 Hardware Performance

Table 3 represents the recent results on hardware performance of Camellia on ASIC (Application
Speci c Integrated Circuit) and FPGA (Field Programmable Gate Array). Table 4 shows theenvironment of our hardware design and evaluation.
5

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

Table 4: Hardware evaluation environment (ASIC, FPGA)
Language (ASIC, FPGA) Verilog-HDL
Design library (ASIC) Mitsubishi Electric 0.35m CMOS ASIC library
Mitsubishi Electric 0.18m CMOS ASIC library
0.25 m CMOS ASIC library (reported by CRYPTREC
Report 2000)(FPGA) Xilinx XC4000XL series
Xilinx VirtexE series
Simulator (ASIC, FPGA) Verilog-XL (except for 0.25m)(ASIC) VCS5.1 (used for 0.25m)
Logic synthesis (ASIC) Design Compiler version 1998.08 (used for 0.35m)
Design Compiler version 2000.11-SP1 (used for 0.18m)
Design Compiler version 2000.05-1 (used for 0.25m)(FPGA) Synplify version 5.3.1 and ALLIANCE version 2.1i
(used for XC4000XL series)
Synplify version 6.1.3 and ALLIANCE version 3.3.07i(used for VirtexE series)

Table 5: Hardware design policies (outline)
TypeTop priority
Outline of logic
Type 1 Fast implementation from the viewpoint of Enc(Dec) speed Figure 1
Type 2 Small implementation from the viewpoint of total logic size Figure 2
Type 3
Small implementation (special case for FPGA)
Figure 3
Type 4
Pipeline implementation
Figure 46

Copyright NTT and Mitsubishi Electric Corporation 2000-2001
We evaluated Type 1 through Type 4 logic. Table 5 shows the top priorities of the logic types.
The details of each type are described in Section 5.

7

Table 1: Camellia Software Performance (updated on Aug.31, 2001)
RAM Usage(*1)

Speed
Processor

Language

Key Size

Key setup(*2)[bits]

Pentium III (*4)

Assembly

Pentium III (*5)

Assembly

Pentium II (*6)
Pentium III (*8)

ANSI C(*7)
Java(*9)

Alpha 21264 (*10)

Assembly

Alpha 21264 (*11)

Assembly

UltraSPARCIIi (*12)

Assembly

128
128
192
256
128
128
128
128
128
128
128
192
256
128
128
128
128
128

[cycles]Enc. / Dec.
[cycles]

1,570
160
222
226
‑

308
371
494
494
326
(Enc) 467 (*3)
(Dec) 474 (*3)
263
577
9,091
793
158
326
118
339
176
445
176
445
282
‑
(Enc) 448 (*3)
(Dec) 435 (*3)
355‑
403 (*3)[Mbps]

290.9
241.5
181.4
181.4
255.2
0.72msec
0.73msec
66.6
161.4
261.9
251.8
191.9
191.9
210.2
0.97msec
0.94msec
144.2
1.01msec

ROM Usage

Key setup(*2)

Enc. / Dec.

Total size

Key setup(*2)

Enc. / Dec.

Table

[bytes][bytes][bytes][bytes][bytes][bytes]

288
28
28
28
‑
‑
‑
44
‑
48
48
48
48
‑
‑
‑
‑
‑

20
36
36
36
‑
‑
‑
64
‑
48
48
48
48
‑
‑
‑
‑
‑

15,012
11,42013,032
13,04829,285
20,11020,236
9,461‑
21,04020,73622,19622,20431,552
25,792
25,792
15,24023,992

6,788
1,046
1,469
1,485
‑
‑
‑
1,600
‑
1,600
1,132
1,668
1,676
‑
‑
‑
‑
‑

0
2,150
3,323
3,323
‑
‑
‑
3,733
‑
2,928
3,076
4,000
4,000
‑
‑
‑
‑
‑

Reference

8,224 [AIK+00b]
8,224 [AIK+00b]
8,240 [AIK+00b]
8,240 [AIK+00b]
[C01]
‑
[C01]
‑
[C01]
‑
4,128 [AIK+00b]‑ Not published
16,512[AIK+00b]
16,528[AIK+00b]
16,528[AIK+00b]
16,528[AIK+00b]
[C01]
‑
[C01]
‑
[C01]
‑
[C01]
‑
[C01]
‑

(*1) The figure includes stack area, and excludes text area and key area.
(*2) Key schedule may be included.
(*3) The figure includes key generation and one block encryption. This is achieved by using the on-the-fly subkey generation.
(*4) IBM PC/AT compatible PC, Intel Pentium III (700MHz), 256KB on-die L2 cache, FreeBSD 4.0R, 128MB main memory.
(*5) IBM PC/AT compatible PC, Intel Pentium III (650MHz), 256KB on-die L2 cache, Windows98 SE, 64MB main memory.
(*6) IBM PC/AT compatible PC, Intel Pentium II (300MHz), 512KB L2 cache, Windows95, 160MB main memory.
(*7) Microsoft Visual C++ 6 with the optimization options /G6 /Zp16 /ML /Ox /Ob2.
(*8) IBM PC/AT compatible PC, Intel Pentium III (1GHz), 256KB on-die L2 cache, Windows2000, 512MB main memory.
(*9) IBM Java Compiler 1.2.2 and IBM Java VM 1.2.2.
(*10) Alpha 21264 (667MHz), Tru64 UNIX 4.0F, 2GB main memory.
(*11) Alpha 21264 (463MHz), Tru64 UNIX V5.1, 512MB main memory.
(*12) Ultra SPARC IIi (400MHz), Solaris 7, 256MB main memory.

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

Table 2: Camellia Software Performance for Smart Cards and Embedded Systems (updated on Aug.31, 2001)
Processor

Language

Speed

RAM Usage

ROM Usage

Key
size

Key setup(*1)

Enc. / Dec.

Key setup(*1)

Enc. / Dec.

Total size

Key setup(*1)

Enc. / Dec.

Table

[bits][cycles][cycles][bytes][bytes][bytes][bytes][bytes][bytes]

Sharingsize(*2)[bytes]Reference(*3)

8051 (*7)

Assembly128
128

Z80 (*8)

Assembly128

H8/3113 (*9)

Assembly

128

MC68HC705B16 (*10)

Assembly

128

MC68HC908AB32 (*11)

Assembly

128

M32Rx/D (*12)

Assembly

128

10,217
10.22msec
5,146
28,382
1.03msec
5.68msec(Enc) 35,951 (*3)
7.19msec(Dec) 37,553 (*3)
7.51msec
2,380
0.95msec
7,500
3.57msec
5,679
0.71msec
642
6.42msec

4,100
1.64msec
9,900
4.71msec
8,430
1.05msec
1,236
12.36msec

0

32 (*4)

990

0

702

288

44 (*5)62 (*5)

1,698

358

1,183

288

0

60 (*5)

‑

1,023

‑

0

60

[AIK+00b]-131 Not published-797 Not published

1,268
(*5)

0

‑

1,042

‑

208 (*6)

0

‑

‑

‑

‑

‑

[Y01a]

208 (*6)

0

‑

‑

‑

‑

‑

[Y01a]

208 (*6)

0

‑

‑

‑

‑

‑

[Y01b]

44 (*5)44 (*5)

8,684

1,392

3,164

4,128

0

[AIK+00b](*1) Key schedule may be included.
(*2) Some ROM size may be reduced, since some functions can be shared among key generation, encryption and decryption.
(*3) The figure includes key generation and one block encryption. This is achieved by using the on-the-fly subkey generation.
(*4) The figure includes stack area, and excludes text area and key area.
(*5) The figure includes stack area, text area and key area.
(*6) The figure shows the size of round keys.
(*7) Intel 8051 (12MHz; 1cycle=12 oscillator periods) simulator on Unix.
(*8) Z80 (5MHz) simulator on Windows.
(*9) Hitachi H8/3113 (5MHz; 1cycle=2 oscillator periods) on Hitachi's E6000 Emulator.
(*10) Motorola 6805 series MC68HC705B16 (2.1MHz) on Motorola's In-Circuit Simulator Kits.
(*11) Motorola 6805 series MC68HC908AB32 (8MHz) on Motorola's In-Circuit Simulator Kits.
(*12) Mitsubishi 32-bit microcomputer M32Rx/D (100MHz) on MSA2310 evaluation board.

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

Table 3: Camellia Hardware Performance (updated on Aug.31, 2001)
Architecture

Unrolled Type 1

ASIC
Loop

Type 2Type 2Type 3Loop
FPGA

Type 2Unrolled Type 1
Pipeline Type 4

Design Library

Mitsubishi 0.35µm
Mitsubishi 0.18µm
Mitsubishi 0.18µm
Mitsubishi 0.35µm
Mitsubishi 0.35µm
Mitsubishi 0.18µm
Mitsubishi 0.18µm
Mitsubishi 0.18µm
Mitsubishi 0.18µm
Mitsubishi 0.18µm
Mitsubishi 0.18µm
0.25µm
0.25µmXilinx XC4000XL
Xilinx XC4000XL
Xilinx VirtexE
Xilinx VirtexE
Xilinx VirtexE
Xilinx VirtexE
Xilinx VirtexE

Speed

Key
size

Key setup[bits][nsec]

128
128
128
128
128
128
128
128
128
128
128
256
256
128
128
128
128
128
128
128

24.36
40.00
45.96
110.20117.04144.88
25.92
28.20
23.20
137.2412.96‑‑
362.83‑135.03126.00127.04
97.70
83.25

Max.
delay(*1)[nsec]

109.35
40.00
45.96
27.67
28.73
36.22
6.48
7.05
5.80
34.31
3.24
5.46
11.51
78.82
50.00
30.56
28.80
26.80
318.5018.96

Area Size(*2)

LatencyThroughput[cycles][Mbps][unit]

1,170.55
3,200.00
2,785.00
220.28212.16168.28940.62864.571,050.90
177.65
1,881.25
837.00397.0077.34
122.01
199.46211.90227.42401.896,749.99

272.82355.10244.90
11.35
9.66
8.51
27.46
21.45
11.87
8.12
44.30
39.35
23.12
1,296
874
1,816
1,816
1,780
9,426
9,692

1
1
1
21
21
21
21
21
21
21
21
‑
‑
21
21
21
21
21
1
20

Unit

Kgate

Kgate

CLB

Slice

Total

Key
expan.(*3)[unit]

55.91
‑
‑
4.98
5.75
‑
‑
‑
‑
‑
‑
22.76
13.30
‑
‑
‑
‑
‑
‑
‑

Efficiency
Enc./Dec.

(*4)[unit]

216.91
‑
‑
6.37
3.91
‑
‑
‑
‑
‑
‑
16.33
9.67
‑
‑
‑
‑
‑
‑
‑

Throughput/Area

Reference[Kbps/unit]

4.29
9.01
11.37
19.41
21.96
19.77
34.25
40.31
88.52
21.87
42.47
21.27
17.17
59.68
139.60109.83116.69127.7642.64
696.45[AIK+00b]
Not publishedNot published[AIK+00a][AIK+00b]
Not publishedNot publishedNot publishedNot publishedNot publishedNot published
[C01]
[C01]
[AIK+00b][AIK+00b][ISKM01][ISKM01][ISKM01][ISKM01][ISKM01](*1) Critical path of data encryption (or decryption)(*2) The figure includes key scheduling logic, encryption/decryption logic, data selector (if necessary), output register, subkey register and buffers for fan-out adjustment.
(*3) The figure includes subkey register.
(*4) The figure includes output register and data selector (if necessary).

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

4 Software Implementation TechniquesThis section describes how to implement Camellia eciently in software. In most cases, animplementation can be divided into two parts: setup including key schedule and data randomization, that is, encryption or decryption. We rst describe how to optimize the setup code, andthen describe how to optimize the data randomization code.
This section describes speci c techniques for 8-, 32-, or 64-bit processors. However, a technique for 8-bit processors may be applicable to 32- or 64-bit processors and a technique for 32-bit
processors may be applicable to 64-bit processors. Other word sizes may need to be considered.
We assume that you rst implement Camellia using the speci cation as it is. This section
will optimize the resulting code.
Note that in this section \word" means the natural size of the target processor. For example,
the words of IA-32 without MMX technology, IA-32 with MMX technology and Alpha are 32-,64-, and 64-bits long respectively.
4.1 Setup4.1.1 Store All Subkeys

Store all subkeys into memory once you generate them if you have sucient memory, and use
the stored subkeys for data randomization.

4.1.2 Subkey Generation Order

You do not have to compute subkeys in order. For example, when you compute subkeys for a
128-bit key, rst compute the subkeys that only depend on KL , and then compute subkeys that
only depend on KA . This reduces the number of registers or memory for storing KA .

4.1.3 XOR Cancellation Property in Key Schedule

The key schedule of Camellia is based on the Feistel structure. Between the 2nd round and the
3rd round, KL is XORed to an intermediate value. This structure causes cancellations of KL .
More precisely, the input of the 3rd round can be computed by the following equations.
((right half) = F (KLL ; 61 )for 128-bit keys
(lefthalf) = F (KLR 8 (right half); 62)((right half) = KRR 8 F (KLL 8 KRL ; 61)(left half) = KRL 8 F (KLR 8 (right half); 62) for 192- and 256-bit keys
Using the above equations, we can eliminate 3 and 2 XORs in L for 128- and 192/256-bit keys,
respectively, compared to the straightforward implementation of the speci cation.

4.1.4 Rotation Bits for KL, KR , KA, and KB

You do not need to keep KL , KR , KA , and KB , but you should keep their rotated values whengenerating subkeys. You can generate subkeys by rotating the kept values by a sum of integral
multiples of 16 6 1 bits.
11

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

4.1.5 kl5 and kl6 Generation from k11 and k12

For 192- and 256- bit keys, you can use word-oriented rotation to generate (kl5 ; kl6 ) from(k11; k12 ), since (kl5 ; kl6 ) equals (k11; k12 )<<<32 . This saves a few instructions compared to general rotation.

4.1.6 On-the- y Subkey Generation

You can generate subkeys on-the- y . All subkeys are one of the rotated values of KL , KR ,KA , and KB . Thus, you rst generate KL , KR , KA , and KB , and then rotate them to get thesubkeys. Refer to Section 4.1.4 for the rotated numbers of bits for KL , KR , KA , and KB .

4.1.7 128-bit key and 192/256-bit key

If your code does not need to use key sizes larger than 128 bits, you do not need to generate

KB . That is, you can omit the computations for the last two F -functions.

4.1.8 How to Rotate an Element in Q
8-bit processor. As stated in Section 4.1.4, the amount of rotation in bits is a sum of integral
multiples of 16 6 1. Thus, you can rotate an element in Q by 16 6 1 bits by rotating 1-bit leftor right followed by a 2-byte move.

32-bit processor. Consider the use of a double precision shift instruction: shrd or shld if
you are programming on IA-32.

4.1.9 F -function

Key schedule includes F -functions, but the main usage of the F -function is for data randomization. Refer to Section 4.2.

4.1.10 Keyed Functions

Camellia has three keyed functions: bitwise XOR, bitwise OR, and bitwise AND. Consider theuse of a self-modifying code, if possible.
4.2 Data Randomization

4.2.1 Endian Conversion

Camellia prefers big endian. Thus, the code for little endian processors needs additional codefor endian conversions.
The most straightforward implementation converts the endian when loading a register frommemory and storing a register to memory. Only F L- and F L01 -functions are endian dependent.
More precisely, only the 1-bit rotation in F L- or F L01-function is endian dependent. This meansthat you can convert endians just before or just after the 1-bit rotation with the appropriate
12Copyright NTT and Mitsubishi Electric Corporation 2000-2001
subkey generation scheme. A combination of computing endian conversion and 1-bit rotation
may increase the performance of Camellia. Details are described in Section 4.2.2.
Some processors have a special instruction for endian conversion. For example, IA-32 (after
80486) has bswap instruction. Use these instructions. However, do not use the byte swap
technique described in [C98, Appendix A]. The technique reduces the code size, but it is not
fast, since the memory load and store instruction incurs long latency.
As described above, the endian problem only e ects the 1-bit rotation of a 32-bit word.
Thus, we do not need full 64-bit word endian conversion.
The following are general methods to realize endian conversion for 32-bit register x. In
the following techniques, you can use either [ or 8 instead of + in the equations, and you canswitch the computational order between shifts including rotations and ANDs with an appropriate
conversion of masked constants.

Straightforward.

(x 24) + ((x \ 0xff00) 8 ) + ((x 8) \ 0xff00) + (x 24 )The technique has high parallelism.
x

Minimum operations without rotation.
(x 16) + (x 16 )((x \ 0xff00ff) 8 ) + ((x 8) \ 0xff00ff)xx

Using rotations.
x((x \ 0xff00ff)>>>8 ) + ((x<<<8 ) \ 0xff00ff)

Using SSE. New Intel Pentium family processors including Pentium III have a very e ective
instruction for reordering data, which is called pshufw [I99]. 5 instructions including pshufw
are sucient to convert endian for 64-bit data.
4.2.2 1-bit Rotation in Little Endian Interpretation

As described in Section 4.2.1, we do not need endian conversion when loading and storing texts
if we can eciently implement 1-bit rotation in F L- and F L01-functions.
Assuming x to be a 32-bit register that contains little endian data to be rotated by 1-bit, we
can compute 1-bit rotation by the following equation.
x ((2x) \ 0xfefefefe) + ((x>>>15 ) \ 0xfefefefe)(1)
Of course, this technique requires an appropriate changes to subkey setup and other functions.
Note that + in Equation (1) can be replaced with [ or 8, and computing 2x can be done by1 , <<<1 or addition with x itself, and you can switch the computational order between shifts
including rotations and ANDs with an appropriate conversion of masked constants.
Con rm whether your processor has ANDNOT instruction, such as pandn in IA-32 and bic
in Alpha. In this case, you do not need to prepare the constant, 0xfefefefe.
13

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

4.2.3 Whitening

The key additions kw2 and kw4 can be combined into other keyed operations using the following
equations.
(x 8 k) 8 y = (x 8 y) 8 k;
(x 8 k) 8 l = x 8 (k 8 l);(x 8 k) \ l = (x \ l) 8 (k \ l);(x 8 k)<<<1 = (x<<<1) 8 (k<<<1);(x 8 k) [ l = (x [ l) 8 (k \ l);(2)where x, y, k, l are bit strings. Adjust subkeys at setup to eliminate 2 XORs in L.

4.2.4 Key XOR

Using Equations (2), you can move key XORs to any place if the movement does not go throughthe S -function. For example, changing F -function computation P (S (X 8 k)) to P (S (X )) 8 k0
may improve instruction scheduling.

4.2.5 S-function

s1 is de ned by the arithmetics in GF(28 ). However, do not compute GF(28 ) arithmetics; instead

precompute and hard-code a table in your program, see Table 4 in the speci cation.
We strongly suggest that you also precompute and hard-code s2 , s3, and s4 tables in addition
to s1 , if you have sucient memory and 8-bit rotation is expensive. If you do not have sucient
memory, the data of s2, s3 , and s4 can be generated from the table for s1 using one rotation(See Section 4.5 in the speci cation).
If you have sucient memory, and cost of table lookup is heavy, as is true for the current Javavirtual machines, consider the use of a two s-box combined table, for example (s1 (y1); s2 (y2)).

4.2.6 P -function
32-bit processor. Let (ZL; ZR ) = ((z1; z2; z3; z4); (z5; z6; z7; z8)) be the input of P -functionand (ZL0 ; ZR0 ) = ((z10 ; z20 ; z30 ; z40 ); (z50 ; z60 ; z70 ; z80 )) be the output of P -function.
From Figure 5 in the speci cation, you can see that P -function can be computed as follows.
ZL
ZR
ZL
ZR
ZL0
ZR0

ZL 8 (ZR <<<8 )ZR 8 (ZL <<<16 )ZL 8 (ZR >>>8 )ZR 8 (ZL >>>8 )
ZR
ZL

14

Copyright NTT and Mitsubishi Electric Corporation 2000-2001
The critical path of this computation is long. We can modify the computation as follows.
ZR
ZL 8 ZR ZR
ZL >>>8ZR
ZL 8 ZR ZR
ZL <<<8
ZR
ZR
ZR0

ZL
ZL
ZL
ZL
ZL0

ZR <<<8
ZR <<<8
ZR 8 ZLZR <<<16
ZR 8 ZLZL

The critical path of the above computation is decreased. It seems that the technique requires one
additional rotation, however, you can probably combine the rst step of the above computationand S -function without any additional cost.

8-bit processor (orthogonal mnemonics). If the instruction in your processor can XOR
any combination of registers and has sucient registers, you can compute P -function by using
just 16 XORs using Figure 5 in the speci cation.
8-bit processor (accumulator based). If your processor is accumulator based, minimizing

the number of XORs is not always a good idea, since the computation may require register loadfrom memory and store into memory many times. The following computation is optimized foran accumulator based processor.
z80
z40
z70
z30
z60
z20
z50
z10

z1 8 z4 8 z5 8 z6 8 z7
z80 8 z1 8 z2 8 z3z40 8 z2 8 z7 8 z8
z70 8 z1 8 z2 8 z4
z30 8 z1 8 z6 8 z7
z60 8 z1 8 z3 8 z4
z20 8 z4 8 z5 8 z6
z50 8 z2 8 z3 8 z4

When indexing zi0 costs many operations, the following is useful.

z10
z20
z30
z40
z50
z60
z70
z80

z1 8 z2 8 z3 8 z4 8 z5 8 z6 8 z7 8 z8
 8 z 2 8 z5
 8 z 3 8 z6
 8 z 4 8 z7
 8 z 1 8 z8
 8 z 3 8 z4 8 z5
 8 z 1 8 z4 8 z6
 8 z 1 8 z2 8 z7
 8 z 2 8 z3 8 z815

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

4.2.7 Substitution and Permutation

This section describes how to eciently compute P  S compared to independently computing

S and P .

64-bit processor. If your processor has a suciently large rst level cache, use the techniquedescribed in [RDP+ 96]. The technique prepares the following tables de ned by Equations (3).
SP1 (y1 )SP2 (y2 )SP3 (y3 )SP4 (y4 )
SP5 (y5 )
SP6 (y6 )SP7 (y7 )
SP8 (y8 )= (s1(y1 ); s1 (y1); s1 (y1);0; s1 (y1 );0;0; s1(y1 ))= ( 0; s2 (y2); s2 (y2); s2(y2 ); s2 (y2 ); s2 (y2);0;0)= (s3(y3 );0; s3 (y3); s3(y3 );0; s3 (y3); s3(y3 );0)= (s4(y4 ); s4 (y4);0; s4(y4 );0;0; s4(y4 ); s4(y4 ))= ( 0; s2 (y5); s2 (y5); s2(y5 );0; s2 (y5); s2(y5 ); s2(y5 ))= (s3(y6 );0; s3 (y6); s3(y6 ); s3 (y6 );0; s3(y6 ); s3(y6 ))= (s4(y7 ); s4 (y7);0; s4(y7 ); s4 (y7 ); s4 (y7);0; s4(y7 ))= (s1(y8 ); s1 (y8); s1 (y8);0; s1 (y8 ); s1 (y8); s1(y8 );0)
Next, compute the following equation:
8
M(z10 ; z20 ; z30 ; z40 ; z50 ; z60 ; z70 ; z80 )SPi (yi )

(3)

i=1

This technique requires the following operations.
# of table lookups 8# of XORs
7
Size of table (KB) 16
If the rst cache of the target processor is moderately large, replace a few of the tablesde ned by Equations (3) with the tables below.
SP (y )SP (y )SP (y )SP (y )= (s1 (y); s1(y); s1(y); s1(y ); s1(y ); s1 (y); s1 (y); s1 (y))= (s2 (y); s2(y); s2(y); s2(y ); s2(y ); s2 (y); s2 (y); s2 (y))= (s3 (y); s3(y); s3(y); s3(y ); s3(y ); s3 (y); s3 (y); s3 (y))= (s4 (y); s4(y); s4(y); s4(y ); s4(y ); s4 (y); s4 (y); s4 (y))(4)

Then, mask the necessary byte positions. This technique requires the following operations if
you use just tables of Equations (4).
# of table lookups 8# of XORs
7# of ANDs
8
Size of table (KB) 8
When implementing this technique on Alpha architecture [C98], and if the number of registers
is insucient for storing constants for masking operation, use zap or zapnot instructions.
16

Copyright NTT and Mitsubishi Electric Corporation 2000-2001
If your processor can eciently copy half bits of a register to the other half, for example, punpckldq/punpckhdq or pshufw instructions in IA-32 [I99] which are realized after Pentium with MMX technology and Pentium III, respectively, prepare SP1, SP2 , SP3, and SP4
de ned in Equations (3). Then, compute the following equation:(z10 ; z20 ; z30 ; z40 ; z50 ; z60 ; z70 ; z80 )SP1 (y1 ) 8 SP2 (y2 ) 8 SP3 (y3 ) 8 SP4 (y4 ) 8  (SP1 (y8 ) 8 SP2 (y5 ) 8 SP3 (y6 ) 8 SP4 (y7 ));where  denotes the operation that copies the rst 4 bytes to the last 4 bytes. This techniquerequires the following operations.
# of table lookups 8# of XORs
7# of  s1
Size of table (KB) 8

32-bit processor. [AU00] shows ecient implementations of Camellia-type substitution andpermutation networks. One of the techniques prepares the following tables de ned by Equations (5):SP1110 (y) = (s1 (y); s1 (y ); s1 (y );0)SP0222 (y) = ( 0; s2 (y ); s2 (y ); s2 (y))(5)
SP3033 (y) = (s3 (y);0; s3(y ); s3 (y))
SP4404 (y) = (s4 (y); s4 (y );0; s4 (y))
Then, compute as follows:
D
U
0
0
0
(z1 ; z2 ; z3; z40 )(z50 ; z60 ; z70 ; z80 )SP1110 (y8 ) 8 SP0222 (y5 ) 8 SP3033 (y6 ) 8 SP4404 (y7 )SP1110 (y1 ) 8 SP0222 (y2 ) 8 SP3033 (y3 ) 8 SP4404 (y4 )D8U(z10 ; z20 ; z30 ; z40 ) 8 (U>>>8)

This technique requires the following operations.
# of table lookups 8# of XORs
8# of rotations
1
Size of table (KB) 4[AU00] also shows an implementation that is suitable for a processor in which rotation is very
costly. The technique prepares the following tables in addition to tables de ned by Equations (5):SP1001 (y)SP2200 (y)SP0330 (y)SP0044 (y)= (s1(y); 0; 0; s1 (y))= (s2(y); s2(y ); 0; 0)= ( 0; s3(y ); s3(y ); 0)= ( 0; 0; s4(y ); s4 (y))
17Copyright NTT and Mitsubishi Electric Corporation 2000-2001
Then, compute as follows:D000(z1; z2; z3 ; z40 )(z 0 ; z0 ; z0 ; z0 )
5

6

7

8

SP1110 (y8 ) 8 SP0222 (y5 ) 8 SP3033 (y6 ) 8 SP4404 (y7 )D 8 SP1110 (y1 ) 8 SP0222 (y2 ) 8 SP3033 (y3 ) 8 SP4404 (y4 )D 8 SP1001 (y1 ) 8 SP2200 (y2 ) 8 SP0330 (y3 ) 8 SP0044 (y4 )This technique requires the following operations.
# of table lookups 12# of XORs
11
Size of table (KB) 8

4.2.8 Making Indices for s-box

You can make an index for s-box by simply using shifts and ANDs. However, several processors
have special instructions for making an index, for example, movzx in IA-32 [I99] and extbl in
Alpha [C98].
movzx is a fast operation in P6, but it can be used only for the two least signi cant bytes.
A straightforward implementation uses eax, ebx, ecx, and edx registers for storing (Lr ; Rr ),and 2 rotations are used for making indices; 2 rotations are used for recovering byte order inthe registers every round. However, you can remove 2 rotations for recovering byte order every
round if you prepare rotated tables. Note that the byte order in registers returns to a naturalorder every 4 rounds.
4.3 General Guidelines

This section describes general guidelines. The guidelines are useful to optimize Camellia as wellas other block ciphers. Please refer to the optimization manuals for each processor.

Avoid misaligned data accesses. Almost all processors penalize misaligned data access.

Align data to the word boundary.
Avoid partial data accesses. Most processors have a function to access a smaller part thanword size. However, this function may cause a penalty. Do not access partial data, even
if you do not need full size of word and you have sucient memory.
Be careful of the size of the cache. If the program or its data exceeds the size of the cache,the speed of the program will signi cantly decrease. Loop unrolling and table expansion
are good techniques to speed up the program, but do not exceed the size of the cache.
Use intrinsic functions. Several compilers support intrinsic functions. For example, when
you use Microsoft Visual C++ version 6 compiler on IA-32, and declare \#pragma
intrinsic( lrotl)" and use \ lrotl", the compiler generates rotation instructions inassembly language. Refer to the manual of the compiler that you use for details.
Measuring precise speeds is dicult. The running time of your code depends on manyfactors: cache hit misses, OS interrupts, and so on. Furthermore, the cryptographic
18

Copyright NTT and Mitsubishi Electric Corporation 2000-2001
properties, for example, the number of blocks to be encrypted, also e ect the runningtime.
A few processors have an instruction to get the time stamp. For example, IA-32 (after
Pentium) has rdtsc [I99] and Alpha has rpcc [C98]. It is a good idea to use the timestamp counter for measuring speeds, but you should not directly apply these instructions
to out-of-order architectures such as P6 and EV6.
If you want to measure speed precisely, consult good guidebooks. For example, if you
use Pentium family processors, refer to [F00].

19

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

5 Hardware Evaluations
In Section 3, we showed evaluation results of hardware implementations (ASIC, FPGA) of
Camellia. In this Section, we describe the design policies of the four types of logic evaluated in
Section 3. The details of each type are described below.
5.1 Type 1: Fast Implementation-1 (Fully loop unrolled architecture)

Plaintext / Ciphertext
Encryption
andDecryption
Logic

OutputRegisters

Subkey Registers

Critical Path of Data Encryption(or Decryption)

In Type 1, we evaluate the hardware implementation (ASIC and FPGA) where the goal is toachieve the fastest encryption and decryption speed with no consideration of logic size. Figure 1
outlines the Type 1 logic. Table 6 shows the basic Type 1 components.

Key Expansion
Logic

Key

Critical Path of Key Expansion

Ciphertext / Plaintext

Figure 1: Outline of Type 1 (ASIC, FPGA)
Table 6: The basic Type 1 components
Encryption anddecryption logic
Output register
Key expansion logic
Subkey register

Data randomizing logic for encryption and decryption,
which consists of combinational logic.
Register for the encryption (decryption) data.
Logic in which subkeys are generated from key,which consists of combinational logic.
Register for the output data of key expansion logic.

The design policies of these basic components are listed below.
1. \Encryption and decryption logic" and \Key expansion logic"(a) Loop architecture is not introduced.
20

Copyright NTT and Mitsubishi Electric Corporation 2000-2001(b) Pipeline architecture is not introduced.
(c) Substitution tables (s-boxes) are designed by logic synthesis tool.
2. \Output register" and \Subkey register"(a) The size of Output register is one block (=128 bits).
(b) The size of Subkey register is the total length of all subkeys in the algorithm.
Under the above design policies, we evaluated Camellia on ASIC and FPGA devices. The
results are summarized in Table 3 in Section 3. \Throughput" is de ned as follows:size(128 [bits])
Throughput[b=s] = Critical path ofBlockdata encryption(decryption)[sec] :5.2 Type 2: Small Implementation-1 (Loop architecture)

Key

Critical Path of Data Encryption(or Decryption)

Plaintext / Ciphertext
Key Schedule Logic
anda part of
Key Expansion Logic

Data Selector

One Round of
Encryption and Decryption
Logicwith sharing a part of(or all of) Key Expansion Logic

Subkey Registers

Critical Path of Key Expansion

In Type 2, we evaluate the hardware implementations on ASICs and FPGAs with the goal ofachieving the smallest logic in encryption (and decryption). Figure 2 outlines the Type 2 logic.
Table 7 shows the basic Type 2 components.

Output Registers

Ciphertext / Plaintext

Figure 2: Outline of Type 2 (ASIC, FPGA)
The design policies of these basic components are as follows.
1. \Encryption and decryption logic" and \Key scheduling logic"(a) Loop architecture is introduced (which consists of one round operation).
(b) Pipeline architecture is not introduced.
21

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

Table 7: The basic Type 2 components
Encryption anddecryption logic

Data randomizing logic for one round operation of encryption anddecryption, which includes (a part of) key expansion logic, andconsists of combinational logics.
Output register
Register for the output (and intermediate) data.
Data selector
Selector which selects either encryption/decryption data or output data.
Key scheduling logic Logic in which subkeys are generated using (a part of)
key expansion logic in encryption and decryption logic andconsists of combinational logics.
Subkey register
Register for the output data of key scheduling logic.
(c) Substitution tables (s-boxes) are optimized by hand.
(d) Key scheduling logic consists (a part of) key expansion logic and control logic.
2. \Output register", \Subkey register" and \Data selector"(a) The size of Output register is one block (=128 bits).
(b) The size of Subkey register is that of the subkeys used in Encryption and decryption
logic.
(c) Data selector is 2-1 selector, whose size is one block (=128 bits).
Under the above design policies, we evaluated Camellia on ASICs and FPGAs. The results
are summarized in Table 3 in Section 3. \Throughput" is de ned as follows:size(128 [bits])
Throughput[b=s] = Critical path of dataBlockencryption(decryption)[sec] 2 latency :5.3 Type 3: Small Implementation-2 (Special Case for FPGA, Loop architecture)

In Type 3, we evaluated the hardware implementation (FPGA) as a special case of Type 2.
In Type 3, we assume that all subkeys are given and are loaded into FPGA internal memory.
Figure 3 outlines the Type 3 logic. Table 8 shows the basic Type 3 components.
The design policies of these basic components are as follows.
1. \Encryption and decryption logic"(a) Loop architecture is introduced (which consists of one round operation).
(b) Pipeline architecture is not introduced.
(c) Substitution tables (s-boxes) are optimized by hand.
2. \Output register", \Subkey memory" and \Data selector"
22

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

Data Selector

One Round of
Encryption
andDecryption
Logic

Subkey Memory

Critical Path of Data Encryption(or Decryption)

Plaintext / Ciphertext

Subkeys

Output Registers

Ciphertext / Plaintext

Figure 3: Outline of Type 3 (FPGA)

Table 8: The basic Type 3 components
Encryption and Data randomizing logic for one round operation of encryption anddecryption logic decryption, which includes (a part of) key expansion logic, andconsists of combinational logic.
Output register Register for the output (and intermediate) data.
Data selector Selector which selects either encryption (decryption) data or output data.
Subkey memory Memory for the subkeys loaded from outside.

23

Copyright NTT and Mitsubishi Electric Corporation 2000-2001(a) The size of Output register is one block (=128 bits).
(b) The size of Subkey memory is the length of all subkeys in the algorithm.
(c) Data selector is 2-1 selector whose size is one block (=128 bits).
Under the above design policies, we evaluated Camellia on an FPGA. The results are summarized in Table 3. \Throughput" is de ned as follows:size(128 [bits])
Throughput[b=s] = Critical path of dataBlockencryption(decryption)[sec] 2 latency :5.4 Type 4: Fast Implementation-2 (Pipeline architecture)

In Type 4, we evaluate the hardware implementation (FPGA) where the goal is to achieve
the fastest encryption and decryption speed with no consideration of logic size. (The pipelinearchitecture cannot realize any feedback modes, such as CBC, CFB, and OFB). Figure 4 outlines
the Type 4 logic. Table 9 shows the basic Type 4 components.
Plaintext / Ciphertext

Encryption and
Decryption Logic
1 round

Subkey Registers

Stage 1

Critical Path of
Pipeline Stage

Register 1

Stage n-1

1 round
Register n-1

Stage nKey Expansion
Logic

1 round
Register nCritical Path of Key Expansion

Ciphertext / Plaintext

Figure 4: Outline of Type 4 (FPGA)
The design policies of these basic components are as follows.
1. \Encryption and decryption logic" and \Key expansion logic"(a) Loop architecture is not introduced.
(b) Pipeline architecture is introduced.
(c) Substitution tables (s-boxes) are designed by logic synthesis tool.
(d) The size of Registers (1  n) is one block (= 128 bits).
24

Key

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

Table 9: The basic Type 4 components
Encryption anddecryption logic

Data randomizing logic for encryption and decryption,
which consists of combinational logic, andRegisters (1  n) for the output and intermediate data.
Key Expansion logic Combinational logic in which subkeys are generated from the key.
Subkey register
Register for the output data from key expansion logic.
2. \Subkey register"(a) The size of Subkey register is the total length of all subkeys in the algorithm.
Under the above design policies, we evaluated Camellia on an FPGA devices. The results
are summarized in Table 3. \Throughput" is de ned as follows:
size (128 [bits])
Throughput[b=s] = CriticalBlockpath of Pipeline Stage [sec] :25

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

6 Security
6.1 Di erential and Linear Cryptanalysis

The most well-known and powerful approaches to attacking many block ciphers are di erential
cryptanalysis, proposed by Biham and Shamir [BS93], and linear cryptanalysis, introduced by
Matsui [M94]. There are several methods of evaluating security against these attacks, where
there is a kind of \duality" relation between them [M95, CV95]: in other words, the security
against both attacks can be evaluated in similar ways.
It is known that the upper bounds of di erential/linear characteristic probabilities can, forseveral block ciphers, be estimated using the minimum numbers of di erential/linear active
s-boxes in some consecutive rounds. Kanda [K00] shows the minimum numbers of di erential/linear active s-boxes for Feistel ciphers with conservative SPN (S-P) round function. Hereafter, we assume that linear transformation P is bijective.

De nition 1 The branch number B of linear transformation P is de ned by
B = min(wH (x) + wH (P (x)));x6=0

where wH (x) denotes the bytewise Hamming weight of x.

De nition 2 A di erential active s-box is de ned as an s-box given a non-zero input di erence.
A linear active s-box is de ned as an s-box given a non-zero output mask value.

Theorem 1 The minimum number of di erential/linear active s-boxes in any eight consecutive

rounds is equal or larger than 2B + 1.

De nition 3 For any given 1x, 1y, 0x, 0y 2 GF(2m), the di erential/linear probabilities ofsi -box: GF(2m ) ! GF(2m ) are de ned as:#fx 2 GF(2 )jsi (x) 8 si (x 8 1x) = 1yg
Pr
[
s
(
x
)
8 si (x 8 1x) = 1y ] =
i
x
2m
m
Pr
[x 1 0x = si (x) 1 0y] = #fx 2 GF(2 )jx2m1 0x = si (x) 1 0y g
x
De nition 4 Let ps and qs be the maximum di erential/linear probabilities of all s-boxes
fs1 ; s2 ; : : :g.
m

ps = max max Pr[s (x) 8 si (x 8 1x) = 1y ]i 1x=
6 0;1y x i
qs = max max (2 Pr[x 1 0x = si (x) 1 0y ] 0 1)2i 0y=
6 0;0x x

Theorem 2 Let D and L be the minimum numbers of total di erential/linear active s-boxes.
Then, the maximum di erential/linear characteristic probabilities are bounded by pDs and qsL ,respectively.
26

Copyright NTT and Mitsubishi Electric Corporation 2000-2001
With the above-mentioned techniques, we prove that Camellia o ers immunity to these
attacks by showing the upper bounds of maximum di erential/linear characteristic probabilities,
since Camellia is a Feistel cipher whose round function uses the S-P round function.
In the case of Camellia, the maximum di erential/linear probabilities of the s-boxes are
ps = qs = 206 :The branch number of the linear transformation (P -function) is 5, i.e.
B = 5:

Letting p, q be the maximum di erential/linear characteristic probabilities of Camellia reduced
to 16-round without F L- and F L01-functions, respectively, we haveB+1) = (206 )22 = 20132 and q  q 2(2B+1) = (206 )22 = 20132p  p2(2ssfrom Theorems 1 and 2. Both probabilities are below the security threshold of 128-bit blockciphers: 20128 . It follows that there is no e ective di erential characteristic or linear characteristic for Camellia reduced to more than 15 rounds without F L- and F L01 -functions. Since
F L- and F L01 -functions are linear for any xed key, they do not make the average di erential/linear probabilities of the cipher higher. Hence, it is proven that Camellia o ers enoughsecurity against di erential and linear attacks.
Note that the result above are based on Theorems 1 and 2. Both theorems deal with generalcases of Feistel ciphers with SPN round function, so we expect that Camellia is actually moresecure than shown by the result above. As supporting evidence, we counted the number of active
s-boxes of Camellia with reduced rounds. The counting algorithm is similar to that describedin [M99] except following three items.
 Prepare the table for the number of active s-boxes instead of transition probability table.
 Count the number of active s-boxes instead of computing transition probability.
 F L- and F L01 -functions set all elements to the minimum number of active s-boxes in thetable. This means that the algorithm gives consideration to existence of weak subkeys inserted to F L- and F L01 -functions, since there may be some possibility of connecting every
later di erential/linear characteristic with the previous one with the highest probability,
which is equivalent to the minimum number of active s-boxes.
As a result, we con rmed that 12-round Camellia with F L- and F L-functions has no di erential/linear characteristic with probability higher than 20128 (see Tables 10 and 11).
6.2 Truncated Di erential Cryptanalysis

The attacks using truncated di erentials were introduced by Knudsen [K95]. He de ned themas di erentials where only a part of the di erence can be predicted. The notion of truncateddi erentials introduced by him is wide, but with a byte-oriented cipher it is natural to study
bytewise di erentials as truncated di erentials [MT99].
27

Copyright NTT and Mitsubishi Electric Corporation 2000-2001# of rounds
Estimation basedon Th. 1 and 2
Camellia

1

2# of rounds
Estimation basedon Th. 1 and 2
Camellia

1

2

3

4

5

12
2096
(2) (5)
(7)
(11)
(16)
0
6
0
12
0
42
0
54
0
66
0
72
0
72
0
78
0
108
0
120
1 2 2 2 2 2 2 2
2 2
2
20132
(0) (1) (2) (7) (9) (11) (12) (12) (13) (18) (20) (22)01without F L/F L - 1 206 2012 2042 2054 2066 2078 2090 20108 20126 20132
functions(0) (1) (2) (7) (9) (11) (13) (15) (18) (21) (22)Note: The numbers in brackets are the number of active s-boxes.
Table 10: Upper bounds of di erential characteristic probability of Camellia
3452012 2030

6

7

6

7

2042

8

9

10

11

8

9

10

11

2066

12
2096
(2) (5)
(7)
(11)
(16)
1 206 2012 2036 2054 2066 2072 2072 2078 20102 20120 20132(0) (1) (2) (6) (9) (11) (12) (12) (13) (17) (20) (22)without F L/F L01- 1 206 2012 2036 2054 2066 2078 2084 20108 20120 20132
functions(0) (1) (2) (6) (9) (11) (13) (14) (18) (20) (22)Note: The numbers in brackets are the number of active s-boxes.
Table 11: Upper bounds of linear characteristic probability of Camellia
2012 2030

2042

2066

The maximum di erential probability is considered to provide the strict evaluation of security against di erential cryptanalysis, but computing its value is impossible in general, since adi erential is a set of all di erential characteristics with the same input di erence and the same
output di erence for a Markov cipher [LMM91]. On the other hand, a truncated di erential
can be regarded as a subset of the di erential characteristics which are exploitable in cryptanalysis. For some ciphers, e.g., byte-oriented ciphers, the probability of truncated di erential
can be computed easily and correctly, and it gives a more strict evaluation than the maximum
di erential characteristic probability.
A truncated di erential cryptanalysis of reduced-round variants of E2 was presented by Matsui and Tokita at FSE'99 [MT99]. Their analysis was based on the \byte characteristic," wherethe values to the di erence in a byte are distinguished between non-zero and zero. They found a
7-round byte characteristic, which leads to a possible attack on an 8-round variant of E2 without
IT -Function (the initial transformation) and F T -Function (the nal transformation). The best
attack of E2 shown in [MSAK00] breaks an 8-round variant of E2 with either IT -Function or
F T -Function using 294 chosen plaintexts. In [MSAK00] we also show the attack which distinguishes a 7-round variant of E2 with IT - and F T -Functions from a random permutation using
291 chosen plaintexts.
Camellia is a byte-oriented cipher similar to E2, and it is important to evaluate its security
against truncated di erential cryptanalysis. We searched for truncated di erentials using an
28

Copyright NTT and Mitsubishi Electric Corporation 2000-2001
algorithm similar to the one described in [MT99, MSAK00]. The main di erence of the round
function between E2 and Camellia is the adoption of the 1-round SPN not the 2-round SPN,
i.e. S-P-S. In the search for truncated di erentials of E2, we used about 208 as the probabilityof di erence cancellation in byte at the XOR of Feistel network. However, the round functionof Camellia doesn't have the second s-boxes-layer, and the cancellation sometimes occurs withprobability 1. As a result, more than 10-round Camellia is indistinguishable from a random
permutation both with/without F L-/F L01 -function layers.
Recently, Sugita et al.'s paper on truncated and impossible di erential cryptanalysis ofCamellia (without F L-/F L01 -functions) was accepted for ASIACRYPT 2001 [SKI01]. They
claim that they found two non-trivial 9-round truncated di erentials (with the same input/output
di erential patterns), which lead to a possible attack of Camellia reduced to 11 rounds without
input/output whitenings and F L-/F L01-functions. However we think it is still open how manyrounds of Camellia can be attacked using the truncated di erentials.
6.3 Truncated Linear Cryptanalysis

We introduce a new cryptanalysis called truncated linear cryptanalysis.
Due to the duality between di erential and linear cryptanalysis, we can evaluate security
against truncated linear cryptanalysis by using a similar algorithm to that above. To put it
concretely, we can perform the search by replacing the matrix of P -function with the transposed matrix. As a result, more than 10-round Camellia is indistinguishable from a random
permutation without F L-/F L01 -function layers.
6.4 Cryptanalysis with Impossible Di erential

The impossible di erential means the di erential which holds with probability 0, or the di erential which never exists. Using such an impossible di erential, it is possible to narrow down thecandidates of the subkey. It is known that there is at least one 5-round impossible di erential
in any Feistel network with a bijective round function. Since Camellia has the Feistel network(with F L- and F L01 -functions inserted between every 6 rounds) and the round function is bijective, Camellia has 5-round impossible di erentials. Additionally as a recent result, Sugita et al.
found a 7-round impossible di erential for Camellia (without F L-/F L01 -functions) [SKI01]. We
expect F L- and F L01 -functions make attacking Camellia using impossible di erentials dicult,since the functions change di erential paths depending on key values. In consequent, Camellia
with full rounds will not be broken by cryptanalysis using impossible di erentials.
6.5 Boomerang Attack

Boomerang attack [W99] requires 2 di erentials. Let the probability of the di erentials be p1
and pr. An boomerang attack that is superior than exhaustive key search requires
p1 pr  2064 :(6)

Using Table 10, there is no combination that satis es Inequality (6) for Camellia without F Land F L01-functions. The best boomerang probability for Camellia without F L- and F L01 functions reduced to 8-round is bounded by 2066 that is obtained by p1 = 2012 (3 rounds) and29

Copyright NTT and Mitsubishi Electric Corporation 2000-2001
pr = 2054 (5 rounds). Since attackable rounds for Camellia without F L- and F L01 -functions isbounded by much shorter than the speci cation of Camellia, 18, Camellia seems secure against
a boomerang attack.
6.6 Higher Order Di erential Attack

Higher order di erential attack is generally applicable to ciphers that can be represented as
Boolean polynomials of low degree. In the higher order di erential attack described in [JK97,
Theorem 1], the property that if the intermediate bits are represented by Boolean polynomialsof degree at lea st d, the (d + 1)-th order di erential of the Boolean polynomial becomes 0 is
utilized.

Degrees of Boolean polynomials of the s-boxes The functions ane (over GF(2)) equiv-

alent to the inversion function in GF(28) are adopted as the s-boxes. It is known that the degreeof the Boolean polynomial of every output bit of the inversion function in GF(28) is 7, but thedegree for the s-boxes of Camellia is not trivial, since the ane functions are added at the input
and output. We con rmed that the degree of the Boolean polynomial of every output bit of thes-boxes is 7 by nding Boolean polynomial for every output bit of the s-boxes.

Degrees of Boolean polynomials of the entire cipher It is expected that the degreeof an intermediate bit in the encryption process increases as the data pass through many sboxes, whose degree is 7. Therefore, we expect that higher order di erential attacks failagainst Camellia with full rounds. However, there is still room for further study on higher orderdi erential attacks of Camellia, because there are other approaches for higher order di erential
attacks. In [KK01] Kawabata et al. shows that Camellia with 10 rounds (without F L- andF L01 -functions) can be attacked faster than exhaustive search when the key size is 256-bit.
The attack is applicable to 9 rounds for 192-bit keys and 8 rounds for 128-bit keys. Although
the above attack is titled a \higher order di erential attack", the used approach is similar tothat used for the Square attack.
6.7 Square Attack

The Square attack was proposed as a dedicated attack on Square [DKR97] that exploits its
byte-oriented structure. It works well for other byte-oriented ciphers such as Rijndael, Hierocrypt
and Camellia. For our cryptanalysis of Camellia using the Square attack, see Sect. 6.8.
The approach of Square attack resembles that of higher order di erential attacks: onechooses a certain complete set of plaintexts, and after some rounds of the cipher, predicts a
key-independent property with probability one. The higher order di erential attack of Camellia
by Kawabata et al. [KK01] also takes this approach.
Another Square attack by He and Qing [HQ01] on 6 rounds of Camellia was accepted
for ICICS 2001. The claimed attack on 6 rounds of Camellia requires much more complexity than Kawabata and Kaneko's attack (the attack [HQ01] requires 2112 encryptions and theattack [KK01] 222=6 encryptions), but fewer plaintexts (the attack [HQ01] requires 13 2 28
plaintexts and the attack [KK01] 217 plaintexts).
30

Copyright NTT and Mitsubishi Electric Corporation 2000-2001
6.8 Interpolation Attack and Linear Sum Attack

The interpolation attack proposed in [JK97] is typically applicable to attacking ciphers that use
simple algebraic functions.
The principle of interpolation attack is that, roughly speaking, if the ciphertext is represented
as a polynomial or rational expression of the plaintext whose number of unknown coecientsis N , the polynomial or rational expression can be constructed using N pairs of plaintexts andciphertexts. Once the attacker constructs the polynomial or rational expression, he can encrypt
any plaintext into the corresponding ciphertext or decrypt any ciphertext into the corresponding
plaintext for the key without knowing the key. Since N determines the complexity and thenumber of pairs required for the attack, it is important to make N as large as possible. If N is
so large that it is impractical for the attackers to gather N plaintext-ciphertext pairs, the cipher
is secure against interpolation attack.
Linear sum attack [A00] is a generalization of the interpolation attack [JK97]. A practicalalgorithm that evaluates the security against linear sum attack was proposed in [A00]. We
searched for linear relations between any plaintext byte and any ciphertext byte over GF(28 )using the algorithm. Table 12 summarizes the results.

Table 12: Smallest number of unknown coecients for 128-, 192-, and 256-bit keys
whitening21 + round2r (r < 4) 1
whitening21 + round24
255
More rounds
256
Table 12 shows that Camellia is secure against linear sum attack including interpolation
attack. It also implies that Camellia is secure against Square attack [DKR97] followed by [A00,
Theorem 3].
6.9 No Equivalent Keys

Since the set of subkeys generated by the key schedule contain the original secret key, there
is no equivalent set of subkeys generated from distinct secret keys. Therefore, we expect that
there are no distinct secret keys both of which encrypt each of many plaintexts into the same
ciphertext.
6.10 Slide Attack

In [BW99, BW00] the slide attacks were introduced, based on earlier work in [B94, K93]. In
particular it was shown that iterated ciphers with identical round functions, that is, equal
structures and equal subkeys in the round functions, are susceptible to slide attacks.
In Camellia, F L- and F L01-functions are \inserted" between every 6 rounds of a Feistel
network to provide non-regularity across rounds. Moreover, from the viewpoint of the keyschedule, slide attacks seems to be very unlikely to succeed (See Section 6.11).
31

Copyright NTT and Mitsubishi Electric Corporation 2000-2001
6.11 Related-key Attack

We are convinced that the key schedule of Camellia makes related-key attacks [B94, KSW96] verydicult. In these attacks, an attacker must be able to get encryptions using several related keys.
If the relation between, say, two keys, is known then if the corresponding relations between thesubkeys can be predetermined, it might become possible to predict how the keys would encrypta pair of di erent plaintexts. However, since the subkeys depend on KA and KB , which are theresults of encryption of a secret key, and if an attacker wants to change the secret key, he can't
get KA and KB desired, and vice versa, these subkey relations will be very hard to control andpredict.
6.12 Statistical Tests

Most of statistical characteristics depends on the di erential attack and other cryptanalytic
attacks. For example, it is frequently discussed how many ciphertext bits are complemented
when one plaintext bit is complemented. According to the de nition and the property of thedi erential distribution table, the resistance to di erential attacks implies that the number ofcomplemented bits is about a half. Of course, we may nd a statistical weakness, if we haveenough computational resource. However, none in the world has an ecient resource to compute
such a statistical measure for a 128-bit block cipher.
Note that the following. It is frequently tested for a round function, because of the limited
computational resource. However, we think that it is not signi cant, because we can constructa cipher that does not show good statistical properties for the round function but shows good
statistical properties for a cipher and we can also construct a cipher that shows good statisticalproperties for the round function but does not show good statistical properties for a cipher.
In the CRYPTREC Report 2000 [C01], it is reported that the avalanche-e ect evaluation on
Camellia was held and that they found some points which deviate from the expected value inthe round function, but no particular characteristics in the data-randomizing part after the 4thround.
6.13 Implementation Attacks

It is well known that a poor implementation can leak information by timing attacks [K96] orpower analysis attacks [KJJ99]. Using the classi cation proposed in [DR99], Camellia is in thegroup of \favorable" algorithms, since it uses only logical operations and table-lookups and xed
rotations.
On the other hand, Chari et al. [CJRR99] claims that all AES candidates are susceptible topower analysis attacks. As these two papers contradict with each other, how to resist against
power analysis attacks is not known, since study on power analysis attacks has just begun. We
think that Camellia should be protected by the hardware techniques and should not be evaluatedby the security directly derived from the speci cation, considering the current art. We hope thatthe study on implementation attacks will be progressed in the near future.

32

Copyright NTT and Mitsubishi Electric Corporation 2000-2001
6.14 Brute Force Attacks

Most brute force attacks are applicable to any deterministic block cipher, and the corresponding
complexity depends on only the block size or key size3 , regardless of its design. Camellia has
a block size of 128-bit and allows for the three key sizes of 128-, 192-, and 256-bit. In thediscussions below, k denotes the key size in bits.

Exhaustive key search. In exhaustive key search, if an attacker gets one pair of plaintext

and ciphertext encrypted in ECB mode, he can nd the correct key by encrypting the plaintext
with all 2k possible keys.
A weakness in the key scheduling of the cipher can help improve the eciency of exhaustive
key search attack [K94], but we have not found such a weakness in Camellia. The complexityof the exhaustive key search is estimated to be about 2k01 encryptions on average. Thus, therequired complexity for exhaustive key search is 2127 , 2191 , and 2255 encryptions for Camellia
with 128-, 192-, and 256-bit keys, respectively. Therefore, Camellia's security against exhaustive
key search is adequate.

Time-memory trade-o attack. There are some words that are often used in plaintexts.

If an attacker encrypts such a plaintext block using 2k keys and store them in space for 2k
ciphertexts, then after he gets the corresponding ciphertext, he only has to look it up to nd
the corresponding key. This attack is called table attack. In this attack, after 2k encryption isdone, the attack complexity is much smaller than is true for exhaustive key search.
Time-memory trade-o attack [H80, KM96] can drastically reduce both time complexity on
intercepted ciphertexts of exhaustive key search and space complexity of table attack. However,both attacks require precomputation equivalent to the time complexity of exhaustive key search.
The key sizes supported by Camellia are long enough for security against exhaustive key searchby today's technology.

Dictionary attack. In dictionary attack, an attacker collects plaintext-ciphertext pairs under

the same key and put them in a \dictionary". When the attacker can see only a ciphertext
encrypted by the key, he can check if it is in the dictionary. If it is, he has already the plaintext.
Since the block size of Camellia is 128 bits, dictionary attack would require the space for 2128
di erent plaintext blocks to allow the attackers to encrypt or decrypt arbitrary messages underan unknown key. The success probability depends on the space for the dictionary, and as
the block size is larger, the required space to achieve the same success probability increases
exponentially. The 128-bit block cipher Camellia has enough security against this attack.

Matching ciphertext attack. In matching ciphertext attack [K98, Theorem 2], when about
the square root of all ciphertexts are available identical ciphertext blocks can be expected withprobability more than 21 by the \birthday paradox" for some modes of operations such as ECB,
CBC, and CFB modes. Then, valuable information about the plaintexts can be derived. Note
3 Strictly speaking, the computation time required for the attack depends on the performance of the blockcipher. However, the performance only a ects the encryption time and only changes the time complexity by
negligible factor.

33

Copyright NTT and Mitsubishi Electric Corporation 2000-2001
that this attack is independent of the key size. Since the block size of Camellia is 128 bits, thethreat to this attack is small, if encryption of as many as 264 blocks under the same key is not
performed.

34

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

7 Conclusion
We have presented Camellia, the rationale behind its design, its suitability for both softwareand hardware implementation, and the results of our cryptanalyses.
The performances shown in this paper leave room for further optimizations. The latest
performance results will be posted on the Camellia home page: http://info.isl.ntt.co.jp/
camellia/.
We have analyzed Camellia and found no important weakness. The cipher has a conservative
design and any practical attacks against Camellia would require a major breakthrough in thearea of cryptanalysis. We think that Camellia is a very strong cipher, which matches the securityof the existing best block ciphers.

35

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

References[A00]

K. Aoki. Practical Evaluation of Security against Generalized Interpolation Attack.
IEICE Transactions Fundamentals of Electronics, Communications and Computer
Sciences (Japan), Vol. E83-A, No. 1, pp. 33{38, 2000. (A preliminary version waspresented at SAC'99).
[ABK98] R. Anderson, E. Biham, and L. Knudsen. Serpent: A Flexible Block Cipher With
Maximum Assurance. In The First AES Candidate Conference, 1998.
[AIK+ 00a] K. Aoki, T. Ichikawa, M. Kanda, M. Matsui, S. Moriai, J. Nakajima, and T. Tokita.
Implementations of the 128-bit block cipher { Camellia {. Technical Report
ISEC2000-73, The Institute of Electronics, Information and Communication Engineers, 2000. (in Japanese).
[AIK+ 00b] K. Aoki, T. Ichikawa, M. Kanda, M. Matsui, S. Moriai, J. Nakajima, and T. Tokita.
Camellia: A 128-Bit Block Cipher Suitable for Multiple Platforms { Extended Abstract {. In First NESSIE Workshop, 2000.
[AU00] K. Aoki and H. Ueda. Optimized Software Implementations of E2. IEICE
Transactions Fundamentals of Electronics, Communications and Computer Sciences(Japan), Vol. E83-A, No. 1, pp. 101{105, 2000. (The full paper is available on
http://info.isl.ntt.co.% linebreak[3]jp/e2/RelDocs/).
[B94]
E. Biham. New Types of Cryptanalytic Attacks Using Related Keys. Journal of
Cryptology, Vol. 7, No. 4, pp. 229{246, 1994. (The extended abstract was appearedat EUROCRYPT'93).
[BS93]
E. Biham and A. Shamir. Di erential Cryptanalysis of the Data Encryption Standard. Springer-Verlag, Berlin, Heidelberg, New York, 1993.
[BW99] A. Biryukov and D. Wagner. Slide Attacks. In L. Knudsen, editor, Fast Software
Encryption | 6th International Workshop, FSE'99, Volume 1636 of Lecture Notes
in Computer Science, pp. 245{259, Berlin, Heidelberg, New York, 1999. SpringerVerlag.
[BW00] A. Biryukov and D. Wagner. Advanced Slide Attacks. In S. Vaudenay, editor,
Advances in Cryptology | EUROCRYPT2000, Volume 1807 of Lecture Notes in
Computer Science, pp. 589{606, Berlin, Heidelberg, New York, 2000. SpringerVerlag.
[C98]
Compaq Computer Corporation. Alpha Architecture Handbook (Version 4),
1998. (You can download the manual from Compaq's technical documentation library: http://www.support.compaq.com/alpha-tools/documentation/
current/chip-docs.html).
[C01]
CRYPTREC. CRYPTREC Report 2000, April 2001.
36

Copyright NTT and Mitsubishi Electric Corporation 2000-2001[CJRR99] S. Chari, C. Jutla, J. R. Rao, and P. Rohatgi. A Cautionary Note Regarding Evaluation of AES Candidates on Smart-Cards. In Second Advanced Encryption Standard
Candidate Conference, pp. 133{147, Hotel Quirinale, Rome, Italy, 1999. Information
Technology Laboratory, National Institute of Standards and Technology.
[CV95] F. Chabaud and S. Vaudenay. Links Between Di erential and Linear Cryptanalysis. In A. D. Santis, editor, Advances in Cryptology | EUROCRYPT'94, Volume
950 of Lecture Notes in Computer Science, pp. 356{365. Springer-Verlag, Berlin,
Heidelberg, New York, 1995.
[DKR97] J. Daemen, L. R. Knudsen, and V. Rijmen. The Block Cipher Square. In E. Biham,
editor, Fast Software Encryption | 4th International Workshop, FSE'97, Volume1267 of Lecture Notes in Computer Science, pp. 54{68, Berlin, Heidelberg, New
York, 1997. Springer-Verlag.
[DR98] J. Daemen and V. Rijmen. AES Proposal: Rijndael, 1998. (http://www.esat.
kuleuven.ac.be/~rijmen/rijndael/).
[DR99] J. Daemen and V. Rijmen. Resistance Against Implementation Attacks. A Comparative Study of the AES Proposals. In The Second AES Candidate Conference,
1999.
[F00]
A. Fog. How to optimize for the Pentium microprocessors, 2000. (http://www.
agner.org/assem/).
[H80]
M. Hellman. A Cryptanalytic time-memory trade-o . IEEE Transactions on Information Theory, Vol. IT-26, No. 4, pp. 401{406, 1980.
[HQ01] Y. He and S. Qing. Square Attack on Reduced Camellia Cipher. submitted to the
3rd International Conference on Information and Communications Security (ICICS
2001), 2001.
[I99]
Intel Corporation. Intel Architecture Software Developer's Manual (Volume 2: Instruction Set Reference), 1999. (You can download the manual from Intel's developersite: http://developer.intel.com/).
[ISKM01] T. Ichikawa, T. Sorimachi, T. Kasuya, and M. Matsui. On the criteria of hardware
evaluation of block ciphers (1). Technical Report ISEC2001-53, The Institute ofElectronics, Information and Communication Engineers, 2001. (in Japanese).
[JK97]
T. Jakobsen and L. R. Knudsen. The Interpolation Attack on Block Cipher. In
E. Biham, editor, Fast Software Encryption | 4th International Workshop, FSE'97,
Volume 1267 of Lecture Notes in Computer Science, pp. 28{40, Berlin, Heidelberg,
New York, 1997. Springer-Verlag.
[K93]
L. R. Knudsen. Cryptanalysis of LOKI91. In J. Seberry and Y. Zheng, editors, Advances in Cryptology | AUSCRYPT'92, Volume 718 of Lecture Notes in Computer
Science, pp. 196{208. Springer-Verlag, Berlin, Heidelberg, New York, 1993.
37

Copyright NTT and Mitsubishi Electric Corporation 2000-2001[K94]

L. R. Knudsen. Practically secure Feistel ciphers. In R. Anderson, editor, Fast
Software Encryption 1993 | Cambridge Security Workshop (FSE1), Volume 809 of
Lecture Notes in Computer Science, pp. 211{221, Berlin, Heidelberg, New York,1994. Springer-Verlag.
[K95]
L. R. Knudsen. Truncated and Higher Order Di erentials. In B. Preneel, editor,
Fast Software Encryption | Second International Workshop, Volume 1008 of Lecture
Notes in Computer Science, pp. 196{211. Springer-Verlag, Berlin, Heidelberg, New
York, 1995.
[K96]
P. Kocher. Timing Attacks on Implementations of Die-Hellman, RSA, DSS, andOther Systems. In N. Koblitz, editor, Advances in Cryptology | CRYPTO'96,
Volume 1109 of Lecture Notes in Computer Science, pp. 104{113. Springer-Verlag,
Berlin, Heidelberg, New York, 1996.
[K98]
L. R. Knudsen. Block Ciphers | A Survey. In B. Preneel and V. Rijmen, editors,
State of the Art in Applied Cryptography, Volume 1528 of Lecture Notes in Computer
Science, pp. 18{48, Berlin, Heidelberg, New York, 1998. Springer-Verlag.
[K00]
M. Kanda. Practical Security Evaluation against Di erential and Linear Attacks for
Feistel Ciphers with SPN Round Function. In SAC2000, Seventh Annual Workshop
on Selected Areas in Cryptography, 14-15 August 2000, Workshop Record, 2000.
[KJJ99] P. Kocher, J. Ja e, and B. Jun. Di erential Power Analysis. In M. Wiener, editor,
Advances in Cryptology | CRYPTO'99, Volume 1666 of Lecture Notes in Computer
Science, pp. 388{397. Springer-Verlag, Berlin, Heidelberg, New York, 1999.
[KK01] T. Kawabata and T. Kaneko. A Study on Higher Order Di erential Attack ofCamellia. In Second NESSIE Workshop, 2001. (This paper is based on T. Kawabata,
Y. Ohgaki and T. Kaneko, \A Study on Strength of Camellia against Higher OrderDi erential Attack," (in Japanese), Technical report of IEICE, ISEC2001-9, pp.55{
62, The Institute of Electronics, Information and Communication Engineers, 2001.).
[KM96] K. Kusuda and T. Matsumoto. Optimization of Time-Memory Trade-O Cryptanalysis and Its Application to DES, FEAL-32, and Skipjack. IEICE Transactions
Fundamentals of Electronics, Communications and Computer Sciences (Japan),Vol. E79-A, No. 1, pp. 35{48, 1996.
[KMA+ 98] M. Kanda, S. Moriai, K. Aoki, H. Ueda, M. Ohkubo, Y. Takashima, K. Ohta, andT. Matsumoto. A New 128-bit Block Cipher E 2 . Technical Report ISEC98-12,
The Institute of Electronics, Information and Communication Engineers, 1998. (inJapanese).
[KSW96] J. Kelsey, B. Schneier, and D. Wagner. Key-Schedule Cryptanalysis of IDEA, GDES, GOST, SAFER, and Triple-DES. In N. Koblitz, editor, Advances in Cryptology| CRYPTO'96, Volume 1109 of Lecture Notes in Computer Science, pp. 237{251.
Springer-Verlag, Berlin, Heidelberg, New York, 1996.
38

Copyright NTT and Mitsubishi Electric Corporation 2000-2001[KTM+ 99] M. Kanda, Y. Takashima, T. Matsumoto, K. Aoki, and K. Ohta. A Strategy for
Constructing Fast Round Functions with Practical Security against Di erential andLinear Cryptanalysis. In S. Tavares and H. Meijer, editors, Selected Areas in Cryptography | 5th Annual International Workshop, SAC'98, Volume 1556 of Lecture
Notes in Computer Science, pp. 264{279, Berlin, Heidelberg, New York, 1999.
Springer-Verlag.
[LMM91] X. Lai, J. L. Massey, and S. Murphy. Markov Ciphers and Di erential Cryptanalysis.
In D. W. Davies, editor, Advances in Cryptology | EUROCRYPT'91, Volume 547 of
Lecture Notes in Computer Science, pp. 17{38. Springer-Verlag, Berlin, Heidelberg,
New York, 1991.
[M94]
M. Matsui. Linear Cryptanalysis Method for DES Cipher. In T. Helleseth, editor,
Advances in Cryptology | EUROCRYPT'93, Volume 765 of Lecture Notes in Computer Science, pp. 386{397. Springer-Verlag, Berlin, Heidelberg, New York, 1994.
(A preliminary version written in Japanese was presented at SCIS93-3C).
[M95]
M. Matsui. On Correlation Between the Order of S-boxes and the Strength of
DES. In A. D. Santis, editor, Advances in Cryptology | EUROCRYPT'94, Volume
950 of Lecture Notes in Computer Science, pp. 366{375. Springer-Verlag, Berlin,
Heidelberg, New York, 1995.
[M97]
M. Matsui. New Block Encryption Algorithm MISTY. In E. Biham, editor,
Fast Software Encryption | 4th International Workshop, FSE'97, Volume 1267
of Lecture Notes in Computer Science, pp. 54{68, Berlin, Heidelberg, New York,1997. Springer-Verlag. (A preliminary version written in Japanese was presented at
ISEC96-11).
[M99]
M. Matsui. Di erential Path Search of the Block Cipher E2. Technical Report
ISEC99-19, The Institute of Electronics, Information and Communication Engineers,
1999. (in Japanese).
[MIYY88] M. Matsui, T. Inoue, A. Yamagishi, and H. Yoshida. A note on calculation circuits
over GF(22n). Technical Report IT88-14, The Institute of Electronics, Information
and Communication Engineers, 1988. (in Japanese).
[MSAK00] S. Moriai, M. Sugita, K. Aoki, and M. Kanda. Security of E2 against TruncatedDi erential Cryptanalysis. In H. Heys and C. Adams, editors, Selected Areas in
Cryptography | 6th Annual International Workshop, SAC'99, Volume 1758 of Lecture Notes in Computer Science, pp. 106{117, Berlin, Heidelberg, New York, 2000.
Springer-Verlag.
[MT99] M. Matsui and T. Tokita. Cryptanalysis of a Reduced Version of the Block Cipher
E2. In L. Knudsen, editor, Fast Software Encryption | 6th International Workshop,
FSE'99, Volume 1636 of Lecture Notes in Computer Science, pp. 71{80, Berlin,
Heidelberg, New York, 1999. Springer-Verlag. (Japanese version was presented at
SCIS99.).
39

Copyright NTT and Mitsubishi Electric Corporation 2000-2001[RDP+ 96] V. Rijmen, J. Daemen, B. Preneel, A. Bosselaers, and E. De Win. The Cipher
SHARK. In D. Gollmann, editor, Fast Software Encryption | Third International Workshop, Volume 1039 of Lecture Notes in Computer Science, pp. 99{111.
Springer-Verlag, Berlin, Heidelberg, New York, 1996.
[SKI01] M. Sugita, K. Kobara, and H. Imai. Security of Reduced Version of the Block Cipher
Camellia against Truncated and Impossible Di erential Cryptanalysis. submitted to
ASIACRYPT 2001, 2001.
[W99]
D. Wagner. The Boomerang Attack. In L. R. Knudsen, editor, Fast Software Encryption | 6th International Workshop, FSE'99, Volume 1636 of Lecture Notes in
Computer Science, pp. 156{170, Berlin, Heidelberg, New York, 1999. SpringerVerlag.
[Y01a]
C.-H. Yang. Performance Evaluation of AES/DES/Camellia on the 6805 and H8/300
CPUs. In Proceedings of the 2001 Symposium on Cryptography and Information
Security, Volume II of SCIS2001, pp. 727{730, Oiso, Japan, 2001. Technical Groupon Information Security (IEICE).
[Y01b]
C.-H. Yang. Supplementary information for C.H. Yang SCIS 2001 paper.
http://www.geocities.com/chyang00/SCIS2001, 2001.

40

Copyright NTT and Mitsubishi Electric Corporation 2000-2001

A History
Ver 2.0 (September 26, 2001)
 Abstract was renewed with the latest performance gures.
 Section 1, the paragraph of \Future developments" was renewed based on the current
status. The title was also changed into \Standardization activities".
 Section 3 was renewed with the latest performance gures.
 In Section 4.2.7, the equation to calculate Eq.(3) using only four tables, SP1 ; SP2 ; SP3 ; SP4 ,was corrected.
 Section 5 was renewed by adding the latest information on hardware evaluations.
 In Section 6.1 (Di erential and Linear Cryptanalysis), an erratum in Table10 \Upper
bounds of di erential characteristic probability of Camellia" (in the row of \without
F L=F L01 -functions") was xed.
 Section 6.2 (Truncated Di erential Cryptanalysis) was renewed by adding the recent result.
 Section 6.4 (Cryptanalysis with Impossible Di erential) was renewed by adding the recent
result. An erratum was also xed: \more than 6 rounds" ! \more than 5 rounds"
 Section 6.6 (Higher Order Di erential Attack) was renewed based on the recent result.
 Section 6.7 (Square Attack) was added.
 Section 6.12 (Statistical Tests) was renewed by adding more information.

41