# Integer factorization based password authentication

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.

-
Why not the much simpler "The client software applies a password-hashing algorithm $\hspace{1.43 in}$ to the password, obtaining the authentication token, and the server can verify that $\hspace{1.41 in}$ because it stores the SHA-256 hash of that string."$\hspace{.01 in}$? $\;$ – Ricky Demer Sep 16 '13 at 1:37
Well, I believe that is the same reason the plain password is not stored on the server (or partially): if anyone can read the database, he/she will be able to login into the system. – lvella Sep 16 '13 at 2:19
Check out the Secure Remote Password Protocol (SRP). It's the "right" way to do password authentication with small shared secrets, and has the additional benefit that the user can authenticate the server in the process. – Max Krohn Sep 16 '13 at 2:24
Uhh... how? $\:$ If the password-hashing algorithm was a password-based kdf, then there would be a simple reduction from such an attack to (an) attack(s) on SHA-256's onewayness and/or the password-based kdf's security. $\;\;\;$ – Ricky Demer Sep 16 '13 at 2:24
Sorry. I understood now what you suggested... it really seems better. – lvella Sep 16 '13 at 3:18