A HIGH THROUGHPUT FPGA CAMELLIAIMPLEMENTATION
Daniel Denning, James Irvine, Malachy Devlin
Institute of System Level Integration, Alba Centre, Alba Campus,
Livingston, EH54 7EG, UK
E-mail: daniel.denning@sli-instiute.ac.uk

ABSTRACTIn this paper we present a Field Programmable
Gate Array (FPGA) implementation of theCamellia
encryption
algorithm.
Our
implementation deeply sub-pipelines the algorithm
for the FPGA architecture. Camellia has been
included in both portfolios of the New European
Schemes for Signatures, Integrity, and Encryption(NESSIE) for Europe and the Cryptography
Research and Evaluation Committee (CRYPTREC)
in Japan. The implementation is the fastest
published throughput for the entire block ciphers
recommended in both portfolios for NESSIE andCRYPTREC, and runs at a throughput of
33.25Gbit/sec.

1. INTRODUCTION
The Camellia [1] symmetric-key block cipher has
been recognised by an open call from NESSIE [2]and CRYPTREC [3] as a cryptographic algorithm
to help protect the current and future informationsociety. FPGAs provide a very beneficial platform
for implementing cryptographic systems because of
the inherent parallelism of the device.
NESSIE was a European Union (EU) initiative
and a project with in the Information Society
Technologies (IST) of the EU. Camellia wasselected with three other block ciphers from the 42encryption algorithms that were submitted. The
other two block ciphers being MISTY1 andSHACAL-2. The AES algorithm was also selected
but selected on its evaluation from the National
Institute of Standards and Technology (NIST).
Other algorithms included digital signatures,
identification schemes, public-key encryption, MAC
algorithms, and hash functions.
The Camellia algorithm is a 128-bit blockcipher jointly developed by NTT and Mitsubishi
Electric Corporation. The algorithm has also been
submitted to other standardisation organisations andevaluation projects such as ISO/IEC JTC 1/SC 27,
IETF, and TV-Anytime Forum. Previous Camellia
implementations have been published in [4,5] but
do not investigate a sub-pipelining architecture.
2. OVERVIEW OF CAMELLIAALGORITHM
The Camellia algorithm processes data blocks of
128-bits with secret keys of lengths 128, 192, or 256
bits. Note that Camellia has the same interface asthe AES (Advanced Encryption Standard). In ourimplementation we focus on the algorithm using akey length of 128-bits that is key agile. A key agile
core requires that on each clock cycle new data andcipher key must be accepted.
A key length of 128-bits results in an 18 round
Feistel structure. After the 6th and 12th rounds
FL/FL-1 function layers are inserted to provide some
non-regularity across rounds. There are also two
64-bit XOR operations before the first round andafter the last, also known as pre- and postwhitening. The top-level structure of the algorithm
can be seen in Figure 1, as well as the inner 6 roundstructure. The key schedule, discussed later in thissection, generates subkeys for each round, FL/FL-1layers, and pre- and post-whitening.
The FL-function is defined by:
YR(32) = ((XL(32) ∩ klL(32)) <<< 1) ⊕ XR(32),(1)YL(32) = (YR(32) ∪ klR(32)) ⊕ XL(32),(2)where YL(32) are the 32 most significant bits of the64-bit output and YR(32) are the 32 least significantbits. The FL-1 function is just the inverse of FL.
Each round can be composed of an F-function witha XOR. A different subkey is applied to each Ffunction and the output is XORed with the previous
but one result. The F-function is defined as
Y(64) = P(S(X(64) ⊕ k(64)).

(3)

The P-function is constructed only of XOR
components and is a linear transformation from 8
input bytes to 8 output bytes. The S-functionM(128)x(64)kw1
k 1, k 2,k 3, k 4,k 5, k 6

kw2
64

64

k1

64

64

Fk2

FL-1

FL

kl2

k 7, k 8,k9, k10,k11, k12

z-1

z-1

z-1

z-1

z-1

z-1z-1

z-1

z-1

z-1

z-1

z-1

z-1

z-1

z-1

S2

S1
F

kl1

z-1

z-1

z-1

S2

S4
z-1

z-1

S3
z-1

S4
z-1

S1
z-1

z-1

k3
Fk4

z-1
Fkl3

S3

FL-1

FL

kl4

z-1
z-1k5)

z-1

Fk13, k14,k15, k4,k 5, k 6

z-1

k6

z-1
z-1
z-1

F

kw4

kw3
C(128)

z-1

z-1

z-1

z-1

z-1

z-1

z-1

z-1

