1

International Standard Encryption
Algorithm from Japan"Camellia"
NTT Information Sharing Platform Laboratories
Camellia website
http://info.isl.ntt.co.jp/crypt/eng/camellia/
E-mail: camellia@lab.ntt.co.jp

Handout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

2

Why needs Camellia?
Camellia is the only international standard cipherthat is an alternative to the US standard cipher AES
 All information systems depending only on a single

cipher (i.e. AES) seem to be unstable and risky
Alternative choice should be prepared because of the risk
hedging Easy use as well as AES

Same Interface
Royalty-free license
Already adopted to various standardizations
Already loaded with various open source software
Handout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

3

Features of Camellia
Camellia 128-bit block cipher (allowing key sizes of 128, 192, and256 bits), jointly developed in 2000 by NTT & Mitsubishi
Win-win collaboration on cryptography in Japan

World’s highest security and efficiency – technicallycomparable to AES
Many evaluations in the cryptographic community have publishedAdopted as international standard specification andrecommended specification for the coming encryption
algorithms
AES, Camellia, and SEED are only ciphers selected as the future
ISO/IEC standard ciphers
Already adopted in IETF (TLS, IPsec, S/MIME, OpenPGP, XML) and
RSA PKCS#11, etc.
Handout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

4

Features of Camellia (Cont.)Camellia essential patents can be used at no charge by
any Camellia user without concluding such royalty-freelicensing agreement
http://info.isl.ntt.co.jp/crypt/eng/info/chiteki.html

NTT publishes NTT’s open source codes of Camellia freeof charge through multiple open source software
licenses (GPL, LGPL, BSD, MPL, and OpenSSL)
http://info.isl.ntt.co.jp/crypt/eng/camellia/source.html

NTT contributes to major open source communities
Some major open source communities, e.g., Mozilla, OpenSSL,
Linux, FreeBSD and Kerberos, have already supported Camellia into
their open source softwareNTT joined in Kerberos Consortium as an executive
advisory board member
Handout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

5

Supported Open Source Software
Major OSS communities loaded Camellia to theirtools/kernels as the first Japanese cipher
Open Source & Information by NTT
i. C-language code (GPL, LGPL, BSD,
OpenSSL, MPL)
ii. Java code (GPL, BSD)
iii. Ruby Camellia package
iv. Guidance & Instructions (in Japanese)i. FreeBSD 6.4 (or later)/7.0 (or later)OSii. Linux kernel 2.6.21 (or later)
Kerneliii. Fedora Core 7 (or later)
i. Firefox 3.0 (or later)ii. ipsec-tools 0.7 (or later)
Applicationiii. GnuPG 2.0 (or later)
iV. Kerberos KRB5 1.9 (or later)
Handout of Camellia Ver7.0

Toolkiti. OpenSSL toolkit 0.9.8c (or later)
Notes: the option “enable-camellia” isneeded when openssl-0.9.8x is built.

ii. NSS (Network Security Services)
3.12 (or later)iii. Crypto++ library 5.4 (or later)
iv. The Legion of the Bouncy Castle
1.30 (or later)
v. GNU Transport Layer Security
Library 2.20 (or later)i. Camellia for Open Souce Softwares
Third ii. Camellia for Python
party iii. Perl Camellia encryption module
codes iv. openCrypto.NET
v. Pascal source by Wolfgang Ehrhardt
Copyright NTT 2010
All rights reserved

6

SSL/TLS by Camellia
WWW Server(Ex: EC site)

SSL/TLS by Camellia

Camellia Sever:
Apache+OpenSSL

WWW Browser(Ex: Customer)

Browser: Firefox 3

引用： Apache Lounge, http://www.apachelounge.com/forum/viewtopic.php?t=1992

Notes: Camellia is already available by default
in the bundled OpenSSL in the later OS kernels

Firefox 3 establishes SSL
by Camellia

Fedora Core 9 (or later), OpenSUSE 10.3 (or later),
Gentoo Linux 2008.0 (or later), FreeBSD 7.0 (or later),
FreeBSD ports 2007/6/12 (or later)
Handout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

