Except an attacker wouldn't have to perform that expensive operation: she could just iterate over the range of the KDF. Unless there were rate-limiting!
Well I guess if the range is large enough it might not be feasible. But the hypothetical system is not rate-limiting (if it were, doing the KDF server-side wouldn't be a big deal), and it is not storing an individual salt, so time is the only thing standing in the way of this attack.
