How to get a speedup linear in the number of iterations on unsalted iterated password hashing?

Question

In their 2015 paper "More Rounds, Less Security?" Guo, Jean, Mouha and Nikolić claim in section 5.4 that one can recover a password $P$ given hashes of $D$ different passwords generated from $H^k(P)$ with about $T_1=\frac{2^n}{D\cdot k}$ hash evaluations.

Now I understand that using standard preimage search you are expected to find at least one preimage in $2^n/D$ evaluations of the full iterated hash, so $T_2=\frac{k\cdot 2^n}{D}$ hash evaluations.

The reasoning given for $T_1$ is:

Now observe that the time complexity can be reduced by a factor of $k$. This is because evaluating one password guess requires $k$ evaluations of the hash function used inside [the password hash], but every additional guess has an additional cost of only one hash function evaluation. This effectively speeds up exhaustive search by a factor of $k$: given $D$ password hashes, recovering any of them has a time complexity of $2^n/(D \cdot k)$.

My question is now (based on my current understanding of the above quote):
Given $H^{i}(P)$ for $i\in\{1,\ldots,k\}$ using only one evaluation of $H$ how does one compute $H^k(P')$ for any $P'\neq P$?

Or asked differently but (hopefully) equivalently:
How exactly does this pre-image search speedup trick work where additional checks after the initial evaluation only cost one hash evaluation?

Answer 1

The only way I see to justify the claim is that the authors are thinking as follows thus it is not for any $P'\neq P,$ but specific $P'$ in that trail:

Compute $H^i(P),$ for $i=1,2,\ldots,k.$ This gives you the hash for $P,$ call it $H_0.$

Now define the sequence $P'_i=H^i(P),$ for $i\geq 1,2,3,\ldots.$

Evaluate $H^i(H_0)$ to obtain $H(P'_i),$ for $i\geq 1,2,3,\ldots,$ at extra cost of one evaluation each. Of course these $P_i'$ are almost certainly distinct until the trail length is comparable to square root of the hash output space.