7Standardization of Symmetric Ciphers
Camellia is internationally recognized
as representative of Japanese ciphers
Notes: “X” mark means “selected”

Nationality

Camellia Japan
128-bitblock
ciphers

Streamciphers

Government-related standard ciphers/ recommended ciphers

IETF standard ciphers
RSA
PKCS#11[ISO/IEC18033]

SSL/TLS

IPsec

S/MIME

XML

X

X

X

X

[RFC4132][RFC4312][RFC3657][RFC4051]

X
--

X
X

X
X

X
X

X
--

X

X

(NESSIE)

Japan
recommended(CRYPTREC)

Koreanstandard

Canadianstandard

--

X

X

--

--

X
--

X
--

X
--

-X

X
--

X

--

X

--

X

-X
-----

-------

X------

X

--

--

---

---

US
standard(FIPS/SP)European Union
recommended

AES

USA

SEED

Korea

X
X

Triple DES

USA

X

X

X

X

X

X

CAST-128

CanadaMISTY1

Japan

Blowfish

USA

IDEA

Swiss

RC2

USA

RC5

USA

X
X
-----

X
-X
X
X
X

---X
X
--

X
--X
-X

X
--X
X
X

--------------

-X
-----

RC4

USA

--

X

X

--

--

X

--

--

MUGI

Japan

SNOW

Sweden

X
X

---

---

---

---

---

---

---

Transition
64-bitblock
ciphers

ISO/IEC
standard
ciphers

Handout of Camellia Ver7.0(Recommended)(Conditional)(Conditional)

X--

Copyright NTT 2010
All rights reserved

8

Users & Products equipped with Camellia
Welcome to use Camellia into any products !!
 Users
Japanese government systems, Financial services, Online
Game (eg. Capcom), SNS services (eg. mixi), Network
services, Manufacturing systems, Universities, etc.
 Supported Venders

More than 60 companies adopt Camellia into their products
NTT Software
NTT Electronics
NTT-AT
Mitsubishi Electric
Renesas Technology
AuthenTec (prev. SafeNet)
THALES (prev. nCipher)
IAIK
Bloombase

CipherCraft/Mail, CipherCraft/VPN, CipherCraft/File, etc
Camellia LSI, IP Super-Compact MPEG-2 Codec, etc
Smart Leak Protect, File Lock II, etc
Cryptopia, MistyGuard(R)<CRYPTOFILE(R) PLUS>, etc
SH7781 MPU and MCU/SuperH RISC engine Family
QuickSec Toolkit
netHSM, nShield series, miniHSM
IAIK-JCE, iSaSiLk, CMS-S/MIME, IAIK-XSECT
Spitfire Ethernet Encryptor, Spitfire StoreSafe, Spitfire Messaging, etc.

Handout of Camellia Ver7.0

Copyright NTT 2009
All rights reserved9Security
Camellia achieves world’s highest security level
against state-of-the-art attacks and future unknown attacks
 Published design rationale and self-evaluations
Camellia is practically secure against known strong attacks, e.g.
differential and linear cryptanalysis
No vulnerabilities against state-of-the-art attacks
NO attacks are found against Camellia with any size of keys by theworld’s top-class researchers[FYI] In 2009, AES-192/256 can be theoretically broken using related-key attack
proposed by Alex Biryukov, et al.

World’s top-class resistant security (security margin)(2009.9 at the present time)against unknown attacks in the future
Breakable
rounds7
ISA: 258.6

128-bit keys VSA: 290.6
256-bit keys VSA: 2146.6

8
ISA: 298
ICA: 274.6
ISA: 282
VSA: 2194.6
ICA: 266.6

9
ISA: 2122

ISA: 2146

10

11

12

13

14

15

Original

Unknown Unknown Unknown Unknown Unknown Unknown Unknown attacks
attacks
attacks
attacks
attacks
attacks
attacks up to 18 rounds
BestISA:
known
2210
attackHandout of Camellia Ver7.0

HDC: 2256