Figure 1. Top-level procedure of Camellia(left-hand side) showing inner structure of 6Rounds (right-hand side)
K(128)y(64)FFigure 3. Sub-Pipelined F-Function

Σ1(64)
Σ2(64)
FK(128)Σ3(64)F
Σ4(64)

FKA(128)

Figure 2. Key schedule architecture forCamellia
represents a substitution using one of 4 s-boxes thatare defined by:
S1(x) = h(g(f(x ⊕ a))) ⊕ b,
S2(x) = S1(x) <<< 1,
S3(x) = S1(x) >>> 1,
S4(x) = S1(x <<< 1),(4)
(5)
(6)
(7)

where f and h are linear mappings, g is an inverse
over GF(28), and a, b are fixed constants.
The Camellia key schedule for a 128-bit keyproduces twenty-six 64-bit subkeys, for use in the18 rounds, pre- and post-whitening and FL/FL-1
function layers. Figure 2 shows the first step thatinvolves deriving a 128-bit variable KA(128) from theoriginal secret key K. Then the second step
involves generating further round keys by cyclic
rotating either K (now KL) or KA by 15 or 17.
The Camellia decryption procedure is exactly
the same as the encryption, it does not have any
inverse functions like with in the AES algorithm,
but the keys are needed in reverse order. So thesubkey that was needed to encrypt the data block inround 18 is now needed to decrypt in round 1. Thiscan cause a delay in the overall decryption process
if the subkeys need to be produced first, before
decryption can take place. This can be overcome
when the decryption receives the pre-computed
subkeys from the sender.

Table 1. Summary of CRYPTREC and NESSIE 128-bit Block Cipher Winners
and Finalists on FPGAs
Key Throughput Efficiency
Algorithm
Authors
DeviceArea
Gbits/sec Mbps/slices
Slices agility(BRAMS)

1Camellia

Authors

XC2Vp50

AES-1281

11,287(88)16938

