A Good Hash Function is Hard to Find, and Vice Versa

Abstract

Secure hash functions are the unsung heroes of modern cryptography. Introductory courses in cryptography often leave them out; since they do not have a secret key, it is difficult to use hash functions by themselves for cryptography. In addition, most theoretical discussions of cryptographic systems can get by without mentioning them. However, for secure practical implementations of public-key ciphers, digital signatures, and many other systems, they are indispensable. In this article, the author discusses the requirements for a secure hash function and relates his attempts to come up with a “toy” system which is both reasonably secure and also suitable for students to work with by hand in a classroom setting.

Keywords:

• course development
• hash functions
• teaching cryptography
• toy ciphers

Notes

¹This course met four days a week with most days consisting of a one-hour lecture, a one-hour break, and then a two-hour block which was usually divided into about an hour of lecture and an hour of hands-on work. One entire day was devoted to digital signatures and hash functions, with a general introduction and the idea of RSA signatures before the break. After the break, I covered the hash function from [2, Example 3.6.1, p. 233] mentioned above, JHA-1, examples of hash functions and digital signatures, and the classroom exercise. The students were already familiar with RSA encryption at this point.

²I found in my classes in 2010 that despite more powerful calculators being fairly cheap and convenient, nontechnical students often did not have them or did not bring them to class. However, most of them had a cell phone, and most cell phones now include a four-function calculator!

³I suggest the name “Housecat” for the 12-bit version.

⁴For 1976, the year in which the famous article “New Directions in Cryptography” [3] was published.

⁵An early version without this step was shown to be insecure by Michael Pridal-LoPiccolo, an undergraduate at Rose-Hulman who was able to find two-letter preimages.

⁶On the other hand, the Tiger hash function [1] uses multiplication by a different constant in each round, rather than addition. So perhaps the multiplication by 7 in JHA-2 could be looked on in this manner. It should also be noted, however, that much of the security purpose of the constant comes from not using different constants in different steps or rounds, in order to eliminate symmetry that could be exploited.

Additional information

Notes on contributors

Joshua Holden

Joshua Holden is currently an Associate Professor in the Mathematics Department of Rose-Hulman Institute of Technology, an undergraduate engineering college in Indiana. He received his PhD from Brown University in 1998 and held postdoctoral positions at the University of Massachusetts at Amherst and Duke University. His research interests are in computational and algebraic number theory, cryptography, and the application of graph theory to fiber arts. His teaching interests include the use of technology in teaching and the teaching of mathematics to computer science majors, as well as the use of historically informed pedagogy. His non-mathematical interests used to include fiber arts, but that now seems to be a mathematical interest. Still largely in the non-mathematical category are his interests in science fiction and music, both classical and contemporary.