Tuesday, September 18, 2018

OSCAR Student Zaine Wilson Seeks to Expand Research in the Field of Automated Generation of Cryptographic Hash Functions through the Use of Genetic Algorithms

The primary goal of my research is to expand research in the field of automated generation of cryptographic hash functions through the use of genetic algorithms. Cryptographic hash functions are one-way functions, that is, given an output D, it is computationally difficult to find the input to the function M, such that for a function f f(M)=D. Generally speaking, a hash function has a construction, the framework on which it is based, and a round function, which operates within the construction and permutes and digests the input to create the output. The procedure for automated generation is to select a construction, then apply a genetic algorithm to create a round function within that construction. In the past, this was done with a construction called Miyaguchi-Preneel, under the pretense that Miyaguchi-Preneel was a likely candidate for SHA-3, the US Government’s new standard cryptographic hash function. SHA-3’s actual construction, as selected in 2013, is the Sponge Construction. As such, my research applies the methodology from prior research while changing the construction to a more up-to-date version.

This project is a carry-over from my freshman HNRS-110 class. At the start of the class, I wanted to do a project related to cryptography and artificial intelligence. I already had some experience with hash functions, and after reading the prior research, this project seemed to fit well with my desires. Over the course of this project, I’ve learned a lot about the sponge construction, genetic algorithms, and hash functions in general. I currently plan to go into cryptography research, so this project also aligns well with my long-term goals.

It’s difficult to describe what I do week-to-week because, until recently, each week has been something different. The first few weeks were devoted to creating a pure-Java implementation of the sponge construction, the next few to the creation of the genetic framework, and more recently work has been devoted to tuning and running the algorithms. On average, the algorithm took around 4 hours to produce a good candidate for a weakened form of a round function (word size, which is typically 8-64 bits, was reduced to 1 bit). My current weekly work concerns attacking the full problem, with word sizes of 64 bits. This will necessitate some overhauling of the genetic framework, as well as the pure-Java sponge implementation.

Over the course of the semester, I have produced several candidate functions that satisfy properties of typically secure cryptographic hash functions. 12 candidates with word size 1 bit have been created, and work is currently underway to expand the word size to 64 bits. Of these 12 candidates, several can be shown to trivially have good randomness of output, with more rigorous testing of randomness still underway.