Over the weekend I was thinking about the problem of scaling various web services. One common practice to scale authorization is to use cryptographically signed tokens. This way when a request comes into your service you don't need to look up a session ID in a database or perform an expensive hash on an API key or password -- you just verify the signature in their token and if it's valid then you trust the credentials presented.
This works for authorization after a person is logged in. They give a username and password, the password is compared with one stored in the database, and if it matches a token is generated, signed, and returned to the client. But how does one scale the actual process of logging in?
To prevent passwords from being easily recovered from their hashes, everyone knows that it's best practice to use an "expensive" hash function. I usually opt for something that takes at least 100ms to run on modern server hardware. This way no more than 10 login attempts can be attempted per second if someone is brute forcing the service, and if someone did manage to gain access to hashed passwords they would be incredibly slow to figure out. I also use a long and randomly generated salt with each password to negate rainbow tables and such.
But when more than 10 individuals attempt to log into this service per second, the server can't handle that many hash computations. I can scale up the number of servers and put a load balancer in front, but I don't like the thought of scaling with hardware - that's a bad precedent to set and can cause costs to balloon.
So I started thinking if there were ways to offload computation onto the client, or eliminate the need for it entirely. That's when I started thinking about secure key exchange. The only secure key exchange algorithm I'm familiar with is Diffie-Hellman, but I figure it would serve as a good base line to determine if the idea has merit.
The process would go something like this:
- The server generates (or selects from a precomputed list) a unique prime and primative root for a user when their account is created (or when they change their password)
- The server has a constant secret, kept secure in much the same way a JWT signing key or SSL cert is kept secret
- The server sends the prime and primative root to the client
- The client hashes their password (using however simple or complex of a hash you like - for the sake of example we'll just say they use bcrypt) to get a number that will serve as their secret. If the result of the hashing algorithm is larger than the unique prime, you can simply take the modulo
- The client sends the modular exponent of the primitive root with their computed secret (the hash of their password) to the server. We can call this the "password prime" (e.g.
P') or similar, if it helps - as this is what's actually sent to the server to authenticate a user - The server computes the modular exponent of the password prime with its own secret. This is the hash that gets stored in the database along with the chosen prime and primitive root
- When a user later logs in, the prime and primitive root are pulled from the database instead of choosing random ones, to guarantee the same secret will be generated (if the secret matches, a signed token is delivered to the user)
For an attacker to "log in" with this system they wouldn't necessarily need to guess the user's password, they would only need to determine the password prime. However due to the difficulty of the discrete logarithm problem, I don't believe someone who acquired the secret from the database would be able to work backwards to retrieve P', causing it to function like a hashed password in the database. Meanwhile all expensive hashing operations are performed on the client so the server resources are kept low.
This sounds like a good idea to me, but while I have more knowledge about security than most developers I have just enough rope to hang myself. I'd like to hear from some experts in the field.