Unknown Unknown Unknown Unknown Unknown attacks
attacks
attacks
attacks
attacks up to 24 rounds
Copyright NTT 2010
All rights reserved

10Performance and Flexibility
Camellia is extremely flexible and highly efficientaccording to circumstances

Camellia possesses high-speed software that is platform
independent such as PCs or smart cards
For PCs: Performance is achieved by using many registers, precomputed large tables and powerful instruction sets
For smart cards: Containment of memory usage is achieved using
small tables and on-the-fly subkey generation

World's smallest hardware implementation with world
top-class efficiency
Substitution tables are implemented using an inversion function over
GF(28)
Encryption and decryption circuits can be shared since theseprocedures are identical except for the order of subkey insertion
Handout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

11Performance and Flexibility (Cont.)

Performance of Camellia is comparable to that of AES on
any platform
No disadvantage in terms of efficiency

High performance software
for smart cards
Memory usage of RAM: Approx. 60 B
ROM: Approx. 1.5 KB
Processing time: Approx. 2 msec(@15 MHz) (Using Assembly)

Compact and efficient
hardware chip
Approx. 8 KG, Approx. 200 Mbps
(Using 0.18-µm ASIC)
Approx. 2 K slice, Approx. 250 Mbps
(Using FPGA)
Handout of Camellia Ver7.0(when using 128-bit key)

High-speed hardware chip
Approx. 45 KG, Approx. 2 Gbps
(Using 0.18-µm ASIC)
Approx. 9.5 K slice, Approx. 400 Mbps
(Using FPGA)High-speed software for PCs
Approx. 1 Gbps (Using Assembly)(@Pentium 4, 3.2 GHz)

Copyright NTT 2010
All rights reserved

12

Win-Win Collaboration on Crypto in Japan
NTT’s know-how for designing
ciphers suitable for high-speed
software implementation
Secret key (128 bits)

Mitsubishi’s know-how for designing
ciphers suitable for high-performance
hardware implementation

New co-designing

Plaintext (128 bits)
F-function

S1
S4

F-function

Rotation & Choice

S3

Intermediate key

Intermediate key generation

Main function

FL/FL-1 layer

F-function

Main function

F-function

S2
S4
S3

FL/FL-1 layer
Main function

S2

F-function

S1
F-function

SubkeysSubkeySubkey generation

Lineartransformation
using byte-wise
XOR

Si: Substitution table

Randomized function

Ciphertext (128 bits) Subkey

Handout of Camellia Ver7.0

FL

FL-1

SubkeyCopyright NTT 2010
All rights reserved

13

What is “Camellia” – Origin of the Name Camellia (Tsubaki in Japanese)

Japan is the place of origin and thescientific name is Camellia japonica.
In the language of flowers it means
Good fortune and loveliness, gratitude.
 Our minds:

Although this encryption technology originates fromJapan, after leaving Japan we want it to grow in various
forms – as well as Camellia flowers

Handout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

14

For More Detail …
Please see the Camellia website !!
http://info.isl.ntt.co.jp/crypt/eng/camellia/

Handout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

15Technical Details

Handout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

16

Camellia SpecificationsInterface: Compatible with AES
Block length : 128 bits
Key length: 128, 192, and 256 bits



Main structure: Similar to DES-like ciphers, not AES
18-round Feistel structure for 128-bit key
24-round Feistel structure for 192- and 256-bit keys
FL/FL-1 function layers: Inserted every 6 roundsComponents
Round function (F-function): Byte-oriented SPN structure
FL/FL-1 function layers: Combination of AND, OR, Rotation, and XOR
Whitening: XOR

Subkey generation
Intermediate keys are generated from secret key using 2-round
Feistel structure
Subkeys are created from secret key and intermediate keys using
Rotation & Choice techniqueHandout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

17

Software Performance for PCs


Available to software-based encryption for high-quality
videosProcessor

Core2 Duo
E8400

AMD Phenom
9850

Language

ANSI CJava

ANSIC

Assembly

Pentium 4CJavaThroughput (both encryption and decryption)
192-bit key

256-bit key

505 cycles

