I'm working on a project where each each user will have a public/private RSA key-pair. Users will be able to send encrypted messages to each other using the each target user's public key so that only target users can read the message (similar to PHP's openssl_seal). Since we want the user to be able to use any device to read or send a message, the key-pair will be stored on an API server, and the private key will be encrypted with the user's password.

When a user logs in from a new device, they will use their password to decrypt the private key. The catch is that ideally, the API server should never be able to decrypt the user's private key, even to authenticate the user. Originally, I was just going to send the client the encrypted private key and let the client decrypt it. If the client can decrypt it, they must have the correct password, but this would be vulnerable to offline dictionary attacks. To prevent that, I need to authenticate the user before I give them the encrypted private key.

I could have the client send the password to the server and let the server attempt to decrypt the key using the password or even just validate the password against a hash, but then the server would temporarily have the password and be able to decrypt the user's private key. That's OK, but I'd rather figure out a way to authenticate the user without the server knowing their password.

In my case, the client will be a PHP web server or a native mobile or desktop app, not a browser, so I have access to a wide range of cryptographic methods. The only client authorized to make the call to the API server to create an account will be the PHP web server, and I'm currently planning on having it create the public/private key-pair and encrypt the private key with the user's password. It will then send that information to the API server (also running PHP) to create the account. The API server will store the encrypted private key, the public key, information about the user, and any encrypted messages, but won't be able to decrypt any of it.

I'm not trying to protect against a MITM attack here. All API calls will be over HTTPS. My goal is to build the API in such a way that even if the Chinese government could gain access to the API server, they still couldn't read any of the messages. The web server can have the private key temporarily, just not the API server.

How can I let the API server authenticate the user without being vulnerable to an offline brute-force attack and without the API server needing the user's password?

Feel free to tell me I'm doing something totally wrong and suggest something completely different.

  • 3
    Without a well thought out threat-model this just looks paranoid and needlessly complex. – rook Dec 4 '13 at 17:29
  • @Rook The content of the messages could potentially get users in trouble in restrictive countries like China. The threat would be that the Chinese government would try to hack the server and get the data. We want to make it impossible for anyone but the desired recipient to read the message (or at least as close to impossible as we can). We do know what we're trying to prevent. – Joshua Dwire Dec 4 '13 at 17:37
  • In that case this design is extremely hazerioudus and should not be used. Moxie Marlin Spike's comment about "promising not to peak" works so well here. If your app is hacked or subpoenaed, then this "promise" goes away. – rook Dec 4 '13 at 17:45
  • @Rook That's a risk we'll have to live with. User's who are paranoid can use a native app so that our server will never have their password. For user's who aren't quite as paranoid, they can live with the risk. If you can suggest a way that the only thing the user has to input on a new device to be able to read their messages is their password, I'd love to hear it. – Joshua Dwire Dec 4 '13 at 17:57
  • I cannot put my hands back on it, but there was an article in Scientific America ("Pour la Science" in French) where the servers sends a challenge to the client (a graph AFAIR) then the client use their password (which is also a graph here) to generate a result, and the server does a check on this result. Check has like 50% of being passed if user had the password. Repeating the process as many times as server wants brings a fair trust that the client has the password, without the server knowing it. – Xenos Jun 15 '18 at 8:13

Do it the way MEGA does it: perform all encryption decryption within your browser using JavaScript. Only allow encrypted files to be sent to the server (unless of course public keys).

You wouldn't need to send the private key at any point to the server (because everything is being done browser side). One small caveat though, if your user looses a password or an encrypted file goes corrupt, then you are basically screwed and all messages will be useless since you don't have the key anymore.

For authenticating the user you could use something like open OpenID. The user would still need to supply a password to decrypt his private key, but at no point is the password decrypted key sent to the server (everything stays within the browser).

  • I will have the client perform the encryption and decryption, but I don't want the client to have to store the private key. Our market includes users who know practically nothing about technology, and we don't want them to have to keep track of a private key on multiple devices, just a password. The server must store the private key, so that the user doesn't have to enter their private key on every device. To prevent losing access to the private key, we will also store it encrypted with secret answers to secret questions. – Joshua Dwire Dec 4 '13 at 16:50
  • @Joshua Dwire By storing all of the keys in one place, having a single place of failure, you make the system's security meaningless. theregister.co.uk/2013/11/09/… – rook Dec 4 '13 at 17:00
  • @Rook Yes, the server will be able to decrypt the user's private key when they log in to their account, but keys would be stored the API server and the decryption would happen on the web server or on the user's personal device. We could gain access to the the user's data if we logged their password, but we won't. The goal is that if the storage is hacked, no one can just decrypt all of the data. The setup for the most paranoid users would be for them not to use the web UI, but to use the native apps where only their device knows the password, preventing us from doing any decryption. – Joshua Dwire Dec 4 '13 at 17:07
  • MEGA is not a good example of a secure application. It suffers from the "promise not to peek" paradox. XSS, MITM or a subpoena would undermine the application. – rook Dec 4 '13 at 17:59

PBKDF2 - This will allow you to validate that the user has the password, without having him send the password. On the server side, you don't save the password, but instead you save a hash of the password.

  • Actually, that's almost exactly what I'm planning to do. The client will do several thousand iterations of SHA-512 (for JS support) so it doesn't need a salt. It will then send that to the API server which will do a password_hash when creating the account and password_verify to verify the possession of the password before giving the client the encrypted private key. This way the server also never stores the raw password hash it will be given; it stores a hash of a hash. – Joshua Dwire Dec 5 '13 at 15:38
  • I don't get it: you'll send the password to the server anyway so it can compare it to the stored PBKDF2 it already have for this password? So you still send the password? Or you send the PBKDF2 from the client to the server? That way, your PBKDF2 is the password (anyone getting it will be able to log in right away). It doesn't bring more security (maybe less since you know that every user's password is a PBKDF2 result) – Xenos Jun 15 '18 at 8:06

