Crypto is hard. Thank you for helping me learn.

My encryption scheme currently looks like this:

1. Salt is stored out in the open
2. Secret is the user's password, known only to them
3. EncKey||AuthKey = PBKDF2(Secret, Salt, n) where n = lots
4. My encrypted payload consists of IV||Ciphertext||HMAC
1. IV = secure random bytes, unique to each payload
2. Ciphertext = AES-256 CBC(EncKey, IV, Plaintext)
3. HMAC = HMAC-SHA1(AuthKey, IV||Ciphertext)

Now, I want to change Secret. As it stands, this will make all of my already encrypted data unreadable. So, I want to keep the same EncKey.

Will the following be a secure scheme?

1. EncKey||AuthKey = secure random bytes, chosen once ever
2. PwdEncKey||PwdAuthKey = PBKDF2(Secret, Salt, n)
3. EncKey and AuthKey are encrypted as above, but using the PwdEncKey and PwdAuthKey
4. Everything else is encrypted and signed with EncKey and AuthKey

To rotate my password, I can then decrypt the payload which has EncKey and AuthKey (which now never change) and re-encrypt it with the newly derived PwdEncKey and PwdAuthKey.

Does it weaken my security having EncKey and AuthKey stored in an encrypted blob alongside the data which they are encrypting? Is there a smarter way to do this?

No, wrapping the data key set seems a good idea to me. It's pretty standard and should even work with e.g. hardware modules.

Note that your old ciphertext would still rely on the security of your old secret (password) when you choose this scheme! If $Enckey$ is ever guessed it can be confirmed by decrypting (the first part of) your ciphertext.

There is a more efficient way: you can simply calculate the difference on bit level using XOR between the keys calculated from your old and new secret. Then store that difference with the ciphertext. So retrieve the old key simply XOR with your newly created key to retrieve the older key.

This is more efficient CPU-wise and may require fewer bits (if CBC padding is used). I'd still go for your current scheme though. The XOR method is less flexible and will expose your new master key if any of the data keys is ever leaked.

Notes:

• I would not request too much output from PBKDF2, rather use another KBKDF such as HKDF to split off multiple keys from the derived key;
• PBKDF2 requires an iteration count (work factor) as configuration parameter, which seems to be missing;
• HMAC can be configured to use SHA-1, but it isn't SHA-1 and SHA-1 doesn't take two input parameters;
• you could consider using SIV to encrypt your keys, in that case you don't need a second authentication key or IV;
• you might consider storing a random salt with the ciphertext;
• a fully random data key set for each separate encryption is more secure;
• addition 1: if you do not use an IV when encrypting the keys then it is easy to spot which ciphertext was encrypted with the old keys.
• Thanks! I edited my question to clarify some of the functions. I'm currently using n = 4096 for the PBKDF. Thanks for pointing me at HKDF; that looks quite useful for splitting off the Enc/Auth keys from the PBKDF. Right now I get 96 bytes from PBKDF and chop the first 32 for AES (256-bit) and the remaining 64 for HMAC-SHA1. – Dave Jun 27 '16 at 0:58
• I did realise the old ciphertext would only be as secure as my previous password. This is for encrypting data at rest (S3) I might add, so there is some cost to re-encrypting all the old data. That's why encrypting the keys separately seemed like a good idea. Glad to hear it's not unheard of. Also, the XOR idea blew my mind a bit (had to think about that one for a while), but I agree it could bring the whole chain toppling down. – Dave Jun 27 '16 at 1:03