655 cycles

655 cycles(801Mbps@3.16GHz)(618Mbps@3.16GHz)(618Mbps@3.16GHz)

698 cycles

869 cycles

869 cycles(580Mbps@3.16GHz)(466Mbps@3.16GHz)(466Mbps@3.16GHz)

470 cycles

610 cycles

603 cycles(683Mbps@2.5GHz)(526Mbps@2.5GHz)(532Mbps@2.5GHz)

N/A

N/A

Papers (WinXP, Hyper-threading off)

900 cycles

1168 cycles

1165 cycles(455 Mbps@3.2 GHz)

(351 Mbps@3.2 GHz)

(352 Mbps@3.2 GHz)

Old version of open source code published on
Camellia website(WinXP, Hyper-threading off)
NESSIE Performance Reports (Linux)

361 cycles(1.1 Gbps@3.2 GHz)

Assembly1376 cycles

1376 cycles(158 Mbps@1.7 GHz)

(158 Mbps@1.7 GHz)

N/A

N/A

Old version of open source code published on
Camellia website(WinXP, Hyper-threading off)

N/A

N/A

Two block parallel encryption(WinXP, Hyper-threading on)

N/A

N/A

Bitslice encryption(WinXP, Hyper-threading on)

N/A

N/A

CRYPTREC Report 2002
(Win98 SE)

1552 cycles(264 Mbps@3.2 GHz)

(1.6 Gbps@2.2 GHz)

243 cycles
Assembly

Open source code published on
Camellia website(FreeBSD)

1008 cycles(1.2 Gbps@2.2 GHz)

Pentium III

Open source code published on
Camellia website(Fedora)(216 Mbps@1.7 GHz)

175 cycles
Athlon64 3500+

Notes

128-bit key

326 cycles(255 Mbps@650 MHz)

Handout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

18Tradeoff Between Security and Efficiency
Good balance of security and performanceCamellia gives greater importance to security than performance

Camellia

Advancement ofcryptanalysis

1.5
Triple DES

1

AES

Breakable

Insecure

Excepted security margin

2

1

2

3

4

5

6

7

8

Speed ratio by openssl toolkit (Triple DES = 1)
Handout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

19

Software Performance for Smart Cards
World’s highest performance even under containment ofmemory usage
Few additional costs are needed even if decryption is required
Memory usage

Processor

RAM

ROM

[bytes] [bytes]

Z80

8051
H8/3113
AE45X

SLE66
CLX320P
M32Rx/D

63

1,698

60

1,268

32

990

Unknown Unknown

60

Unknown

248

1,279

58

1,311

44

8,684

Speed per block (128-bit message)
Encryption / decryption[cycles]

Subkey generation[cycles]

28,382 (5.68 msec)

5,146 (1.03 msec)

Speed ratio (Triple DES = 1)

Reference:[3] CRYPTREC Report 2002
[4] 2nd NESSIE Workshop

4(enc. w subkey gen.) 35,951 (7.19 msec)(dec. w subkey gen.) 37,553 (7.51 msec)

10,217 (10.22 msec)
4,100 (1.64 msec)

2,380 (0.95 msec)

2(enc. w subkey gen.) 8,136 (1.11 msec)(dec. w subkey gen.) 8,658 (1.18 msec)

17,920 (2.64 msec)

6,144 (0.91 msec)(enc. w subkey gen.) 24,064 (3.55 msec)(dec. w subkey gen.) 24,576 (3.62 msec)

1,236 (12.36 msec)

Handout of Camellia Ver7.0

642 (6.42 msec)

0Camellia
enc [3]

Camellia
dec [3]AES
enc [3]AES
dec [3]

Triple DES
enc [4]

Copyright NTT 2010
All rights reserved

20

Hardware PerformanceDesigned world’s smallest circuit for 128-bit blockciphers (smaller than 10 Kgates) with world top-classefficiency(when using 128-bit key)Type

Design library
MELCO 0.18 μm

ASIC

Commercial-based product

IBM 0.13 μm
IBM 0.18 μm
Xilinx VertexE
FPGA(Pipeline implementation)

