6 Hash functions
This chapter covers
- One-way functions and their importance in cryptography
- Using hash digests as fingerprints of data
- Security properties of hash functions, including preimage resistance and collision resistance
- The birthday paradox and collision attacks
- Understanding and implementing rainbow tables for space-time trade-off while performing dictionary attacks
Hash functions are ubiquitous in cryptography. They are so popular that there seems to be some level of general understanding among the technologically savvy that websites should not store users’ plaintext passwords directly but instead should hash them before storing them on disk. In this chapter, we will look at why hash functions are needed, what makes them useful, and how their implementations have been attacked and broken over the years. Specifically, we will see how rainbow tables are used to crack hashed passwords and how many hash algorithms are affected by a class of attacks known as length-extension attacks.
6.1 Hash functions as one-way digital fingerprints
The main purpose of hash functions is to provide a deterministic way of calculating a hash digest from an arbitrarily long input value in a manner that is impractical to reverse. As mentioned in the introduction, a common use case is to store a hash digest on disk that corresponds to a user’s password. A given password must always hash to the same digest. Otherwise, the digests will mismatch between the user’s registration and their login time.