This design suffers from a "promise not to peak" paradox and is very similar to the security problems LavaBit had, MEGA also has this problem.

In order to verify that a user has the correct authentication credentials you need a centralized system to check these credentials. This centralized system can be modified by an attacker to record authentication credentials. .

MITM is the problem and it this attack is used by governments. A app logging all passwords has the same effect and could be introduced by an attacker.

  • Can't the client can hash the password and have the server can verify the hash, that way the server knows the client has the right password but doesn't know what the password is. Our one non-negotiable is that the user needs to be able to log in with just a password. The goal is to provide that with as few risks as possible. We'll have to live with any risks we can't eliminate. – Joshua Dwire Dec 4 '13 at 18:02
  • @Joshua Dwire Not without the ability to peek. I'm pretty sure that "failing to address risks" is the definition of insecure software. Obviously cyrpto systems are bypassing government control, tor, bitcoin, freenet, certificate pinning, and i'm sure the list goes on. – rook Dec 4 '13 at 18:05
  • The way we will address the peeking risk without making things difficult for the user will be by providing a native app. The native app can perform all of the decryption and the server should never need the user's password. This question is to find out how I can let the API server authenticate the user without knowing their password. If I can do that, the only way to bypass the decryption would be by brute force or by publishing an insecure update to the app. If a user chooses to take advantage of the convenience of our webapp, we'll make sure to let them know of the risks involved. – Joshua Dwire Dec 4 '13 at 18:46
  • So I guess you'd be sending the native app an encrypted copy of the private key and have the native app use some sort of password-based key-derivation scheme to decrypt it? Because if you're storing unencrypted private keys on the server then I just don't see the point.. – neubert Dec 5 '13 at 13:39

Why not just use an existing token-based authentication method like Kerberos and build off of it?

So the user authenticates normally and receives a kerberos token. Then, you go to the API server, say "Hey I got this token!" The API server verifies it, and sends a copy of the encrypted data to the user, who can decrypt the keys on their machine?

Seems simple enough.

  • I think that's fairly close to what we ended up doing. We're using OAuth for authentication, but the user's password is SHA512-hashed in the browser and PBKDF2-hashed again on the server so the server never sees the password. Once authenticated, the OAuth token allows the application to authenticate with the API server and get encrypted private keys. – Joshua Dwire Oct 9 '14 at 20:39

You are saying that the private key cannot be decrypted server-side for authentication (because then the server would need the password), and it also cannot be sent to anybody requesting it, and then decrypted client-side (because then the private key would be vulnerable to an offline brute force attack).

Basically, what's left is to design a completely separate password mechanism and store some form of the password (of course, hashed/salted etc.) on the server independently of the private key. The big drawback is that this doubles the attack surface of your private key: an attacker can get to the private key either by directly cracking it, or by breaking into such a password database.

