Camellia

  • Block length = 128 bits
  • Key length = 128, 192 or 256 bits

The cipher was developed in Japan by Mitsubishi and NTT companies in 2000. It was later approved by the International Organization for Standardization (ISO), the European Union's NESSIE project and the Japanese CRYPTREC project.

Usage

Camellia was designed to be efficient for both software and hardware implementations and it is used in various devices from low-cost smart cards to high-speed network protocols.

Algorithm

Camellia is a symmetric block cipher with secret key of size of 128, 192 or 256 bits. The length of plaintext and ciphertext blocks is always equal to 128 bits.

In the following description, the original names of variables and functions the Camellia documentation are used to describe its algorithm.

The most importnt elements of the algorithm are F-functions. They are used during encryption, decryption and creating helper variables of the key. The F-function takes 128 input bits, mixes them with bits of subkeys ki and returns 128 new bits. Modification of bits in the F-function is referred to as one round of the algorithm. F-function calls are gathered in blocks. Each block contains six rounds.

Six-round blocks (that means block of six calls of  the F-function) are separated by calls of FL-functions and FL-1-functions. They manipulate 64-bit long parts of data and mix them with subkeys kli.

Both encryption and decryption algorithms are about to perform some repetitions of the 6-round blocks described above. The number of repetitions depends on the length of the currently used secret key:

  • 3 repetitions of the 6-round blocks - for the 128-bit secret key,
  • 4 repetitions of the 6-round blocks - for the 192-bit or 256-bit secret keys.

Furthermore, at the beginning and at the end of both encryption and decryption algorithms, additional operations are performed: data bits are added to bits of subkeys kwi.

Subkeys, which are used to encrypt each data block (or to decrypt each ciphertext block), are created in the separate process. Tens of subkeys are calculated from the secret key for each block. They are used for various operations in the main algorithm.

Key schedule

The secret key using in the Camellia cipher can consist of 128, 192 or 256 bits. In order to encrypt data blocks, one have to create a few helper variables and then subkeys, based on secret key bits. Each subkey is 64-bit long.

At first, one should calculate two variables of size of 128 bits (KL and KR) and four variables of size of 64 bits (KLL, KLR, KRL and KRR). The following equations describe connections between those variables:

  • KLL = 64 left bits of KL
  • KLR = 64 right bits of KL
  • KRL = 64 left bits of KR
  • KRR = 64 right bits of KR

The rest of connections should be determined based on the length of the secret key K.

  • for the 128-bit long key:
    • KL = K
    • KR = 0
  • for the 192-bit long key:
    • KL = 128 left bits of K
    • KRL = 64 right bits of K
    • KRR = ~KRL (negation of bits)
  • for the 256-bit long key:
    • KL = 128 left bits of K
    • KR = 128 right bits of K

Then, it is possible to calculate two new helper variables: KA and KB, based on the previous ones. They are both 128-bit long. KB is nonzero if and only if the secret key consists of 192 or 256 bits. While creating KA and KB one should use six help constant values, which are referred to as ∑i.

At the end, based on four 128-bit long just created variables KL, KR, KA and KB, one should compute all secret subkeys of size of 64 bits: ki, kwi and kli. Subkeys are used in all the steps during encryption and decryption in the Camellia algorithm.

Block Diagram of Camellia Encryption for 128-bit Key

Scheme of encryption for 128-bit key

Block Diagram of Camellia Encryption for 192 or 256-bit Key

Scheme of encryption for 192 or 256-bit key

Block Diagram of Camellia Decryption for 128-bit Key

Scheme of decryption for 128-bit key

Block Diagram of Camellia Decryption for 192 or 256-bit Key

Scheme of decryption for 192 or 256-bit key

Block Diagram of Camellia 6-round Block

Scheme of 6-round block

Block Diagram of Camellia - Creating Helper Variables of Key

Scheme of creating variables Ka and Kb

Maths:

Camellia uses a few basic bitwise operations: bitwise AND, bitwise OR, exclusive OR (XOR), logical negation on all bits and left circular rotation of the operand by n bits: <<< n (leftmost bits move to rightmost positions of the variable).

Beyond those operations, there are defined some more complex functions. They are used during encryption and decryption processes, and during creating subkeys.

S-function

S-function is used inside the F-function. The input data of size of 64 bits are substituted by other 8 bytes, which are returns for further processing.

The function uses four substitution tables. They are referred to as s-boxes.

The input data is divided into eight separate bytes x1,...,x8. x1 contains eight leftmost bits, x2 contains eight next bits and x8 contains eight last rightmost bits.

