13

Suppose a less-than-trusted server is used to store users' confidential data (encrypted at the client side), and both tasks - authentication and encryption/decryption - should be doable with a single password. Would it be enough to:

  1. Strenghten the password with a slow key derivation function and a trivial salt [1], yielding k;
  2. Use k as the SRP "password", authenticating with the server and receiving the ciphertext;
  3. Decrypt the ciphertext to get the actual key(s) to be used for signing, encryption, etc.

A malicious server (low risk) would have to perform an offline dictionary attack - on the verifier or on the ciphertext - to retrieve k, while an external attacker (higher risk) would only be able to do online attacks (since he has access neither to the verifier nor the ciphertext), unless he gets a copy of the database - which would just put him in a similar situation of the server [2].

Is this reasoning correct? Any flaws I didn't anticipate? Some notes:

  1. I say the salt is "trivial" because it's either: a) empty; b) derived from the username; c) random, but the server will give it to anyone who requests it. Normally that would be a concern, but here the key never leaves the client machine, so it doesn't matter if two users have the same key.

  2. One of my concerns is that an attacker could create a rainbow table targeted at a particular user, then get the database and almost immediatly log in as that user, since brute-forcing the verifier or the ciphertext is quicker if you have a list of candidate keys rather than a list of candidate passwords (which still need to be stretched before becoming keys).

    Of course, if an attacker has that computing power (of if the password was weak) any leaked ciphertext will eventually be cracked, but future harm could be avoided if the server were stronger against this scenario (before learning about SRP I designed a more convoluted protocol that took this into account, but was more wasteful and had open questions).

  3. [For my particular case] All these are out of scope of the question (assume already figured out): all communication will be over TLS, option to use proper keys and 2-factor auth will be given (but not mandated), the client code will not come from the less-than-trusted server, MACs will be used, etc.
Community
  • 1
mgibsonbr
  • 2,925
  • 2
  • 21
  • 35
  • 2
    "the client code will not come from the less-than-trusted server" how are you going to achieve that without TLS? – Hubert Kario Jun 29 '13 at 09:49
  • @HubertKario First, I **will** use TLS, plase see the last point. Second, I made that remark because it's imperative that the code comes from a trusted source - either pre-installed in the client machine, or downloaded on-demand but from another server. If I don't trust the storage server enough to keep my data private, I can not trust it not to tamper with the code it sends me (e.g. bypassing the encryption entirely). – mgibsonbr Jun 29 '13 at 11:10
  • The salt can be random but put a unique constraint on the db column. That eliminates the risk of two users having same salt such that if they pick the same password it is visible due to rows in the db having same salt and same verifier. – simbo1905 May 20 '15 at 20:47
  • Offline dictionary attack is most likely from offsite db backups so it's a good idea to encrypt the verifier db column. – simbo1905 May 20 '15 at 20:53
  • @simbo1905 Thanks for your suggestions, actually the odds of a randomly generated salt colliding are negligible, though adding a unique constraint doesn't hurt, so I'll do it anyway. About the offline dictionary attack, encripting the verifier is usually not a feasible option (where would I store the key?) but what protects against this scenario is the password hashing itself (in SRP the hash must be done to each password candidate in order for the password to verify; the fact that it's an offline attack doesn't change that). – mgibsonbr May 20 '15 at 21:23
  • 1
    It's only negligible if your secure PRNG doesn't fail or isn't deliberately weakened by a state level adversary. Likewise if your using an SRP JavaScript library then the quality if the browser PRNG is not known and can fail or have been compromised. So to prevent against repeated `A` you can hash the browser PRNG with the current time. – simbo1905 May 21 '15 at 06:00

3 Answers3

6

As an exercise in healthy cautiousness, I would advise the following:

  • When you derive your key k from the user password, make it longer, and split it in two. Use the first half for SRP, the second half for encryption. A simple way to achieve that is to hash k with SHA-256, yielding 256 bits which can then be split into two fine 128-bit keys. Alternatively, use a key derivation function with tuneable output size, like PBKDF2.

    The point here is that we want to avoid any unwanted "interaction", however implausible, between the symmetric encryption and the computations performed in SRP. Intercalating a layer of one-wayness between the two subkeys ought to prevent such issues (assuming SHA-256 to more or less behave like a random oracle).

  • You encrypt for a reason: you then must assume that an attacker may observe, at some point, the symmetrically encrypted data blob. Otherwise, what would be the point of encryption ? But if such an eavesdropping is possible, then the salt must be proper. An empty salt would not cut it, because all users would use the same salt, allowing for attack optimisations (namely, rainbow tables).

    Now there is an interesting point, which is that SRP itself includes some salt processing. Take a close look at RFC 5054, which describes how SRP is to be integrated in a TLS handshake. In the initial step, the client (in its ClientHello) sends the user's identity (I). The server responds with some messages, including the ServerKeyExchange which contains (among other values) the salt s. So you have, right here, your "server which sends the salt to everybody who asks for it".