There is a completely different approach. Instead of having one key pair per user, have one key pair per device. I believe Apple uses it for the iCloud. When a user connects a new device, a completely new key pair is generated. That obviates the need for the private key to ever leave the device. The tricky part - and the one I do not fully understand - is how the key pairs for several devices interact with each other.


Apple has some information on how this works. Look at the section for the iCloud keychain. It is not detailed technical, but enough for me to venture a couple additional guesses.

With this scheme, you would not use the password to encrypt any keys (which is a major benefit because passwords are always the weakest part of encryption).

Here is how it could apply to your situation:

  • Each device on your service gets its own key pair when the user registers it. This would happen transparently; the private key will never get to your server (neither encrypted nor unencrypted).

  • Each user account has one master encryption key (symmetric, not public key) that is actually used to encrypt the content. Apple apparently uses AES128.

On initial sign-up for the first device:

  • The device generates a key pair and sends the public key to the server.

  • The server generates the master key, encrypts it using the public key, and stores the encrypted master key in the device record of your database. This is the only time the server ever has the master key in unencrypted form.

When signing on to your service:

  • User logs on to your service using user name/password.

  • The device retrieves the master encryption key that was encrypted using its own public key.

  • The device locally decrypts the master encryption key, and uses it to access the content on your server.

When adding a new device, the user need an already-registered device (device A) and of course the new device (device B)

  • User uses device B to register with your service. This will generate another key pair. You may require user name and password to do so.

  • device B sends public key to the server.

  • User logs on using device A and "authorizes" device B.

  • device A retrieves master key with device A's public key.

  • device A retrieves device B's public key.

  • device A decrypts master key using its own private key, and then re-encrypts master key using device B's public key.

  • device A uploads master key encrypted with device B's public key to the server.

At this point, the server has two copies of the same symmetric master key: one encrypted with device A's public key, one with device B's public key.

Device A and device B can now both access content using the same master key.

Apple apparently also allows storing the master encryption key unencrypted on their server to allow key recovery if you lose all your devices. This obviously undermines your stated goal.

Obviously, this approach is vulnerable to at least two attacks:

  • A malicious client application can exfiltrate the unencrypted master key.
  • A compromised server can store the master key as it is being generated. You can prevent that by generating the master key client-side on the initial client.

One more catch: this method may well be subject to a patent.

  • For phase 1, we ended up SHA512 hashing the password in the browser before sending it to the server. We then hash it further for storage. Essentially, for authentication purposes, the user's password is a hash of their real password. We aren't working with encrypted content yet, but our plan is to pbkdf2 the password to derive a key used to encrypt the user's private key. This allows the user to log in to a webapp that can retrieve/decrypt their key while ensuring the server doesn't have the info to decrypt it. We'll definitely consider your suggestion of 1 key per device when we get there. – Joshua Dwire Apr 6 '15 at 1:39
  • +1 on using a good solid strong hashing algorithm; I like SHA512. One thing to keep in mind here is that a simple hash is a password equivalent and susceptible to a replay attack. Basically, an attacker does not need to know the actual password - he just needs to be able to intercept the SHA512 hash (or get it by breaking into your authentication database). Also keep in mind that you'll need to add a salt. Otherwise, the hash may be broken with a rainbow table - and then the password would be good to decrypt the user's private key. – Kevin Keane Apr 6 '15 at 4:59
  • Ran out of space on my previous comment: also make sure to provide an easy mechanism for changing the hashing algorithm later, in case SHA512 is discovered to have a vulnerability. For instance, that is why entries in /etc/shadow in Linux start with $6$ (or some other number) that identifies the algorithm used. – Kevin Keane Apr 6 '15 at 5:01
  • We're using HTTPS to prevent interception and PHP's password_hash function which automatically adds a salt. Even if the attacker were able to get the SHA512 hash of the password, he would be unable to decrypt the user's private key as it's encrypted with the user's password not the hash of the password. For ease of implementation, we're not salting the SHA512 hash as we never actually store it, and we don't have an easy way to change the hash algorithm, but we'll develop that in the future of needed. – Joshua Dwire Apr 6 '15 at 10:57
  • If you don't store the SHA512 hash, how do you verify the password? Are you somehow using a challenge-response scheme? Also keep in mind that while HTTPS is good as long as you only enable the best ciphers, a determined enough attacker may have a zero day, or the client app may be compromised. – Kevin Keane Apr 6 '15 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.