Is public-key cryptography the only option in this scenario?

Question

Two parties: a client and a server are to a agree on a symmetric key. Both the client and the server are aware of a master password. The way this is currently done is:

1. Both parties hash the master password using SHA-256 to create a password hash.
2. The password hash is used by the client to encrypt a message which includes, amongst other things 128 pseudo-random bits. This encrypted message is then sent to the server.
3. The server checks if the message is valid since it knows the master password and in turn the password hash. If the message is indeed valid, the server also generates a message (of similar structure to the client's message) and in the same way encrypts it using the password hash. The server then responds to the client using the encrypted message.
4. The client decrypts the encrypted response using the password hash.
5. At this point both parties have agreed on 256 random bits (128 bits from the client's request and 128 bits from the server's response).

The aim is to make sure that:

1. It is infeasible to recover the unencrypted contents of either the client request or the server response.
2. It is infeasible to recover the master password or the password hash from either the client request or the server response.

The problem is that this technique leaves room for offline attacks to guess the master password (online attacks can be dealt with) and there may be other attacks that I haven't thought of yet. This gives rise to the question:

Are there any other possible attacks?

I considered that I could use PKC (RSA specifically) to add another layer of encryption (PKC on top of SKC) on both the client request and the server response so that an attacker cannot brute-force the low entropy master password without having the RSA private key. Now, additional questions arise.

Is this a valid method for achieving the goals mentioned above?

In either case are there better solutions?

Are there solutions which do not involve PKC?

Which alternative solutions are the most secure?

The question was edited to clear any confusion.

Any help would be appreciated.

Answer 1

"Is to be encrypted" is not a ultimate goal. You do not encrypt data for the sake of it; you encrypt data as a way to ensure a given security property, e.g. transmitting some data between two machines, without compromising the data confidentiality with regards to attackers who may spy on the transmission line (or even alter data in transit).

If:

• your problem is indeed a question of data transmission;
• you can arrange for both sender and receiver to share a common password;
• the transmission uses an online protocol where messages can flow in both directions;

then you can use a secured data tunnel, with a Password-Authenticated Key Exchange protocol to establish a shared symmetric key (used for tunnel encryption and integrity) with mutual authentication relative to the password. PAKE protocols ensure that attackers spying on the line, and even active attackers who can try to impersonate the client or the server, learn nothing which can be used to "guess passwords". With a PAKE protocol, each "password guess" must imply some communication with an honest system (the real server or client). Server and clients can then easily detect brute-forcing attacks after only a few dozen tries. Therefore, PAKE protocols are secure even with passwords of low entropy.

A secure tunnel with a PAKE protocol is a complex beast, easy to get wrong in many ways. Hence you really should rely on an existing, well-analyzed protocol. I suggest SSL/TLS with SRP; this is supported by at least the opensource GnuTLS library.

If the transmission is offline (e.g. in an emailing context: the sender must send all its data in one go, and that must be sufficient for the receiver who acts only afterwards), then a password will not be enough, although you can make it quite hard for the attacker by using an appropriate key derivation process, in which the password is hashed many times with a random salt. Usual recommendations are PBKDF2 and bcrypt. A password with about 30 bits of entropy is sufficient if you use a key derivation process which implies at least a few seconds of computation on a reasonably recent PC.

To get more security than that, you must use a stronger shared secret key; if this implies an unsolvable key distribution process, then you can go to a public-key based scheme, the archetypal protocol being OpenPGP (see GnuPG for an opensource implementation). You still need to make sure that the sender has the genuine receiver's public key, but (at least) this implies no sharing of secret data.

---

Edit: with the new phrasing of the question, the answer is now clear: PAKE. You want to get a shared secret with mutual password-based authentication, and resilience against offline dictionary attacks. PAKE protocols are precisely designed for that. All currently known PAKE protocols involve some "public-key-like" elements, so you will not avoid at least some mathematics. SRP is an adequate, well-documented PAKE protocol.

Answer 2

You can make brute forcing the password as difficult as you need to.

You didn't define the overall problem very well. It's not clear why or how public-key cryptography would even be an alternative. In the usual case, you have nothing to 'bootstrap' with. Your keys or credentials are stored encrypted, and you need the master key to get to them. You have no secure place to store the master key, so it must be stored encrypted. But where would you then store the credentials to decrypt the master key?

The solution is to generate the master key from a password. Generally, you have no alternative solution. Public-key encryption wouldn't help you because you'd have no way to store the private key securely, so when you needed to do the thing you were trying to stop an attacker from doing, all you would have is the password with no way to get a private key.

To prevent brute forcing of the password, there are three things you generally want to do:

1) Increase the number of passwords an attacker needs to try by making sure the password is long and complicated. You can enforce minimum lengths, required character classes (must have one digit, at least one punctuation, and so on). However, the more complex the password, the more likely it will be written down or forgotten.

2) Increase the amount of effort the attacker will need to exert for each password he tries. Algorithms like scrypt or repeated hashing increase the computational cost of each password an attacker has to try, making it less likely he can brute force the password.

3) Ensure the attacker cannot re-use previous effort. That is, you don't want to let an attacker try to break a large number of passwords with the same computational effort or generate a rainbow table that lets him try thousands of passwords with ease. Increasing the effort per password won't help you much if he can easily try each password against thousands of accounts. Salting is the main method used here. The salt is some random data, stored in the clear and different for each password/user, that is 'mixed' with the password to generate the key. Since each user has a different salt, the computation of the key from the password must be done afresh for each user.

Answer 3

Your scheme has several serious flaws. The first two are closely related:

1. Offline password search by an eavesdropper. An eavesdropper who records the conversation between client and server can mount an offline dictionary search against the password. The attacker just tries all plausible passwords (using standard techniques: e.g., a dictionary, etc.). For each candidate password, the attacker decrypts the recorded conversation to see whether it consists of valid messages; this will allow the attacker to discard incorrect guesses and identify the correct password.

   Because most user passwords have relatively low entropy (even a pretty good password probably has around 30 bits of entropy, and many have fewer), this attack is devastating. Each trial at the password requires only one or two hash computation and a decryption or two, so an attacker can try 2³⁰ candidate passwords very quickly: probably in a matter of hours, at most.

2. Offline password search by impersonating a server. An attacker who can't eavesdrop on the communication can still attack the system, if he can impersonate a legitimate server or lure the user into connecting to his server. In this case, the attacker captures a message encrypted with the password hash; the attacker can then proceed to use the above method to try candidate passwords and check for a valid decryption. The attacker can also mount a man-in-the-middle attack.

3. Insufficient authentication, and lack of key confirmation. An attacker who eavesdrops and captures a legitimate conversation between client and server can then open a new connection to the server and impersonate the legitimate client, as follows: the attacker can replay the old message previously sent by the client, to the server. The server will respond and treat the key exchange as a success. Now half of the 256-bit key will be a repeat, and half will be new.

   The attacker might not know any part of the key, but there still may be vulnerabilities, depending upon how the 256-bit key is used: if the server takes any action after the exchange completes, under the assumption that the client has proven his/her identity, then this can be exploited; and depending how the 256-bit key is used by both parties, it may be possible to replay old message. Also, this may enable related-key attacks in some circumstances.

Therefore, I do not recommend use of the scheme you outline.

Instead, you should use PAKE. It is designed to solve exactly the problem you mention. It deals with the problem of offline password search in a powerful, effective way. @Thomas Pornin's answer nails it; I recommend that you follow his advice.