After looking at this security issue at DjangoProject, I started to think in a password-based authentication that places the burden of PBKDF2 (or whatever is the hashing function) on the client. So I came up with the following scheme:
When the user types the password, the client software (browser or whatever) hashes the password to form a seed to use in a pseudo-random generator. Then this pseudo-random generator is used to build two big primes $P_1$ and $P_2$ in a deterministic way. This two primes are the authentication token, sent encrypted through the wire (like the password is sent to websites nowdays). The server side just keeps stored in the database the product of $P_1$ and $P_2$, so — to verify the user — all the server has to do is to multiply $P_1$ and $P_2$ and see if it matches the stored product.
So, what do you think of this method? Is it secure? How big must $P_1$ and $P_2$ be for this to work? And in the prime generation process, would be better to use some algorithm like Mersenne-Twister ( with huge period size), or Rabbit (which is cryptographically secure), or doesn't it matter?
I think the hashing pass to get the seed must use something like PBKDF2, to make it hard to brute-force attack (like it is today, but it is done on client side). The drawback I see is that rainbow tables with the most common passwords could be built for easy look-up of the stored products. But this problem is easy to circumvent, by using the user name plus the website host (or some website-specific token) to salt the password hashing.