You can couple Rendezvous Hashing with a redundancy method like replication or erasure coding.
The default for Tahoe-LAFS (a distributed filesystem that uses a form of Rendezvous Hashing) uses erasure coding to split each file into (by default) 10 segments of which any 3 are necessary to reconstruct the file. Those 10 segments are then stored across the first 10 servers in the list. [https://tahoe-lafs.readthedocs.io/en/latest/architecture.htm...]
That way, even when servers go away with your data (whether due to crash or even network partitions(!)), you still have a decent chance to locate your data.
Thanks for pointing out that I was off in my original estimate (a hasty web search showed the wrong cryptocurrency; almost nobody mines bitcoin on CPUs anymore :).
From what I can see, a more realistic estimate for a single core on a desktop is in the 2^26 range. Keep in mind that the PBKDF2 defender is single-threaded by design, whereas the attacker is not.
This still represents ~a half million x advantage for the attacker/$2k they spend. For $1m, they can guess passwords ~200 million times faster than you.
If we assume memory is the limiting factor for argon2, then even if a specialized attacker can use it at scale for 1/20th the cost, a 20x advantage is much better for the defender than a 500,000x advantage.
I think this misses the point: we should be doing everything we can to deprecate PBKDF2 because of the big differences between what a specialized attacker can do vs. the defender.
As a rough estimate: a $2k bitcoin miner can do 2^45 SHA-256 hashes/sec whereas your $2k laptop can do 2^16 hashes/sec; the attacker has ~a billion x advantage over you that can be multiplied based on their funding. At that point, doing even 10,000 PBKDF2 hashes may not make much of a difference.
argon2, scrypt and other memory hard password hashing algorithms reduce the orders of magnitude advantages of the attacker by requiring RAM. Attackers might be able to purchase RAM cheaper than the defender, but nothing close to a billion times cheaper.
Addressing concern #3 (want to have a password set on a laptop that decodes in a reasonable amount of time on a low-end smartphone), you could restrict the RAM to some small amount (like 256MB) if you anticipate needing to use a low-end device. This will still be a vast reduction in the attacker's advantage over PBKDF2.
The default for Tahoe-LAFS (a distributed filesystem that uses a form of Rendezvous Hashing) uses erasure coding to split each file into (by default) 10 segments of which any 3 are necessary to reconstruct the file. Those 10 segments are then stored across the first 10 servers in the list. [https://tahoe-lafs.readthedocs.io/en/latest/architecture.htm...]
That way, even when servers go away with your data (whether due to crash or even network partitions(!)), you still have a decent chance to locate your data.