# A new orthogonal cryptographic system for database security based on Cellular automata and Hash Algorithm.

I. INTRODUCTIONDatabase security is the most important issue of cloud computing, information sharing and processing where many users are assigned to share the same information stored on the distributed networks or database servers. Although there are many security checks and authentication techniques to identify the users before they are allowed to access the data centers or database servers but yet the unauthorized users and hackers can always find a way to bypass all these security checks and illegally access the database. The multilayer encryption is one the best ways to secure the contents of database table and prevent the access of the illegal users from the original data even they have reached to the core of data centers.

They are several different encryption techniques that have been used for database security but none of them have used three levels of security as we applied. In addition we have applied another algorithm called Malakooti-Bazofti Hash algorithm to generate a unique Tag or Hash pattern for the entire database content to be compared with previous stored Tag. If the new Tag is different from the previous Tag, then the system will activate the Attack Alarm and informs the administrator via SMS or Email.

The idea of securing databases using cryptographic system is not new and several researchers have proposed new techniques for the database encryption. Gudes, Koch and Stahl [1] have presented anew method for database encryption based on substitution, transposition,

Reduction and expansion of data items but it preserves data structures. Davida, Wells and Kam [2] have proposed an encryption technique based on the Chinese Remainder Theorem in which some algebraic operation are performed on the content of database and each records are encrypted by applying some mathematical operations. The encrypted data also can be decrypted by the inverse operation using Chinese remainder theorem. Several other researchers including [3-6] have used Data Encryption Standard (DES) and RSA algorithm to perform the encryption and decryption based on the public and private keys as well as performed the authentication based on the checksums of the data elements and the checksum are obtained from the identifiers and the database key.

Our proposed method for encrypting the database contents is based on the Malakooti Orthogonal Transform in which its orthogonal property can be used to invert the Transformation matrix by Matrix Transpose operation instead of direct calculation of the matrix inversion, during the decryption process. To increase the level of security on the database contents we have obtained the matrix of secret byesby applying the Cellular Automata on the elements of the M-T matrix. Once the secrete key matrix is calculated it will be multiplied with the matrix of coded data elements and finally XOR operation is applied on the resulting elements and the Hash values derived from Hash function applied on the corresponding database records.

In addition to applying three levels of security on database based on the M-T transform, Cellular Automata, and Hash Algorithm, we have generated a Unique Hash pattern or Authentication Tag based on Malakooti-Bazofti (MB) Hash Algorithm, in which the generated Tag can be compared with the stored Tag and Any difference between these two Tags will activate the attack alarm to inform the administrator via SMS or Email. The proposed Attack Alarm Tag will make our cryptographic system unique, robust, reliable, and fully alert in which can be applied for the highly secure database used over the distributed system, cloud computing environment, and internet.

II. MALAKOOTI TRANSFORM ALGORITHM

The Malakooti Transform, M-T, is an orthogonal transform similar to the Hadamard Transform that was developed by Mohammad V. Malakooti in 1987 for the data compression, encryption, and watermarking. Once this transform is applied on the data matrix the resulting coefficients contained useful information about the spectral characteristic of the underlying data matrix and can be used for data transmission, encryption and compression. Many of the databases elements are highly redundant and this transform can be applied to reduce the redundancy and increase the data storage capacity. The optimal selection of M-T coefficients can be used to reconstruct or to represent the desired database elements with less coefficients and resulting in a saving of transmission speed and memory [11].

III. GENERATION OF M-T MATRIX

Assume that the initial value of the first order M-T matrix, [M.sub.0], is equal to one, thus [M.sub.0] = 1, (3.1) and the elements of the second order M-T matrix, [M.sub.1], is formed according to following equation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.2)

Where "a" and "b" are two constant parameters to change the content of M-T Matrices.

The matrix M is a 2 x 2 anti-symmetric unitary matrix