The actual password processing, in SRP, is the computation of x = SHA1(s | SHA1(I | ":" | P)). This is a salted, but insufficiently iterated password hashing function. This is a known flaw in SRP as it is currently defined. However, it would be trivial to replace this operation with a strong password hashing function, as long as client and server agree.

This then yields the following scheme:

  • At registration time, the user chooses his password P, and a random salt s is generated (say, 128 bits from a cryptographically strong PRNG).
  • From P and s, a strong password hashing function (such as bcrypt) is applied, yielding some intermediate value z, which we then hash with SHA-512, yielding 512 bits. These 512 bits are split into two 256-bit halves; the first half will be the x value for SRP, while the second half (let's call it y) will be used for symmetric encryption.
  • When logging in, the client first send the user name (I) to the server, and gets the salt s. The same computation of x and y is done again. The x part is used for SRP, the y part to decrypt the blob stored on the server.

This scheme combines all the points discussed above. Password-to-key derivation uses a proper function with a good, random salt; there is an isolation layer of SHA-512 between the two usages of the password; no extra message exchange is needed compared to basic SRP. In effect, what I suggest here is a strengthening of the password hashing done in SRP, with an extra leeching of a password-derived key for your symmetric encryption need.

Note that while you can first establish a SSL/TLS tunnel and then perform SRP in it, you can also follow the RFC 5054 road and use SRP for the TLS handshake. This would require control of both client and server code, including the SRP implementation, since I am suggesting here modifying the password-to-key derivation process (namely, to strengthen it). Correspondingly, the client must already have the needed code. In a Web-Javascript context, you would need first a "normal" SSL/TLS, although at that point the benefits of SRP become quite small.

Letting the server send the salt value to whoever asks, as is inherent in SRP, is not a serious issue. Salts don't need secrecy. Keeping salt values secret does not harm, but this is only a secondary goal. The main point of salts is uniqueness. Don't let an unwarranted itch for secrecy get in the path of uniqueness.

Community
  • 1
Thomas Pornin
  • 322,884
  • 58
  • 787
  • 955
  • Thanks for your advice, I think I'll follow this route. Just a comment on the code distribution: the server that provides the client code (trusted) is different from the server that provides the storage ("less-than-trusted"), so even though I'd need a "normal" SSL/TLS connection first, I'd have to make a second one anyway. Although the storage server shall run my code (including custom handshakes, if necessary), it's not in my direct control - each customer will hire its own, according to its budget and security/availability needs. Client-side encryption is thus part of the defense-in-depth. – mgibsonbr Jul 01 '13 at 23:21
5

I am going to assume you mean that the data is encrypted using key k (the same value used as the SRP password). You did not specify this, so if this is not what you had in mind, please edit your question.

Yes, this is a reasonable scheme.

I would suggest using the user's username plus the server's identifier (e.g., domain name) as the salt to your slow key derivation function, if possible. You could also make it a random value that is public and different for each user.

Rainbow tables: Rainbow tables don't help the attacker much, since the cost of creating the rainbow tables is as much as just trying a bunch of candidate passwords. Rainbow tables only help when you are attacking multiple times (e.g., attacking multiple users) and you want to amortize the cost. If you think some username is very common (e.g., alice), it would be possible to create a rainbow table specific to alice (a one-time computation) and then use it to attack multiple servers, in hopes that there is an account named alice on all of those servers. This however only gets you a speedup if you find multiple users with the same username (presumably, on multiple different servers). I don't think it is much of a threat in practice. If you are concerned about it, it can be avoided by using as salt a random value that is different for each user, or using the combination of the user's username and the server's identifier as the salt.

Other: The biggest weakness is probably where the client will get the code to decrypt the ciphertext. If this is a dedicated client-side application, you can build it into the code of the client program. But if the client is accessing some website through a web browser, and the decryption code is provided by the server as Javascript (say), then you haven't actually gained as much security as you think you have, since a malicious/compromised/spoof server can send malicious Javascript that steals the user's password.

D.W.
  • 98,860
  • 33
  • 271
  • 588
  • "the data is encrypted using key `k` (the same value used as the SRP password)" that's correct, sorry if I wasn't clear. – mgibsonbr Jun 30 '13 at 03:16
2

There's another approach you might want to consider. Take the user password p, apply a salt and push it through key derivation to generate a longer key k. Then split k into two parts a and b. The first part, a, is used to encrypt the data and the second part, b, is used to authenticate to the server.

Does that satisfy your ease of use and security requirements?

u2702
  • 2,086
  • 10
  • 11
  • That might work, my concern is in the key generation cost. I want to apply the maximum work factor tolerable, so if I double the key size I might have to decrease the work factor (to keep the performance constant). In the end it boils down to a compromise: I decrease the expected time to crack and in exchange I avoid the risk of using the same key for two purposes leading to unintended consequences. – mgibsonbr Jul 01 '13 at 23:31