Every of the s-blocks changes eight received bits into eight other bits indicated by the table. The four s-blocks are referred to as s1,...,s4. If y1,...,y8 are the eight subsequent output bytes (the byte y1 contains leftmost input bits, y8 contains rightmost output bits), modifications performed by the S-function can be defined as:

    y1 = s1(x1)
    y2 = s2(x2)
    y3 = s3(x3)
    y4 = s4(x4)
    y5 = s2(x5)
    y6 = s3(x6)
    y7 = s4(x7)
    y8 = s1(x8)

s-box s1 contains 256 following numbers:

11213044236179 3919222922813387532341217465
3523910714769251653323714797829101146189
13418417514312423531206624822095941971126
16622557202213719361217 190214818610877
1391315410225120417645116184332240177132153
2237620319452126118 51091831694920923 4215
20885897222271728501515622832424234
2546820717819518112214536 82321689625210580
17020816012516113798151849130149224255100210
16196 072163247117219138 3230218 963221148
13592131 22057414451115103246243157127191226
8215521638200551985912915011175191909946
233121167140159110188142412452491824725318089
120152 6106231701131862123717166136162141250
114 718585248238172105473421046056241164
64402111231872016719321227173244119199128158

S-blocks return values determined by the one-byte input number. All cells in the table are numbered from 0 to 255, from left to right and from top to bottom. For example s1[0] is equal to 112, s1[1] is equal to 130, and s1[255] is equal to 158.

The remaining three s-boxes can be also defined as tables of 256 numbers. Alternatively, their substitutions can be defined as operations on s1, with changed input data:

    s2(x) := (s1(x) <<< 1)
    s3(x) := (s1(x) >>> 1)
    s4(x) :=   s1(x<<<1)

P-function

P-function is used inside the F-function. P-function takes input data of size of 8 bytes (which are output bytes of the S-function), modifies them and returns the vector, which is also 8-byte long. Output data of the P-function is also output data of the F-function.

The input data is divided into eight separate bytes x1,...,x8. The byte x1 contains leftmost eight bits, x2 next eight bits, and x8 contains rightmost eight bits.

If y1,...,y8 are the eight subsequent output bytes (y1 contains eight leftmost bits, y2 next eight bits, and y8 contains rightmost eight output bits), modifications performed by the P-function can be defined as:

    y1 = x1 XOR x3 XOR x4 XOR x6 XOR x7 XOR x8
    y2 = x1 XOR x2 XOR x4 XOR x5 XOR x7 XOR x8
    y3 = x1 XOR x2 XOR x3 XOR x5 XOR x6 XOR x8
    y4 = x2 XOR x3 XOR x4 XOR x5 XOR x6 XOR x7
    y5 = x1 XOR x2 XOR x6 XOR x7 XOR x8
    y6 = x2 XOR x3 XOR x5 XOR x7 XOR x8
    y7 = x3 XOR x4 XOR x5 XOR x6 XOR x8
    y8 = x1 XOR x4 XOR x5 XOR x6 XOR x7

F-function

F-function is on of the main functions. It is used during encryption and decryption processes, and during creating subkeys. The input data X of size of 64 bits are mixed with one of the subkeys k (also 64-bit long). The function returns a 64-bit long output block Y.

Data bits are added XOR to key bits and the result is modified by two functions S and P.

    (X, k) -> Y  =>  P (S (X XOR k)) -> Y

FL-function

FL-function is used during both encryption and decryption processes. It takes 64-bit long input data and one of the subkeys, then it performs some modifications and finally it returns a block of data, which contains also 64 bits.

An input data block is referred to as X, while Y is a 64-bit long output block. kl is one of the subkeys created before:

    (X, kl) -> Y  =>  (XL || XR, klL || klR) -> YL || YR

At the beginning X is divided into two 32-bit long parts: XL contains 32 left bits of X, and XR contains 32 right bits of X. Then, two new blocks (each 32-bit long) are calculated:

    YR = ((XL AND klL) <<< 1) XOR XR
    YL = (YR OR klR) XOR XL

YL contains 32 left output bits of the FL-function, and YR contains 32 right output bits.

FL-1-function

FL-1-function is used during both encryption and decryption processes. It takes 64-bit long input data and one of the subkeys, then it performs some modifications and finally it returns a block of data, which contains also 64 bits.

An input data block is referred to as X, while Y is a 64-bit long output block. kl is one of the subkeys created before:

    (Y, kl) -> X  =>  (YL || YR, klL || klR) -> XL || XR

