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.

-
The last link is broken. – otus Oct 6 '15 at 10:58

Let's make things slightly more abstract at first.

The attacker knows $n$ salts $s_i$. Passwords have $e$ bits of entropy and are hashed to $h_i = H(s_i, p_i)$. The attacker can calculate $2^c$ hashes $H(s_i, p)$ per second and can query some kind of an oracle $2^q$ times per second for the prefix length shared by $H(s_i, p)$ and the target $h_i$.

Simplest would be if the shared prefix length was known to the bit. In that case when the attacker knows the first $b$ bits of $h_i$, they can look for a $p$ for which $H(s_i, p)$ starts with those $b$ bits ($2^b$ work) and by querying the server would find an expected 2 more bits of $h_i$. Thus, finding the $e$-bit entropy password would take about $2^{e-1}$ hashing work and $e/2$ queries on average.

If the length is known with byte accuracy, the attacker would need to query up to 255 times to go from knowing $b$ bytes to knowing (usually) one more. The hashing work would remain the same at $2^{e-1}$, but about $128(e/8) = 16e$ queries would be required. With $w$-bit words, the number of queries required would be about $2^{w-1}e/w$.

So, in cracking those $n$ passwords, the attacker would spend $n2^{e-1-c}$ seconds hashing and $ne2^{w-1-q}/w$ seconds querying. With your numbers of $n=16$, $c=40$, $q=10$ and assuming $w=8$, cracking even 70-bit passwords would require less than half a minute of queries total, which means it is negligible compared to hashing time for anything remotely secure and the attack is effectively offline. Only with $w = 32$ and larger does it start to matter – each password would require a month or two of queries at that point.

With prefix queries at byte accuracy and 44-bit passwords, the attacker would require 8 seconds of hashing and less than a second of queries to crack all 16 passwords. They might be limited by network latency and need several extra seconds due to that.

-