# Attacking hashed password by timing attack and other means

This question is inspired by this recent one, which raises a point that need to be made quantitative to be meaningfully discussed. I chose an unusual approach: a new question worded as homework that could be asked in a computer security with applied cryptography class (please use meta for critics of that method).

Some system keeps track of user passwords as (userID, H) pairs with H of 20 octets and a single pair per userID. To test an alleged Password for some userID, it is checked that some (userID, H) exists; then computed D of 20 octets as
PBKDF2(PRF = HMAC-SHA-1, Password, Salt = userID, c = 10000, dkLen = 20);
then the alleged Password is accepted according to the C expression memcmp(D, H, 20)==0. The value of c is 10 times what is described to be a significant burden for opponents in RFC 2898 defining PBKDF2. The documentation of memcmpstates:

int memcmp(const void *s1, const void *s2, size_t n);

The function compares successive elements from two arrays of unsigned char, beginning at the addresses s1 and s2 (both of size n), until it finds elements that are not equal:

• If all elements are equal, the function returns zero.
• If the differing element from s1 is greater than the element from s2, the function returns a positive number.
• Otherwise, the function returns a negative number.

1. can submit (userID, Password) pairs and determine if that's accepted or not, at a rate of $r\approx2^{10}$ pairs per second;
2. can at every such attempt measure the running time to fine accuracy, and consistently deduce how many elements have been compared in memcmp;
3. can perform PBKDF2 at a rate of $h\approx 2^{40}$ per second (less computing power than devoted to bitcoin mining according to this statistic);
4. does not initially know any H;
5. gets hold of $n\approx16$ target userID.

Give some approximation (as a function of the parameters) of the expected wall clock time since (5) for a competent adversary to find an acceptable (userID, Password) pair, without and with the insight given by (2), for these two models of choice of Password:

• uniformly at random among $2^b$ for $7\le b\le90$; detail the adversary's strategy when $b\approx44$ per XKCD recommendation;
• by user, with $u\approx 1/4$ of users having picked a password that occurs at least $5$ times in a list known to the attacker, comprising password choices assumed about representative of how actual users choose passwords, with statistics per these 2040 lines of the form a*b (or just a when b is $1$), each line meaning that b distinct password choice(s) each occur a times in the list (note: the threshold of $5$ keeps $\approx50\%$ of the $32603388$ choices, and $\approx4\%$ of the $14344391$ distinct choices).

Propose C code for a memneq function, usable as replacement of memcmp where sign of its result is immaterial, and likely to close the timing vulnerability.

Outline standard techniques to dramatically improve security with no change of the current passwords.

-