Xilinx Vertex3200E(Pipeline implementation)
Handout of Camellia Ver7.0

Throughput
1,881.3 Mbps
1,050.9 Mbps
177.7 Mbps
71.5 Mbps
71 Mbps2,154.9 Mbps
1,907.6 Mbps
325.8 Mbps
567.3 Mbps
204.6 Mbps
401.9 Mbps
227.4 Mbps
6,750 Mbps
369.0 Mbps
223.7 Mbps
25,440 Mbps

Area size
44.3 KG
11.9 KG
8.1 KG
6.4 KG
6.4 KG
29.8 KG
20.8 KG
6.5 KG
9.1 KG
6.3 KG
9,426 slices
1,780 slices
9,692 slices
8,957 slices
1,678 slices
19,482 slices

Efficiency
42.47
88.52
21.87
11.23
11.09
72.31
91.76
50.12
62.34
32.66
42.64
127.76--42.14133.31--Copyright NTT 2010
All rights reserved

21

Sketch of Procedure for 128-bit Key
Secret key (128 bits)

Plaintext (128 bits)
F-function

S1
S4

F-function

Main function

Rotation & Choice

FL/FL-1 layer

F-function

Main function

F-function

Lineartransformation
using byte-wise
XOR

S3

FL/FL-1 layer

F-function

Main function

F-function

S2
S1
Si: Substitution table

SubkeySubkeySubkey generation

S2
S4

SubkeysIntermediate key

Intermediate key generation

S3

FL

FL-1

SubkeyRandomized function

Ciphertext (128 bits)
Handout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

22

Sketch of Procedure for 192-&256-bit Keys
Secret key (192/256 bits) Plaintext (128 bits)
F-function

S1

Rotation & Choice

Intermediate keys

Intermediate key generation

S3

FL/FL-1 layer

F-function

Main function

F-function

S2
S4

Lineartransformation
using byte-wise
XOR

S3

FL/FL-1 layer

F-function

Main function

F-function

S2
S1
Si: Substitution table

SubkeySubkeys

FL/FL-1 layer

Subkey generation

S4

F-function

Main function

Main function

SubkeyFL

FL-1

SubkeyRandomized function

Ciphertext (128 bits)
Handout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

23

Sketch of Intermediate Key Generation(For 128-bit key)

KL

C1

F-function

C2

F-function

Constants Ci：
the continuous values from the second hexadecimal
place to the seventeenth hexadecimal place of thehexadecimal representation of the square root of 2,
3, 5, and 7, respectively

KL
C3

F-function

C4

F-function

KA
Handout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

24

Sketch of Intermediate Key Generation (Cont.)(For 192-/256-bit keys) KL

KR

C1

F-function

C2

F-function

Constants Ci：
the continuous values from the second hexadecimal
place to the seventeenth hexadecimal place of thehexadecimal representation of the square root of 2,
3, 5, 7, 11, and 13, respectively

KR

KL
C3

F-function

C5

F-function

C4

F-function

C6

F-function

KA
Handout of Camellia Ver7.0

KB
Copyright NTT 2010
All rights reserved

25

Sketch of Round Function (F-function)
SubkeyS-function

P-function

S1
S4
S3
S2
S4
S3
S2
S1
Handout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

26

Useful Implementation for 32-bit CPU
Using an equivalent round function with large S-boxes
This technique is very effective on CPUs equipped with 4-KB cache
SP11100

SP1110 is precomputed from S1
SP1110SP4404

S1

＝

S1
S1

SP3033S4SP0222SP4404S3SP4404SP3033SP02228-bit data

32-bit data<<<8-bit rotation



SP3033

0

＝ S4
S4

S3

＝ 0
S3
SP0222

S2
S2

＝ S2

SP11100Handout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

27

Useful Implementation for Embedded CPU
Equivalent round function based on 32-bit operations withoutchanging S-boxes

S3

S4
S3
S2
8-bit data

32-bit data<<<8-bit rotation

S2>>>8-bit rotation

S4>>>8-bit rotation

