Skip over navigation

Applying Karnaugh Map Analysis to the
Candidate Cryptographic Hash Functions
of the NIST SHA-3 Competition

Advisers: Edward W. Felten, Boaz M. Barak

Christina C. Ilvento

Computer Science

“... Being disciplined about your organization and methodology is absolutely essential to staying sane while writing a thesis.”

ilvento-christina-cathryn

My senior thesis research topic was analyzing the candidate cryptographic hash functions for the National Institute of Standards and Technology (NIST) SHA-3 competition. It built on my prior junior paper (JP) research analyzing the cryptographic hash functions MD5 and SHA-2 using a new technique I developed of analyzing Karnaugh maps (k-maps) to try to identify nonrandom behavior. The premise of my research is that a cryptographic hash function is supposed to behave like a random function, so showing any nonrandom behavior will have security implications for the use of the function in cryptographic applications.

I originally chose the topic for my JP because it was an area I wanted to learn more about, and it presented me with the opportunity to propose and implement a new approach for analyzing cryptographic hash functions that had not previously been used. My initial goal for the research was to attempt to find vulnerabilities that could be exploited to propose collision attacks by using the inherent structure of k-maps as a representation of Boolean circuits. However, it became clear after the initial implementation and testing performed for my JP that a more fundamental application could be using the proposed method as a distinguishing function. Although not as glamorous as a collision attack, distinguishing functions are an important part of the analysis of any potential candidate for a new cryptographic hash function standard, due to their widespread use as assumed random oracles.

There were three major parts of my research process. The first was the groundwork of implementing the code and the framework for the analysis. For me, this was one of the most challenging parts of the project because of the large amount of up-front work without any assurance that the technique I was implementing would be successful. One of the main lessons that I learned during this part of the project was the need to be disciplined and rigorous in testing absolutely every module I wrote. When working on class projects, one of the things that most of us ignore is maintainability, but for a project that ended up spanning more than a year and a half, maintaining clearly readable, reusable, efficient code was an absolute necessity (as I learned the hard way). Throwing some code together to test an idea is fine as a first approximation, but it has to be followed by a thorough clean up, or you’ll end up with a messy, buggy pile of useless code that will come back to haunt you later. Even for projects that don’t involve writing code or running experiments, being disciplined about your organization and methodology is absolutely essential to staying sane while writing a thesis.

The second step in my research was running a series of experiments using the new technique and analyzing the results. Each analysis of a new run of the experiment provided new insight and would lead to another new experiment. The most important thing that enabled this part of my research was having enough time to comfortably repeat experiments and modify techniques based on my observations and input from my advisers. For projects on a shorter timeline, it’s reasonable to run a single set of experiments and write on those results alone. For me, however, it was important to have enough time to exhaust as many ideas as possible and present a more coherent set of conclusions based on several iterations of the experiment and to have enough data to make significant observations.

Working on original research can be daunting. There’s no guarantee that you’re approaching the problem from the right angle or that your technique is the right one. The main way that I kept myself from getting too far off track was to involve my advisers in all of the major decisions that I made for experiments and to make myself write a brief summary of each attempt, its results, and what I planned to do given the results. The simple act of preparing to justify why I chose to do something in a given way helped me to avoid wasting too much time on fruitless ideas and concentrate on the parts of the project that I could reasonably tackle.

My advisers were the main reason that my project was successful. I met with my principal adviser, Professor Edward Felten, weekly throughout the project, and as it was coming to a close met with my second reader and adviser, Professor Boaz Barak, nearly as frequently. The best part about working with Professor Felten and Professor Barak was that I felt that I could always ask for advice and get a clear answer, but that my project wasn’t being overtly directed by either of them. For me, this was a good way to stay on top of my time line and manage the direction and scope of the project while maintaining the freedom to make my own mistakes and discoveries. I’m sure that plenty of students can be successful thesis writers without meeting with their adviser as frequently, but it’s up to you to determine what level of involvement from your adviser will make you most successful. As silly as it sounds, it’s important to remember that your advisers are there to advise, and you should never hesitate to go to them with a list a mile long of things you tried that failed or are unsure about.

As an engineering student, I did not have to write a thesis, but choosing to write one was one of the best decisions I made at Princeton. Writing a thesis helped me to build project and research management skills and gave me the confidence to start tackling problems that interested me on my own. In many of your classes at Princeton, you’re expected to find the right answer to a problem. Your thesis is a unique opportunity for you to choose your own problem, make mistake after mistake (after mistake), change the specifications of the problem, and still get credit for writing a paper about the process.

Applying Karnaugh Map Analysis to the
Candidate Cryptographic Hash Functions
of the NIST SHA-3 Competition

Christina C. Ilvento

Edward W. Felten

Professor of Computer Science and Public Affairs

“I often tell students that one key to a successful senior thesis is not a superhuman burst of work at the end. ...”

I had supervised Christina Ilvento’s junior independent work, so when I agreed to advise her senior thesis, I thought I knew what to expect. I knew that Christina was smart, hardworking, and creative, and that she would produce a strong thesis. What I didn’t expect was that her thesis would be so much better than her previous work (which was already very good), nor that I would learn as much from her as I did.

