Any advantage of multiple salts/keys for single password when using PBKDF for multiple secrets?

Question

Background: I'm putting together a personal project to store multiple short message protected by a master password. This is more to learn and demonstrate that I understand how to use some standard cryptographic primitives than for practical use.

I am using HMAC_SHA256 inside a standard pbkdf2 function (part of OpenSSL). I have ended up with a choice between two designs for data model when it comes to deriving an AES key from a master password:

1. Store a pbkdf2 salt for each message, and derive a different AES key for each one.

2. Store a single pbkdf2 salt for the whole database, and derive a single AES key used for all the messages.

I am using a cryptographic RNG for salts and for initial values in AES 256 CBC. I store the salts and ivs in the clear in the database, the threat model is attacker has copy of all encrypted text, salts and ivs, but not the master password. Attacker is not able to request encryption, but they may observe any existing encryptions and may correctly guess one or more plaintexts.

As far as I can tell, both schemes have the same level of secrecy for the data at rest. The use of random initial values and the short messages mean that there is no real need to have a different key per message. There is no known plaintext attack that could take advantage of the fact that the key is shared in scheme 2. Both schemes support re-keying without changing the password, although I don't think that is particularly useful.

I think scheme 2 offers some advantages in performance - the costly pbkdf2 is only used once for multiple messages. It doesn't make brute-forcing the password any easier. It does mean ignoring the password and brute-forcing the key is potentially more damaging, but I think that is entirely unrealistic for AES 256, and that the password is the most vulnerable to attack secret in my project.

Have I missed anything? Is there some additional reason why I would choose one approach over the other?

Answer 1

Store a single pbkdf2 salt for the whole database, and derive a single AES key used for all the messages.

This is the better approach.
I'm confident to say that, because if you derive a new key using a proper password-based key derivation function (PBKDF) for each and every entry, you have to set the cost parameters for the PBKDF to not frustrate the user. But if you do this, then an attacker only needs to break a single one of the weaker password hashes to recover the password. So rather go with only one PBKDF operation, but make that one costly (maybe 100ms - 1s on the user's machine).

Additionally you can use a key-based key derivation function (KBKDF) to derive a new key for each entry from your master password-derived key. This KBKDF should be HKDF using most of its features (salt? key identifier? personalization string?), but if HKDF is impossible for you, simple HMAC should do as well.

---

There are a few gripes though with the choice of the primitives you mentioned, namely:

• HMAC-SHA256 for PBDKF2. SHA-256 is based on 32-bit operations and thus performs best on 32-bit machines. If possible you should use SHA-512 because it is based on 64-bit operations and not only will perform better on 64-bit machines (your clients?) but will also be more costly for an attacker to implement in a parallel fashion because most of these devices can do 32-bit operations much more cheaply than 64-bit (especially GPUs are today always 32-bit processors)
• Don't use PBKDF2 if possible, use Argon2, scrypt or bcrypt. The latter three PBKDF are modern successors to PBKDF2 and are more hardened to attacks by GPUs, FPGAs and ASICs than PBKDF2 ever could be. Also see the canonical answer on Information Security SE about this topic.
• Use authenticated encryption. You have OpenSSL and as such you can use its authenticated encryption implementations, especially AES-GCM, which will give you better security than plain AES-CBC. Note though that plain AES-CTR provides less security than AES-CBC, because it is even more easier and targeted malleable, e.g. if you know where the data to change is you trivially flip the bits with CTR, with CBC you at least screw up the previous block.

Answer 2

pbdkf2 is a Password-Based Key Derivation Function which you would use to derive a somewhat stronger master key from a human password. If you needed a large number of keys (e.g. to encrypt different messages) you could then simply use something like HMAC to quickly derive new keys from the master key. So basically, scheme 1 & scheme 2 can have the same performance.

Now as to the security: CBC has some flaws. In particular, if the attacker can read the IV and knows/guesses the plaintext of a single message the scheme becomes vulnerable. So if you were to store the IV's in the clear with your messages CBC would be unsafe unless you use a different (derived) key for each block (like scheme 1).

Instead you could use AES-CTR; as long as you make sure the CTR is unique for each message and never reused (e.g. randomly generated or the hash of the ID of the message). The only drawback with AES-CTR is that it is not authenticated which means that you wouldn't know whether your messages have been tampered with.