What about appending a significantly long random string to all passwords? Would that slow down re-computation of hashes significantly enough to thwart brute-force attacks? I don't know enough about GPU architecture to tell for sure.
The reason why longer passwords take long is not a property of the GPU or computation, it is because there are many more possible passwords as the length increases and you have to try sizable portion of them.
For example, there are (to make the math simple) 10 000 four number pins (0000, 0001, ... 9999). However, if you append 4 to every pin, you have made them longer, but there are still 10 000 of them, because the 4 is fixed. However if you use 5 number pins, there are 100 000 of possible ones.
Random string would work only if you can store it in a way that attacker can't get to them. However since the application that uses them needs them to verify the password, this is not very realistic assumption.
I was thinking more along the lines of somehow forcing certain space complexity on every hash computation so it can't be as easily parallelized.
However, I see that my exact reasoning in the post above is not solid. Having longer strings as the final result of password comparison is irrelevant, because they are not part of the brute-force computation in the first place.
