Is it safe to use unauthenticated AES CBC when encrypting random bytes?
Is this a safe implementation?


No. An adversary can change just the first encrypted block that contains part of the AES data key. Then HMAC authentication will succeed, but decryption with the AES key will result in the wrong plaintext message. If an IV is used then the IV can also be changed, resulting in only the first 128 bits of the AES data key to be changed.

After all, CBC has limited error propagation, and the block size of AES requires a minimum of 4 blocks to encrypt two 256 bit keys.

If padding is used then padding errors may also result in a padding oracle attack on the key material. But those would only work in a limited amount of scenarios.


  Does the fact that the key material is random byte data change its need to have HMAC authentication to protect it from attacks?


No, not necessarily. It depends on how the random data is used. If alteration of the random data can help with creating an active attack then integrity / authenticity is required. To state that it doesn't need protection just because it is random data is certainly wrong.


  Is the key material decryption from step 4 subject to the same attack vectors as standard string decryption, as in step 5?


No. The bits of the encrypted random data are unrelated to each other and they do not need to be padded, which thwarts many attacks on CBC mode. But it still has limited error propagation and no integrity / authenticity.



PBKDF2 should indeed be limited to generate only as many bits as the internal hash function provides. Generally you'd use an additional Key Based Key Derivation Function or KBKDF such as HKDF to derive the keys from a master secret, generated by PBKDF2:

$$K_{master} = \text{PBKDF2}(p, ...)$$
$$K_{enc} = \text{HKDF}(K_{master}, \text{"enc"})$$
$$K_{mac} = \text{HKDF}(K_{master}, \text{"mac"})$$

This doesn't require any additional storage as the labels "enc" and "mac" are simply constant values. 



An ugly hack would be to also include the IV (if present) and ciphertext of the encrypted keys in the HMAC verification. I'm just mentioning this because the protocol may have used this already - it could be just a change of an offset - and it may have been overlooked.