Sending Encrypted Messages with Hybrid RSA, AES and HMAC SHA-256

Question

Is this a Secure strategy for sending a large Encrypted Message using Hybrid RSA 2048, AES 256 and authenticated with HMAC SHA-256:

Given the Alice already has Bob's RSA Public Key, Alice:

1. Generates a new 128bit IV (strong PRNG)
2. Generates a new AES 256bit/CBC/PKCS7 Crypt Key (Kc)
3. Generates a new AES 256bit/CBC/PKCS7 Auth Key (Ka)
4. Encrypts her Message + Timestamp with (Kc) and IV => (M)e
5. Authenticates IV+(M)e with (Ka) using HMAC SHA-256 => IV+(M)e+Tag
6. Encrypts (Ka)+(Kc) with Bob's RSA Public Key padded with OAEP => (Kc+Ka+P)e
7. Authenticates (Kc+Ka+P)e with (Ka) using HMAC SHA-256 => IV+(Kc+Ka+P)e+Tag
8. Sends Bob RSA Encrypted IV+(Kc+Ka+P)e+Tag and AES HMAC-256 Message IV+(M)e+Tag

Bob then proceeds to:

1. Extracts IV from IV+(Kc+Ka+P)e+Tag
2. Checks IV against nonce cache, rejecting messages with repeated IV's
3. Extracts and Decrypts (Kc+Ka+P)e with his RSA Private Key => (Ka)+(Kc)
4. Verifies IV+(Kc+Ka+P)e+Tag with (Ka), rejecting invalid messages
5. Verifies IV+(M)e+Tag with (Ka), rejecting invalid messages
6. Decrypts IV+(M)e+Tag with (Kc)
7. Extracts Timestamp and Message
8. Verifies Timestamp isn't older than Max Request Age, rejecting expired messages

Basically would like to know if there are any obvious weaknesses with the above Hybrid RSA/AES/HMAC SHA-256 approach or anything anyone would do differently?

The above strategy has been revised to include @puzzlepalace's feedback of creating separate AES keys for Encrypting and Authenticating instead of deriving them from the SHA-512 hash of the master key.

Any other feedback or suggestions for improvements are welcomed!

Answer 1

I'll step by step and then overall crypto system, seems most logical to me.

1. Generate a new AES 256bit/CBC/PKCS7 Master Key (Km)
2. Generate a new 128bit IV (strong PRNG)

CBC is fine here as there isn't any sort of oracle the attacker would have access to and bit-flipping attacks are ruled out by the tag. Random IV is correct, 256 bits is more than enough for key size.

3. Generate the SHA-512 Hash of (Km) => (Hm)
4. Splits (Hm) into Crypt Key => (Kc) and Auth Key => (Ka)

This should be fine. One comment, I'm actually not familiar with the master secret being expanded via a hash (so if this is considered best practice please correct me), is there any reason you don't just generate two 256 bit keys? I'd say unless you really need to conserve packet sizes on the network why not just generate two 256 bit keys, one for AES and one for the HMAC? It's only 256 bits more on the network.

5. Encrypts her Message + Timestamp with (Kc) and IV => (M)e
6. Signs (IV)+(M)e with (Ka) using HMAC SHA-256 => (IV+(M)e+Tag)

This is good, Encrypt-then-MAC is IND-CCA (i.e. the best generic construction). A nit-picky note: a HMAC is not a signature, but rather a tag. (a tag provides integrity and authenticity, a signature also provides nonrepudiation).

7. Encrypts (IV+Km) with Bob's RSA Public Key padded with OAEP => (IV+Km+P)e
8. Sends Bob RSA encrypted AES key (IV+Km+P)e and Signed AES Message (IV+(M)e+Tag)

OAEP is a good choice for RSA padding, and is IND-CCA, I see no issues here.

It looks to me like both your symmetric and asymmetric schemes are not susceptible to a chosen ciphertext attack, which is very secure. As such I don't think having the same IV encrypted in both the RSA and AES ciphertexts is an issue. Especially since the IV does not even have to be secret in CBC mode (it just should not be predictable or reused!), and so could be sent in the clear (perhaps by appending the plaintext IV to the AES ciphertext and computing the MAC of that). Then it also would not have to be encrypted under the recipients public key.

Hope that helps, happy to clarify or expand on anything you have questions about!