I have to admit that I was a bit skeptical of Christina’s specific project idea. I had no doubt that she could carry out her plan, but the question was whether her approach, novel as it was, would lead to an interesting result. Christina’s work concerned the properties of mathematical constructs called cryptographic hash functions (CHFs). Though this may sound like an abstract, purely theoretical topic, the fact is that we rely constantly on the properties of CHFs to secure our online transactions and keep our communications secret. Subtle flaws in the mathematical properties of CHFs can destroy the security of everyday e-commerce.

CHFs are supposed to produce values that look random in a certain sense—their output is supposed to be free from recognizable patterns. Christina had come up with a clever way to search for patterns very efficiently, and she hoped that her search would manage to find patterns in commonly used CHFs.

My worry was simple: What if she looked, and found nothing? What if she didn’t even find any clues about where to look next? A negative result would still have scientific value—it can be very useful to know that a certain method does not work—but finding a negative result might be a less-than-satisfying thesis experience. Despite this risk, Christina knew what she wanted to do, and I knew her well enough not to discount her instinct that her method would work.

I often tell students that one key to a successful senior thesis is not a superhuman burst of work at the end—although that doesn’t hurt—but steady work throughout the year. The thesis is far bigger, and lasts far longer, than any project students have done before, so many students find it difficult to manage time over the year, and some struggle to stay motivated when they hit the temporary setbacks and disappointments that are inevitable in a long, ambitious project. Christina dealt with these challenges brilliantly. From day one, she was always moving forward, always planning, always working to understand the problem of the moment in light of the overall goals of her project. That kind of discipline, on top of her considerable talent, and a little bit of good luck, led her to a strong result.

In the end Christina was right, and I was happy to learn that my early worries were misguided. Christina demonstrated that her method really is useful for evaluating the security of technologies used in everyday e-commerce. We don’t yet understand the full implications of her work, but it is clear that she is on to something. I am eager to see the next chapter in this story.

Applying Karnaugh Map Analysis to the
Candidate Cryptographic Hash Functions
of the NIST SHA-3 Competition

Christina C. Ilvento

Boaz M. Barak

Associate Professor of Computer Science

“I was extremely impressed by Christina’s diligence and talent, and she somehow managed to not just design, but actually execute and analyze a fairly comprehensive round of experiments.”

Although I am a cryptographer, I have not done any cryptanalysis work. So, when Christina Ilvento asked me to be her second adviser on her cryptanalysis thesis, I wasn’t sure I would be helpful. Indeed, I feel I learned more from Christina’s thesis than any contributions I made to it. The best theses are often this way: They come from the student and the adviser is only along for the ride, enjoying learning about a new topic and making some encouraging remarks here and there.

There is another crucial ingredient in all strong theses—hard work—and Christina’s thesis is no exception. The thesis involved a great many computational experiments. Like any experiment, a great deal of effort is needed in planning the experiment, implementing the mechanism, executing the experiment, and interpreting the results. Christina did all this from beginning to end. The fact that the experiments are run on a computer does not mean you get the results instantaneously. Christina executed much of the computation on her laptop, setting it to wake her up every couple of hours or so when it finished a run on the data.

Christina’s work is about the analysis of cryptographic hash functions. Hash functions are extremely useful objects that are found in nearly any application of computing. Intuitively, the goal of a hash function is to provide a “random-like” mapping of large objects, such as pictures, movies, files, into a short identifier. A common application is to quickly check that two objects are identical by verifying that they map to the same identifier. For example, when you download media or software, a hash function will typically be used to verify that you have indeed received the correct file. Designing hash functions is quite challenging, since they need to be simple and efficient, but still maintain their “random-like” property. With the current state of the art, we have no way to guarantee that a hash function actually has the “random-like” property. Indeed, in 2004 scientists were stunned when it was discovered that MD5—perhaps the most widely used hash function in the world—is far from “random-like,” and in fact collisions can be found quickly. (As one example of hash functions’ ubiquity, this discovery caused an Australian judge to throw out a speeding ticket as the electronic reports from a speeding camera could no longer be trusted.)

Because of these flaws in known hash functions, in 2007 the National Institute of Standards and Technology announced a competition for designs for a new standard hash function. About 60 designs were submitted, of which there remained 14 after two rounds of filtering. Christina set out to analyze these 14 hash functions to see if she could detect statistical weaknesses in any of them that would demonstrate that they are “not random.” She came up with some very original ways of attack, implemented them, and tested them out. Overall, she tried about a dozen different metrics on each of the 14 hash functions. While her results were only preliminary, and would need to be replicated and scaled up, it seems there is promise that her methods could demonstrate statistically significant bias for some of these candidate designs. Such work is extremely important, as it’s crucial to discover any flaws in the design before a hash function is chosen as standard and widely deployed, after which such flaws could have significant commercial and/or national security implications.

The thesis was very ambitious. It involves a research program that should take much more than a year to complete. Indeed there is still more to be done to understand the full applicability of Christina’s ideas. But I was extremely impressed by Christina’s diligence and talent, and she somehow managed to not just design, but actually execute and analyze a fairly comprehensive round of experiments. I am often surprised by the capacity of some Princeton students to go beyond any reasonable expectations, and Christina’s case is one such example. 

I believe Christina’s hard work paid off. While she didn’t end up “breaking” any hash function (at least not yet), her work gives some insight into what “random-like” means, and what designs have some advantages over others. I think she has learned a lot about cryptanalysis, computation, statistics, and research in general from this thesis. I know I have.