International Journal of Computer Network and Information Security(IJCNIS)

ISSN: 2074-9090 (Print), ISSN: 2074-9104 (Online)

Published By: MECS Press

IJCNIS Vol.7, No.6, May. 2015

Fast and Efficient Design of a PCA-Based Hash Function

Full Text (PDF, 445KB), PP.31-38

Views:252   Downloads:5


Alaa Eddine Belfedhal, Kamel Mohamed Faraoun

Index Terms

Cryptographic Hash Function;Programmable Cellular Automata;Pseudo-randomness;Avalanche effect


We propose a simple and efficient hash function based on programmable elementary cellular automata. Cryptographic hash functions are important building blocks for many cryptographic protocols such as authentication and integrity verification. They have recently brought an exceptional research interest, especially after the increasing number of attacks against the widely used functions as MD5, SHA-1 and RIPEMD, causing a crucial need to consider new hash functions design and conception strategies. The proposed hash function is built using elementary cellular automata that are very suitable for cryptographic applications, due to their chaotic and complex behavior derived from simple rules interaction. The function is evaluated using several statistical tests, while obtained results demonstrate very admissible cryptographic proprieties such as confusion, diffusion capability and high sensitivity to input changes. Furthermore, the hashing scheme can be easily implemented through software or hardware, and provides very competitive running performances.

Cite This Paper

Alaa Eddine Belfedhal, Kamel Mohamed Faraoun,"Fast and Efficient Design of a PCA-Based Hash Function", IJCNIS, vol.7, no.6, pp.31-38, 2015.DOI: 10.5815/ijcnis.2015.06.04


[1]Naor, M., & Yung, M. (1989, February). Universal one-way hash functions and their cryptographic applications. In Proceedings of the twenty-first annual ACM symposium on Theory of computing (pp. 33-43). ACM.

[2]Preneel B, Govaerts R, and Vandewalle J. (1993). Hash Functions Based on Block Ciphers: A Synthetic Approach. In Crypto '93, volume 773 of LNCS, pages 368–378. Springer-Verlag.

[3]Black J, Rogaway P, and Shrimpton T. (2002). Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV. In Crypto'02, volume 2442 of LNCS, pages 320–335. Springer-Verlag.

[4]Buchmann J and Paulus S. (1997). A One Way Function Based on Ideal Arithmetic in Number Fields. In Crypto '97, volume 1294 of LNCS, pages 385–394. Springer-Verlag.

[5]Contini S, Lenstra A, and Steinfeld R. (2006). VSH, an E?cient and Provable Collision- Resistant Hash Function. In Eurocrypt '06, volume 4004 of LNCS, pages 165–182. Springer-Verlag.

[6]Charles D, Lauter K, and Goren E. (2007). Cryptographic Hash Functions from Expander Graphs. Journal of Cryptology, 22(1):93–113.

[7]Jeon J-C. (2013) Analysis of Hash Functions and Cellular Automata Based Schemes, International Journal of Security and Its Applications Vol. 7, No. 3, May, 2013.

[8]Maqableh M, Samsudin A, and Alia M. (2008) New Hash Function Based on Chaos Theory (CHA-1). International Journal of Computer Science and Network Security, 8(2):20–27.

[9]Xan Yi. (2005) Hash Function Based on Chaotic Tent Maps. IEEE Transactions on Express Briefs, 52(6):354–357.

[10]Norziana J, Ramlan M, Muhammad Reza Z, Nur Izura U and Zuriati Ahmad Z. (2012) A New Cryptographic Hash Function Based on Cellular Automata Rules 30, 134 and Omega-Flip Network. International Proceedings of Computer Science & Information Tech. Vol. 27, p163.

[11]Menezes A, Oorschot P and Vanstone S. (1996). Handbook of Applied Cryptography, chapter Hash Functions and Data Integrity, pages 321–384. 

[12]NIST. (2002) Federal Information Processing Standard (FIPS) Publication 180-2, Secure Hash Standard (SHS), U.S. Doc/NIST, Available from 180-2.pdf.