Zambreno XC2V4000et al. [6]1Rouvroy et XCV1000
6,322
MISTY1al. [7]SHACAL-12
McLoone et XC2V4000 13,729
al. [8]
IDEA2Gonzalez et XCV600
12,026(estimated)al. [9]
RC62
Beuchat
XC2V3000 8,554
[10]
(80)
Hierocrypt-3 3
Rogawski EPF10K130V 25811[11]
LE
CIPHERUNICORN- NEC [12] EP20K1500E 7072 LE
3(66AESB)SC20004
Shimoyama [0.25µm65K
et al. [13] CMOS ASIC gates
3. SUB-PIPELINING ARCHITECTURE
In this section we describe the sub-pipelined
architecture but it includes previous classicalencryption optimisation techniques to increase thealgorithms throughput at the higher level within thealgorithm. These include such optimisations as
unrolling, round pipelining, and transformation
partitioning. The implementation is key agile thus
providing very high security and throughput as new
data blocks can be encrypted on each clock cyclewith a different key.
For the sub-pipelining architecture we have fully
unrolled and added pipelining registers between
each encryption round. We have then also added 5
stages of sub-pipelining shift registers into the FFunction. The registers have been added between
the P-Function, S-Function and the XOR. With apipeline stage also added into the P-Function and aregister at the output of the F-function. Thisarchitecture produces a pipeline delay of 108 clock
1

Included in both CRYPTREC and NESSIE.
Finalists not included in NESSIE portfolio.
3
Implemented on a Altera FPGA device
4
Only able to find ASIC implementation
2

YES

33.25

-

YES

23.57

1.39

YES

19.34

3.06

NO

17.02

1.24NO

8.3

0.69

NO

15.2-

YES

0.397

-

YES

0.044

-

YES0.397-(assumed)(assumed)(assumed)cycles but does not have an effect on throughput.
Further improvements might be made with somealgorithm optimisations or floor planning. Adding
the registers into the P-Function means that thefunction now has a branch number of 3 or 2 insteadof 5 depending on the data path. The architectureof F-Function can be seen in Figure 3 on theprevious page. The registers can be seen inbetween each of the F-function operations.
One other important optimisation techniques
specific for the FPGA architecture is the use ofdual-port block-RAM. Every round has its own
associated F-function, as described earlier, and eachfunction utilises 4 different s-boxes for byte
substitution. Each F-function makes 2 calls to thesame s-box. For this implementation we havechosen to use dual ported block-RAMs for the sboxes.
4. RESULTS
We have implemented the sub-pipelined
architecture on a Virtex-II pro XC2Vp50 device.
The core was designed with Xilinx’s System
Generator, which produced the VHDL andassociated files. The VHDL was synthesised withISE 5.2 and verified with the test vectors that weresubmitted to NESSIE. The core runs at a frequencyof 259MHz that results in a throughput of33.25GBits/sec.
The implementation requires
11,287 slices (47%) of the FPGA and uses 88 blockRAMs (37%). Generally comparisons against otherencryption implementations can be difficult and candepend on architecture, device, embedded coressuch as block-RAM, key agility, on-chip key
scheduling, and other such criteria. Table 1 showsa list of other known high throughput FPGA
architectures for NESSIE and CRYPTREC. Forimplementations that have used block-RAMs wehave not included the efficiency. It is possible tocalculate the extra number of slices that the blockRAMs would occupy if distributed memory was tobe used, but this sort of calculation doesn’t take into
account the extra routing, which would have aneffect on the total throughput and therefore theefficiency.
5. CONCLUSION
In this paper we have presented a sub-pipelined
Camellia implementation that has a throughput of33.25Gbit/sec. Compared to other published FPGA
implementations this is the fastest known
throughput of all block ciphers (128-bit)recommended by NESSIE and CRYPTREC. The
importance of this algorithm has been proved in theopen-call by NESSIE and CRYTREC.
The core is able to receive new secret keys anddata on every clock cycle. We have utilised theavailable dual-port block-RAMs for use in the FFunction and been able to pipeline the algorithm tothe lowest level and then apply this to the FPGA
architecture. The core has a very high throughput
and thus could be used in a secure highperformance computing application. As the coretakes less then 50% of the Virtex 2 pro it might bepossible to put two cores down thus being able toobtain a throughput on one FPGA device of around
66Gbits/sec. This will be part of the work for thefuture.
6. REFERENCES[1] Aoki, K., Ichikawa, T., Kanda, M., Matsui, M.,
Moriai, S., Nakajima, J., Tokita, T.,“Specification of Camellia – 128-bit BlockCipher”,
URL:
http://info.isl.ntt.co.jp/camellia/#Spec,
September 2001.

[2] NESSIE, “NESSIE Project Announces Final
Selection of Crypto Algorithms”, IST-19912324, February 2003.
[3] CRYPTREC,
Information-Technology
Promotion Agency, Japan, “CRYPTREC
Report 2002”,[4] Denning, D., Irvine, J., Delvin, M., “A Key
Agile 17.4Gbit/sec Camellia Implementation”,
proceedings of FPL’04, Antwerp, Belgium,Aug. 2004.
[5] Ichikawa, T., Sorimachi, T., Kasuya, T.,
Matsui, M., “On the Criteria of Hardware
Evalution of Block Ciphers(1)”, Techn reportof IEICE, ISEC2001-53, September 2001.
[6] Zambreno, J., Nguyen, D., Choudhary, A.,“Exploring Area/Delay Tradeoffs in an AES
FPGA Implementation”, proceedings ofFPL’04, Antwerp, Belguim, Aug. 2004.
[7] Rouvroy. G., Standaert, F.X., “Efficient FPGA
Implementation of Blcok Cipher MISTY1”,
proceedings IPDPS’03, France, April 2003.
[8] McLoone, M., McCanny, J. V., “Very High
Speed 17 Gbps SHACAL Encryption
Architecture”, in Proc. Of the 13th Int’lConference on Field-Programmable Logic andits Applications (FPL), Portugal, September
2003.
[9] Gonzalez, I., Lopez-Buebo, S., Gomez, F. J.,
Martinez, J., “Using Partial Reconfiguration in
Cryptographic
Applications:
AnImplementation of the IDEA Algorithm”, inProc. Of the 14th Int’l Conference on FieldProgrammable Logic and its Applications(FPL), Portugal, September 2003.
[10] Beuchat, J. L., “FPGA Implementations of theRC6 Block Cipher”, in Proc. Of the 13th Int’lConference on Field-Programmable Logic andits Applications (FPL), Portugal, September
2003.
[11] Rogawski, M., “Analysis of Implementation
Hierocrypt-3 Algorithm (and its comparison toCamellia algorithm) using ALTERA devices”,
Electronic Edition, CoRR cs CR/0312035,
2003.
[12] NEC Corporation, “Self Evaluation Report –CIPHERUNICORN-A”, unpublished date.
[13] Shimoyama, T., Hitoshi, Y., Kazuhiro, Y.,
Takenaka, M., Itoh, K., Yjima, J., Torii, N.,Tanaka, H., “Specification and Supporting
Document of the Block Cipher SC2000”, IST199-12324, February 2003.