Is a padding oracle attack possible with randomly generated keys?

Question

In a project we collect data from devices in the field using a hybrid encryption scheme. When a device wants to send data it generates a random AES key (session key) and encrypts the payload with that. Then it uses an RSA public key to encrypt the session key and sends that encrypted session key along with the AES encrypted payload. On the server side we decrypt the session key (as we have the private key there) and then use the decrypted session key to decrypt the payload. The advantage of this is that you don't need a shared secret between the devices in the field and our server collecting the data.

Now during an audit it came up that we use AES/CBC/PKCS5Padding and that this is vulnerable to a padding oracle attack. From what I understand this attack works by sending manipulated packets to guess the AES key.

Given the scheme I described, I would argue that this attack is not really feasible here as every message has an own AES key and in addition we do not give any message back to the caller even if the packet could not be successfully decrypted.

Is that assumption correct or would we need move away from CBC?

Answer 1

If I understand your scheme correctly, it's this:

1. Client generates a random AES key and initialisation vector (IV).
2. Client encrypts that key with the RSA public key of your server, which it already possesses.
3. Client pads the message with PKCS#5 and encrypts it with AES-CBC using the IV + key they generated.
4. Client concatenates IV + encrypted key + ciphertext and sends it to the server.
5. Server receives the packet and splits it back out into IV + encrypted key + ciphertext.
6. Server decrypts the encrypted key using its RSA private key, but returns no error message if this fails.
7. Server uses the IV and decrypted key to decrypt the ciphertext, again using AES-CBC.
8. Server validates the PKCS#5 padding of the decryption and discards the message if the padding is not correct. No error is returned to the client.

If so, there are a number of problems here, mostly relating to malleability:

1. An attacker can pick a tweak T and replace the IV with IV ⊕ T, resulting in the first block of decrypted plaintext becoming M₀ ⊕ T. This can be used along with known plaintext in order to spoof message contents.
2. An attacker can pick a tweak T and replace any ciphertext block C_n with it, resulting in M_n becoming corrupted and M_n+1 becoming M_n+1 ⊕ T. If an attacker knows that the data in M_n is not validated or not important for the purposes of the attack scenario, this can be used to spoof message contents via a known plaintext.
3. Even if you send back no error messages, there may be timing differences in your code that allow an attacker to distinguish (within a reasonable probability bound) between valid and invalid padding. This could be exploited in order to recover the plaintext of packets.

I recommend that you modify your scheme to the following:

1. Client generates a pair of random keys K_e and K_m plus a random initialisation vector (IV).
2. Client concatenates K_e and K_m together to make a combined key K.
3. Client encrypts K with the RSA public key to create the encrypted combined key K'.
4. Client pads and encrypts the plaintext message M with PKCS#5 and AES-CBC using K_e and the IV, resulting in ciphertext C, i.e. C = E(M, IV, K_e)
5. Client concatenates IV and K' and C to create an encrypted packet P.
6. Client computes H(P, K_m) where H is a HMAC function, e.g. HMAC-SHA256, resulting in an authenticity record A.
7. Client concatenates P and A and sends this to the server.
8. Server extracts P and A from the packet.
9. Server splits P back into IV, K', and C.
10. Server decrypts K' with its RSA private key. If this step fails, the message is discarded. If not, the server now has the combined key K.
11. Server extracts K_e and K_m from K.
12. Server validates that H(P, K_m) == A. If this step fails, the message is discarded.
13. Server decrypts C using K_e and IV, i.e. M = D(C, IV, K_e), and validates the PKCS#5 padding. If the padding is invalid, the server discards the message.

The addition of an authenticity record ensures that an attacker cannot capture a message from the client, modify it, and re-send it to exploit a malleability attack or padding oracle issue. The idea is that an attacker could replace K' with their own value in order to know K_m and forge messages, but in the process they'd also have to replace K_e which would result in invalid padding or completely garbled plaintext.