[M.sup.T.sub.1] [M.sub.1] = [M.sub.1] [M.sup.T.sub.1]

= cl, (3.3)

Where the matrix I is a 2 x 2 identity matrix and constant parameters c is equal to the determinant of [M.sub.1]. Thus,

c = [a.sup.2] {1 + [b.sup.2]) (3.4)

Thus, [M.sub.1] inverse is given as

[M.sup.-1.sub.1] = [M.sup.T.sub.1]/c (3.5)

Similarly, the fourth order M-T matrix, [M.sub.2] can be obtained according to (3.6)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.6)

The matrix [M.sub.2] is a 4 x 4 anti-symmetric unitary matrix

[M.sup.T.sub.2] [M.sub.2] = [M.sub.2] [M.sup.T.sub.2] =[C.sup.2] I, (3.7)

where the matrix I is an 4 x 4 identity matrix, c is given in (3-4), and the inverse of [M.sub.2] is calculated according to

[M.sub.2.sup-1] = [M.sup.t.sub.2]/[C.sup.2] (3.8)

Without loss of generality, the [2.sup.k] x [2.sup.k] M-T matrix, can be obtained from

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.9)

And [M.sub.k] inverse is given according to (3.10)

[M.sup.-1.sub.k] = [M.sup.t.sub.k]/[C.sup.k]. (3.10)

Using the Kronecker product notation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (3.11)

Thus, the M-T matrices can written accordingly,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.12)

And

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.13)

Where [M.sup.(2).sub.1] is the Kronecker power 2 of [M.sub.1] and the symbol [cross product] denotes the Kronecker product. Similarly,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.14)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.15)

We can easy generate the elements of the M-T matrices by assuming that a=1, b=2, and expand the idea to get

M-T matrices of size 2, 4, 8, 16, ... recursively as following:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.16)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.17)

The generation of any size M-T matrix can be obtained easily by a recursive equation and it can be multiplied by a data matrix of the same size to obtain the encrypted database with a high speed and accuracy due to its orthogonal property. In addition, we can take advantage the orthogonal property of MT transform matrix and can calculate its inverse by using orthogonal property of the M-T matrix and calculate the inverse by using its matrix transpose rather than direct calculation of the inverse matrix.

One can easily see that M-T matrix has special features that can be used to encrypt the content of database tables with low calculation cost and high accuracy. The process of decryption is also similar to encryption but the inverse of transformation matrix can be obtained via matrix transpose rather than direct inverse calculation. This high speed inverse transformation can decrease the calculation cost ad increase the speed of decryption process[12].

IV. CELLULAR AUTOMATA BASICS

A Cellular Automaton (CA) is a discrete model consists of a regular grid of cells that each cell has finite number of states but usually they holds two states of on and off. The grids are usually considered to be one dimensional or two dimensional but higher order dimension grids also are also possible. The application of CA is in several filed of science and technology including mathematics, physics, biology, and other branches of sciences. In two dimensional CA grids each cell has a few neighborhood cells. If the neighboring cells are located at right side, left side, top, or bottom of the specified cell, they are called Von Neumann Neighborhood in the honor of Von Neumann who worked with Stanislaw Ulam at Los Alamos National Laboratory, New Mexico, USA, 1940.

An initial state of each cell at time t=0 is givens but the new state of each cell at other times, t>0, is calculated based on current state of the cell and the sates of cells in its neighborhood. The mathematical rules for updating the state of all cells are the same and it will not be changed over the time [7].

Given the rule, anyone can easily calculate future states, but it appears to be very difficult to calculate previous states. However, the designer of the rule can create it in such a way as to be able to easily invert it. Therefore, we can say that it is Cleary a trapdoor function, and can be used as a public-key cryptosystem. The security of such systems is not currently known [8].

The idea of Cellular Automata is intuitive and simple, and it consists of a regular grid of cells. Each of which may be in a predetermined number of states. Cell [a.sub.i+1] with the following rule:

