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.
Notes
1This 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 [Citation2, 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.
2I 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!
3I suggest the name “Housecat” for the 12-bit version.
4For 1976, the year in which the famous article “New Directions in Cryptography” [Citation3] was published.
5An 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.
6On the other hand, the Tiger hash function [Citation1] 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.