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 from the Camellia documentation are used to describe its algorithm.

The most important 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 k_i 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 kl_i.

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 kw_i.

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 used in the Camellia cipher can consist of 128, 192 or 256 bits. In order to encrypt data blocks, one has 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 (K_L and K_R) and four variables of size of 64 bits (K_LL, K_LR, K_RL and K_RR). The following equations describe connections between those variables:

• K_LL = 64 left bits of K_L
• K_LR = 64 right bits of K_L
• K_RL = 64 left bits of K_R
• K_RR = 64 right bits of K_R

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

• for the 128-bit long key:
  • K_L = K
  • K_R = 0
• for the 192-bit long key:
  • K_L = 128 left bits of K
  • K_RL = 64 right bits of K
  • K_RR = ~K_RL (negation of bits)
• for the 256-bit long key:
  • K_L = 128 left bits of K
  • K_R = 128 right bits of K

Then, it is possible to calculate two new helper variables: K_A and K_B, based on the previous ones. They are both 128-bit long. K_B is nonzero if and only if the secret key consists of 192 or 256 bits. While creating K_A and K_B 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 K_L, K_R, K_A and K_B, one should compute all secret subkeys of size of 64 bits: k_i, kw_i and kl_i. Subkeys are used in all the steps during encryption and decryption in the Camellia algorithm.

Block Diagram of Camellia Encryption for 128-bit Key

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

Block Diagram of Camellia Decryption for 128-bit Key

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

Block Diagram of Camellia 6-round Block

Block Diagram of Camellia - Creating Helper Variables of Key

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 returned 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 x₁,...,x₈. x₁ contains eight leftmost bits, x₂ contains eight next bits and x₈ 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 s₁,...,s₄. If y₁,...,y₈ are the eight subsequent output bytes (the byte y₁ contains leftmost input bits, y₈ contains rightmost output bits), modifications performed by the S-function can be defined as:

y₁ = s₁(x₁)
y₂ = s₂(x₂)
y₃ = s₃(x₃)
y₄ = s₄(x₄)
y₅ = s₂(x₅)
y₆ = s₃(x₆)
y₇ = s₄(x₇)
y₈ = s₁(x₈)

s-box s₁ contains 256 following numbers:

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 s₁[0] is equal to 112, s₁[1] is equal to 130, and s₁[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 s₁, with changed input data:

s₂(x) := (s₁(x) <<< 1)
s₃(x) := (s₁(x) >>> 1)
s₄(x) := s₁(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 x₁,...,x₈. The byte x₁ contains leftmost eight bits, x₂ next eight bits, and x₈ contains rightmost eight bits.

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

y₁ = x₁ XOR x₃ XOR x₄ XOR x₆ XOR x₇ XOR x₈
y₂ = x₁ XOR x₂ XOR x₄ XOR x₅ XOR x₇ XOR x₈
y₃ = x₁ XOR x₂ XOR x₃ XOR x₅ XOR x₆ XOR x₈
y₄ = x₂ XOR x₃ XOR x₄ XOR x₅ XOR x₆ XOR x₇
y₅ = x₁ XOR x₂ XOR x₆ XOR x₇ XOR x₈
y₆ = x₂ XOR x₃ XOR x₅ XOR x₇ XOR x₈
y₇ = x₃ XOR x₄ XOR x₅ XOR x₆ XOR x₈
y₈ = x₁ XOR x₄ XOR x₅ XOR x₆ XOR x₇

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 => (X_L || X_R, kl_L || kl_R) -> Y_L || Y_R

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

Y_R = ((X_L AND kl_L) <<< 1) XOR X_R
Y_L = (Y_R OR kl_R) XOR X_L

Y_L contains 32 left output bits of the FL-function, and Y_R 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 => (Y_L || Y_R, kl_L || kl_R) -> X_L || X_R

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

X_L = (Y_R OR kl_R) XOR Y_L
X_R = ((X_L AND kl_L) <<< 1) XOR Y_R

X_L contains 32 left output bits of the FL^-1-function, and X_R 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.

Creating Subkeys

Using four 128-bit long variables K_L, K_R, K_A and K_B one should calculate subkeys k_i, kw_i and kl_i (all subkeys have 64 bits).

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

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

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