At the beginning Y is divided into two 32-bit long parts: YL contains 32 left bits of Y, and YR contains 32 right bits of Y. Then, two new blocks (each 32-bit long) are calculated:

    XL = (YR OR klR) XOR YL
    XR = ((XL AND klL) <<< 1) XOR YR

XL contains 32 left output bits of the FL-1-function, and XR contains 32 right output bits.

The key schedule constants

During creating subkeys in encryption and decryption processes, one should use six constant predefined values, commonly referred to as i.

The values below are 64-bit long and they are presented in hexadecimal.

1 = 0xA09E667F3BCC908B
2 = 0xB67AE8584CAA73B2
3 = 0xC6EF372FE94F82BE
4 = 0x54FF53A5F1D36F1C
5 = 0x10E527FADE682D1D
6 = 0xB05688C2B3E6C1FD

Creating Subkeys

Using four 128-bit long variables KL, KR, KA and KB one should calculate subkeys ki, kwi and kli (all subkeys have 64 bits).

The table for creating subkeys for the secret key of size of 128 bits:

subkey received value where used
kw164 left bits KLat the beginning
kw264 right bits KLat the beginning
k164 left bits KAF (round 1)
k264 right bits KAF (round 2)
k3 64 left bits (KL <<< 15)F (round 3)
k4 64 right bits (KL <<< 15)F (round 4)
k5 64 left bits (KA <<< 15)F (round 5)
k6 64 right bits (KA <<< 15)F (round 6)
kl1 64 left bits (KA <<< 30)FL
kl2 64 right bits (KA <<< 30)FL-1
k7 64 left bits (KL <<< 45) F (round 7)
k8 64 right bits (KL <<< 45) F (round 8)
k9 64 left bits (KA <<< 45) F (round 9)
k10 64 right bits (KL <<< 60) F (round 10)
k12 64 left bits (KA <<< 60) F (round 11)
k12 64 right bits (KL <<< 60) F (round 12)
kl3 64 left bits (KL <<< 77) FL
kl4 64 right bits (KL <<< 77) FL-1
k13 64 left bits (KL <<< 94) F (round 13)
k14 64 right bits (KL <<< 94) F (round 14)
k15 64 left bits (KA <<< 94) F (round 15)
k16 64 right bits (KA <<< 94) F (round 16)
k17 64 left bits (KL <<< 111) F (round 17)
k18 64 right bits (KL <<< 111) F (round 18)
kw3 64 left bits (KA <<< 111) at the end
kw4 64 right bits (KA <<< 111) at the end

The table for creating subkeys for the secret keys of size of 192 bits and 256 bits:

subkey received value where used
kw1 64 left bits KLat the beginning
kw264 right bits KLat the beginning
k1 64 left bits KBF (round 1)
k2 64 right bits KBF (round 2)
k3 64 left bits (KR <<< 15)F (round 3)
k4 64 right bits (KR <<< 15)F (round 4)
k5 64 left bits (KA <<< 15)F (round 5)
k6 64 right bits (KA <<< 15)F (round 6)
kl1 64 left bits (KR <<< 30)FL
kl2 64 right bits (KR <<< 30)FL-1
k7 64 left bits (KB <<< 30) F (round 7)
k8 64 right bits (KB <<< 30) F (round 8)
k9 64 left bits (KL <<< 45) F (round 9)
k10 64 right bits (KL <<< 45) F (round 10)
k12 64 left bits (KA <<< 45) F (round 11)
k12 64 right bits (KA <<< 45) F (round 12)
kl3 64 left bits (KL <<< 60) FL
kl4 64 right bits (KL <<< 60) FL-1
k13 64 left bits (KR <<< 60) F (round 13)
k14 64 right bits (KR <<< 60) F (round 14)
k15 64 left bits (KB <<< 60) F (round 15)
k16 64 right bits (KB <<< 60) F (round 16)
k17 64 left bits (KL <<< 77) F (round 17)
k18 64 right bits (KL <<< 77) F (round 18)
kl5 64 left bits (KA <<< 77) FL
kl6 64 right bits (KA <<< 77) FL-1
k19 64 left bits (KR <<< 94) F (round 19)
k20 64 right bits (KR <<< 94) F (round 20)
k21 64 left bits (KA <<< 94) F (round 21)
k22 64 right bits (KA <<< 94) F (round 22)
k23 64 left bits (KL <<< 111) F (round 23)
k24 64 right bits (KL <<< 111) F (round 24)
kw3 64 left bits (KB <<< 111) at the end
kw4 64 right bits (KB <<< 111) at the end

Implementation

On the website of NTT Corporation you can find source codes and detailed descriptions of the Camellia cipher:
    info.isl.ntt.co.jp/crypt/eng/camellia