Abstract
Hybrid cubes are generated from a combination and permutation of integers as shown in Latin squares and orthogonal Latin squares. In this paper we extend our earlier non binary block cipher using all possible combination of hybrid cubes layers as the source for the encryption and decryption keys. The overall security of the cipher is improved with the inclusion of substitution box (SBOX) and diffusion functions. The experimental results indicate that the proposed generator matrices from hybrid cubes layers are suitable as candidate for a key schedule algorithm. Large key space will make brute force attack on the key space difficult and time consuming.
Keywords: Non binary cipher; Block cipher; Hybrid cubes.
Introduction
Fast advancement of computer systems and telecommunications infrastructure indirectly boosts the need for ensuring the secrecy of transmitted data using reliable and secure protection mechanisms. Ciphers become an important technique for protecting the secrecy of messages can be dated back as early as in the mid-19th century with the advancement of telegraphy. Currently, ciphers offer higher level of security for modern digital transmission because it provides the flexibility for the user to change the encryption keys regularly as compared to the use of a codebook [1].
Permutation of a finite set of numbers or symbols plays an important role in the development of block ciphers as shown in [2],[3],[4],[5],[6] and [7]. In simple transposition cipher [2], permutation is used to mix up symbols or numbers to create ciphertext. This technique preserved the number of symbols or number of a given type within a block which make it easy to be analyzed by cryptanalyst if the block size is small. Development of efficient computer hardware and software make permutation only algorithm more prone to attack by cryptanalysts. Modern binary based cryptographic algorithms such as Rijndael, Twofish, SAFER+ [9] used combination of substitution and transposition to enhance the complexity of the ciphertext. Substitution creates confusion in the ciphertext to avoid attack just by applying simple permutation of symbols to get the encryption or decryption keys. Substitution Boxes or SBoxes are used as confusion element in Rijndael [3] and Twofish [4]. Diffusion function for binary ciphers such as MDS and PHT are used in Rijndael and Twofish, respectively. A non binary block cipher, on the other hand, is a block cipher that use integer as a block. In non binary cipher, the message, ciphertext and keys exist in the decimal form {0, •••, 9}as appears in TOY100 [6], DEAN18 [7] and A Large Block Cipher [8]. These ciphers provide an alternative to the existing binary block ciphers. Meanwhile, TOY100 [6] is used to encrypt 32 decimal digits. The diffusion function for TOY100 consists of two similar components called MixColumns and MixRows. MixColumns is performed by applying Mix function to each column and MixRows when applying Mix function to each row in the matrix. These two functions provide diffusion to the decimal ciphertext. DEAN18 is also used to encrypt 18 decimal numbers and has a fixed bijective substitution box (S-Box) which is used to provide non linear relation between the message and the ciphertext [7]. The application of S-Box is based on the mapping of an element (a, b)e Z^ which is represented as integer 10* a + b e [0,99]on each 2-digit element of the ciphertext. In this paper we extend our earlier proposed algorithm [10] to include the confusion and diffusion functions in the encryption algorithm, key schedule algorithm based on hybrid cubes of order 4 and decryption algorithm. The overall security of the cipher is improved with the inclusion of substitution box (SBOX) and diffusion functions. The experimental results indicate that the proposed generator matrices from hybrid cubes layers are suitable as candidate for a key schedule algorithm. Furthermore, large key space will make brute force attack on the key space difficult and time consuming.
The rest of the paper is organized as follows: Section 2 describes the construction of hybrid cubes from combination and permutation of integer numbers. Section 3 outlines the proposed Hybrid Cubes Encryption Algorithm (HiSea) which consists of key schedule algorithm, encryption algorithm and decryption algorithm. Section 4 discusses the experimental result. Section 5 presents conclusion and future work of this research.
Construction of Hybrid Cubes
Series of permutation and combination of a set of integers {l, 2, 3, 4} is used as the foundation for constructing all 576 Latin squares of order 4. All these Latin squares are then used to construct 3,456 pairs of orthogonal Latin squares. The existence of 880 Magic squares of order 4 was available in [11]. Adopting Trenkler’s formulation [12], we can then construct Magic cubes where layers entries fall within the set of integers {1, 2,—,63, 64}. Using layers of magic cubes, we developed a new cube structure called hybrid cube where layers entries within a set of integers {1, 2, —,4095, 4096} [10]. This new combination of layer entries can be used to add complexity in the design of our encryption algorithm. Furthermore, all layers of this hybrid cube are invertible, which can be used as the decryption keys for our new design.
The following sub-section will discuss each step for construction hybrid cubes.
Latin Squares of Order 4
A Latin square of order n is an n x n matrix where each element can occur exactly once in each row and column as defined in Definition 1.
Definition 1 ([See 13]). A Latin square of order n, denoted as
is a two dimensional (n x n) matrix such that every row and every column is a permutation of the set of natural number (1,—, n}.
Thus, a Latin square is a square array in which each row and column consists of the same set of entries without repetition. Based on Definition 1, Latin squares of order 4 are generated using series of combination and permutation of (1,2,3,4} as described in the following steps.
a. Generate all possible combination of (1, 2,…, 24} with 4 elements which are used as an index for selecting possible sequence for generating Latin squares of order 4.
b. Generate permutation of the set (1, 2, 3, 4}. This permutation is then used to build entries for constructing Latin square of order 4.
c. Generate permutation for each entry in step 1 and used this as an index to select and sort entry based on columns in step b. This step will generate all possible combination of 4-by-4 matrices.
d. Select only matrices where intersection between all rows and columns with standard set (1, 2, 3, 4} will result in unique matrix with entries values of all 4′s. This unique characteristic of Latin square as in Definition 1 is used to select Latin square in our implementation.
e. This method will generate 576 Latin square of order 4 which can be used to generate orthogonal Latin squares.
Only Latin square matrices are selected in this process and otherwise are excluded because the intersection of row and column does not give a unique matrix with entries values of all 4′s.
Orthogonal Latin Squares of Order 4
Definition 2 ([See 13]). Two Latin squares,
are said to be orthogonal if whenever
are such that
Thus, two Latin Squares
order n are said to be orthogonal if and only if the
are all different.
The following steps are used for generating orthogonal Latin squares as in Definition 2.
a. Compare Latin square L1 with Latin square L2.
b. Calculate the new entries for superimposed Latin square using the following formula
This step is used to create a superimposed matrix where all the entries are based on combination of entries from two Latin squares. c. Check if there are orthogonal (superimposed of two Latin squares should give unique elements of the set
Superimposed matrix with element similar to this set is used for find orthogonal Latin square of order 4. d. Repeat these steps for all the Latin square generated in sub-section 2.1.
For example, a superimposed matrix (S) of the following Latin squares L1 and L2 is produced using the formula in step b.
Each element in matrix S is then compared for uniqueness because an orthogonal Latin square should produce sixteen unique entries of the following set
In matrix S, all elements are similar to the above set. This result indicates that L1 and L2 are orthogonal.
Magic Square of Order 4
Magic square is described as in definition 3.
Definition 3 (See [13]). A magic square of order n, denoted as
is a two dimensional n x n matrix (square table) containing the natural numbers 1,—, n2 in some order such that the sum of the number along every row, column and main diagonal is a fixed constant of
A complete list of Magic squares of order 4 is adopted from [11].
Magic Cubes
Magic cube of order
can be viewed as layers of (n x n) matrices which elements are permutation of numbers in
magic cube of order 4 can be sub-divided into fifty-two columns:
a. sixteen horizontal columns from the front to the back
b. sixteen vertical column from the top of the cube to the bottom
c. sixteen horizontal columns from right to left, and
d. four main diagonal columns uniting the four pairs of opposite corners.
Adopting similar approach as in [14], we can sub-divided magic cube of order 4 using layers (group of four columns) as appear in [15]. Using axis (i, j, k) as the reference point, we can have twelve different layers. These 12 layers can be used to form twelve (4×4) matrices which elements are in {1,…,n3}. These layers can be generalized into triple matrices (a, b, c ) where A is based on i layers, B is based on j layers and C on the kth layers respectively. Using this method, there exist eight matrices with similar column values which occur in the diagonal intersection between axis j and axis k as defined below:
Definition 4. Grouping of "magic cube" of order 4 into layers based on axis i, j and k will resulted in similar columns values when values of coordinates (j = k) with (i = 1, — ,4) as follow:
The development of hybrid cubes is form using inner matrix multiplication of elements, we omitted layers based on axis k and only use eight layers from axis i and axis j to generate unique hybrid cube.
Hybrid Cubes [See [10]]
Hybrid cube is formed using inner matrix multiplication of layers between two "magic cubes". For example, hybrid 1 is based on inner matrix multiplication of layer in the same coordinate (i = 1,2,3,4) of "magic cube" 1 and layer (i = 1,2,3,4) of "magic cube" 2. Hybrid cube 2 is based on matrices multiplication of cubes 2 and 3, and so on.
Hybrid Cubes Encryption Algorithm (HiSea)
The implementation of Hybrid Cubes Encryption Algorithm consists of three algorithms: key schedule, encryption and decryption algorithms. The detail design of each algorithm is described in the following sub-section.
Key Schedule Algorithm
Hybrid cubes generated from Section 2.5 is used to construct Key Table as depicted in Figure 1.
|
Rows/ Column |
1 – 4 |
5 – 8 |
9 – 12 |
13 -16 |
|
1 – 4 |
H1L1 |
H1L2 |
H1L3 |
H1L4 |
|
5 – 8 |
H2L1 |
H2L2 |
H2L3 |
H2L4 |
|
9 – 12 |
H3L1 |
H3L2 |
H3L3 |
H3L4 |
|
13 – 16 |
H4L1 |
H4L2 |
H4L3 |
H4L4 |
|
((n*4)-3) -(n*4) |
HnL1 |
HnL2 |
HnL3 |
HnL4 |
Fig. 1. Structure of Key Table
Based on Figure 1, hybrid cube layers are ordered based on rows and column. For example, Hybrid Cube layer 1 is placed in row 1 to row 4, column 1 to 4 for layer 1, column 5 to 8 for layer 2, column 9 to 12 for layer 3 and column 13 to 16 for layer 4, respectively. This process is repeated for all other 30,000 hybrid cubes. Master key for the encryption is selected from Key Table based on values of password (secret integer number) entered by the user. A step for obtaining master key is described below.
a. Calculate the first values of the seed based on (modulo 30000) + 1 and an index for accessing key table is calculated using the second value (modulo 4) + 1. For our implementation, 30,000 hybrid cubes are used for the construction of the Key Table.
b. The first value is to locate the row number of Key Table.
c. The second value is for the column number of Key Table.
d. Extract master key from key table using row and column numbers.
Four sub-keys for the encryption algorithm are generated using the following simple steps :
a. Sub-Key1 = apply permutation 1 to master key.
b. Sub-Key2 = apply permutation 2 to master key.
c. Sub-Key3 = apply permutation 3 to master key.
d. Sub-Key4 = apply permutation 4 to master key.
Permutation 1 to 4 are based on rows and column permutation as applied in Arkin et al. [16] for defining orthogonality of Latin cubes based on relation among three cubes or in general among k Latin k-cubes. These sub-keys are used to encrypt message 1 (M1) to message 4 (M4) in the encryption algorithm.
Encryption Algorithm
The overall design for the encryption algorithm is depicted in Figure 2. In the encryption process, messages, keys and ciphertext are formatted in (4 x 4) matrix . In our design, the intermediate result (message 1′) for message 1 is used in the process of encrypting message 2. Intermediate result (message 2′) for message is used in the process for encrypting message 3. This process is repeated with message 4. Primary reason for incorporating this technique is to ensure that any changes to message 1 is reflected in the other ciphertext, thus introduce complexity to the overall ciphertext. The ciphertext diffusion is perform using MixRow and MixCol from T0Y100 [5] while confusion from SBox of DEAN18 [7]. The ADDITION and MULTIPLICATION of matrices are similar as in [10].
Fig. 2. Encryption Algorithm
Decryption Algorithm
In decryption algorithm, Inverse SBox, Inverse MixRow and Inverse MixCol, Inverse K1 to K4 are used to get the original message from Ciphertext 1 (C1) to ciphertext 4 (C4).
Experimental Result and Discussion
For our approach, we demonstrate the experimental result of HiSea by encrypting the following message:
Using integer 298765 as the password. The message is formatted into four (4 x 4) matrices. The matrices
(Character ‘X’ (ASCII character of 88) are padded to the message if the message is less than 64 characters).
The following ciphertexts
are obtained from the encryption algorithm.
Based on the results from the ciphertext C1 to C4 and the key schedule algorithm are then evaluated using brute force attack and entropy which are described in the following sub-sections.
Brute Force Attack
The encryption keys used in this algorithm is represented as a 4 x 4 matrix of integer numbers with each entry is an integer of 212 bits. The key space for encryption and decryption keys are
or approximately
This large key space will make brute force attack on the key space difficult and time consuming.
Entropy
We can evaluate the randomness of the session keys and the ciphertext using entropy [17]. Table 1 shown the result of entropy for Initial Matrix (IM), session keys and ciphertext.
Table 1. Entropy for session keys and ciphertext
|
Items |
Entropy (H) |
|
Initial Matrix (IM) |
0.8199 |
|
Session keys |
0.8632 |
|
Ciphertext 1 (C1) |
0.9477 |
|
Ciphertext 2 (C2) |
0.8382 |
|
Ciphertext 3 (C3) |
0.9447 |
|
Ciphertext 4 (C4) |
0.8658 |
From Table 1, the entropy for all session keys are 0.8632. This result indicates that session keys generated using hybrid cubes are 86.32% random. Initial Matrix (IM) which is used to mix message 1 in the encryption process has entropy of 0.8199 or 81.99% random. These key components create a ciphertext which is more than 83% random. Our experimental results indicate that ciphertext block which consists of sixteen decimal numbers are on average 0.8991 or 89.99% random which hides the relationship between message, key and the ciphertext.
Conclusion
In this paper, we have developed our earlier algorithm [10] using 3,456 orthogonal Latin squares of order 4 and 880 magic squares to generate magic cubes. These magic cubes are then used to generate hybrid cubes which are used for the key schedule algorithm. The entropy of encryption keys are more than 85% random which can be used to strengthen our encryption algorithm. The inclusion of a confusion function and diffusion functions increase the randomness of the ciphertext up to 89.99%. The result of this research can be further analyzed in the future against Linear Cryptanalysis, Differential Cryptanalysis and other suitable cryptanalysis for decimal ciphertext.
