Hash function generation by means of Gene Expression Programming

• Autorzy: Varrette S. , Muszyński J. , Bouvry P.

Identyfikatory

DOI

10.2478/v10065-012-0027-x

• Języki publikacji: EN

Abstrakty

EN

Cryptographic hash functions are fundamental primitives in modern cryptography and have many security applications (data integrity checking, cryptographic protocols, digital signatures, pseudo random number generators etc.). At the same time novel hash functions are designed (for instance in the framework of the SHA-3 contest organized by the National Institute of Standards and Technology (NIST)), the cryptanalysts exhibit a set of statistical metrics (propagation criterion, frequency analysis etc.) able to assert the quality of new proposals. Also, rules to design "good" hash functions are now known and are followed in every reasonable proposal of a new hash scheme. This article investigates the ways to build on this experiment and those metrics to generate automatically compression functions by means of Evolutionary Algorithms (EAs). Such functions are at the heart of the construction of iterative hash schemes and it is therefore crucial for them to hold good properties. Actually, the idea to use nature-inspired heuristics for the design of such cryptographic primitives is not new: this approach has been successfully applied in several previous works, typically using the Genetic Programming (GP) heuristic [1]. Here, we exploit a hybrid meta-heuristic for the evolutionary process called Gene Expression Programming (GEP) [2] that appeared far more efficient computationally speaking compared to the GP paradigm used in the previous papers. In this context, the GEPHashSearch framework is presented. As it is still a work in progress, this article focuses on the design aspects of this framework (individuals definitions, fitness objectives etc.) rather than on complete implementation details and validation results. Note that we propose to tackle the generation of compression functions as a multi-objective optimization problem in order to identify the Pareto front i.e. the set of non-dominated functions over the four fitness criteria considered. If this goal is not yet reached, the first experimental results in a mono-objective context are promising and open the perspective of fruitful contributions to the cryptographic community.

Słowa kluczowe

EN

hash function; Gene Expression Programming; Genetic Programming; GEPHashSearch; cryptography

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2012
• Tom: Vol. 12, no. 3
• Strony: 37--53
• Opis fizyczny: Bibliogr. 23 poz., rys., tab.

Twórcy

autor

Varrette S.

• University of Luxembourg, Computer Science and Communications (CSC) Research Unit, 6, rue Richard Coudenhove-Kalergi, L-1359 Luxembourg, Luxembourg

autor

Muszyński J.

• University of Luxembourg, Computer Science and Communications (CSC) Research Unit, 6, rue Richard Coudenhove-Kalergi, L-1359 Luxembourg, Luxembourg

autor

Bouvry P.

• University of Luxembourg, Computer Science and Communications (CSC) Research Unit, 6, rue Richard Coudenhove-Kalergi, L-1359 Luxembourg, Luxembourg

Bibliografia

• [1] Koza J. R., Genetic Programming, MIT Press, (1992)
• [2] Ferreira C., Gene expression programming: A new adaptive algorithm for solving problems, Complex Systems 13(2) (2001): 87–129.
• [3] Menezes A. J., Vanstone S. A., Van Oorschot P. C., Handbook of Applied Cryptography, Computer Sciences Applied Mathematics Engineering, CRC Press Inc., 1st edition (1996).
• [4] Rivest R., The MD5 Message-Digest Algorithm, Request for Comments (RFC) 1321, Network Working Group (1992).
• [5] Eastlake D., Jones P., US Secure Hash Algorithm 1 (SHA1), Request for Comments (RFC) 3174, Network Working Group (2001).
• [6] Bellare M., Micciancio D., A new paradigm for collision-free hashing: Incrementality at reduced cost, Advances in Cryptology—EUROCRYPT 97 volume 1233 of Lecture Notes in Computer Science, Springer-Verlag (1997): 163–192.
• [7] Darwin C., The Origin of Species, John Murray (1859).
• [8] Hernandez-Castro J. C., Viñuela P. I., Evolutionary computation in computer security and cryptography, New Gen. Comput. 23(3) (2005): 193–199.
• [9] Clark A. J., Optimisation heuristics for cryptology, PhD thesis, Queensland University of Technology (1998).
• [10] Daemen J., Govaerts R., Vandewalle J., A framework for the design of one-way hash functions including cryptanalysis of damgåd’s one-way function based on a cellular automaton, Advances in Cryptology ASIACRYPT ’91, volume 739 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg (1993): 82–96.
• [11] Damgå rd I., A design principle for hash functions, Advances in Cryptology CRYPTO’89 Proceedings, volume 435 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg (1990): 416–427.
• [12] Damiani E., Tettamanzi A. G. B., Liberali V., Automatic synthesis of hashing function circuits using evolutionary techniques, Institute of electrical and electronics engineers, Los Alamitos (1998): 42–45.
• [13] Safdari M., Evolving universal hash functions using genetic algorithms, In Proc. of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers, GECCO ’09, New York, NY, USA, ACM (2009): 2729–2732.
• [14] Estevez-Tapiador J. M., Hernandez-Castro J. C., Peris-Lopez P, Ribagorda A., Automated Design of Cryptographic Hash Schemes by Evolving Highly-Nonlinear Functions, Journal of Information Science and Engineering 24(5) (2008): 1485–1504.
• [15] Ferreira C., Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence, Springer-Verlag, 2nd edition (2006).
• [16] Aumasson J.-P., Henzen L., MeierW., Phan R. C.-W., SHA-3 proposal BLAKE, Technical report, NIST (2010); http://www.131002.net/blake/blake.pdf
• [17] Knudsen L. R., Gauravaram P., Matusiewicz K., Mendel F., Rechberger C., Schläffer M., Thomsen Søren S., Grøstl a SHA-3 candidate, Technical report, NIST (2011); http://www.groestl.info/Groestl.pdf
• [18] Wu H., The Hash Function JH, Technical report, NIST (2011); http://www3.ntu.edu.sg/home/wuhj/research/jh/jh_round3.pdf
• [19] Daemen J., Bertoni G., Peeters M., Van Assche G., Van Keer R., Keccak implementation overview, Technical report, NIST (2012); http://keccak.noekeon.org/Keccak-implementation-3.2.pdf
• [20] Schneier B., Ferguson N., Lucks S., Whiting D., Bellare M., Kohno T., Walker J., Callas J., The Skein Hash Function Family, Technical report, NIST (2010); http://www.skeinhash.info/sites/default/files/skein.pdf
• [21] Preneel B., Van Leekwijck W., Van Linden L., Govaerts R., Vandewalle J., Propagation characteristics of boolean functions (1990).
• [22] Rukhin A. and al., NIST SP 800-22 – A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, Technical report, NIST (2010); http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html
• [23] Deb K., Agrawal S., Pratap A., Meyarivan T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evolutionary Computation 6(2) (2002): 182–197.