Cell [a.sub.i+1] = Cell [a.sub.i-1] + Cell [a.sub.i] (4.1)

Suppose that we have the string of 11010010 and we want to use the above rule such as our cellular automata, then the Generated string will be 10101011. Table-1 shows the Generated string of internal cellular automata rule [9].

V. PROPOSED METHOD

In addition to our suggested method for encrypting the database using Malakooti Orthogonal Transform that applied on the matrix of ASCII values representing the elements of each record in the database, the idea of Cellular Automata also is used.

We have used the mathematical rules of Cellular Automat and applied on the elements of MT matrix to generate the elements of secret key matrix, Kt, that is required to multiply by each row of coded matrix, [M.sub.c], to obtain the elements of the encrypted data matrix, Me, that represents the encrypted version of the corresponding data table.

We also have proposed an entirely fast, secure, and irreversible Hash algorithm to obtain the Hash streams of the each database stored on the server. We have called this method as the Log2 Algorithm, because the log2 of number of records in the database is calculated to divide the entire records in to "N" different groups. Once the number of rows or records in each group is obtained, then our proposed Hash Algorithm based on the consecutive XOR and NOR operations at each stage is calculated.

This approach is repeated so that hashed keys, rows and columns and every database table could be turned into a set of characters so called the Authentication Tag. This Tag can be saved on a safe place that is totally different than places where the databases are stored and it will be used for the database protection and authentication.

VI. HASHING TECHNQUES

The databases are the most valuable resources that are stored on the servers that can be accessed and shared by several clients with different level of privilege, authentication and security. Thus, the confidentiality, protection and maintenance of these valuable resources are highly recommended. Thus, we have proposed and applied several levels of security on the database to obtain the required security on the database servers.

One of the effective technique to protect the database and prevent it from the unauthorized access and illegal manipulation of its contents by the hackers and attackers is to apply the fast, efficient, and robust encryption algorithm to apply several levels of security on the databases and finally use the hash algorithm to obtain the fixed size hash values and store them on severs or send them through distributed network to other servers. Our proposed methods are based on Encryption Algorithm, Cellular Automata, hash function operation and finally calculation of the Hash Value to generate the Authentication Tag.

Hash Value Generation Method

Due to the significance of data accuracy and originality of the available information in each database table, we have proposed the Hash Value, HV, generation algorithm to be applied for each table of the database. This hash value algorithm provide the final hash value as the authentication Tag that is able to detect any unauthorized access and database manipulation while database is unlocked and in protected mode. The new generated hash value will be compared with the old hash value that is stored on the safe location. Once any slight different between these two hashes are reported, the attack alarm flag will be activated and the network administration will be informed via SMS or Email.

Hash Algorithms

1--Calculate the ASCII value of each record and save it into data matrix, Ma.

2--Count the number of records in each database tables, N.

3--Compute the logarithm base 2 of N to get M.

4--Divide the records of each table into M sections.

5--Perform the XOR & NOR operations on the selected records in each group to get level -1 hash operation.

6--Replace the value of N with M, N=M.

7--Perform the operations of steps 3-6 to generate the level- 2 of hash operation.

8--Repeat the operation of steps 3-6 to change all records in to one hash value, Hv, required for the authentication.

The Log2 Algorithm for calculation the Hash Value Input is [a.sub.11], [a.sub.12], ..., [a.sub.n] For I= 2: [log.sub.2.sup.n] + 1 T= n/[2.sup.i]-2 S= n/[2.sup.i]-1 IF T is even Then For j=1 IF I is even Then [a.sub.ij] = [a.sub.i-1,j] XOR [a.sub.i-1,(n-(j-1))] Else [a.sub.ij] = [a.sub.i-1,j] NOR[a.sub.i-1,(n-(j-1))] End Else T is odd For j=1 IF I is even [a.sub.ij] = [a.sub.i-1,j] XOR [a.sub.i-1,(n-(j-1))] [a.sub.is] = [a.sub.i-1,s] Else [a.sub.ij] = [a.sub.i-1,j] NOR [a.sub.i-1,(n-(j-1))] End End End.

