The effect of bias on the guesswork of hash functions
Yair Yona, Suhas N. Diggavi · 2017
In this work we analyze the average guesswork for the problem of hashed password cracking (i.e., finding a password that has the same hash value as the actual password), when averaging over all hash functions whose effective distribution is i.i.d. Bernoulli(p) for any strategy of guessing passwords one by one (i.e., the fractions of passwords that are hashed to any bin, correspond to a probability mass function, which is i.i.d. Bernoulli(p)). We analyze the average guesswork under both online and offline attacks by deriving upper and lower bounds on the average guesswork as a function of the bins to which passwords are hashed, along with the most likely average guesswork, that is, the average guesswork of the most likely set of bins. Furthermore, we provide a concentration result that shows for this problem, that the probability mass function of guesswork is concentrated around its mean value. These results give quantifiable bounds for the effect of bias as well as the number of users on the average guesswork of a hash function, and show that increasing the number of users has a far worse effect than bias in terms of the average guesswork. However, when there exists a backdoor mechanism that enables “beamforming” certain passwords to the least likely bins, bias can in fact increase the average guesswork.