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:

  1. 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)
  2. The server has a constant secret, kept secure in much the same way a JWT signing key or SSL cert is kept secret
  3. The server sends the prime and primative root to the client
  4. 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
  5. 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
  6. 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
  7. 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.

  • 1
    Or you could use existing challenge response authentication mechanisms with the bulk of the work being done by the client, such as SCRAM. Please don't re-invent things.
    – Marc
    Aug 24, 2020 at 13:36
  • @Marc thank you for the lead. I hadn't heard of existing challenge response authentication mechanisms. When you Google authentication best practice 100% of the articles, YouTube channels, and StackOverflow posts just say "use a strong hash function" and leave it at that. If you're using bcrypt or argon2i then you're following best practice. I'll read up on SCRAM - it may be exactly what I'm interested in
    – stevendesu
    Aug 24, 2020 at 13:41
  • @Marc reading up on SCRAM, it sounds like the hash function is performed on both the client and the server. This doesn't solve the original problem I was trying to solve of eliminating expensive CPU operations on the server. I realize that the "simple" answer of having the client compute the hashed password is no better than storing passwords in plain text (if someone gains access to the database, they can log in by passing the hashes as-is), so I considered modular exponents as a low-cost "hash" for storing the actual hashed password
    – stevendesu
    Aug 24, 2020 at 13:57
  • 1
    No, the server stores the hashed password and uses it during verification, it does not need to recompute it for password verification (it can't, it's not being given the plaintext password). I recommend you reread the wiki page or read the rfc
    – Marc
    Aug 24, 2020 at 14:09
  • 1
    @stevendesu What you are describing sounds very similar to PAKE (password authenticated key exchange), or more specifically, SRP. see srp.stanford.edu for more info.
    – mti2935
    Aug 25, 2020 at 8:51


You must log in to answer this question.