VII. KEY GENERATION ALGORITHM

The Generation of secret key matrix is based on the Malakooti-Bazofti(M-B) Algorithm as following:

1--Set the size of M-T Input matrix equal to the number of records in the database, i.e, N = 4, and generate the M-T matrix as following:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

2--Specify the Rule of Cellular Automata for Key generation algorithm, For example, we used this rules for cellular automata:

Cell [a.sub.i+1] = Cell [a.sub.i-1] + Cell [a.sub.i] (7-1)

3--Apply the internal rule of cellular automata on all elements of M-T matrix to get secret key matrix.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

4--Compute the determinant of the key matrix to make sure that key matrix is invertible. Its inversion is required for the decryption process.

5--Generate a new key matrix if the determinant of the key matrix is equal to zero.

The inverse of matrix Kt must exist otherwise the decryption process cannot be performed. One can easily show that possibility of the determinant of Kt to be zero is very low because the rows of database table have different value and chance of the determinant to be zero is very low but it is not impossible.

The Source Code of key Generation Algorithm int u = 0,g; publicvoidKey_Gen_Cellula() { if (u == 0) { for (inti = 0; i<= 7; i++) { for (int j = 0; j <= 7; j++) { g = j; for (int k = j + 1; k <= j + 1; k++) { if (k == 8) {} if (j == 0) { Matrix_KeyGen_Cellula_Data[i, j] = M_Transfer[i, j] + 1; } elseif (j == 7) Matrix_KeyGen_Cellula_Data[i, j] = 1; else Matrix_KeyGen_Cellula_Data[i, j] = M_Transfer[i, g - 1] + M_Transfer[i, k]; } } } for (inti = 0; i<= 7; i++) { for (int j = 0; j <= 7; { Matrix_KeyGen_Cellula_Copy_Data[I,,j] = Matrix_KeyGen_Cellula_Data[i, j]; } } } else { for (inti = 0; i<= 7; i++) { for (int j = 0; j <= 7; j++) { Matrix_KeyGen_Cellula_Data[i,j] = Matrix_KeyGen_Cellula_Copy_Data[i, j]; } } for (inti = 0; i<= 7; i++) { for (int j = 0; j <= 7; { g = j; for (int k = j + 1; k <= j + 1; k++) { if (k == 8) {} if (j == 0) { Matrix_KeyGen_Cellula_Data[i,j] = Matrix_KeyGen_Cellula_Copy_Data[i, j] + 1; } elseif (j == 7) Matrix_KeyGen_Cellula_Data[i, j] = 1; else Matrix_KeyGen_Cellula_Data[i,j] = Matrix_KeyGen_Cellula_Copy_Data[i, g-1] + Matrix_KeyGen_Cellula_Copy_Data[i, k]; } } } for (inti = 0; i<= 7; i++) { for (int j = 0; j <= 7; jtt) { Matrix_KeyGen_Cellula_Copy_Data[i,j] = Matrix_KeyGen_Cellula_Data[i, j]; } } } u++; }

VIII. DATABASE ENCRYPTION ALGORITHM

The encryption algorithm for the records of the database tables is given as following:

1--Read the entire table of database or just read some important column of database tables (fields of database table).

2--Calculate the ASCII code of the records and save them into one matrix.

3--Insert the ASCII code of all records into a matrix called ASCII Code matrix, Ma.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We have obtained an 8*8 Matrix for three rows of the database table.

4--Generate the elements of M-T matrix according to the size of the ASCII matrix.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

5--Multiply the M-T matrix with ASCII code matrix.

Cd = [M.sub.T] * [M.sub.a] (8-1)

6--Set the size of M-T Input matrix equal to the number of records in the database.

7--Generate the secret key matrix by applying the rule of Cellular Automata.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[M.sub.c] = [K.sub.t*] [C.sub.d] (8-2)

8--Multiply the Hash Value of each row obtained from Hash function, [H.sub.f], into the corresponding row of the secret key matrix, [K.sub.t], to get complex secret key values. Apply these keys on each row of [M.sub.c] Matrix to obtain the Encrypted data matrix, Me, that represents the encrypted version of the corresponding data table.

Me= MCXOR([H.sub.f]*Kt) (8-3)

IX. DATABASE DECRYPTION ALGORITHM

The decryption algorithm for the records of the database tables is given as following:

1--Read the content of the encrypted data matrix, Me, that was transformed, encrypted, and Hashed during the encryption process.

2--Apply the XOR operation on Me and ([H.sub.f]*Kt) to get the matrix of M-coding, MC.

[M.sub.C]=Me XOR ([H.sub.f*] x Kt) = [M.sub.C] XOR([H.sub.f*] x Kt) XOR ([H.sub.f*] x Kt) (9-1)

3--The result of above process will transform the encrypted, hashed matrix into the M-coding.

4--Apply the inverse of Kt on the MC matrix to obtain the matrix of coded data.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

5--Apply the inverse of the MT on the Cd matrix to obtain the matrix of ASCII code.

[M.sub.a] = [([M.sub.T]).sup.-1] x [C.sub.d]

= ([M.sub.T]).sup.-1]* [M.sub.T] *[M.sub.a] (9-3)

X. GENERATION OF AUTHENTICATION TAG

In this section we have generated an Authentication Tag Value based on the Malakooti- Bazofti (M-B) Algorithm, in which multiple level of XOR and NOR operations are applied on each group of hash values obtained from the database records. Thus, all hash values that obtained from the records are combined together to obtain a unique hash value require for the database security and authentication. We have proposed a robust and fast algorithm for the database security and authentication that automatically and accurately will generate the Hash values for the entire rows of the database tables to obtain a unique Hash value for each table. This unique hash value can be used to check the validity of the data inside the database and guarantee the authentication of all information in each database. Should any slight change is made on the database while the database is in the protected mode, the generated hash value would be totally different from the stored hash value and the software system automatically will activate the alarm flag to inform the administrator about unauthorized change of database via SMS or Email.

In our proposed method, we have divided each database table into "N" different records and used the concept of parallel algorithm to calculate the Hash values of all records of each table in database as well as to calculate the Hash values of all columns, accurately and efficiently. Once the hash values are calculated, the fast XOR and NOR operations are applied on the generated Hash values to obtain a unique hash values for the Authentication Tag.

XI. CONCLUSION AND FUTURE WORK

The objective of this research is to apply multilevel of security on database and protect the contents of the database tables from the unauthorized users and hackers who tried to access our database illegally and perform the read, write, change operations on the database tables. To obtain the above objectives we have transformed the contents of the database records into to ASCII code and then applied the M-T transform on the ASCII code matrix to calculate the matrix of coded data. The matrix of coded data also will be multiplied by the matrix of secret keys that obtained by applying the rule of cellular automata on the elements of the M-T matrix to calculate the matrix of M-coding. To increase additional level of security on the encrypted data, the hash value of each record of the database is calculate and then multiplied by matrix of secret key to obtain the bit patterns that can be used in XOR operation with the matrix of M-coding to obtain the highly secure encrypted values for the records of the database.

We have proposed a robust and fast algorithm for the database security and authentication that automatically and accurately will generate the Hash values for the entire rows of the database tables to obtain a unique Hash value for each table. This unique hash value can be used to check the validity of the data inside the database and guarantee the authentication of all information in each database.

Should any slight change is made on the database while the database is in the protected mode, the generated Hash value would be totally different from the stored hash value and the software system automatically will activate the alarm flag to inform the administrator about unauthorized change of database via SMS or Email.

Our proposed algorithm applied three levels of security on the database contents and guarantees the security of database tables. It also use the orthogonal property of M-T matrix to obtain its inverse using its transpose rather than the direct inverse calculation, required for the decryption process More work need to done to obtain a fast algorithm to perform the cellular automata for generating the matrix of secret keys.

XII. REFERENCES

[1] E. Gudes, H.S. Koch and F.A. Stahl "The application of cryptography for data base security". Proceedings of AFIPS National Computer Conference, 1976, pp. 97-107.

[2] G.1. Davida, D.L. Wells and J.B. Kam, "A database encryption system with subkeys", ACM Trans. on Database System, Vol. 6, No. 2, June 1981, pp. 312-328.

[3] A. Afyoni "Database Security and Auditing", 2005, Amazon.com.

[4] L. Bouganim, Y.Guo," Database Encryption", Le Chesnay, France, 2009.

[5] L. M. Batten "public key cryptography' application and attacks", 2013, john wily & Sons.

[6] C. Peikariand S. Fogie, Sams, "Wireless maximum security", 2002, Sams.ISBN 0-6723-2488-1.

[7] M. Thomas "Cellular Automata", Nova Science, 2010, ISBN 978-1-62100-148-5(eBook).

[8] T. Ceccherini- Silberstein, Michel Coornaert, "Cellular Automata and Group", Springer, 2010, ISBN 978-3-642-140334.

[9] J. L. Schiff, "Cellular Automata", John Wiley & Sons, 2008, ISBN 978-0-470-10879-0.

[10] A. Mousa, O.S. Faragallah, S. El-rabaie and E M Nigm "Security Analysis of Reverse Encryption Algorithm for Databases", IJCA Journal, 66(14):19-27, March 2013. New York, USA.

[11] S. Kulkarni, S. Urolagin, "Databases and Database Security Techniques", IJETAE, ISSN 22502459, Vol 2, Issue 11, November 2012.

[12] M. V. Malakooti, M. Raeisi Nejad Dobuneh "Developing a Lossless Digital Encryption System for Multimedia Using Orthogonal Transforms", Malaysia, 2011.

Dr. Mohammad V. Malakooti (1), Ebrahim Akhavan Bazofti (2)

(1) Faculty and Head of Department of Computer Engineering, Islamic Azad University (IAU), UAE Branch, Dubai, UAE

(2) Department of Computer Engineering, Islamic Azad University (IAU), UAE Branch, Dubai, UAE

(1) malakooti@iau.ae, (2) e bazofti@yahoo.com

Table 1: An Example of Cellular Automata Input string 1 1 0 1 0 0 1 0 Internal Cell [a.sub.i+1] = Cell [a.sub.i-1] + cellular rule Cell [a.sub.i] Generated 1 0 1 0 1 0 1 1 Table 2: The Content of original database table stunum name Iname score 8800155 Alis ayne 18 90115302 Mohsen dehghani 10 90115807 BOB Anderson 20 Table 3- The Hash Table id hash 37 KG01S9zUhXiCw... 38 t8eIMnon5bu9O... 39 mCnBdN2H70/a... Table 4- Decrypted Table of the database id stunum name Iname score 32 8800155 Alis ayne 18 33 90115302 Mohsen dehghani 10 34 90115807 BOB Anderson 20

Printer friendly Cite/link Email Feedback | |

Author: | Malakooti, Mohammad V.; Bazofti, Ebrahim Akhavan |
---|---|

Publication: | International Journal of Digital Information and Wireless Communications |

Article Type: | Report |

Date: | Apr 1, 2014 |

Words: | 4259 |

Previous Article: | Robust nonlinear composite adaptive control of quadrotor. |

Next Article: | Designing and implementing bi-lingual mobile dictionary to be used in machine translation. |

Topics: |