Crypto analysis and its applications to password hashing

Abstract: Hash functions are a type of mathematical function that takes an input of arbitrary length and gives an output of fixed length, called a hash value. Many consider hash values to be sort of a “fingerprint” of some data, since they can be assumed to have unique outputs for any possible input. This assumption does not make a lot of sense, because the size of the input space is infinite while the size of the output space remains finite! It is, nevertheless, defensible because of the infeasibility of finding two inputs that yield the same hash value. Hash functions are often used to store passwords in databases since it is not feasible either to go from a hash value to a preimage. By saving the hash value rather than the password and checking the hash value of the user’s input it is possible to check passwords without the need to store them, which is an advantage if one wants to control the damage of a possible data leakage. This work researches different cryptanalytic techniques for searching for preimages to hash values in a password-cracking context. A 27% increase in performance is gained using a time/memory tradeoff instead of naively iterating through password candidates. The attack is also demonstrated in practice, where it attains a 50% improvement. The data is then analyzed and discussed for the purpose of assessing the implementability of the attacks in already existing cracking implementations.