[13]Jamil N, Mahmood R, Z'aba M R, Udzir N I and Zukarnaen Z A. (2012a). A New Cryptographic Hash Function Based on Cellular Automata Rules 30, 134 and Omega-Flip Network International Conference on Information and Computer Networks (ICICN 2012) IPCSIT vol. 27 (2012) IACSIT Press, Singapore.

[14]Neumann J V. (1987). The World of Physics: A Small Library of the Literature of Physics from Antiquity to the Present, chapter The General and Logical Theory of Automata, pages 606–607. Simon and Schuster, New York.

[15]Wolfram S. (2002). A New Kind of Science. Wolfram Media.

[16]Wolfram S. (1985). Cryptography with Cellular Automata in Advances in Cryptology: Crypto'85 Proceedings. LNCS 218. Springer 429-432.

[17]Chai Z, Cao Z, and Zhou Y. (2005). Encryption Based on Reversible Second-Order Cellular Automata. ISPA Workshops, LNCS 3759, pp. 350–358.

[18]Clarridge A and Salomaa K. (2009). A Cryptosystem Based on the Composition of Reversible Cellular Automata. LATA 2009, LNCS 5457, pp. 314–325.

[19]Damgard I. (1989). A Design Principle for Hash Functions. In Crypto '89, volume 435 of LNCS, pages 416–427. Springer-Verlag.

[20]Daemen J, Govaerts R, and Vandewalle J. (1991). A Framework for the Design of One-Way Hash Functions Including Cryptanalysis of Damgard's One-Way Function Based on a Cellular Automaton. In Asiacrypt '91, volume 739 of LNCS, pages 82–96. Springer-Verlag.

[21]Daemen J, Govaerts R, and Vandewalle J. (1992) A hardware design model for cryptographic algorithms, Computer Security – ESORICS 92, Proc. Second European Symposium on Research in Computer Security, LNCS 648, Springer-Verlag, 1992, pp. 419–434.

[22]Chang D. (2006) Preimage Attacks on CellHash, SubHash and Strengthened Versions of CellHash and SubHash. Cryptology ePrint Archive, Report 2006/412. (

[23]Mihaljevic M, Zheng Y, Imai H. (1999). A Fast Cryptographic Hash Function Based on Linear Cellular Automata over GF(q). Special Section on Cryptography and Information Security. IEICE TRANS. FUNDAMENTALS,Vol. E82. A, NO. 1 January 1999.

[24]Mihaljevic M, Zheng Y and Imai H. (1998). A Cellular Automaton Based Fast One-Way Hash Function Suitable for Hardware Implementation, proceeding of PKC'98, LNCS 1431, (1998), pp. 217-233.

[25]Dasgupta P, Chattopadhyay S and Sengupta I. (2001). Theory and Application of Non-group Cellular Automata for Message Authentication, Journal of Systems Architecture, vol. 47, no. 55, pp. 383-404.

[26]Hirose S and Yoshida S. (1997). A one-way hash function based on a two-dimensional cellular automaton, The 20th Symposium on Information Theory and Its Applications (SITA97), Matsuyama, Japan, Dec. 1997, Proc. vol. 1, pp. 213–216.

[27]Webster A.F and Tavares S.E (1985). On the design of s-boxes, Lecture notes in computer sciences; 218 on Advances in cryptology—CRYPTO 85, New York, NY, USA, pp.523–534, Springer-Verlag New York, Inc.

[28]Castroa J C H, Sierrab J M, Sezneca A, Izquierdoa A and Ribagordaa A. (2005). The strict avalanche criterion randomness test. Mathematics and Computers in Simulation 68, 1–7.

[29]Forre R. (1990). The strict avalanche criterion: spectral properties of booleans functions and an extended definition. Advances in cryptology, in: S. Goldwasser (Ed.), Crypto'88, Lecture Notes in Computer Science, vol. 403, Springer-Verlag, 1990, pp. 450–468.

[30]Doganaksoy A, Ege B, Ko?cak O and Sulak F. (2010). Cryptographic Randomness Testing of Block Ciphers and Hash Functions. IACR Cryptology ePrint Archive 2010: 564.

[31]Marsaglia G. (1995). Diehard Battery of Tests of Randomness. http://www.stat.f

[32]Walker J. (2008). ENT A Pseudorandom Number Sequence Test Program.

[33]Dai W (2013). Crypto++,