S1>>>16-bit rotation

This technique is effective on smart cards and embedded CPUs withmemory constraints>>>8-bit rotation

S1
Handout of Camellia Ver7.0

Copyright NTT 2010
All rights reserved

28

Useful Implementation for Reducing Memory

S1

y

x

=

x-1

affinexaffineThis technique is effective on
smart cards, embedded CPUs,
and small hardware design with
ROM constraints

x

S4

y

x

S1

=
y

x

=

S1

1>>>

S1

=

1<<<

S3

x

1>>>

x

S2

y

y

y

y

S2, S3, and S4 can be computed
only from S1
Handout of Camellia Ver7.0

subkey generation
This technique is effective on smart
cards, embedded CPUs, and small
hardware design with RAM
constraintsy

S1 is affine equivalent to an inversion
function over GF(28)x Reducing memory usage of

Secret key (128/256 bits)
KL

KR

Intermediate key
generation
KA

KB

Rotation & choice Reducing capacity of S-boxes

Subkeys(1664/2176 bits)

Intermediate keys (128/256 bits)

On-the-fly subkey generation technique can beused with secret key and intermediate keys
If only 128-bit secret keys are acceptable, only
KL and KA are required
Copyright NTT 2010
All rights reserved29

Security Evaluation Overview
Best known attacks can break the reduced-versions of Camellia in
only with 9-rounds (128-bit key) or 11-rounds (256-bit key), while
original versions require 18-rounds and 24-rounds, resp. (2009.9 at the present time)
Breakable rounds
56
10.6
ISA: 218
128-bit Modified- ISA: 2
keys
versions ICA: 25.8 VSA: 218.6(except
ICA: 213.7
FL/FL-1
layers)
HDC: 218
Reduced-versions256-bitkeys

Modified- versions(except
FL/FL-1
layers)Reduced-versions

-

7
8
58
ISA: 2
VSA: 233.5 VSA: 274.6
ICA: 254.7 ICA: 294.9

9

10

11

VSA: 290
ICA: 2119.4

12
13
14
15
Unknown Unknown Unknown Unknown
attacks
attacks
attacks
attacks

IDC: 2126
HDC: 257

HDC: 2120

TDC: 192 TDC: 255.6
ISA: 2122 Unknown Unknown Unknown Unknown Unknown Unknown
ISA: 258.6 ISA: 298
attacks
attacks
attacks
attacks
attacks
attacks
VSA: 290.6
ICA: 274.6
Unknown
ISA: 250
250.8)
25.6
66.6
122
186
250
(VSA:
2
attacks
VSA: 2
VSA: 2
VSA: 2
VSA: 2
VSA: 2
ICA: 246.7 ICA: 278.9 ICA: 2143.4 ICA: 2207.4
IDC: 2232.5
HDC: 2188 HDC: 2252
ISA: 282
ISA: 2146 ISA: 2210
Unknown Unknown Unknown Unknown
146.6
194.6
attacks
attacks
attacks
attacks
VSA: 2
VSA: 2
ICA: 266.6
HDC: 2256

References:
Duo Lei, Li Chao, and Keqin Feng, “New Observation on Camellia,” SAC 2005, LNCS 3897
Guan Jie, and Zhang Zhongya, “Improved Collision Attack on Reduced Round Camellia,” CANS 2006, LNCS 4301
Lei Duo, Chao Li, and Keqin Feng, “Square Like Attack on Camellia,” ICICS 2007, LNCS 4861
Jiqiang Lu, Jongsung Kim, Nathan Keller, and Orr Dunkelman, “Improving the Efficiency of Impossible Differential Cryptanalysis of Reduced Camellia and MISTY1,” CT-RSA 2008, LNCS 4964

Handout of Camellia Ver7.0

ISA: Improved Square Attack / VSA: Variant Square Attack
ICA: Improved Collision attack
IDC: Impossible Differential Cryptanalysis
HDC: Higher Order Differential Cryptanalysis
TDC: Truncated Differential Cryptanalysis

Copyright NTT 2010
All rights reserved